Polygon from collection of Latitudes & Longitudes

Question

I have a collection of latitudes and longitudes and I'll be grabbing sets of these and want to draw a polygon based on them.

The datasets won't be the outline so will need an algorithm to establish which ones make up the outline of a polygon containing all the latitudes and longitudes supplied. This polygon needs to be flexible so the polygon can be concave if the points dictate that.

Any help would be appreciated.

** UPDATE **

Sorry, should have put more detail.

My code below produces a horrible looking polygon. As explain in my first post I want to create a nice concave or convex polygon based on the latlng's provided.

Just need a way of plotting the outer latlngs.

Apologies if this is still asking too much but thought it was worth one last try.

function initialize() {
    var myLatLng = new google.maps.LatLng(51.407431, -0.727142);
    var myOptions = {
        zoom: 12,
        center: myLatLng,
        mapTypeId: google.maps.MapTypeId.TERRAIN
    }; 

    var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);

    var bermudaTriangle;

    var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);

    var triangleCoords = [
    new google.maps.LatLng(51.392692, -0.740358),
new google.maps.LatLng(51.400618, -0.742469),
new google.maps.LatLng(51.40072, -0.72418),
new google.maps.LatLng(51.400732, -0.743817),
new google.maps.LatLng(51.401258, -0.743386),
new google.maps.LatLng(51.401264, -0.741445),
new google.maps.LatLng(51.401443, -0.725555),
new google.maps.LatLng(51.401463, -0.744042),
new google.maps.LatLng(51.402281, -0.739059)
    ];

    var minX = triangleCoords[0].lat();
    var maxX = triangleCoords[0].lat();
    var minY = triangleCoords[0].lng();
    var maxY = triangleCoords[0].lng();

    for (var i = 1; i < triangleCoords.length; i++) {
        if (triangleCoords[i].lat() < minX) minX = triangleCoords[i].lat();
        if (triangleCoords[i].lat() > maxX) maxX = triangleCoords[i].lat();
        if (triangleCoords[i].lng() < minY) minY = triangleCoords[i].lng();
        if (triangleCoords[i].lng() > maxY) maxY = triangleCoords[i].lng();
    }

    // Construct the polygon
    bermudaTriangle = new google.maps.Polygon({
        paths: triangleCoords,
        strokeColor: "#FF0000",
        strokeOpacity: 0.8,
        strokeWeight: 2,
        fillColor: "#FF0000",
        fillOpacity: 0.35
    });

    bermudaTriangle.setMap(map); 
}

What have you tried so far? No one here will do your work for you, we can only guide you. — Phonon, Dec 23 '11 at 15:06
Also, this is an open global community. Not everyone on SO celebrates Christmas, and [not everyone](http://en.wikipedia.org/wiki/Eastern_Orthodox_liturgical_calendar) who celebrates Christmas celebrates it this time of the year. References to personal and religious themes are generally considered bad manners. Please edit it out. — Phonon, Dec 23 '11 at 15:09
Your comment was posted as an answer, so it was probably deleted because it wasn't an answer. As Phonon noted, this question isn't narrow enough to really answer correctly. Despite the "any help" plea, you are asking for someone else to write the code for you. That really won't work here. — LarsTech, Dec 23 '11 at 17:11
The problem I see with a concave outline is that depending on how much concave you allow it to be, more or less points will belong to the outline. If you do not limit the concaveness then your outline will just go through each point and you will get a polygon looking much like a star. — Olivier Jacot-Descombes, Dec 23 '11 at 18:31
well another solution would be to search a bit for existing questions on so.. like this one : http://stackoverflow.com/questions/828905/polygon-enclosing-a-set-of-points — GameAlchemist, Dec 23 '11 at 18:44
Hi Vincent, I have search this forum and not found quite what i'm after. — AndyW, Dec 24 '11 at 10:17
Hi oliver, you correct. I think there are several algorithms that calculate this for you. Wonder if anyone has done this? — AndyW, Dec 24 '11 at 10:20

score 0 · Answer 1 · answered Dec 28 '11 at 19:19

Your problem is not enough defined : with a given set of points, you may end up with many different polygons if you do not add a constraint other than 'create a nice concave or convex polygon'.

And even a simple example shows that : imagine a triangle ABC, and let D be the center of this triangle, what output will you expect for {A,B,C,D} set of points ?

ABC, since D is inside ?
or ADBCA polygon ?
or ABDCA polygon ?
or ABCDA polygon ?

now if you say 'well D is in the center, it's obvious we should discard D', let D be closer and closer from, say, the AB segment. When do you decide the best output is ABC or ADBCA ?

So you have to add constraints to be able to build an algorithm, since if you cannot not decide by yourself for the above {A,B,C,D} example, how could a computer do ? :-) For example if you call AvgD the average distance beetween points, you could add the constraint that no segment of your outer polygon should be longer than 1.2*AvgD (or, better, Alpha*AvgD, and you try your algorithm with different alpha).

To solve your issue, i would use first a classical hull algorithm to get the outer convex polygon (which is deterministic), then break down the segments that are 'too' long (with the constraint(s) you want) putting more and more inner points into the outlining until all constraints are ok. Something like 'digging holes' into the convex polygon.

'Breaking down' a too long segment is also a thing you can do in quite different maners. One may be to search for the nearest not-in-the-outline point from the middle point of the segment. Another would be to choose the point having lowest radius with current segment... Now that you have your new point, break the segment in two, update your list of too-loong segment, and do it again until you're done (or until you reach a 'satisfactory' average length for too long segments, or ...)

Good luck !

Your correct, I was thinking of scanning from point A (lets imagine its the lowest/southern most point) clockwise from 180 degrees for the nearest point then slowly increasing the scan radius until I hit another point (point B) then draw a line from point A to B and repeat the process from point B (from a different angle though). You convex hull then digging holes sounds interesting, will give it a try. Think I stumbled across some code that will help me at some point. — AndyW, Dec 29 '11 at 10:47

Polygon from collection of Latitudes & Longitudes

1 Answers1