排序多边形的点

Question

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

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

ABCD顺序的多边形具有交叉边.但是在ABDC订单中:

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

没有边相交,所以ABDC是预期的输出.

我怎样才能做到这一点？

Answer 1

选择多边形上的两个点.该线的中点将包含在该多边形内.让那一点成为M.

然后,根据基于M(沿X轴)的角度对点进行排序,根据距离M的距离打破简并性.按顺序迭代确保没有两条边相交.

Answer 2

假设您的点都在多边形的凸包上,您可以使用以下内容:

1. 选择具有最小和最大X值的两个极值点(称为X _min和X _max)并在它们之间绘制线.如果您在极值处有多个具有相同X值的点,请选择具有最小Y值的X _min和具有最大Y值的X _max.
2. 将点列表拆分为两个子列表,其中连接X _min和X _max的线下方的所有点都在一个列表中,而那一行上面的所有点都在另一个列表中.在第一个列表中包含X _min,在第二个列表中包含X _max.
3. 按X值的升序对第一个列表进行排序.如果您有多个具有相同X值的点,请按升序Y值对它们进行排序.这应该仅发生在具有与X _max相同的X分量的点上,因为多边形是凸的.
4. 按X值的降序对第二个列表进行排序.同样,在具有相同X值的多个点的情况下,以Y值下降排序(这应该仅发生在具有X分量X _min的点处.
5. 将两个列表附加在一起(哪个是第一个并不重要).