Better “centerpoint” than centroid

问题:

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?

回答1:

One approach would be to generate and refine a skeleton of the polygon, then use the midpoint of the skeleton to place your marker (and if it's text, to orient the text correctly). This works well for most shapes, including ones with holes, and banana-shaped or tadpole-shaped crescents.

The CGAL library has a 2D Straight Skeleton and Polygon Offsetting module, or you could use PostGIS, for example.

回答2:

To rephrase comment of ChristopheRoussy we may look for the largest circle inside of the polygon.

The largest circle is the one which cannot grow anymore because it touches three vertices or edges (if it touches only two, it can become bigger or just moved until it touches third).

So if you have few vertices, you can just enumerate all possible triples of vertices/edges, find for each one a circle and then select the largest one.

But it will require creating four functions:

1. Circle(vertex,vertex,vertex)
2. Circle(vertex,vertex,edge)
3. Circle(vertex,edge,edge)
4. Circle(edge,edge,edge)

All of them are possible, but may require some effort.

回答3:

I have no idea how to solve this for any possible shape (and not doing heavy computation), but maybe for simpler shapes like the ones you have shown:

https://en.wikipedia.org/wiki/Force-directed_graph_drawing

Heuristic: This could converge to a reasonable approximation after a while

• transform shape border into many points (more = more precise)
• start out with many random points inside the polygon
• push them until they are furthest away from border points, or just compute distance ... (can be done in parallel)
• take best point

Another way could be to use multiple algorithms depending on the nature of the shape (like another one for donuts ...). Also perhaps relying on measuring 'fattest' sections first ?

IMHO would ask this on a math forum.

Similar: Calculate Centroid WITHIN / INSIDE a SpatialPolygon

Similar: How to find two most distant points?

回答4:

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.

回答5:

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

回答6:

for (int i = 0; i < n; /*++i*/) {
    p = RandomPointInsideConvexHull();
    if (IsInsidePolygon(p)) {
        ++i;
        d = DistanceToClosestEdge(p);
        if (d > bestD) {
            bestP = p;
        }
    }
}

After running this loop you will approximate solution by bestP. n is parameter to choose. If you want more accurate result you can restart search, but now instead of picking a point inside polygon's convex hull you can pick one in the neighborhood of bestP, say not farther than bestD / 5 (this time you don't need to check if random point is inside polygon).