# Algorithm for finding irrregular polygon centroid (label point)

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).

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

• I hadn't thought about this. Ideally I'd like this point in the polygon and not on the edge, but this might be what I fall back to. – Jason Sep 23 '10 at 18:50
• Once you have found an edge point you can intersect a small square centered at that point with the polygon and then choose the centroid of the intersection. When the square is small enough this is guaranteed to be an interior point (although it will of course be very close to an edge). – whuber Sep 23 '10 at 21:47
• @Jason If you use the real centroid you may be less likely to encounter this problem. Shouldn't be too hard to translate something quickly to JavaScript: github.com/cartesiananalytics/Pipra/blob/master/src/… – Dandy Sep 24 '10 at 2:09
• While my solution (rays from false centroid) will work most of the time, I think this solution would probably work best because of its simplicity and the fact that you're guaranteed to find a point at least on the edge, and could easily shift it to be inside the polygon with very little effort. – Jason Sep 25 '10 at 13:05

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/

• If you wanted to implement this on the server side, both JTS(Java) and Geos(C) implement this functionality. – DavidF Sep 23 '10 at 15:26
• Yeah, I probably should have added that I already have the code to determine if my "calculated" centroid is within the polygon or not. What I actually want is some way to create a centroid that is within the polygon. – Jason Sep 23 '10 at 18:48

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.

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();
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 = [
];
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.

• This method will fail for some tortuous polygons. For example, buffer the polyline {{0, 9}, {10, 20}, {9, 9}, {20, 10}, {9, 0}, {20, -10}, {9, -9}, {10, -20}, {0, -9}, {-10, -20}, {-9, -9}, {-20, -10}, {-9, 0}, {-20, 10}, {-9, 9}, {-10, 20}, {0,9}} by less than 1/2. It's also inefficient compared to Dandy's QAD method, for instance. – whuber Sep 23 '10 at 21:44

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)

• +1 because this may have a fair chance of a hit the second time around. So long as your "random" is reproducible each time to not annoy the user this is a valid solution as well. The odds of it not hitting a valid point soon are slim, especially if you start with a good guess point. – Dandy Sep 24 '10 at 3:01
• @Dandy: Actually, in some cases this can be a really poor algorithm. Consider a narrow diagonal sliver for instance. These exist in practice (e.g., long parcels of road frontage) and can easily occupy less than 0.1% of the bounding box (sometimes far less). To be reasonably sure (95% confident) of hitting such a polygon with this technique would require about 3,000 iterations. – whuber Sep 24 '10 at 13:37
• @Whuber: If you pick a bad starting location yeah that could take a while to run to completion. If you also consider that hypothetically 95% of clicks will be on more desirable geometries this may only be a problem 5% of the time. Also as with another GIS.se question if performance is the aim there is never a single solution, it is best to change tactics based on heuristics. There is no reason to run this out for 3000 iterations. You can always bail out to my QAD after 10. I think it would be worth it to try this one for a few iterations as the location may be more desirable. – Dandy Sep 24 '10 at 14:25
• @Dandy: But what's the matter with your QAD solution? You could even modify it a tiny bit by moving from the original trial labelpoint to the nearest vertex in some internal buffer of the polygon: still QAD but now guaranteed to land on an internal location of the original feature. BTW, your strategy of bailing out soon is a good one. Whenever I code a random probe like this, I precompute the ratio of the feature's area to that of its bounding box, use that to find expected time to success, and immediately warn the user if it could be long. – whuber Sep 24 '10 at 16:03
• @Whuber the area ratio heuristic is a great idea because you just about calculate the centroid when you calculate the area. As for the problem with my QAD solution: it is on the edge. If I choose that point and buffer it like you say, that "small" radius may be larger than the length across that narrow section. There is always a corner case. So much to consider, just to make a balloon that will clutter up the UI and obscure the geometry anyway. Probably better to choose the highest or lowest vertex. – Dandy Sep 24 '10 at 17:13

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.)

• I understand what you were saying about using the edge of a geometry such that the edge is within the interior of the polygon of interest. I don't understand how you would go about creating this edge/vertex. The only thing I can think of is to make a virtual triangle by intersecting a perpendicular ray from the point of interest to the segment opposite the segment of the selected point. The midpoint between those two points could be the top of that virtual triangle. – Dandy Sep 24 '10 at 17:52
• @Dandy: That gets to the heart of it. There are many ways to go about this depending on what your GIS does natively. For example, once you have found a ray that intersects the original feature in a set of positive length, that intersection will be a disjoint union of line segments. Use the center of any of those segments. Another way is to start with any point on the feature (preferably near its middle, which is what your QED method accomplished), create a small simple polygon (e.g., square) centered there, intersect it with the original feature, pick the unique connected component ... – whuber Sep 24 '10 at 18:05
• (continuation)... containing the starting point, and recursively choose a center for that component. There will be loads of methods available when your GIS lets you loop over the sequences of vertices describing the feature's boundary. If negative buffers are supported, you can iteratively find a set of maximum-distance interior points (the "skeleton", which is a subset of the MAT). This is a little expensive but is fairly easy to program and produces excellent label points. – whuber Sep 24 '10 at 18:08

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.)

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

• It can be selected by a mouse click or non-spatial query, so this wouldn't always work. – Jason Sep 24 '10 at 15:52

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.

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