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

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]

我正在尝试尽可能简单地实现算法,因为提到的点集对应于~420000点的网格上的每个顶点的N环邻域,并且我必须对网格上的每个点执行此操作.

前段时间对二维中的点进行了类似的讨论,但目前我不清楚如何从这种方法转向我的三维场景.

Answer 1

没有轴和方向,"顺时针"或"逆时针"的概念没有明确定义!(证据:例如,如果你从显示器屏幕的另一侧观察这些点,或者将它们翻转,会怎样!)

您必须定义轴和方向,并将其指定为附加输入.指定方法包括:

• 一行(1x=2y=3z),使用右手规则
• 一个(单位)向量(A_x, A_y, A_z),使用右手规则; 这是这样做的首选方式

为了确定方向,您必须更深入地研究您的问题:您必须定义网格的"向上"和"向下"大小.然后,对于每组点,您必须采用质心(或另一个"内部"点)并构造一个指向"向上"的单位向量,该向量与表面垂直.(实现此目的的一种方法是找到最小二乘拟合平面,然后找到通过该点的两个垂直向量,从"向上"方向选择一个.)

您需要使用上述任何建议来确定您的轴.这将允许您按如下方式重新表述您的问题:

输入:

• 点集{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

一旦你有角度,你可以只对它们进行排序.