如何將點分成兩組 - 分佈的上下部分

我有3d（x，y，z）中的點列表對於每個列表，我想將該列表分成兩個列表，其中一個包含來自輪廓和第二下半部的上部，就像這樣：如何將點分成兩組 - 分佈的上下部分

enter image description here

我在這裏的問題是如何確定哪個點應該去上部，哪一個應該去下部距離有那些點與他們的座標（x，y，z）。

是否有始終在「頂」和「底」同等數量的點？ – Geobits

恐怕不行，如果是的話會怎樣？ –

我在想一個快速和骯髒的方式（如果他們）會找到最左邊的點，並將該點和下一個「n/2」點（順時針旋轉）標記爲「頂部」。但是，這只是針對特定的情況，而您確認的情況並非如此。 – Geobits

由於點可以在很多方面分成兩半，所以有更多的標準如何分割它們是很好的。

在這種情況下，您似乎在尋找一條曲線，它將點雲分割，形狀與雲相似。可以覆蓋你的形狀的擬合曲線可以提供幫助。二階或三階多項式可能適用於這些形狀。

第二個想法是創建一些經過「幾何中間」的東西。在2D情況下，您可以使用中軸的方法。可以通過Delaunay三角測量計算點雲。如果點靠近某架飛機，可以將它們投射到飛機上並使用此方法。

2013-09-06 07:36:58 Ante

首先，在每個相鄰點之間創建「線條」。假設這些點是按照循環順序給出的，這應該很容易。

然後，從0,0（左上角）投射一條線到每個點。如果它與另一條線相交，則不在上方。如果沒有，那就是。

這是O（n^2），所以我肯定有一個更好的解決方案，但對於小組點，它應該沒問題。請注意，它不適用於極其凹陷的形狀，但適用於所有這些。

2013-09-05 18:12:25 Geobits

好吧，我知道它。我會盡力實現這個認識。 –

優化此操作將使用掃描線算法，掃描線處於「向上」方向（朝向0,0？）。這將它帶到O（n log n）。 –

加入相鄰的邊緣以獲得線..以逆時針的角度爲正.. 在雲的上部，連續線具有增加的角度.. ，而在下部的連續線已經降低角度..

阿律試驗和錯誤應該引領你到一個合適的hueristic ..

enter image description here

2013-09-10 06:37:16

回答