2

给定一组点 P 和一组线段 S，有没有办法有效地找到任何线段指定距离 d 内的所有点？没有蛮力比较顺序O(|P||S|)？

Bentley-Ottman 搜索一组线段之间的所有交点在 中运行O(n log n)，并且由于这个问题具有相似的味道，我想知道是否有可能实现相似的性能。

在 C++ 中允许的开源实现的奖励积分。

4

1 回答 1

0

在这些点上构建一个Voronoi 图网络。让每个单元保持指向其所有邻居的指针。比一切皆有可能。

  1. 给定一个点，找到它所在的单元格。简单，从网络的左下角画一条线到该点，然后从那个角单元格开始，接近该点，从而找到它所在的单元格。

  2. 给定一条线，找到它穿过的所有单元格。琐碎的。

  3. 给定一条线和一个偏移距离，找到走廊内的所有单元。从 2 开始。

  4. 等等

Voronoi 网络用作空间导航和查询的支持结构。所有的操作都是局部的，所以线性复杂。图建好后。:)

于 2012-09-20T07:44:52.003 回答