What is the fastest way to find the center of an irregular convex polygon?

Question

I'm interested in a fast way to calculate the rotation-independent center of a simple, convex, (non-intersecting) 2D polygon.

The example below (on the left) shows the mean center (sum of all points divided by the total), and the desired result on the right.

Some options I've already considered.

• bound-box center (depends on rotation, and ignores points based on their relation to the axis).
• Straight skeleton - too slow to calculate.

I've found a way which works reasonably well, (weight the points by the edge-lengths) - but this means a square-root call for every edge - which I'd like to avoid.
(Will post as an answer, even though I'm not entirely satisfied with it).

---

Note, I'm aware of this questions similarity with:
What is the fastest way to find the "visual" center of an irregularly shaped polygon?

However having to handle convex polygons increases the complexity of the problem significantly.

Answer 1

I think its easiest to do something with the center of masses of the delaunay triangulation of the polygon points. i.e.

def _centroid_poly(poly):

    T = spatial.Delaunay(poly).simplices
    n = T.shape[0]
    W = np.zeros(n)
    C = 0

    for m in range(n):
        sp = poly[T[m,:],:]
        W[m] = spatial.ConvexHull(sp).volume
        C += W[m] +np.mean(sp, axis = 0)

    return C / np.sum(W)

This works well for me!

Answer 2

There is no much better way than the accumulation of coordinates weighted by the edge length, which indeed takes N square roots.

If you accept an approximation, it is possible to skip some of the vertices by curve simplification, as follows:

• decide of a deviation tolerance;

• start from vertex 0 and jump to vertex M (say M=N/2);

• check if the deviation along the polyline from 0 to M exceeds the tolerance (for this, compute the height of the triangle formed by the vertices 0, M/2, M);

  • if the deviation is exceeded, repeat recursively with 0, M/4, M/2 and M/2, 3M/4, M;

  • if the deviation is not exceeded, assume that the shape is straight between 0 and M.

• continue until the end of the polygon.

Where the points are dense (like the left edge on your example), you should get some speedup.

Answer 3

The points of the polygon can be weighted by their edge length which compensates for un-even point distribution.

This works for convex polygons too but in that case the center point isn't guaranteed to be inside the polygon.

Psudo-code:

def poly_center(poly):
    sum_center = (0, 0)
    sum_weight = 0.0
    for point in poly:
        weight = ((point - point.next).length +
                  (point - point.prev).length)
        sum_center += point * weight
        sum_weight += weight

    return sum_center / sum_weight

Note, we can pre-calculate all edge lengths to halve the number of length calculations, or reuse the previous edge-length for half+1 length calculations. This is just written as an example to show the logic.

---

Including this answer for completeness since its the best method I've found so far.