将 3d 共面点列表排序为顺时针或逆时针

本文介绍了将 3d 共面点列表排序为顺时针或逆时针的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I have a list of 3D points. I know they are all coplanar. I have the center that I want to sort them around and the normal to the plane on which the points and the center lie. How can I test if one point is right (or left) of another point?

我了解如何在 2D 中进行操作.按顺时针顺序排序点? 解释了如何比较 2d 点.所以我认为我需要以某种方式将所有点和中心转换为局部二维平面坐标.我怎样才能做到这一点?这是解决这个问题最有效的方法吗?

I understand how to do it in 2D. Sort points in clockwise order? explains how to compare 2d points. So I think I need to somehow covert all the points and the center to local 2d plane coordinates. How can I do that? Is it the most efficient way to solve this problem?

//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 共面点?

How would I adapt this to handle 3d coplanar points?

推荐答案

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

There's no need to convert everything to 2D.

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

You have the center C and the normal n. To determine whether point B is clockwise or counterclockwise from point A, calculate dot(n, cross(A-C, B-C)). If the result is positive, B is counterclockwise from A; if it's negative, B is clockwise from A.