给定一组点(GPS 坐标)和一个包含所有这些点的多边形,是否可以确定这些点覆盖该区域的程度或从多边形内的任何位置到最近点的最长距离是多少?
例如,如果我在纽约市边界内设有所有消防部门,我想知道在最坏的情况下消防车必须行驶多长时间(以防出现紧急情况)。
关于这个问题的名称或这个问题可以简化成什么的任何想法?或者是否有任何现有的算法?
谢谢你:)
最佳答案
首先构造Voronoi diagram站点集(GPS 坐标)。 Voronoi 图是一种数据结构,表示将平面划分为单元格,每个站点一个单元格,这样每个站点的单元格都由离该站点比离任何其他站点更近的所有点组成。
可以使用 Fortune's sweep-line algorithm 在 O(nlog(n))
中构建 Voronoi 图其中 n
是输入站点的数量。
然后遍历 Voronoi 单元。每个单元格都是一个多边形。对于每个单元格,计算单元格站点与多边形每个顶点之间的距离。站点与站点单元顶点之间的最长距离是为了到达该站点必须步行的最长距离。
该算法的运行时间为 O(nlog(n))
,因为该算法的第二阶段(遍历每个 Voronoi 单元的顶点)仅需要线性时间。这是因为整个图中的顶点总数随着站点的数量线性增长。即,使用 Euler's formula for planar graphs 显示并不难Voronoi 顶点的总数受 2n-5
限制。
您可以在网上找到一些 Fortune 算法的开源实现。 This one例如。
关于algorithm - 消防部门覆盖区域,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38904616/