由一组多边形将平面细分为不重叠的区域
Pet*_* K. 5 algorithm computational-geometry
请参阅示例图片：
\n\n
平面上有一组多边形（凸多边形、非凸多边形，但不自相交）。多边形由顶点 \xe2\x80\x93 点（x和y坐标，笛卡尔坐标系）定义。
\n\n多边形示例集：
\n\n- \n
- 第一个多边形是 A、B、C。 \n
- 第二个多边形是 D、E、F、G、H、I、J。 \n
- 第三个多边形是 K、L、M、N。 \n
- 第四个多边形是 O、P、Q。 \n
多边形将平面划分为多个区域。多边形的某些部分可能是重叠的（例如第一和第二多边形、第二多边形和第三多边形）。这些重叠部分也是单独的区域。一些多边形可能在内部其他多边形内部（例如第四个多边形位于第二个多边形内部）。
\n\n细分后的示例区域：蓝色、粉色、绿色、橙色、棕色和紫色。
\n\n为简单起见，我想象该平面是一个具有常数x , y的矩形坐标的矩形。
\n\n目标
\n\n检测查询点所在的区域（蓝色、粉色、绿色等）。
\n\n我正在寻找具有这些假设的平面细分的算法和数据结构。
\n首先，通过迭代查找成对交点并将这对相交多边形替换为其交点以及原始多边形减去交点，将多边形集转换为一组不重叠的多边形。如果您首先将每个多边形分割成一组凸多边形（凸多边形可以简单地“继承”原始凹多边形的“颜色”），这可能会更容易和更快。
然后，您可以将多边形放入四叉树或类似的数据结构中，这样您就可以快速选择候选多边形以用于给定查询点的成员资格测试。
您需要定义多个多边形之间共享的边上发生的情况。