Determine outer boundries of polygon from lat/lng point array

Question

I have a large array of lat/lng points. Could be up to 20k points. I'm plotting them using KML. What I want to do is to take only the outter most points and use them to draw a polygon instead. I already know how to draw a polygon in kml, I just need to figure out how to select only the outer most points of the group.

Any ideas? I'd like to have at least 5 points to the polygon but no more than 25 points total.

So far i've come up with checking for top most and bottom most points (basically crearing a square) using < & > logic.

The points will be in america & canada only if that matters.

Thanks for any help.

EDIT: I've gotten the Convex Hull algorithm to work, but it isnt exactly what I need. I'm trying to map out zip codes. If a zip code has an L shape then the polygon is going to be a triangle shape and not an L shape. Any ideas?

Answer 1

You need to use a Convex Hull algorithm. It's not too hard to implement yourself if it's not available in whatever software package you're using.