algorithm - 将两个重叠的矩形合并到生成的多边形中

Question

我正在寻找一种算法，给定两个部分或完全重叠的矩形，找到顶点的有序列表，该列表定义表示两个矩形之和的多边形。

更具体地说:

• 我有两个有序的点列表作为输入，代表两个矩形
• 我知道如何找到生成的多边形的顶点，该多边形由位于另一个矩形外部的每个矩形的顶点加上一个矩形的每条边与另一个矩形的每条边之间的交点组成
• 我目前不知道如何将如上所述获得的点排序到数组中，以便数组的元素 j 和 j+1 代表同一边的两个顶点(这就是我的意思顶点的有序列表)。

在此先感谢您的帮助

更新: 我找到了一种对顶点进行排序以获得多边形的方法，如下所示:

• 计算顶点质心(坐标平均值)
• 根据质心的线段与顶点之间形成的角度以及通过质心的任何引用线(例如 X 轴)对顶点进行排序。

但是，尽管我始终获得一个包围两个矩形的多边形，没有孔或相交的边，但它并不总是我想要的多边形(有时它包括不属于输入矩形之一的额外区域)。

所以我要回到其中一条评论中指出的解决方案，这里也有描述:

polygon union without holes

Answer 1

一旦你有了 4 个顶点，你只需使用距离公式找到更远的点(因为我们似乎无法假设共线或未旋转的起始矩形)

所以如果你有点 a = (xA, yA), b, c, d 并且你知道这 4 个点构成一个矩形

float dist(Point a, Point b){
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    return Math.sqrt(dx * dx + dy * dy);
}


//somewhere else, where u need it
//put point A into index 0
Point curFarthest = b;
float distance = dist(a, b);
if (dist(a, c) > distance){
    curFarther = c;
    distance = dist(a, c);
} else if (dist(a, d) > distance){
    curFarther = d;
    curFarthest = dist(a, d);
}

//store curFarthest into index 2
// store the rest (exculding points a and curFarthest)
// into index 1 and 3 in no particular order