math - 将 3d 共面点列表按顺时针或逆时针排序

Question

我有一个 3D 点列表。我知道它们都是共面的。我有我想要对它们进行排序的中心以及点和中心所在平面的法线。如何测试一个点是否在另一点的右侧(或左侧)？

我明白如何在 2D 中做到这一点。 Sort points in clockwise order?解释了如何比较 2d 点。所以我想我需要以某种方式将所有点和中心转换为局部二维平面坐标。我该怎么做？这是解决这个问题的最有效方法吗？

//from link:
// a and b are points
//center is the center around which to determine order
//int num = (a.x-center.x) * (b.y-center.y) - (b.x - center.x) * (a.y - center.y);
//if num=0 then they're on the same line
//if num <0 or num>0 then a is to the left or right of b

我将如何调整它以处理 3d 共面点？

Answer 1

无需将所有内容都转换为 2D。

你有中心 C 和正常的 n。要确定点 B 是从 A 点顺时针还是逆时针，请计算 dot(n, cross(A-C, B-C))。如果结果为正，则 B 从 A 逆时针方向；如果是负数，B 是从 A 顺时针方向。