We received a kml file with polygons but the points are not in a logical sequence and we end up with strange overlapping shapes that are supposed to be an open polygon. We did identify a point near the center and found the azimuth and then sorted in that order and it helped but still did not solve. The bounds of the polygon do contain convex sides. Is anyone aware of an approach to process the random points and get the best open polygon? We have considered calculating bearing and distance from each point and looking for non intersecting line segments but wanted to see if there is a better approach.

We are using php to calculate and then pass into mapping api.. our database is mysql.

Trying to do as minimal programming as possible.

  • Are the points expected to be sorted clockwise, or rather counter-clockwise, like in most geometry drawings? – user80481 Aug 9 '16 at 15:12

This sort of thing is what humans are good at but computers aren't good at. One approach that may help is sorting the points in clockwise order, this will give you mostly what you want but will still need some manual intervention with a software package like ArcGis or QGIS.

In essence find the leftest point (lowest X), if two are colinear then the one with the lowest Y. Using Cross Products of the vectors from the start point to all other points in pairs to find the leftest (yes, lots of iteration!)... see here https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line for explanation.

When you've found the left most point move to that and check all the other points until you come back to the same point you started with (leftest, lowest). If points are colinear use the closest (cross product is 0). This will calculate the convex hull, then with the remaining points find the perpendicular closest segment and insert there to make it more concave.

Then check the polygon in your GIS software and adjust where necessary. It depends on how irregular your polygon is as to how well this works and if it has double-backs or islands then you'd be better off drawing it manually.

Depending on how many vertices are in the polygon and how often you need to do this it could be quicker to draw it than code it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.