对折线数组进行排序
本文关键字:排序 数组 折线 | 更新日期: 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)