检查所有线段指定距离内的所有点
检查所有线段指定距离内的所有点
提问于 2012-09-18 18:49:45
给定一组点P和一组线段S，有没有一种方法可以有效地找到任何线段指定距离d内的所有点？没有蛮力比较的O(|P||S|)阶
本特利-奥特曼搜索一组线段之间的所有交点在O(n log n)中运行，由于这个问题有类似的特点，我想知道是否可能有类似的性能。
C++中允许的开源实现的加分。
回答 1
Stack Overflow用户
发布于 2012-09-20 15:44:52
在点上构建Voronoi diagram网络。让每个单元格保持指向其所有邻居的指针。一切皆有可能。
- 给定一个点，找出它所在的单元格。很简单，从网络的左下角到该点绘制一条线，然后从该角单元格开始，接近该点，从而找到它所在的单元格。
- 给出一条线，找到它所跨越的所有单元格。微不足道。
- 给定一条线和一个偏移距离，找到走廊内的所有单元格。来自2.
- etc.
Voronoi网络作为空间导航和查询的支持结构。所有的操作都是局部的，所以线性复杂度。在构建关系图之后。:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12475504
复制相关文章
相似问题
腾讯云开发者
