基本上,圆的方程是
(x - cx)2 + (y - cy)2 = r2。因此,您可以通过用
y 替换为
0 来轻松找到圆和 X 轴之间的交点。然后你只需要解一个简单的
二次方程:
x2 - 2cxx + cx2 + cy2 - r2 = 0。对于它,您有三种可能的结果:
- 没有交点- 行列式将是无理数(JavaScript 中的 NaN),请忽略此结果;
- 一个交点- 两个解相同,请使用 [value, value];
- 两个交点- 两个解不同,请使用 [value1, value2]。
将新计算的交集区间排序,然后尝试在可能的情况下合并它们。但是请注意,每种编程语言都存在近似值,因此您需要为点近似定义delta值,并在合并区间时考虑它。
当区间合并后,您可以通过从每个区间的开头/结尾减去/加上相同的delta值来生成您的x坐标。最后,从所有点中,距离零最近的点就是您的答案。
这是一个复杂度为O(n log n)的示例,更注重可读性。我使用了1*10-10作为delta:
var circles = [
{x:0, y:0, r:1},
{x:2.5, y:0, r:1},
{x:-1, y:0.5, r:1},
{x:2, y:-0.5, r:1},
{x:-2, y:0, r:1},
{x:10, y:10, r:1}
];
console.log(getClosestPoint(circles, 1e-10));
function getClosestPoint(circles, delta)
{
var intervals = [],
len = circles.length,
i, result;
for (i = 0; i < len; i++)
{
result = getXIntersection(circles[i])
if (result)
{
intervals.push(result);
}
}
intervals = intervals.sort(function(a, b){
return a.from - b.from;
});
if (intervals.length <= 0) return 0;
intervals = mergeIntervals(intervals, delta);
var points = getClosestPoints(intervals, delta);
points = points.sort(function(a, b){
return Math.abs(a) - Math.abs(b);
});
return points[0];
}
function getXIntersection(circle)
{
var d = Math.sqrt(circle.r * circle.r - circle.y * circle.y);
return isNaN(d) ? null : {from: circle.x - d, to: circle.x + d};
}
function mergeIntervals(intervals, delta)
{
var curr = intervals[0],
result = [],
len = intervals.length, i;
for (i = 1 ; i < len ; i++)
{
if (intervals[i].from <= curr.to + delta)
{
curr.to = Math.max(curr.to, intervals[i].to);
} else {
result.push(curr);
curr = intervals[i];
}
}
result.push(curr);
return result;
}
function getClosestPoints(intervals, delta)
{
var result = [],
len = intervals.length, i;
for (i = 0 ; i < len ; i++)
{
result.push( intervals[i].from - delta );
result.push( intervals[i].to + delta );
}
return result;
}