给定一个形成多边形的坐标列表_147188_是否有一个特定的算法可用于查找这些点创建的单独多边形的数量？1447189_？
如果没有算法，那么计算这些单独多边形的最有效方法是什么？
我尝试过使用SAT但性能很差，因为我必须创建每个单独的多边形并检查它是否与其他所有多边形相撞 .
为了说明我想要最终实现的目标，在下图中您可以看到我想要计算/找到的多边形在某些情况下由连接方块组成 .
另请注意，我实际上以方块中心的 x, y 坐标开始，并根据半径计算角点，因此我可以访问这两种方法，但主要选择SAT的角点 .
P.S. 我在lua中这样做，但很乐意接受其他语言的代码示例/解决方案 .
2 回答
将每个多边形的所有边放在一个哈希表中，并将边作为键（具体来说，键将是边连接的两个角点，按排序顺序），多边形标识符作为值 . 将边添加到哈希表时，只需检查是否已存在相同的边（相同的键） . 这样可以找到重复/共享边缘 .
这些论文描述了快速扫描线算法：
今井弘，浅野孝雄，
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane，
Journal of Algorithms 4（1983）310-323
H. Edelsbrunner，J . 诉Leeuwen，Th . 奥特曼和D.伍德，
Computing the connected components of simple rectilinear geometrical objects in d-space，
RAIRO通知 . 理论值 . 18（1984）171-183 .