算法来计算剩余多边形减法后 [英] Algorithm to Compute the Remaining Polygon After Subtraction

问题描述

我有一个大的多边形（帕）。内面有很多的小洞，如图所示：

I have a big polygon (Pa). Inside the polygon there are a lot of small "holes", as shown:

下面是一些条件孔：

1. 的孔不能相互重叠
2. 的孔不能去外多边形外
3. 不过，孔的可以的接触外多边形边缘

1. The holes cannot overlap one another
2. The holes cannot go outside the outer polygon
3. However, the holes can touch the outer polygon edge

如何获取剩余的多边形（或多边形列表）以有效的方式？最简单的方法（蛮力的方式）是采取帕，并通过减去孔渐渐计算剩余的多边形。虽然这个想法是可行的，但我怀疑，有一个更有效的算法。

How to obtain the remaining polygon ( or the polygon list) in an efficient manner? The easiest way ( brute force way) is to take the Pa, and gradually computing the remaining polygon by subtracting out the holes. Although this idea is feasible, but I suspect that there is a more efficient algorithm.

编辑：我不要求有关如何执行多边形裁剪（或减）算法！其实这件事情我会用蛮力去做。我问，除了多边形裁剪方法（作为主要的多边形，然后逐渐夹孔出来），有没有其他更有效的方法？

推荐答案

这是很难做到的一般方式。你可以找到源头code这里的解决方案：

This is very hard to do in a general manner. You can find source code for a solution here:

一般多边形帆船（GPC）

这篇关于算法来计算剩余多边形减法后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！