通过一组多边形对平面进行非重叠区域的划分。

Question

请参见示例图像：

有一组在平面上的多边形（凸多边形、非凸多边形，但不是自相交多边形）。多边形由顶点-点（x和y坐标，笛卡尔坐标系）定义。

示例多边形集合：

- 第一个多边形是A，B，C。 - 第二个多边形是D，E，F，G，H，I，J。 - 第三个多边形是K，L，M，N。 - 第四个多边形是O，P，Q。

多边形将平面分成区域。一些多边形的部分可能重叠（如第一个多边形和第二个多边形、第二个多边形和第三个多边形），这些重叠部分也是单独的区域。有些多边形可能在其他多边形内部（如第二个多边形内部的第四个多边形）。

划分后的示例区域：蓝色、粉色、绿色、橙色、棕色和紫色。

我想象简单起见，平面是一个带有恒定x，y坐标的矩形。

目标：

通过查询点检测所在的区域。

我正在寻找具有这些假设的平面划分算法和数据结构。

- Peter K.

---

你的确切问题是什么？你不能先通过检查哪些多边形重叠来构建所有区域，然后对所有区域执行命中测试吗？ - Daniel Brückner

不清楚你是否想要计算区域，还是只想计算查询点所在的区域。这是两个非常不同的问题。前者将需要一个交集算法和一个包含测试，而后者仅需要一个“点在多边形内”的算法。 - gg349

请查看DCEL数据结构。 - Timothy Shields

Answer 1

首先，通过迭代寻找成对的交点并用它们的交集和原始多边形减去交集来将多边形集转换为一组不重叠的多边形。如果您首先将每个多边形分割成一组凸多边形（这些凸多边形可以简单地继承原始凹多边形的“颜色”），那么这可能会更容易和更快速。

然后，您可以将多边形放入四叉树或类似的数据结构中，该数据结构允许您快速选择候选多边形以进行给定查询点的成员资格测试。

您需要定义共享于多个多边形之间的边缘上发生了什么。

- Florian Brucker

Answer 2

我可以推荐使用梯形分解算法http://en.wikipedia.org/wiki/Point_location#Trapezoidal_decomposition来实现平面细分中高效的点查询。

在您的情况下，由于细分是间接定义的，因此需要额外一步。 您可以尝试以下三种方法：

1）使用通用多边形相交算法，并逐步调用它，

2）形成多边形的梯形分解，并对这些梯形图进行融合，

3）修改现有的梯形分解算法，使其接受由重叠多边形组成的细分作为输入。

您需要使用某些2D计算几何库... 还需要勇气。

替代方案：

如果您的精度要求不是太高，则可以使用位图填充每个多边形，在遇到已经填充的像素时更改颜色。

- user1196549