3

我需要一种方法来表征二维点集的大小，因此我可以根据视口的比例确定是将它们渲染为空间中的单个点还是代表性多边形。我已经有一个算法来计算集合的凸包以产生代表性多边形，但我需要一种方法来表征它的大小。一个明显的度量是凸包上点之间的最大距离，即集合的直径。但我真的更感兴趣的是它的横截面垂直于其直径的大小，以弄清楚边界多边形有多窄。考虑到顶点的排序列表和最远点的索引（理想情况下在 Python 中），有没有一种简单的方法可以做到这一点？

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

4

1 回答 1

8

您可以计算：

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

通过以下步骤：

  1. 找到凸包
  2. 找到相距最远a的两个点b
  3. d = (a - b).normalized()找到这两者之间的方向向量

  4. 使用矩阵旋转轴，使该方向向量水平放置：

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

  5. 在这个新坐标系中找到点的最小和最大 y 值。不同的是你的“宽度”

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

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

另一个有用的尺寸定义可能是船体上的点与中心之间的平均距离的两倍

center = sum(convexhullpoints) / len(convexhullpoints)
size = 2 * sum(abs(p - center) for p in convexhullpoints) / len(convexhullpoints)
于 2012-11-05T21:42:44.053 回答