从多边形中减去矩形

Question

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

我一直在浏览互联网，但是找不到很好的线索。

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

Answer 1

这很容易：找到矩形和简单多边形的边缘之间的交点，然后在其中切线。这不需要空间搜索结构，因为多边形的4个边是一个常数因子，因此可以线性运行。

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

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