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 回答