1

我有一个 3D 凸多边形。为简单起见,让它成为一个有顶点的正方形,(0,0,0),(1,1,0),(1,1,1),(0,0,1).。我需要按逆时针顺序排列这些顶点。我在这里找到了解决方案。建议确定多边形中心的角度并对其进行排序。我不清楚这将如何工作。有没有人有办法解决吗?我需要一个强大的解决方案,甚至在顶点非常接近时也可以工作。

一个示例 MATLAB 代码将不胜感激!

4

5 回答 5

1

这实际上是一个相当乏味的问题,所以我没有实际执行它,而是要解释我将如何执行它。首先找到平面方程(您只需要为此使用 3 个点),然后找到您的旋转矩阵。然后在新的旋转空间中找到你的向量。在那之后, 找到你的点在哪个象限,如果在特定象限中 n > 1,那么你必须找到每个点的角度 (theta = arctan(y/x))。然后只需按每个象限的角度对每个象限进行排序(可以说,您可以通过 pi 而不是象限进行分离(当 y 分量(旋转后)大于零时将点排序)。

抱歉,我没有时间实际测试它,但试一试,随时发布您的代码,如果您愿意,我可以帮助调试它。

于 2013-02-27T04:39:25.757 回答
1

幸运的是,您有一个凸多边形,因此您可以使用角度技巧:在内部找到一个点(例如,找到两个不相邻点的中点),然后将向量绘制到所有顶点。选择一个向量作为基础,计算与其他向量的角度并排序。您可以使用点积计算角度: A · B = AB cos θ = |A||B| 系数θ。

于 2013-02-27T05:33:44.653 回答
1

以下是我遵循的步骤。

  1. 可以使用已知公式将 3D 平面多边形旋转到 2D 平面。使用Rotation matrix from axis and angle部分下的那个。

  2. 然后如@Glenn 所示,需要计算一个内部点来找到角度。我将该内部点作为mean顶点位置的 。

  3. 使用 x 轴作为参考轴,可以使用此处解释的函数计算每个顶点的0按比例缩放的角度。2piatan2

    从向量 a 到向量 b 逆时针测量的非负角度,在范围[0,2pi],如果a = [x1,y1]b = [x2,y2],由下式给出:

    angle = mod(atan2(y2-y1,x2-x1),2*pi);

  4. 最后,对角度进行排序,[~,XI] = sort(angle);

于 2013-03-02T23:46:52.077 回答
0

因此,如果您想使用 convhull,这是另一个答案。通过将一个坐标设置为零,可以轻松地将多边形投影到轴平面中。例如,在 (0,0,0),(1,1,0),(1,1,1),(0,0,1) 中设置 y=0 得到 (0,0),(1, 0),(1,1),(0,1)。现在你的问题是二维的。

如果您的多边形平面与某个轴正交,您可能需要做一些工作来选择正确的坐标,如果是,请选择该轴。标准是确保您的投影点不会在一条线上。

于 2013-02-28T18:57:44.777 回答
0

我使用它已经很长时间了,所以我可能是错的,但我相信该命令convhull可以满足您的需要 - 它返回一组点的凸包(因为您说您的点是凸集,所以应该是点本身),按逆时针顺序排列。

请注意,MathWorks 最近提供了一个新类DelaunayTri,旨在取代convhull其他较旧的计算几何材料的功能。我相信它更准确,尤其是当点非常接近时。不过我没试过。

希望有帮助!

于 2013-02-27T11:01:33.993 回答