Better "centerpoint" than centroid

Question

I'm using the centroid of polygons to attach a marker in a map application. This works definitely fine for convex polygons and quite good for many concave polygons.

However, some polygons (banana, donut) obviously don't produce the desired result: The centroid is in these cases outside the polygons area.

Does anybody know a better approach to find a suitable point within any polygons area (which may contain holes!) to attach a marker?

Answer 1

To get a point for a marker I would use Yves Daoust's method.

To get a point that is reliably "within any polygon with holes" I would split polygon into triangles with a reliable library (e.g. OpenGL's GLUtessellator), and then get centroid of triangle with largest area.

If I had time for developing and testing, and I wanted good performance, then I would use a hybrid method: First use Yves Daoust's method to get some candidate points and then test candidates to see if they are within polygon. If all candidates fail, then fall back to slower reliable method (e.g. GLUtesselator).

Answer 2

Find the extreme ordinates and draw an horizontal line in the middle. It is guaranteed to cross the polygon.

Find the intersection with the sides and sort them by increasing abscissa. Pick a point in the middle of two intersections.

This is an O(N + K Log K) process where K is the number of intersections (usually a very small even number). Pretty straightforward to write.

To increase the chances of a nice placement, you can try three horizontals instead of one an pick the longest intersection segment.