0

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.

center of a polygon

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.

Community
  • 1
  • 1
ideasman42
  • 42,413
  • 44
  • 197
  • 320
  • An exact solution requires Ω(N) operations. Do you accept approximate solutions ? –  Dec 03 '15 at 09:08

3 Answers3

1

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.

ideasman42
  • 42,413
  • 44
  • 197
  • 320
  • Assuming a constant linear density, this computation is exact, it does give the centroid of the outline. –  Dec 03 '15 at 08:59
0

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.

0

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!

Alec Day
  • 65
  • 7