从多边形中减去矩形

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

我一直在挖掘互联网，但我还没有找到一个好的主角。

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

2012-11-02 Josh C.

我试图在[张贴在MathOverflow同样的问题（http://mathoverflow.net/questions/111296/subtract-rectangle-from-polygon/111323#111323）来回答。 –

这很简单：找到矩形和简单多边形的边界之间的交集并在那里剪切这些分段。这不需要空间搜索结构，因为多边形的四条边是一个常数因子，因此可以在线性时间内运行。

然后计算所有分段的约束Delaunay三角剖分并使用种子点来生长区域。合适地组合区域（简单多边形内的三角形减去矩形内的三角形减去外部的三角形，剩下的三角形是你的结果，边界边缘是结果多边形的边缘。如果答案是太短了。下图显示了这个想法。
一）这两个输入多边形
b）在CDT的（板缺）链段的插入
c）在生长区域
d）绿色区域之后减去红色区域
e）d区域的边界边缘。

enter image description here

来源

2012-11-04 02:30:20 leftangle

不是批评你的答案，但我发现这些解释可以通过一支铅笔和一张纸进行得更好...... – num3ric

由于矩形的至少一条边与我的多边形共线。我应该先合并这些边缘吗？而且由于我使用的是面向对象编程，我应该将点结构加强到跟踪边的顶点类中吗？另外，我对计算几何知之甚少。你能提出德劳内如何提供帮助的图表吗？ –

我已添加图片。如果合并重复边缘是必要的，取决于您使用的库。 – leftangle

从多边形中减去矩形

回答

相关问题