如何有效地確定三維空間中的多邊形法線？

我有一堆在3D空間中定義多邊形的共麪點。它們總是以同樣的方式纏繞（例如順時針）。我需要確定包含該多邊形的平面的有符號法線，即知道該多邊形的哪個方向「向上」。如何有效地確定三維空間中的多邊形法線？

起初看起來很簡單：取兩條邊（頂點差異）並計算叉積。但是如果邊緣碰巧是共線的（你會得到一個零幅度的交叉積），那就失敗了。

那麼我試着走着頂點列表，直到找到第二個邊緣，這個邊緣與第一個邊緣形成相當大的角度。這可以在凸多邊形上可靠地工作，但如果最終的兩個邊沒有定義多邊形內的三角形，它可能會失敗（指向相反的方向）在非凸多邊形上。

我知道，如果我先對三角形進行三角化，那麼我可以輕鬆可靠地檢查任何三角形的面...但問題是我的三角測量庫需要知道平面正常。所以雞蛋必須放在雞肉前面。

如何在非凸多邊形中選擇兩個邊（或三個頂點），以便可靠地定義多邊形面向哪個方向？

來源

2015-08-28 Joe Strout

Offtopic。不是一個編程問題。這是更多的幾何/數學。嘗試http://math.stackexchange.com –

在這裏被問到，因爲數學家經常給出一個不容易（或不清楚如何）實現的答案，例如，「如果連接相鄰點的線完全在內，則頂點是耳朵多邊形「......一個真實的陳述，但對實際編碼沒有幫助。我在問一個我可以編碼的算法。 –

@JoeStrout我知道你已經有了一個滿意的答案，所以只是想引起你的注意，我添加了一個不同的（更簡單的）方法，我不確定你會「尋找」另一個答案。 – Amit

如果我是你，我會在下面的方式來完成它：

選擇任意點ç多邊形附近（任何頂點或質心）。
總和交叉積（P [i] -C）x（P [i + 1] -C）全部i（包括最後一個和第一個點對）。
標準化矢量。

需要注意的是第2步後你有哪些有正確的方向法線方向的矢量，其大小是2 S，其中小號是你的多邊形的面積。這就是爲什麼它應該工作，除非你的多邊形有零或幾乎爲零的區域。

順便說一下，C點在這裏僅用於使遠離原點的小多邊形的計算更爲精確。您可以選擇C = 0，從計算中有效地將其刪除。

來源

2015-08-28 15:48:48 stgatilov

這聽起來很酷。我會試一下！ –

經測試和確認可以工作（至少在我所有的測試案例中）。非常感謝！ –

@YvesDaoust：我記得你確實完全讀過這個問題。您的解決方案不會產生正常的正確方向。此外，它可能不穩定（取決於實施）。 – stgatilov

位於多邊形的任何邊界框上的任何頂點都不必將兩個邊連接成一個反射角。如果以原始排序順序連接，則任何3個不共線的頂點形成朝向多邊形方向的三角形。用那個三角形，你可以使用一個交叉產品來找到你的法線。

找到3個有效點的一個簡單方法是迭代所有頂點，同時保持最小/最大X，Y和位於該極端的頂點。然後，您只需選取一個軸（如X），取該軸的最小值的頂點，該軸的最大值的頂點，以及任何其他極值的第三個頂點。只要確保選擇max> min的軸，如果不是，選擇一個不同的軸。

來源

2015-08-28 22:18:15 Amit

如何保證答案後半部分的正常方位？另外，您的解決方案會受到各種不穩定性的影響：軸對齊的多邊形（最小=最大的情況），第三個頂點接近第一個或第二個頂點。事實上，它會使用一些寬容的魔法，但它會導致精度降低。 – stgatilov

@stgatilov - 第二部分僅描述如何使用簡單的頂點迭代來找到3個點（頂點）。正如我所解釋的，方向的正確性來自保持原始排序順序。軸對齊問題確實是一個障礙，這就是爲什麼我注意到至少有一個選擇的軸必須符合max> min值。這也增加了頂點不密切的機會，並且在任何情況下精度不是算法的問題，是實現/浮點精度的問題 – Amit

計算三維多邊形的三個signed areas，這些三維多邊形是將三維多邊形投影到XY，YZ和ZX平面上的，這會給出所需的法線。

來源

2015-08-29 09:53:24

在與其直徑相比多邊形區域較小的異常/病理情況下（具有大孔的多邊形，交叉的多邊形），可以通過使用凸殼（由Melkman算法獲得）而不是原始多邊形來改善事物。在大多數情況下，這將是矯枉過正的。 –

如何有效地確定三維空間中的多邊形法線？

回答

相關問題