排列多边形的点 [英] Sorting polygon's points

问题描述

我有一个凸多边形ABCDE ...（它可以有任意数量的点）。我需要对它的所有顶点进行排序，因此没有任何边会相交。

示例：

I have a convex polygon ABCDE... (it can have any number of points). I need to sort all its vertexes so none of the edges will intersect.
example:

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

ABCD顺序中的多边形具有相交的边。然而在ABDC订单中：

That polygon in ABCD order has intersecting edges. however in ABDC order:

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

没有边相交，因此ABDC是预期的输出。

None of the edges intersect so ABDC is the expected output.

我该怎么做？

How can I do this?

推荐答案

假设你的点都在凸你可以使用下面的代码：

Assuming your points are all on the convex hull of your polygon, you can use the following:

1. 用最小和最大X值选取两个极值点，（称它们为X _min 和X _max ）并在它们之间画线。在极端情况下，如果您有多个具有相同X值的点，请选择带有最大Y值的X _min 和最小Y值的X _max 。


2. 将点列表拆分为两个子列表，其中连接X _min 和X _max 的行之下的所有点都在一个列表中而那条线以上的所有线都在另一条线上。在第一个列表中包含X _min ，并在第二个列表中包含X _max 。 按照X值的升序对第一个列表进行排序。如果您有多个具有相同X值的点，请按升序Y值对其进行排序。这应该只发生在与X _max 具有相同X分量的点上，因为多边形是凸的。
   
3. 按照X值的降序对第二个列表进行排序。同样，在具有相同X值的多个点的情况下，对Y值进行降序排序（应该只对具有X分量X _min 的点进行排序。
）

4. 这两个列表在一起（哪一个并不重要）。

1. Pick the two extreme points with the min and max X value, (call them X_min and X_max) and draw the line between them. In the case where you have multiple points with the same X value at the extremes, pick X_min with the minimum Y value and X_max with the maximum Y value.
2. Split the list of points into two sub lists where all of the points below the line connecting X_min and X_max are in one list and all those above that line are in another. Include X_min in the first list and X_max in the second.
3. Sort the first list in ascending order of X value. If you have multiple points with the same X value, sort them in ascending Y value. This should only happen for points with the same X component as X_max since the polygon is convex.
4. Sort the second list in descending order of X value. Again, sort in descending Y value in the event of multiple points with the same X value (which should only happen for points with X component X_min.
5. Append the two lists together (it doesn't matter which is first).

这篇关于排列多边形的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！