强健的多边形法向量计算

Question

强健的多边形法向量计算

11

有没有一个好的强大算法来计算凸多边形的法向量（当然是在三维空间中）？对于三角形，很容易：只需要取两条边，计算它们的叉积即可：

vec3 u = point[0] - point[1], v = point[0] - point[2];
vec3 n = normalize(cross(u, v));

但是，这种方法在多边形中并不适用。多边形的某些边缘可能几乎或者“完全”共线（在进行T型交点移除时经常会发生这种情况），因此需要选择一对边缘，并生成一个“强”的法向量（两个边缘都足够长，它们之间的夹角“几乎垂直”）。

然而，即使采用这种方法，对于某些多边形仍然无法奏效。想象一下一个圆盘形状的多边形。如果它被精细地细分，所有的边缘都会非常短，所有相邻的边缘都几乎共线，而其半径大小则无关紧要。同时，法向量是非常明确的。

一种解决方案是找到最大内接三角形，并计算其法向量。然而，找到它的复杂度为O(n^2)，似乎是不可行的。

更好的解决方案可能是使用SVD或特征值分解来计算法向量，给定所有多边形顶点，而不仅仅是三个或四个点。

是否有标准算法可以解决这个问题？有没有好的方法可以实现呢？

- the swine

3个回答

0

从任意一个顶点（我们称之为顶点A）开始，移动到列表中的下一个顶点（称之为顶点B）。计算垂直于AB向量的垂向量（称之为向量P）。然后继续在顶点列表中迭代，以找到垂直于向量AB最远的顶点。因此，在每次迭代中，使用当前元素（将顶点B视为原点）与向量P的点积，并选择具有最大大小的结果（取绝对值）并称其为C。计算ABC向量的叉积。

如果多边形是凸多边形，则可以停止迭代，直到垂直距离开始变小。

我想出了这个想法，但我不知道这种方法的效率如何，因为我不知道其他算法可以进行比较。

- Kaan99__

在三维空间中，你实际上无法计算出一个垂直向量。即使你限制为单位长度向量，也有无限多个这样的向量。但你可以计算从一个点到通过两个点（AB）的直线的距离。你可以选择这样的C，使其是AB的最大距离。这与选择不同的ABC并通过它们的叉积范数进行评分非常相似。 - the swine

在我的解决方案中，我假设多边形是一个平面表面，并且所有点都共面。 - Kaan99__

这有点像鸡生蛋的问题。你需要先了解那个平面，才能得分。但你又是为了计算那个平面而得分。我觉得这行不通。 - the swine

-1

你可以计算多边形所有点的协方差矩阵（对于三维空间，这将是一个3x3矩阵）。多边形的法向量将是对应于最小特征值的特征向量。

- Sourabh Bhat

有没有想法可以确定法向量的方向？因为在计算协方差矩阵时，顶点的顺序会丢失。显然，可以使用叉积计算出一个不太精确的法向量，并将精确的法向量翻转以指向更相似的方向。你能想到更优雅的解决方案吗？ - the swine

你说得对，协方差矩阵会失去连通性，因此法向量的正负号取决于你的约定。很抱歉，我不知道有什么简单的方法可以得到符号，除了你提出的那个方法。这种方法非常稳健，但与其他方法相比代价高昂。 - Sourabh Bhat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nico Schertler · Accepted Answer

如果你将三角形的公式进行分解，你会得到以下内容：

n ~ (p1 - p0) x (p2 - p0)
  = p0 x p1 + p1 x p2 + p2 x p0

您可以将这个公式推广到任意多边形中：

n ~ p0 x p1 + p1 x p2 + ... + pn x p0

将相邻边的叉积求和。这是一个健壮的算法，适用于非平面多边形。

如果你可以确定该多边形是平面的，我建议采取以下措施（以节省计算时间）：

Repeat k times
    Pick 3 random polygon vertices
    Calculate the normal of the according triangle
Choose the longest normal as the polygon's normal.

您可以丢弃任何 长度 <= epsilon 的普通值。