对折线数组进行排序

本文关键字:排序 数组 折线 | 更新日期: 2023-09-27 18:13:25

我有以下两个类

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

public class PolyLineClass
{
    PointClass startPoint;
    PointClass endPoint;
}

和polylineclass数组

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.

上面的算法是0(可怕)。有没有更有效的排序方法?如果语言很重要,我将使用c#进行编码。

对折线数组进行排序

创建一个类

public class EndPoint {
    PointClass point ;
    int lineIndex ;
}

和数组

EndPoint endPoints[] ;

的长度是polyLineArray的两倍。

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

排序完成后,您可以遍历数组并选择端点。这些是成对的,这些点相等,但是线的指标指向在这一点相连的线。

考虑使用(x,y,z)作为顶点标签的图形,其边缘恰好是你的折线数组中的线段(startPoint, endPoint)。在顶点标签上定义字典顺序。通过O(n log n)中的折线数组迭代一次,构建图形。在O(n)中检测一个长度为n的循环,总O(n)