我在二维平面上有一组具有给定位置和半径的圆。我想确定每个圆是否与任何其他圆相交以及将两者分开所需的距离。在我目前的实现中,我只是遍历所有可能的圆圈组合,然后进行计算。不幸的是,这个算法是 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 树?),我将不胜感激:-/
最佳答案
对于初学者来说,如果您跳过 SQRT 调用,您上面的算法将大大加快。这是用于比较距离的最著名的简单优化。您还可以预先计算“平方半径”距离,这样您就不会多余地重新计算它。
此外,您的某些算法中似乎还有许多其他小错误。以下是我对如何修复它的看法。
此外,如果您想摆脱 O(N-Squared) 算法,您可以考虑使用 kd-tree .构建 KD 树需要前期成本,但可以更快地搜索最近的邻居。
function Distance_Squared(c1, c2) {
var deltaX = (c1.x - c2.x);
var deltaY = (c1.y - c2.y);
return (deltaX * deltaX + deltaY * deltaY);
}
// returns false if it's possible that the circles intersect. Returns true if the bounding box test proves there is no chance for intersection
function TrivialRejectIntersection(c1, c2) {
return ((c1.left >= c2.right) || (c2.right <= c1.left) || (c1.top >= c2.bottom) || (c2.bottom <= c1.top));
}
var circle = function(x,y,radius) {
return {
x:x,
y:y,
radius:radius,
// some helper properties
radius_squared : (radius*radius), // precompute the "squared distance"
left : (x-radius),
right: (x+radius),
top : (y - radius),
bottom : (y+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;
var len = points.length;
var c1, c2;
var distance_squared;
var deltaX, deltaY;
var min_distance;
var seperation;
for (var i = 0; i < len; i++) {
for (var j = (i+1); j < len; j++) {
c1 = points[i];
c2 = points[j];
// try for trivial rejections first. Jury is still out if this will help
if (TrivialRejectIntesection(c1, c2)) {
continue;
}
//distance_squared is the actual distance between c1 and c2 'squared'
distance_squared = Distance_Squared(c1, c2);
// min_distance_squared is how much "squared distance" is required for these two circles to not intersect
min_distance_squared = (c1.radius_squared + c2.radius_squared + (c1.radius*c2.radius*2)); // D**2 == deltaX*deltaX + deltaY*deltaY + 2*deltaX*deltaY
// and so it follows
if (distance_squared < min_distance_squared) {
// intersection detected
// now subtract actual distance from "min distance"
seperation = c1.radius + c2.radius - Math.sqrt(distance_squared);
Console.log(c1, c2, seperation);
}
}
}
关于algorithm - 圆间隔距离 - 最近邻问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4847269/