圆分离距离 - 最近邻问题
我在二维平面上有一组给定位置和半径的圆。我想确定每个圆圈是否与任何其他圆相交,以及将两者分开所需的距离。在我目前的实现中,我只是通过所有可能的圆组合然后进行计算。不幸的是,这个算法是O(n ^ 2),这很慢。
圆圈通常会成组聚集,并且它们具有相似(但不同)的半径。圆圈的近似最大值约为200.算法不必精确,但应该接近。
这是我目前在JavaScript中的一个(慢)实现:
// Makes a new circle
var circle = function(x,y,radius) {
return {
x:x,
y:y,
radius:radius
};
};
// These points are not representative of the true data set. I just made them up.
var points = [
circle(3,3,2),
circle(7,5,4),
circle(16,6,4),
circle(17,12,3),
circle(26,20,1)
];
var k = 0,
len = points.length;
for (var i = 0; i < len; i++) {
for (var j = k; j < len; j++) {
if (i !== j) {
var c1 = points[i],
c2 = points[j],
radiiSum = c1.radius+c2.radius,
deltaX = Math.abs(c1.x-c2.x);
if (deltaX < radiiSum) {
var deltaY = Math.abs(c1.y-c2.y);
if (deltaY < radiiSum) {
var distance = Math.sqrt(deltaX*deltaX+deltaY*deltaY);
if (distance < radiiSum) {
var separation = radiiSum - distance;
console.log(c1,c2,separation);
}
}
}
}
}
k++;
}
另外,如果您用简单的英语解释一个好的算法(KD树?),我将不胜感激: - /
没有找到相关结果
已邀请:
2 个回复
剿畦缄饥小
届甸衬丝蚕
如果圆圈重叠,则这是负数量。对于这个讨论,我将假设一个八叉树,但k = 3的kd树是相似的。 在每个圆圈的八叉树中存储三元组(x,y,r)。 要查找目标圆T的最近邻居,请使用标准算法:
这里
是对到目前为止找到的T的最近圆的参考。最初它是空的。 稍微棘手的部分是确定
。为此,考虑C中的唯一点(x,y,r)就足够了,该点是欧几里德在x和y中最接近T并且具有包含在长方体中的r范围的最大值。换句话说,长方体表示一组圆,其中心在x和y的矩形区域上并且具有半径范围。您要检查的点是表示中心最接近T且半径最大的圆的点。 注意,T的半径根本不参与算法。你只是想知道T的中心在任何其他圆圈内的距离。 (我希望这一开始就像现在看起来一样明显......)