给定一个坐标/点列表，找出其中独立多边形的数量。

2015-8-18 11:39:23
收藏：0
阅读：54
评论：2

给定由坐标(x, y)组成的多边形列表，是否有特定的算法可以用来查找这些点创建的“不相交多边形”的数量？

如果没有算法，最有效的计算这些分离多边形的方法是什么？

我尝试过使用SAT，但性能很差，因为我必须为每个单独的多边形创建它并针对每个其他多边形检查它是否碰撞。

为了说明我最终想要实现的内容，在下图中，您可以看到我想要计算/查找的多边形，有时由连接的正方形组成。

enter image description here

还要注意，我实际上是从正方形的中心的x，y坐标开始的，并基于半径计算角落点，因此我可以使用两种方法，但主要为SAT选择了角落点。

P.S. 我是用lua做这个的，但很乐意接受其他语言的代码示例/解决方案。

点赞
用户4964549
用户4964549

将每个多边形的所有边放入哈希表中，以边作为键（具体而言，键是连接边的两个角点，按顺序排序），多边形标识符作为值。在将边添加到哈希表时，只需检查是否已存在相同的边（相同的键）。这将让您找到重复/共享的边。

2015-08-18 06:04:25
用户107090
用户107090

以下论文描述了快速扫描线算法：

2015-08-18 12:09:37

作者:

用户506374

用户506374
推荐文章