Val*_*rez 5 algorithm geometry voronoi computational-geometry
给定N边线图中的点，Map<Point, List<Edge>>可以得到这些边线形成的多边形O(N log N)？
我知道的是，您必须遍历所有顶点，并以包含该顶点的边为起点。这些是voronoi图的边缘，每个顶点最多包含3个艺术家。因此，在映射中，键是顶点，值是列表，其中顶点是起始节点。
例如：
要点：a,b,c,d,e,f,g
边缘：[a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]
我的想法是逆时针迭代地图，直到获得初始顶点。那是一个多边形，然后我将其放在多边形列表中，然后继续寻找其他多边形。问题是我不想克服复杂性O(N log N)
谢谢！
您可以循环遍历边缘并计算从边缘中点到所有站点的距离。然后按升序对距离进行排序，对于内部 voronoi 多边形，选择第一个和第二个。对于外部多边形，选择第一个。基本上，一条边将 2 个多边形分开/分开。
这是 O(m log n) 的事情。