# Order a list of points to make a polygon with smooth outer border

I have a function that pulls some lat/longs from a Database and then I put those values in a polygon to see it's shape. The problem is they are so random in position and direction from each other that I get a ton of triangle shapes due to the overlapping. Is there a way to order the positions so I get a solid polygon without the overlapping holes? Tried:

``````Dim orderedPoints = points.OrderBy(Function(ll) ll.Lng).ThenBy(Function(ll) ll.Lat).ToList
``````

I feel it needs to be drawn in a circular pattern, finding the farthest as it moves around in a given direction. Hoping to not have to reinvent the wheel if poss here. If there is a name for this process I would be more than happy to research it once I know what it is called.

EDIT: Found this for `Convex Hull`. Made this code so far. Not sure how to proceed from here.

``````Public Class ConvexHull
Public Function ccw(a As PointLatLng, b As PointLatLng, c As PointLatLng) As Integer
Dim area2 = (b.Lat - a.Lat) * (c.Lng - a.Lng) - (b.Lng - a.Lng) * (c.Lat - a.Lat)
If (area2 < 0) Then Return -1
If (area2 > 0) Then Return +1
Return area2 ' basically collinear
End Function
Public Function collinear(a As PointLatLng, b As PointLatLng, c As PointLatLng) As Boolean
Return ccw(a, b, c) = 0
End Function
End Class
``````
• Why not use the convex hull of the points instead? It will give you a smooth shape passing through the extreme points; you can also refine the hull to a concave hull by finding the furthermost point from each segment and inserting it iteratively until all the points are included (or within a predefined tolerance). – Michael Stimson May 25 '15 at 21:22
• @MichaelMiles-Stimson do you have any suggestions? – DonA Jun 5 '15 at 3:38
• Using the Vector dot products look for the leftest left from the Min X and then proceed around... I don't have any python code for this - only C++. There are quite a few examples of convex hulls in code (C, Java..) mathematically if you google them.. Does Sharpmap not have a convex hull from collection function? if not I'll have a hunt around when I'm back in the office. – Michael Stimson Jun 6 '15 at 4:59
• I been searching the internet for anything useful. Most of the examples are incomplete(missing functions or class objects) or simply error ridden when trying to convert. I have not found a function for `ConvexHull` in `GMap.Net` so far. I think I used the wrong library name(SharpMap). – DonA Jun 6 '15 at 14:27

The general problem here, known as polygonization in the literature, is quite difficult. See, e.g., this web page.

The problem with the convex hull is that the region outlined by your points might not be convex. And in fact, you could lose most of the detail: Above, the convex hull of the circled points is the blue-outlined triangle, but perhaps you would prefer the more nuanced light-blue polygon inside.

One idea that would work here and in some other restricted situations is to compute the centroid of your points and then connect them in angular order about the centroid.

• I have read a little bit about what your talking about. I am ok right now with the triangle being the result. Then maybe learn how to do the inner one later. I am trying to figure out how to make a triangle for the remaining points then keep the smallest angle and more to the next. Thanks for your help! – DonA Jun 6 '15 at 17:59
• It is extremely difficult to write a polygonization algorithm, which is why I generally stop at Convex Hull, which is the starting point for complete polygonization, from there find the closest (not already included) point to each line and include iteratively.. but then when do you stop? does every point need to be on the boundary? what about colinear points? they can cause lots of problems depending on where they are. The method described earlier is like Gift Wrapping en.wikipedia.org/wiki/Gift_wrapping_algorithm and in C# michal.is/projects/convex-hull-gift-wrapping-method – Michael Stimson Jun 8 '15 at 22:19
• @MichaelMiles-Stimson: Your suggested incremental pull-inward algorithm "works," and often results in natural polygons. It can be led astray by an adversary, as can any heuristic. – Joseph O'Rourke Jun 8 '15 at 23:43
• The trick is knowing when to stop and just let a point 'be' inside the polygon. I've not found a set of parameters that can satisfy every situation but mostly (99.99%) I can get it to work on buildings from points - but every now and then I get a scribble/hedgehog polygon just to keep me humble. – Michael Stimson Jun 9 '15 at 0:06