algorithm - 如何有效地计算由共面点定义的闭环的法线？

Question

我们有一组共面点，它们定义了一个闭环，它们是逆时针缠绕的。循环保证不会自相交。

我们要计算正常

我们有两个问题。

1. 对于接近共线的点，浮点精度会导致使用叉积计算错误的法线。

2. 对于凹形闭环，一些法线将指向相反的方向。

我们的解决方案是计算定义闭环的所有顺序段的法线。这样，可以通过丢弃离群计算的法线来克服问题 1。可以通过知道大多数法线的方向是正确的来克服问题 2。

这似乎有效，但非常昂贵。

有没有更简单、更便宜、更优雅的解决方案？

标签： algorithmgraphicsgeometryplanecross-product

Answer 1

假设点{p_i}, 0<=i<n, 形成一个逆时针多边形，计算多边形的三角形扇形的每个三角形的叉积之和（即使在凹面部分）：

normal = vector3(0, 0, 0);
for(int i=1; i<n-1; ++i) 
    normal += cross(p[i+1]-p[0],p[i]-p[0]);
normal /= norm(n);

这是从斯托克定理推导出来的。法线的长度（归一化之前）等于循环所包围的有符号面积的两倍。因此，您可以保证它不会为空（如果该区域不为空），并且您可以保证它将指向正确的方向。