Need some help with sorting

Thread view:

jobo - 31 May 2007 21:21 GMT

Hey there,

I'm having some issues trying to figure out an efficient way to do
this.
So I query a database for a bunch of real estate properties that gives
me latitude/longitude coordinates. The maximum number of results that
will be returned is 100.

>From those 100 properties I need to calculate a bounding box that will

enclose all 100 properties. This might sound confusing, but just think
about a graph full of X/Y coordinates and you need to calculate an
appropiate view screen that will show all points.

The solution I have come up with is you have an array of latitude/
longitude and you have two for loops that would iterate and calculate
maximum distance between two points and keep track of the current
maximum distance between two points untl it reaches the end of the
loop. But this is a very inefficient solution.

Given that there are 100 properties it would give me a Big-O of
100*100 = 10,000 iterations.

I was thinking of sorting the points somehow and indexing is (nlogn)
then iterate through it once to find the maximum distance which would
be at most 100*log(100) + 100 = 300.

Anyone have any ideas? Thanks!

Reply to this Message

Eric Sosman - 31 May 2007 21:39 GMT

jobo wrote On 05/31/07 16:21,:

> Hey there,
>
[quoted text clipped - 21 lines]
> then iterate through it once to find the maximum distance which would
> be at most 100*log(100) + 100 = 300.

Use one loop only, no nesting. All you need is
the minimum and maximum values of the two coordinates:

    Thing[] array = ...;
    double minLat = array[0].getLatitude();
    double maxLat = minLat;
    double minLon = array[0].getLongitude();
    double maxLon = minLon;
    for (Thing t : array) {
    minLat = Math.min(minLat, t.getLatitude());
    maxLat = Math.max(maxLat, t.getLatitude());
    minLon = Math.min(minLon, t.getLongitude());
    maxLon = Math.min(maxLon, t.getLongitude());
    }
    System.out.println("longitude: " + minLon + " to " + maxLon);
    System.out.println("latitude: " + minLat + " to " + maxLat);

Signature

Eric.Sosman@sun.com

Reply to this Message

Lew - 31 May 2007 21:40 GMT

> Hey there,
>
[quoted text clipped - 14 lines]
> maximum distance between two points untl it reaches the end of the
> loop. But this is a very inefficient solution.

How does distance help you determine a bounding box?

> Given that there are 100 properties it would give me a Big-O of
> 100*100 = 10,000 iterations.
[quoted text clipped - 4 lines]
>
> Anyone have any ideas? Thanks!

I have an idea that the bounding box longitudeMin will be <= any returned
property's longitudeMin. and its longitudeMax will be >= any returned
property's longitudeMax, and similarly for the latitudeMin and latitudeMax.
Crossing the Prime Meridian might require special handling.

Signature

Lew

Reply to this Message

Lew - 31 May 2007 21:46 GMT

jobo wrote:

>> I'm having some issues trying to figure out an efficient way to do
>> this.
[quoted text clipped - 23 lines]
>>
>> Anyone have any ideas? Thanks!

Any simple closed curve that has all the returned properties on one side or
the other (not some on one side and some on the other) will be a bounding box
for all the properties.

Draw a box one mm on a side anywhere not crossing or within any of the
properties. It'll be a bounding box.

Signature

Lew

Reply to this Message

jobo - 31 May 2007 21:46 GMT

> > Hey there,
>
[quoted text clipped - 33 lines]
> --
> Lew

You're right. I'm overthinking it!

Reply to this Message

Christian - 31 May 2007 21:49 GMT

jobo schrieb:

> Hey there,
>
[quoted text clipped - 23 lines]
>
> Anyone have any ideas? Thanks!

sounds like homework...

1. you can let the database/SQLQuery calculate the Bounding box..
2. if you want java do it than it can be done in O(n)
as you only need maximum and minimum values of longitude and latitude..

just scan through all points and check them against current max and
minvaules and voila you got your bounding box..

3. there is no Big-O of 10000 .. O(10000) = O(1) so for 100 entrys your
solution will allways be in O(1) and therefore "fast"

4. log(100) is not 2 ... not that it matters in O notation... but binary
sort algos log would be of base 2

Reply to this Message

Need some help with sorting

Free Magazines