w****j
发帖数: 237 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: winglj (coolking), 信区: Programming
标 题: 请教个简单的几何算法问题
发信站: BBS 未名空间站 (Tue Jan 31 02:45:09 2012, 美东)
如果有一组二维坐标点（x1,y1),(x2,y2)....(xn,yn),如何找出距离小于d的子集。例
如，找出(xi-xj)^2+(yi-yj)^2<=d^2的子集。
我是这样想的，把坐标点放入二维矩阵(n x 2),用双循环，i=1:n, j=1:n, 一个个比对
，把符合条件的i和j点放入一个(m x 4)的矩阵。但是这样是有重复的吧，另外也不能
剔除自身的情况(i=j)？
抱歉不是cs的，术语可能不对，如果可以用excel实现更好。先谢了。 | z*****n
发帖数: 7639 | 2 suppose there are N points denoted as (1,...,N)
for i=1:N-1
for j=i+1:N
if(distance(i,j)<=d)
put link(i,j) in the set;
endif
endfor
endfor
【在 w****j 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: winglj (coolking), 信区: Programming
: 标 题: 请教个简单的几何算法问题
: 发信站: BBS 未名空间站 (Tue Jan 31 02:45:09 2012, 美东)
: 如果有一组二维坐标点（x1,y1),(x2,y2)....(xn,yn),如何找出距离小于d的子集。例
: 如，找出(xi-xj)^2+(yi-yj)^2<=d^2的子集。
: 我是这样想的，把坐标点放入二维矩阵(n x 2),用双循环，i=1:n, j=1:n, 一个个比对
: ，把符合条件的i和j点放入一个(m x 4)的矩阵。但是这样是有重复的吧，另外也不能
: 剔除自身的情况(i=j)？
: 抱歉不是cs的，术语可能不对，如果可以用excel实现更好。先谢了。
| l********a
发帖数: 1154 | 3 如果只是为了完成任务,用matlab吧
代码==
============================
disp('点个数:');
N = 4
disp('随机生成的N个点(每行是一个(x,y):');
ptMat = randi(100,[N,2])
disp('距离矩阵:');
distMat = squareform(pdist(ptMat))
disp('距离阀值(为了演示,选了距离的均值):');
threshold = mean2(distMat)
disp('得到上三角(下三角也行),去除重复:');
distMat = triu(distMat)
disp('找到距离小于threshold的点对(去除重复):');
idxMat = triu(distMat
disp('找到距离小于threshold的点对序号(每行表示一对):');
[row,col] = find(idxMat);
[row,col]
=========================
运行结果:
=============================
点个数:
N =
4
随机生成的N个点:
ptMat =
38 96
20 93
49 6
34 74
距离矩阵:
distMat =
0 18.2483 90.6697 22.3607
18.2483 0 91.7061 23.6008
90.6697 91.7061 0 69.6348
22.3607 23.6008 69.6348 0
距离阀值(为了演示,选了距离的均值):
threshold =
39.5275
得到上三角(下三角也行),去除重复:
distMat =
0 18.2483 90.6697 22.3607
0 0 91.7061 23.6008
0 0 0 69.6348
0 0 0 0
找到距离小于threshold的点对(去除重复):
idxMat =
0 1 0 1
0 0 0 1
0 0 0 0
0 0 0 0
找到距离小于threshold的点对序号(每行表示一对):
ans =
1 2
1 4
2 4
============================ | w****j
发帖数: 237 | 4 呵呵，这么快就有答案，谢谢。再问问有没有excel的function可以实现？ | i**h
发帖数: 424 | 5
If complexity is not a problem, this is the easiest solution which takes O(n^2) time.
The problem itself is actually a classic computational geometry problem. The best solution for this problem is O(n+k) (k is the number of pairs in the result set). Google "Fixed-Radius Near Neighbors".
【在 z*****n 的大作中提到】
: suppose there are N points denoted as (1,...,N)
: for i=1:N-1
: for j=i+1:N
: if(distance(i,j)<=d)
: put link(i,j) in the set;
: endif
: endfor
: endfor
|
|
