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怎么选呢?
|