来自无序点的简单多边形

Question

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

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

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

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

1- 找到最南端的点（如果与 y 值相同，则找到最西端的点）。

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

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

在极少数情况下，如果某些点以相同角度共线，则它们可能不构成顶点，但包含在边中。

Answer 2

这是 Java 已经由 Reblochon Masque 提供的实现。

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

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

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]

我认为是正确的。

来自无序点的简单多边形

Simple polygon from unordered points

java

algorithm

geometry

polygon