Displaying a subset of longitude/latitude points?

Question

I have an array of coordinates (latitude and longitude) maded in this way:

[0] = "45.01234,9.12345"
[1] = "46.11111,9.12345"
[2] = "47.22222,9.98765"
[...] etc

In a loop, convert these coordinates in meters (UTM northing / UTM easting) and after that I convert these coords in pixel (X / Y) on screen (the output device is an iPhone) to draw a route line on a custom map.

[0] = "512335.00000,502333.666666"
[...] etc

The returning pixel are passed to a method that draw a line on screen (simulating a route calculation).

[0] = "20,30"
[1] = "21,31"
[2] = "25,40"
[...] etc

As coordinate (lat/lon) are too many, I need to truncate lat/lon array eliminating the values that doesn't fill in the map bound (the visible part of map on screen).
Map bounds are 2 couple of coords lat/lon, upper left, and lower right.

Now, what is the best way to loop on this array (NOT SORTED) and check if a value is or not in bound and after remove the value that is outside?
To return a clean array that contains only the coords visible on screen?

Note: the coords array is a very big array. 4000/5000 Couple of items.
This is a method that should be looped every drag or zoom.

How can I optimize search and controls in this array?

This has a fairly specific technical answer, rather than a subjective one. I'd suggest migrating this to SO. — Gary, Jan 17 '11 at 20:27
@Gary: Can posts be migrated *to* SO (I've only ever seen it go the other way)? — FrustratedWithFormsDesigner, Jan 17 '11 at 20:28
Yes, posts can be migrated to SO. And that's where this one is going to end up. — Walter, Jan 17 '11 at 20:32
simply eliminating those points who are outside the window won't do the trick; consider a window "0,0".."320,480" and those points: "-10,240", "400,240" - you still need to draw the line, otherwise something is missing — Erich Kitzmueller, Jan 17 '11 at 21:26
You should improve your title. Write something more descriptive — Dr. belisarius, Jan 17 '11 at 23:38

score 2 · Accepted Answer · answered Jan 17 '11 at 20:41

I'd suggest breaking this into several steps:

Convert each longitude/latitude pair into a pair of meters in your new coordinate system.
Create a kd-tree data structure holding all the points in the set. This allows you to efficiently query which points lie in a given rectangular range very efficiently.
Whenever the viewport changes, find all points in the kd-tree that will be displayed in that rectangle.
To display the points, iterate over the set of points that will be displayed and display each of them.

Displaying a subset of longitude/latitude points?

1 Answers1

Linked