给定边缘映射N中的Map<Point, List<Edge>>点,是否有可能在O(N log N)中获得由这些边缘形成的多边形?

我知道的是,您必须遍历所有顶点,并以包含该顶点的边为起点。这些是voronoi图的边缘,每个顶点最多包含3个艺术家。因此,在 map 中,键是一个顶点,值是一个列表,其中顶点是起始节点。

例如:

:a,b,c,d,e,f,g
:[a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]
我的想法是逆时针迭代 map ,直到获得初始顶点。那是一个多边形,然后我将其放在多边形列表中,然后继续寻找其他多边形。问题是我不想克服O(N log N)的复杂性

谢谢!

最佳答案

您可以遍历边缘并计算从边缘的中点到所有站点的距离。然后按升序对距离进行排序,对于内部voronoi多边形,选择第一个和第二个。对于外部多边形,请选择第一个。基本上是一个边缘分开/划分2个多边形。

这是O(m log n)。

10-05 22:58
查看更多