Determine the outer borders of a polygon from an array of lat / lng points

Question

I have a large array of lat / lng points. There can be up to 20 thousand points. I plan to use them KML. What I want to do is to take only most of the glasses and use them to draw the polygon. I already know how to draw a polygon in kml, I just need to figure out how to select only the outermost points of the group.

Any ideas? I would like to have at least 5 points for a polygon, but no more than 25 points.

So far, I have come up with checking the upper and lower parts of the majority (mainly folding the square) using the <and> logic.

Points will be in America and Canada only if it matters.

Thanks for any help.

EDIT: I got the Convex Hull algorithm, but that is not what I need. I am trying to display zip codes. If the zip code is L-shaped, then the polygon will have a triangle shape, not an L-shape. Any ideas?

Answer 1

You need to use the Convex Hull algorithm . This is not too difficult to implement if it is not available in any software package that you use.