geometry - 从多边形中减去矩形

Question

我正在寻找一种算法，该算法将从一个简单的凹多边形中减去一个矩形并返回剩余的多边形。如果矩形包围了多边形，则余数为空。在大多数情况下，看起来矩形和多边形之间至少会共享一条边。

我一直在互联网上挖掘，但我没有找到一个好的线索。

有人可以指出我正确的方向吗？

Answer 1

这很容易：找到矩形和简单多边形的边缘之间的交点，并在那里切割线段。这不需要空间搜索结构，因为多边形的 4 条边是一个常数因子，因此在线性时间内运行。

然后计算所有段的约束 Delaunay 三角剖分，并使用种子点来增长区域。适当地组合区域（简单多边形内部的三角形减去矩形内部的三角形减去外部的三角形。剩下的三角形是你的结果，边界边缘是结果多边形的边缘。

编辑：如果答案太短，我很抱歉。下图显示了这个想法。
a）两个输入多边形
b）插入（切割）段后的 CDT
c）生长区域
d）绿色区域减去红色区域
e）d 区域的边界边缘。