在三维空间中我有一个无序的，比方说，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]

我想实现一个算法尽可能简单，因为提点的集合对应于〜42万点的网状每个顶点的具有N-Ring附近，我必须这样做的每一个点在网格上。

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.

前一段时间有一个similar就在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（单位）载体（A_X，A_y，A_Z），用右手定则;这是preferred方法，这样做 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.