Width of an arbitrary polygon

3
votes

I need a way to characterize the size of sets of 2-D points, so I can determine whether to render them as individual points in a space or as representative polygons, dependent on the scale of the viewport. I already have an algorithm to calculate the convex hull of the set to produce the representative polygon, but I need a way to characterize its size. One obvious measure is the maximum distance between points on the convex hull, which is the diameter of the set. But I'm really more interested in the size of its cross-section perpendicular to its diameter, to figure out how narrow the bounding polygon is. Is there a simple way to do this, given the sorted list of vertices and and the indices of the furthest points (ideally in Python)?

Or alternatively, is there an easy way to calculate the radii of the minimal area bounding ellipse of a set of points? I have seen some approaches to this problem, but nothing that I can readily convert to Python, so I'm really looking for something that's turnkey.

1
pythoncomputational-geometry

1 Answers

8
votes

You can compute:

the size of its cross-section perpendicular to its diameter

with the following steps:

  1. Find the convex hull
  2. Find the two points a and b which are furthest apart
  3. Find the direction vector d = (a - b).normalized() between those two

  4. Rotate your axes so that this direction vector lies horizontal, using the matrix:

    [ d.x, d.y]
[-d.y, d.x]

  5. Find the minimum and maximum y value of points in this new coordinate system. The difference is your "width"

Note that this is not a particularly good definition of "width" - a better one is:

The minimal perpendicular distance between two distinct parallel lines each having at least one point in common with the polygon's boundary but none with the polygon's interior

Another useful definition of size might be twice the average distance between points on the hull and the center

center = sum(convexhullpoints) / len(convexhullpoints)
size = 2 * sum(abs(p - center) for p in convexhullpoints) / len(convexhullpoints)