按顺时针/逆时针顺序对一组3-D点进行排序

  • Z时代
  • 2024-01-10
  • 分类：问答

在3-D空间中，我有6个点的无序集合。像这样的东西：

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

这些点形成3D轮廓，但它们是无序的。对于无序，我的意思是它们存储在

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

我只想从一个任意位置（例如A点）开始重新组织此列表，然后顺时针或逆时针遍历这些点。像这样：

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

要么

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

我正在尝试实现一种尽可能简单的算法，因为提到的点集对应于〜420000个点的网格上每个顶点的N环邻域，因此我必须对网格上的每个点进行此操作。

一段时间以前，关于2-D点的讨论也类似，但是对于我而言，目前尚不清楚如何从这种方法过渡到3-D场景。

回答：

没有轴和方向，“顺时针”或“逆时针”的概念定义不明确！（证明：例如，如果您从显示器屏幕的另一侧查看这些点或将它们翻转，该怎么办！）

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

  • 一条线（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

一旦有了角度，就可以对其进行排序。

以上是 按顺时针/逆时针顺序对一组3-D点进行排序 的全部内容， 来源链接： utcz.com/qa/415364.html

回到顶部