任意多边形的宽度

Question

我需要一种方法来描述二维点集的大小，以便于根据视口的比例决定将它们渲染为单个点或代表性多边形。我已经有一个算法来计算凸包以产生代表性多边形，但我需要一种方法来描述它的大小。一个明显的度量是凸包上两点之间的最大距离，即该点集的直径。但我更关心的是垂直于其直径的横截面大小，以确定边界多边形有多窄。给定排序后的顶点列表和最远点的索引（最好使用Python），是否有一种简单的方法来解决这个问题？

或者，是否有一种简单的方法来计算一组点的最小区域边界椭圆的半径？我已经看到了一些解决这个问题的方法，但没有一种可以很容易地转换为Python的方法，所以我真的在寻找一些现成的东西。

- acjay

Answer 1

你可以计算出：

横截面大小垂直于直径的大小

按照以下步骤进行操作：

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"

请注意，这不是“宽度”的一个特别好的定义 - 更好的定义是：

两条不同平行线之间的最小垂直距离，每条线都至少与多边形的边界有一个公共点，但没有一条线与多边形的内部相交。

另一个有用的大小定义可能是外壳上点和中心点之间平均距离的两倍。

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

- Eric

---

在我看来，只需要按照所描述的方法旋转两个最远的凸包点，然后沿着x轴（而不是y轴）取它们之间的差值，就可以确定凸包的宽度。 - martineau

@martineau：这只是给出了OP所指的直径。 - Eric

我现在明白了，但我认为是你使用“宽度”而不是称之为“高度”的差异让我感到困惑。 - martineau

这似乎是一个合理的近似值。如果你愿意，它给出了多边形只沿直径平移时可以通过的最小间隙宽度。如果你也可以垂直地滑动它，如果连接点的线本身不垂直于直径，它可能适合更小的间隙，但我认为这个近似值会很好地工作。谢谢！ - acjay

该方法不可行。例如：给定一个正方形，最远的两个点沿对角线分布。将正方形旋转使其对角线水平，沿y轴的跨度是正方形宽度的“sqrt(2)”倍。可以使用旋转卡尺算法（参见此处）来计算宽度。 - Cris Luengo

@CrisLuengo: 这个问题问到：“一个明显的度量是凸包上点之间的最大距离，即该集合的直径。但我真正感兴趣的是它在垂直于其直径方向的横截面大小。”- 我认为我的答案是针对这个问题正确的，但不适用于标题所示的问题。 - Eric