来自无序点的简单多边形

Question

我一直在尝试创建一种算法来查找简单多边形中的点的顺序。目的是当2D平面上的给定点(总是有可能形成简单多边形btw(时，我输出有效简单多边形中的点的顺序。所有点都必须是所述多边形的一部分。

我在一定程度上做到了这一点，但在某些测试用例中失败了。我这样做的方法是找到几何中心

int centerX = (lowX + highX) / 2;
int centerY = (lowY + highY) / 2;
Point center = new Point(centerX, centerY, -1);

然后按极角对所有点进行排序。

Collections.sort(points, (a, b) -> {
if(a == b || a.equals(b)) {
return 0;
}
double aTheta = Math.atan2((long)a.y - center.y, (long)a.x - center.x);
double bTheta = Math.atan2((long)b.y - center.y, (long)b.x - center.x);
if(aTheta < bTheta) {
return -1;
}
else if(aTheta > bTheta) {
return 1;
}
else {
double aDist = Math.sqrt((((long)center.x - a.x) * ((long)center.x - a.x)) +
(((long)center.y - a.y) * ((long)center.y - a.y)));
double bDist = Math.sqrt((((long)center.x - b.x) * ((long)center.x - b.x)) +
(((long)center.y - b.y) * ((long)center.y - b.y)));
if (aDist < bDist) {
return -1;
} 
else {
return 1;
}
}    
});

我正在努力找出是什么让一些测试用例中断。非常感谢任何帮助或建议！还想知道是否有任何有效但不过于复杂的算法可以执行这一操作。

更新

我发现了一个失败的测试案例：当给(101, 101), (100, 100), (105, 100), (103, 100), (107, 100), (102, 100), (109, 100)分别标记为0到9时，

我的程序输出2 4 6 0 3 5 1，但它不是有效的简单多边形

它应该是1 0 6 4 2 3 5的一个置换

Answer 1

以下是Reblochon Masque已经提供的不错答案的Java实现。

请注意，我们不使用任何三角函数来计算角度，而是使用从最小点到被比较的两个点的相对方向(或转弯方向(的比较。就我个人而言，我觉得这比使用角度更优雅，但其他人可能不同意。然而，与基于double的任何计算一样，orient2D方法容易受到舍入误差的影响。

此外，当存在基于方向的平局时，因为最小点和两个点共线，我们通过考虑两个点的相对顺序来打破平局。这意味着我们将按顺序访问点，没有"切换"，我认为这是更可取的。

static List<Point2D> simplePolygon(Collection<Point2D> points)
{       
final Point2D min = minPoint2D(points);
List<Point2D> simple = new ArrayList<>(points);
Collections.sort(simple, (p1, p2) ->
{
int cmp = orient2D(min, p2, p1); 
if(cmp == 0) 
cmp = order2D(p1, p2);
return cmp;
});
return simple;
}
// return lowest, leftmost point
static Point2D minPoint2D(Collection<Point2D> points)
{
Point2D min = null;
for(Point2D p : points)
if(min == null || order2D(p, min) < 0) min = p;
return min;
}
// order points by increasing y, break ties by increasing x
static int order2D(Point2D p1, Point2D p2)
{
if(p1.getY() < p2.getY()) return -1;
else if(p1.getY() > p2.getY()) return 1;
else if(p1.getX() < p2.getX()) return -1;
else if(p1.getX() > p2.getX()) return 1;
else return 0;
}
// Does p involve a CCW(+1), CW(-1) or No(0) turn from the line p1-p2
static int orient2D(Point2D p1, Point2D p2, Point2D p)
{
double dx = p2.getX() - p1.getX();
double dy = p2.getY() - p1.getY();      
double px = p.getX() - p1.getX();
double py = p.getY() - p1.getY();       
double dot = py * dx - px * dy;     
return dot < 0 ? -1 : dot > 0 ? 1 : 0;
}

测试：

int[] a = {101, 101, 100, 100, 105, 100, 103, 100, 107, 100, 102, 100, 109, 100};
List<Point2D> points = new ArrayList<>();
for(int i=0; i<a.length; i+=2) 
points.add(new Point2D.Double(a[i], a[i+1]));
List<Point2D> simple = simplePolygon(points);       
for(Point2D p : simple) System.out.println(p);

输出：

Point2D.Double[100.0, 100.0]
Point2D.Double[102.0, 100.0]
Point2D.Double[103.0, 100.0]
Point2D.Double[105.0, 100.0]
Point2D.Double[107.0, 100.0]
Point2D.Double[109.0, 100.0]
Point2D.Double[101.0, 101.0]

我认为这是正确的。

Answer 2

这里有一个易于实现的O(n logn)算法，它保证生成一个简单的多边形(没有边缘交叉(

1-找到最南边的点(如果你与y值持平，则找到最西边的点(。

2-根据最南端点和水平线之间的角度对所有点进行排序。

3-有序序列是一个简单的多边形。

在某些罕见的情况下，如果某些点以相同的角度共线，则这些点可能不会形成顶点，而是包含在边中。