一尘不染

排序多边形的点

algorithm

我有一个凸多边形ABCDE …(可以有任意数量的点)。我需要对所有顶点进行排序,以便所有边缘都不会相交。
例:

A _____ B
  \   /
   \ /
    X
   / \
  /___\
C       D

该ABCD顺序中的多边形具有相交的边。但是按ABDC顺序:

A _____ B
  |   |
  |   |
  |   |
  |   |
  |___|
C       D

边缘均不相交,因此ABDC是预期的输出。

我怎样才能做到这一点?


阅读 340

收藏
2020-07-28

共1个答案

一尘不染

假设所有点都在多边形的凸包上,则可以使用以下命令:

  1. 用最小和最大X值选择两个极限点(分别称为X min和X max),并在它们之间画线。如果您有多个极端具有相同X值的点,请选择Y 最小值为X的X min和Y最大值为X max的。
  2. 将点列表分成两个子列表,其中连接X min和X max的线下方的所有点都在一个列表中,而该线上方的所有点都在另一个列表中。在第一个列表中包含X min,在第二个列表中包含X max。
  3. 以X值的升序对第一个列表进行排序。如果您有多个具有相同X值的点,请按升序对它们进行排序。因为多边形是凸的,所以这仅应发生在与X max具有相同X分量的点上。
  4. 以X值的降序对第二个列表进行排序。再次,在具有相同X值的多个点的情况下,对Y值递减排序(这仅适用于X分量为X min的点。
  5. 将两个列表附加在一起(无论哪一个都重要)。
2020-07-28