s*******k
发帖数: 227 | 1 平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
的圆里呢? 貌似应该用hash table,hash function怎么选呢? |
l********a
发帖数: 1154 | |
C***U
发帖数: 2406 | 3 这r是给定的么?还是p给定的?
还是都可以变化的?
【在 s*******k 的大作中提到】
: 平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
: 的圆里呢? 貌似应该用hash table,hash function怎么选呢?
|
s*******k
发帖数: 227 | 4 r 是固定的
【在 C***U 的大作中提到】
: 这r是给定的么?还是p给定的?
: 还是都可以变化的?
|
C***U
发帖数: 2406 | 5 那我觉得可以用图论来做
如果点P和点Q的距离小于r那么他们之间有edge 否则就没有
每个点对应一个vertex
然后用adjacency-list来表示这图
不过这样的最坏的搜索时间也是O(n)的
和二楼那个差不多
但是你还有别的操作没有?
纯属初学者的简单想法....呵呵
【在 s*******k 的大作中提到】
: r 是固定的
|
N*m
发帖数: 128 | 6 这不是个图论问题，是个计算几何问题。
如果这个算法是一次性的，就是说每次给一组新的数据然后计算的话，当然不可能有比
O(N)好的算法，因为你不可能在不扫描全部的点的情况下就知道哪些点符合要求。
如果不是一次性的，就是说给你N个点，不断地给出新的p让你查询，那么就有必要对N
个点进行预处理了。可以参考 http://www.cs.uu.nl/geobook/index.html 这里面的第五章，正交区域查询。不过需要的数据结构都比较复杂，不是很容易能弄对的。
【在 s*******k 的大作中提到】
: 平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
: 的圆里呢? 貌似应该用hash table,hash function怎么选呢?
|
s*******k
发帖数: 227 | 7 你这回答很专业. 不是一次性的,需要预处理,也就是需要把所有的点都当成p,来找出它
所有在r之内的点:
for (each point p, in N)
find all points within r distance from p
当然最naive的方法是搜索所有点,复杂度O(N^2).
N
【在 N*m 的大作中提到】
: 这不是个图论问题，是个计算几何问题。
: 如果这个算法是一次性的，就是说每次给一组新的数据然后计算的话，当然不可能有比
: O(N)好的算法，因为你不可能在不扫描全部的点的情况下就知道哪些点符合要求。
: 如果不是一次性的，就是说给你N个点，不断地给出新的p让你查询，那么就有必要对N
: 个点进行预处理了。可以参考 http://www.cs.uu.nl/geobook/index.html 这里面的第五章，正交区域查询。不过需要的数据结构都比较复杂，不是很容易能弄对的。
|
N*m
发帖数: 128 | 8 你先看一下我提到的那本书吧。不过就像我说的，做法比较繁琐。
http://ifile.it/m7yzbk/ebooksclub.org__Computational_Geometry__
中文版的pdf不知道靠不靠谱
http://ishare.iask.sina.com.cn/f/14124175.html
【在 s*******k 的大作中提到】
: 你这回答很专业. 不是一次性的,需要预处理,也就是需要把所有的点都当成p,来找出它
: 所有在r之内的点:
: for (each point p, in N)
: find all points within r distance from p
: 当然最naive的方法是搜索所有点,复杂度O(N^2).
:
: N
|
z******d
发帖数: 302 | 9 如果仅仅只是个算法的话，那么应该可以使用图认论知识来帮忙：
以 邻接表 的形式存储平面上所有N个点：
其中每个节点都存有：1）该点的平面坐标；2）该点的权值为该点与前一点的距离。
计算的时候，直接查找邻接表中P点的链表中所有的节点，只要其权值小于等于R，则存
入到一个新链表中（如果是非完全图的话，还得计算权值总和小于等于R的节点）。最
后输出该新链表。如果该平面上所有N个点之间是两两相通的话（完全图），可以不必
计算权值总和。
空间复杂度是：[符号打不出来：P]（N^2），时间复杂度是：O（N）
如果是想实际编程计算的话，可以使用一些插件。如果是使用C/C++/C#/JSP等的话，可
以使用SharpMap插件，其中就有空间分析函数。 |
z******d
发帖数: 302 | 10 如果使用邻接矩阵的话，在完全图的情况下，只使用上三角或者是下三角，可以减少时
间与空间杂度。呵呵。 |
C***U
发帖数: 2406 | 11 我之前的想法和你的优点类似哎
可惜楼上说这个方法不好
【在 z******d 的大作中提到】
: 如果使用邻接矩阵的话，在完全图的情况下，只使用上三角或者是下三角，可以减少时
: 间与空间杂度。呵呵。
|
N*m
发帖数: 128 | 12 不是说不好，是说你们的做法没有充分利用平面图的特点。
比如说有三个点ABC，A离B很近，B离C很近，那么A必然也离C很近。而如果A离B很近，B
离C很远，那么A必然也离C很远。
所以一个合理的想法是建立一个相对复杂的数据结构，尽量保证离得近的点都保存在一
起。如果直接对每对点建一条边然后来一对一对地处理，那实际上就浪费了平面图所给
出的额外信息。
【在 C***U 的大作中提到】
: 我之前的想法和你的优点类似哎
: 可惜楼上说这个方法不好
|
b***e
发帖数: 1419 | 13 我以前做过一个naive的画格子的方法：
在平面上画相同大小的方格子，给定一个点，只在临近的格子里找。这样可以用格子的
坐标来index.
更近一步，可以画更小的格子来细化。我当时是画了九种不同的格子，最大格和最小格
的边长差1000倍。给定点p和半径r，先在最大格里找临近点。不能确定在找小格子。最
终在最小格不能确定就算严格的距离。
【在 s*******k 的大作中提到】
: 平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
: 的圆里呢? 貌似应该用hash table,hash function怎么选呢?
|
