java - 查找和丢弃多边形之间的共享边

Question

我有一个可能共享边的凸多边形数组（每个多边形由其顶点数组表示）。当其中一些多边形共享边时，我想从唯一的边创建一个新的多边形，而不考虑共享边。输出应该是具有唯一边的（合并的）多边形数组。我可以找到的最接近的算法可以计算出凸包，它与我要达到的目标相近，但并不完全相同。

Answer 1

无法计算具有共享边的多边形的凸包，因为根据定义，结果是凸多边形。在您的情况下，合并具有共享边的多个凸多边形的结果可能不再是凸的。

我将提出以下方法（这并非微不足道，我不知道是否可以通过更简单的方式来完成）：


将多边形的表示形式更改为顶点索引数组（这可以简化后面的步骤）

遍历所有多边形并将其所有顶点附加到大量顶点上。迭代多边形的顶点并将其附加到大数组上时，生成一个小数组，该数组对应的顶点索引（新的多边形表示形式）。现在，多边形是指顶点索引的数组，该顶点索引是指由所有多边形使用的大型顶点数组。
识别共享顶点

维护从顶点索引到计数器的映射（顶点索引是在1中创建的大量顶点中的顶点索引）。这将跟踪一个顶点属于多少个多边形，并允许标识共享的顶点。

遍历所有多边形及其顶点索引，对于您拥有的每个顶点索引，将其插入此地图中，或者如果计数器已在地图中，则将其增加。
识别共享边（并跟踪它们所属的多边形）

维护从（i，j）（i

约束i 计数器计算一条边所属的多边形的数量。问题出在2D中，我认为数据是干净的（多边形彼此不重叠），因此此计数器的值应为1或2。
多边形索引1和多边形索引2指的是边在多边形数组中可能属于的多边形的索引（这些索引可以初始化为-1）。


遍历所有多边形及其边缘（在顶点索引列表上迭代，而不会忘记闭合循环的最终边缘）。对于i 生成新的多边形数组

遍历初始数组中的所有多边形。对于每个多边形，可能会生成一个新的多边形：


在不共享的多边形中找到一个顶点索引（使用2中的贴图）。如果没有这样的顶点索引，则丢弃多边形并移至下一个未丢弃的多边形。
输出（非共享的）顶点索引。从此顶点索引开始，遍历多边形的所有边缘：


如果未共享边，则输出目标顶点索引并移至下一条边。
如果共享边缘，则需要找出共享该多边形的多边形（以继续迭代新多边形的边缘）。使用3中的边缘贴图进行操作。找到另一个多边形的边缘，并继续迭代另一个多边形的边缘（在与共享边缘相反的方向上）。


在新多边形的边缘上进行的此迭代最终应循环回到起始（非共享）顶点索引，这意味着新多边形已关闭并且可以附加到新的多边形数组中。


在迭代不同多边形的边缘以生成最终的合并多边形时，应跟踪所遍历的多边形，以便可以将其丢弃在外循环中。
将新多边形的表示形式转换回顶点数组（如果需要）

只需迭代新的多边形及其顶点索引数组即可。从1中创建的顶点数组中提取相应的顶点，并将其附加到此多边形的新顶点数组中。