Search for external borders from a list of random coordinates

Question

I have a huge list (60,000+) of coordinates, and I have not found a way to recognize external borders.

The list of coordinates is rather random, but they define a specific specific area.

I should be able to draw an area using this list using OpenLayers, so they should also be fine.

It seemed a relatively light nut to break, but it turned out to be rather complicated.

What could be the best approach for this problem?

• Heikki

Answer 1

Are you looking for a convex hull ?

Answer 2

If you just want a bounding box, easy enough:

min_x = MAX_INT; min_y = MAX_INT; max_x = MIN_INT; max_y = MIN_INT; for p in points: if px < min_x then min_x = px; if py < min_y then min_y = py; if px > max_x then max_x = px; if py > max_y then max_y = px; 

If your platform does not have the simple equivalent of MAX_INT and MIN_INT, simply select the first one in the list. This may be a less “cute” code, but it may also be faster with a pointless amount.

Of course, if your data was ordered in some significant way, you could do something smarter than repeating more than 60 thousand elements and making comparisons of 240 thousand (Bearing in mind that ordering 60 thousand points is some significant the way just for this may not pay itself.)

Answer 3

The convex hull is the item I was looking for. I found a really nice script from http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/ .

Many thanks to all the participants!