1

我有以下两个课程

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# 编码。

4

2 回答 2

1

考虑将其边缘恰好是折线数组中(x,y,z)的线段的图形用作顶点标签。(startPoint, endPoint)在顶点标签上定义字典顺序。在遍历 中的折线数组时构建图形O(n log n)。检测长度为 的循环n，O(n)总计O(n)。

于 2013-05-14T18:21:23.240 回答
1

创建一个类

public class EndPoint {
    PointClass point ;
    int lineIndex ;
}

和一个数组

EndPoint endPoints[] ;

其长度是 的两倍polyLineArray。

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

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

于 2013-05-14T18:53:02.620 回答