Algorithm for finding irrregular polygon centroid (label point)

Question

I need to find a centroid (or label point) for irregularly shaped polygons in Google Maps. I'm showing InfoWindows for parcels and need a place to anchor the the InfoWindow that is guaranteed to be on the surface. See images below.

In reality I don't need anything Google Maps specific, just looking for an idea of how to automatically find this point.

My first idea was to find the "false" centroid by taking the average lat and lngs and the randomly placing points out from there until I find one that intersects the polygon. I already have the point-in-polygon code. This just seems awfully "hacky" to me.

I should note that I don't have access to any of the server side code outputting the geometry so I can't do anything like ST_PointOnSurface(the_geom).

Answer 1

Quick and dirty: If the "false" centroid is not in the polygon use the nearest vertex to that point.

Answer 2

You might want to look at this: http://github.com/tparkin/Google-Maps-Point-in-Polygon

It appears to use a Ray Casting algorithm that should match the case that you presented.

There is a blog post about it here. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

Answer 3

An (older) ESRI algorithm computes the center of mass and, after testing it for inclusion in the polygon, moves it horizontally if necessary until it lies within the polygon. (This could be done in many ways depending on what fundamental operations are available within your programming environment.) This tends to produce label points fairly close to the visual center of the polygon: try it out on the illustration.

Answer 4

I solved my problem by extending the popular epoly code from http://econym.org.uk/gmap. Basically what I ended up doing was:

• Create a series of rays that start from out "false centroid" and extend to every corner and side (8 total)
• Incrementally create a point 10,20,30... percent down each ray and see if this point is in our original polygon

Extended epoly code below:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Still a little hacky but it does seem to work.

Answer 5

Another 'dirty' algorithm to do that:

• Take the bounding box of the geometry (Xmax, Ymax, Xmin, Ymin)

• Loop until a random point ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) is found within the geometry (using Google-Maps-Point-in-Polygon)

Answer 6

In light of your recent clarification that you would prefer a strictly interior location, you could select any point on the Medial Axis Transform that is not also on the polygon's boundary. (If you don't have code for an MAT, you can approximate it by negatively buffering the polygon. A binary or secant search will quickly produce a small interior polygon that approximates part of MAT; use any point on its boundary.)

Answer 7

https://github.com/mapbox/polylabel might be useful (javascript and C++). C# implmentation here: https://gist.github.com/dfaivre/acfef42cdbf411555956e9eba65dd30d.

Original SO question here: https://stackoverflow.com/a/38522611/79113

Answer 8

Why not use the centroid for vertical (latitude) position only? Then, you can position the label horizontally by picking the average longitude at that latitude. (For this you'd need to find the longitude value for a polygon edge at a specific latitude, which should not give you any trouble).

Also, be careful of U shapes, and more complex ones. :) Possibly for those, choose the average of the rightmost pair of longitudes (each pair would correspond to a slice of the polygon), since the info window is oriented that way?

This gives you a little more control over positioning, too; for example, it might be nice to position the info window at 66 or 75% vertically, in order to leave more of the polygon visible. (Or it may not! But you have the knob to tweak.)

Answer 9

How about just using the point the user clicked to select it, if it is selected by the user that is.

Answer 10

I'm trying to solve this too. I've imposed a condition on my polygons that they cannot have crossing lines which enters into what I'll describe.

So, my approach uses triangulation. Take a random vertex (possibly take a vertex at the extreme N, E, W, or S may simplify things).

From this vertex, draw lines to the vertex one vertex away, ie if your vertex is vertex 3, look at vertex 3+2.

Construct a line from your original vertex to this vertex. If the constructed line :

1. crosses no other line and
2. its midpoint is not outside the polygon

Then you have constructed a triangle that is within the polygon. If the successful vertex was n+2, then your triangle is {n, n+1, n+2}, which we'll refer to as {v, v1, v2}. If not, try the next vertex, and continue until all vertices have been tried.

When you find a triangle, find the center of that by taking a line from vertex v to the midpoint of v1 and v2. The midpoint of that line is guaranteed to be inside the triangle, and inside the polygon.

I haven't yet coded this, but I can see as I think it over that a polygon with crossing lines will in fact cause some exotic conditions where this does not work. If that's the type of polygons you have, you'd need to test each line segment on the polygon and be sure it was not being crossed. Skip line segments that are crossed, and I think it will work.