如何確定3D頂點的排序

如果我在3D座標空間中有5個頂點，我如何確定這些頂點的排序。即順時針或逆時針。如何確定3D頂點的排序

如果我更多地討論這個，

我有它由一套多邊形的3D模型。每個多邊形都是頂點的集合，我想計算多邊形曲面的範數。要計算範數，我必須考慮逆時針順序的頂點。我的問題是給定的頂點集，我怎樣才能確定它是順時針還是逆時針排序？

這是用於導航網格生成的地方，我想要刪除代理不能走的多邊形。爲此，我的方法是計算表面範數（多邊形的垂直矢量），並根據2D平面的角度去除多邊形。要計算規範，我應該知道排列哪些點。所以對於多邊形中給定的一組點，我怎樣才能確定點的排列順序。

Ex。

polygon1由Vertex1 = [-21.847065 -2.492895 19.569759]，Vertex2 [-22.279873 1.588395 16.017160]，Vertex3的[-17.234818 7.132950 7.453146]這3點，我怎麼能確定它們的順序

來源

2010-01-01 Suranjith

你將有更好的運氣在http://mathoverflow.net。 – 2010-01-01 07:24:26

在3D空間中沒有順時針或逆時針這樣的東西。順時針或逆時針僅適用於2D平面。如果您想首先在2D平面上投影頂點，則由您來定義該平面。如上所述，你的問題毫無意義。 – AnT 2010-01-01 07:25:28

我很困惑;你的頂點已經訂購了，你想確定訂單，還是他們是隨機排列的，你想把它們排列好？你也知道，爲了做出這個決定，頂點需要被映射到一個平面，並且一方需要被聲明爲前方？通常訂購用於指定三角形是否面向相機。無論哪種方式，你爲什麼要這樣做，在什麼語言和框架？或者這是一個家庭作業問題？ – dlamblin 2010-01-01 07:29:15

你的問題定義不足以給出完整的答案，但這裏是一個的骨架。

缺少的部分（肉，如果你願意），是一個函數，需要任何兩個座標，並告訴你哪一個比另一個'更大'。沒有一個明確的定義，你將無法做任何事情。

其餘的骨架非常簡單。使用比較函數對向量列表進行排序。對於五個向量，簡單的bubble sort將是您所需要的，但如果頂點數量顯着增加，您可能需要查看更快的排序算法（即Quicksort）。

如果您選擇的語言/圖書館爲您提供排序，那麼您已經擁有了您的框架。

編輯重新閱讀您的問題後，也發生在我身上，由於這n個頂點定義多邊形，你也許可以做，他們都趴在同一平面上（如果他們不這樣做的假設，那麼好運渲染即）。因此，如果您可以將矢量座標映射到該平面上的2d位置，則可以減少您的問題，以便在二維空間中順時針或逆時針對它們進行排序。

來源

2010-01-01 07:48:19

正如其他人所指出的，你的問題並不完全清楚。是否像3D backface culling測試？如果是這樣，你需要一個點來確定相對於纏繞方向。從多邊形的一側看，頂點將看起來順時針旋轉。從另一側他們會出現逆時針逆時針轉動。

但是，假設你的多邊形是凸的並且是平面的。取任意三個連續的頂點A，B和C.然後，你可以找到使用cross product的surface normal向量：

N = (B - A) x (C - A)

以正常的dot product從給定的角度來看，V矢量，到頂點的人會給你，其符號表示該方式的值頂點出現風從V觀察：

w = N . (A - V)

這是否是積極的順時針和負逆時針爲或者相反，將取決於你的座標系的螺旋。

來源

2010-01-01 08:10:16 Boojum

我覺得你的困惑來自於一個事實，即用於計算跨產品的方法，有時教clockwiseness方面，具有3點A，B，C確定的標誌clockwiseness的檢查： (B-A) X (C - A) 但是一更好的定義實際上決定了這一點。一般而言，三維中的任意點不能說是順時針排列，而是3個，因爲3個點總是位於一個平面內。

來源

2010-01-01 08:22:56

如何確定3D頂點的排序

回答

相關問題