排序折線

Question

數組我有以下兩類

public class PointClass 
{ 
    double x, y, z; 
} 

和

public class PolyLineClass 
{ 
    PointClass startPoint; 
    PointClass endPoint; 
} 

和PolyLineClasses

polyLineArray[]; 

數組假設，如果我們連接中的所有行polyLineArray以某種順序，我們得到一個封閉的非自相關曲線。

例如

    startPt endPt 
polyLineArray[0]: (0,0,0) (1,0,0) 
polyLineArray[1]: (0,1,0) (0,0,0) 
polyLineArray[2]: (1,1,0) (0,1,0) 
polyLineArray[3]: (1,0,0) (1,1,0) 

如果我們通過在0-> 3-> 2-> 1個的順序陣列遍歷，我們創建了一個閉合曲線（在這個簡單的例子中，正方形）。 現在，我有如下算法：

1) int i = 0; 
2) Get the endPt of polyLineArray[i]; 
3) search through the array for an element with index j such that 
    polyLineArray[i].endPoint == polyLineArray[j].startPoint. 
4) i = j; Repeat from step2 until all elements in the array have been visited. 

上述算法是O（嚇人）。有沒有更有效的方法來進行分類？ 如果語言無關緊要，我在c＃中編寫代碼。

Answer 1

創建類

public class EndPoint { 
    PointClass point ; 
    int lineIndex ; 
} 

和陣列

EndPoint endPoints[] ; 

，其長度兩倍的polyLineArray。

對於線i的每個端點e創建EndPoint {e,i}並將其添加到endPoints陣列。然後按point元素順序對此數組進行排序。 （這些點可以分類/比較組件方式）。

排序完成後，您可以遍歷數組並選取EndPoints。這些將成對出現，其中點是相等的，但是線索引將指向在該點加入的線。您可以走路排序的EndPoint陣列來拾取PolyLines的鏈接系列。

Answer 2

考慮使用(x,y,z)作爲圖的頂點標籤，該圖的邊緣恰好是折線數組中的線段(startPoint, endPoint)。定義頂點標籤上的字典順序。在O(n log n)中通過折線數組迭代一次來構建圖形。在O(n)中檢測長度爲n的週期，總計爲O(n)。