r0f*_*0f1 1 algorithm computer-science
给定一组点(GPS坐标)和包含所有这些点的多边形,可以确定这些点覆盖该区域的程度,或者从多边形内的任何位置到最近点的最长距离是多少？
例如,如果我在纽约市区内有所有消防部门,我想知道消防车在最坏的情况下需要多长时间驾驶(在紧急情况下).
关于这个问题的名称是什么或者这个问题可以减少到什么的任何想法？或者是否有任何现有的算法？
谢谢 :)
首先构建一组站点的Voronoi图(GPS坐标).Voronoi图是表示平面划分为单元格的数据结构,每个站点一个单元格,这样每个站点的单元格包含距离该站点更近的所有点,而不是任何其他站点.
构建Voronoi图可以O(nlog(n))使用Fortune的扫描线算法来完成,其中n是输入站点的数量.
然后迭代Voronoi单元格.每个单元格都是多边形.对于每个单元格,计算单元格站点与每个多边形顶点之间的距离.站点和站点单元顶点之间的最长距离是为了到达站点而必须走的最长距离.
算法的运行时间是算法O(nlog(n))的第二阶段(迭代每个Voronoi单元的顶点)仅需要线性时间.这是因为整个图中的顶点总数随着站点的数量线性增长.也就是说,使用欧拉的平面图公式显示Voronoi顶点的总数是从上面限制的并不太难2n-5.
您可以在网上找到一些Fortune算法的开源实现.例如这一个.