按顺时针/逆时针顺序排序一组三维点

Question

在三维空间中，我有一个无序的包含6个点的集合，类似于以下内容：

           (A)*
                          (C)*
(E)*
                         (F)*
     (B)*

                  (D)*

这些点形成了一个三维轮廓，但它们是无序的。所谓无序是指它们以

unorderedList = [A - B - C - D - E - F]

我只想重新组织这个列表，从一个任意点开始（比如点A），并按顺时针或逆时针方向遍历点。类似于这样:

orderedList = [A - E - B - D - F - C]

或者

orderedList = [A - C - F - D - B - E]

我正在尝试实现一个尽可能简单的算法，因为涉及到大约420,000个点网格的每个顶点的N环邻域，而我需要为网格上的每个点执行此操作。

一段时间前有一个关于2-D中点的类似讨论，但目前对我来说还不清楚如何从这种方法转移到我3-D的场景。

- CodificandoBits

Answer 1

“顺时针”或“逆时针”的概念在没有轴和方向的情况下并不明确（证明：例如，如果您从显示器屏幕的另一侧或翻转它们来看这些点会怎样！）。

您必须定义一个轴和方向，并将其指定为附加输入。指定方法包括：

- 使用“右手法则”确定线（1x = 2y = 3z）。 - 使用“右手法则”确定（单位）矢量（Ax，Ay，Az）；这是首选的方法。

为了确定方向，您必须深入研究问题：必须定义网格的“上”和“下”大小。然后，对于每组点，必须取质心（或另一个“内部”点），并构造一个指向“上”的单位矢量，该矢量垂直于表面。 （一种方法是找到最小二乘平面，然后找到通过该点的两个垂直矢量，选择朝“上”的那一个。）

---

你需要使用上述建议之一来确定你的轴，这将允许你重新制定问题如下：

输入：

- 点集 {P_i} - 一个轴，我们称之为“z轴”，并将其视为以点的重心（或某个“内部”位置）为中心的单位向量 - 通过上述方法之一选择的方向（例如逆时针方向）

设置：

对于所有点，选择两个相互正交的单位向量到轴，我们称之为“y轴”和“x轴”。（只需将z轴单位向量在两个方向上旋转90度，详见http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations)

算法：

对于每个点P，将P投影到x轴和y轴上（使用点积），然后使用http://en.wikipedia.org/wiki/Atan2 一旦你有了角度，你可以直接对它们进行排序。

- ninjagecko

---

除了 atan2 函数外都很好，在平面上应该使用向量积来比较点。 - unkulunkulu

使用 atan2 没有什么问题。然而，unkulunkulu 的建议也很有趣！通常 (P1 x P2) · Z 会给出一个不一致的排序顺序，但是如果你将它与适当的排序技术（如快速排序或基于枢轴的排序）结合起来，它就能够工作了。这是因为在圆上进行叉积运算时，会问“通过顺时针还是逆时针旋转更快到达那里？”其他排序算法可能会失败。否则，使用叉积是很困难的；例如，如果你尝试按 (X x P2) · Z 进行排序， sin 在 0度-180度范围内不可逆！另外，像往常一样，必须小心规范化。 - ninjagecko

ninjagecko，我认为你提出的方法（将x、y、z点投影到最佳拟合平面上）在我的情况下似乎是足够的。然而，我正在考虑一个假设性问题：假设我的最佳拟合平面是z=0（法向量：0,0,1），并且要被投影的两个点共享相同的x和y坐标（仅在z坐标上有所不同）。在这种情况下，从3D到2D的投影看起来就像它们只是一个点！我是对的吗？我错过了什么吗？如果是这样，如何解决这个问题？ - CodificandoBits

@Miguel：抱歉，我没有说明。这相当于问“如果两个值相同，在我的排序算法中应该怎么做？”答案是它们是相同的，你应该以同样的方式对待它们。如果这让你不舒服，你可以选择一个不同的轴。类似的问题出现在确定(0,1)是0度还是360度时；由于你所述问题的性质是任意的，所以这是任意的。在你的情况下，我不预计这会让你不舒服，因为你的点可能是在一个局部邻域内“非重叠”生成的。 - ninjagecko

Answer 2

我无法保证这段代码的效率，但它可以工作，您可以根据需要优化其中的部分，只是我不擅长这方面。
代码使用C#编写，使用系统集合类和linq。
Vector3是一个带有浮点型x、y、z和静态向量数学函数的类。
Node是一个带有名为pos的Vector3变量的类。

//Sort nodes with positions in 3d space.
//Assuming the points form a convex shape.
//Assuming points are on a single plain (or close to it).

public List<Node> sortVerticies( Vector3 normal, List<Node> nodes ) {

    Vector3 first = nodes[0].pos;

    //Sort by distance from random point to get 2 adjacent points.
    List<Node> temp = nodes.OrderBy(n => Vector3.Distance(n.pos, first ) ).ToList();

    //Create a vector from the 2 adjacent points,
    //this will be used to sort all points, except the first, by the angle to this vector.
    //Since the shape is convex, angle will not exceed 180 degrees, resulting in a proper sort.
    Vector3 refrenceVec = (temp[1].pos - first);

    //Sort by angle to reference, but we are still missing the first one.
    List<Node> results = temp.Skip(1).OrderBy(n => Vector3.Angle(refrenceVec,n.pos - first)).ToList();

    //insert the first one, at index 0.
    results.Insert(0,nodes[0]);

    //Now that it is sorted, we check if we got the direction right, if we didn't we reverse the list.
    //We compare the given normal and the cross product of the first 3 point.
    //If the magnitude of the sum of the normal and cross product is less than Sqrt(2) then then there is more than 90 between them.
    if ( (Vector3.Cross( results[1].pos-results[0].pos, results[2].pos - results[0].pos ).normalized + normal.normalized).magnitude < 1.414f ) {
        results.Reverse();
    }

    return results;
}

- Max Izrin