计算不在范围集之间的最小值

Question

给定一个圆数组（x、y、r 值），我想放置一个新点，使其具有 fixed/known Y 坐标（显示为水平线），并且是尽可能靠近中心但不在任何现有圆圈内。在示例图像中，红色的点就是结果。

圆具有已知的半径和 Y 轴属性，因此很容易计算出它们在已知 Y 值处与水平线相交的点。效率很重要，我不想尝试一堆 X 坐标并针对 circles 数组中的每个项目测试它们。有没有办法从数学上计算出这个最佳 X 坐标？非常感谢任何帮助。顺便说一句，我使用 Raphael.js 库在 javascript 中编写它（因为它是唯一支持 IE8 的库）——但这更像是一个逻辑问题，所以语言并不重要.

Answer 1

我会按如下方式处理您的问题：

初始化一组区间S，按区间的X坐标排序，到空集合
对于每个圆c，计算交集I_c的间隔c 同X轴。如果c不相交，继续下一个圈。否则，测试 I_c 是否与 S 中的任何间隔重叠（这很快，因为S 排序);如果是这样，从 S 中删除所有相交的间隔，将 I_c 和所有删除的间隔折叠到一个新的间隔 I'_c 并添加 I'_c 到S。如果没有交集，则将I_c添加到S.
检查 S 中的任何区间是否包括中心（再次快速，因为 S 已排序）。如果是，select离中心最近的区间端点；如果不是，select 中心作为最近点。

Answer 2

创建 intersect_segments 数组（在 x=0 y=0 处归一化）
按上限对相交段进行排序，删除上限<0
初始化点 1 = 0 和线段 = 0
loop while point1 is inside intersecsegment[segment]

4.1。将 point1 增加 intersecsegment[段]
的上限
4.2。增量段
按下限对相交段进行排序并删除 loerlimit>0
初始化点 2 = 0 和线段 = 0
loop while point2 is inside intersecsegments[segment]

7.1。将 point2 减去段的下限

7.2。递减段
点是p1和p2的最小绝对值

Answer 3

基本上圆的方程是(x - c_x)² + (y - c_y)² = r²。因此，您可以通过将 y 替换为 0 轻松找到圆和 X 轴之间的交点。之后你只需要一个简单的 quadratic equation 来解决： x² - 2c_xx + c_x² + c_y² - r² = 0 。对于它你有 3 种可能的结果：

无交集-行列式将为无理数（JavaScript中的NaN），忽略此结果；
一个交集 - 两个解决方案匹配，使用 [value, value];
两个交集-两种解法不同，使用[value1,value2].

对新计算的相交间隔进行排序，然后尽可能合并它们。但是请记住，在每种程序语言中都有近似值，因此您需要为点近似值定义增量值，并在合并区间时将其考虑在内。

合并间隔后，您可以通过 subtracting/adding 与每个间隔的 beginning/end 相同的增量值生成 x 坐标。最后从所有点来看，最接近零的就是你的答案。

这是一个复杂度为 O(n log n) 的示例，它更注重可读性。我已经使用 1*10^-10 作为增量：

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;
}

计算不在范围集之间的最小值

Calculate minimum value not between set of ranges

javascript

math

trigonometry

intervals