按顺时针/逆时针顺序对一组 3-D 点进行排序 [英] Sort a set of 3-D points in clockwise/counter-clockwise order

问题描述

在 3-D 空间中，我有一个无序的集合，比如 6 个点；像这样:

In 3-D space I have an unordered set of, say, 6 points; something like this:

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

                  (D)*

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

The points form a 3-D contour but they are unordered. For unordered I mean that they are stored in an

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

我只想从任意位置(假设 A 点)开始重新组织此列表，并顺时针或逆时针遍历这些点.像这样的:

I just want to reorganize this list starting from an arbitrary location (let's say point A) and traversing the points clockwise or counter-clockwise. Something like this:

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

或

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

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

I'm trying to implement an algorithm as simple as possible, since the set of points in mention corresponds to a N-ring neighborhood of each vertex on a mesh of ~420000 points, and I have to do this for each point on the mesh.

前段时间有一个类似的讨论关于点在 2-D 中，但现在我不清楚如何从这种方法转到我的 3-D 场景.

Some time ago there was a similar discussion regarding points in 2-D, but for now it's not clear for me how to go from this approach to my 3-D scenario.

推荐答案

如果没有轴和方向，顺时针"或逆时针"的概念是不明确的！(证明:例如，如果您从显示器屏幕的另一侧查看这些点或翻转它们会怎样！)

The notion of "clockwise" or "counterclockwise" is not well-defined without an axis and orientation! (proof: What if you looked at those points from the other side of your monitor screen, or flipped them, for example!)

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

You must define an axis and orientation, and specify it as an additional input. Ways to specify it include:

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

• a line (1x=2y=3z), using the right-hand rule
• a (unit) vector (A_x, A_y, A_z), using the right-hand rule; this is the preferred way to do so

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

In order to determine the orientation, you have to look deeper at your problem: You must define a "up" and "down" size of the mesh. Then for each set of points, you must take the centroid (or another "inside" point) and construct a unit vector pointing "up" which is normal to the surface. (One way to do this would be to find the least-squares-fit plane, then find the two perpendicular vectors through that point, picking the one in the "up" direction.)

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

You will need to use any of the above suggestions to determine your axis. This will allow you to reformulate your problem as follows:

输入:

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

一旦你有了角度，你就可以对它们进行排序.

Once you have the angles, you can just sort them.

这篇关于按顺时针/逆时针顺序对一组 3-D 点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！