c# - 对多段线数组进行排序

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(scary)。有没有更有效的方法来进行排序？ 如果语言很重要，我会使用 C# 进行编码。

Answer 1

创建一个类

public class EndPoint {
    PointClass point ;
    int lineIndex ;
}

和一个数组

EndPoint endPoints[] ;

其长度是polyLineArray的两倍。

为 i 行的每个端点 e 创建一个端点 {e,i} 并将其添加到 endPoints 数组。然后按照点元素顺序对这个数组进行排序。 (可以按组件对点进行排序/比较)。

排序完成后，可以遍历数组，取出EndPoints。这些将成对出现，其中点相等，但线索引将指向在该点连接的线。您可以遍历排序的 EndPoint 数组，拾取一系列链接的多段线。