给定边缘映射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)。