计算不在一组范围内的最小值

Question

给定一个圆形数组（包括x、y、r值），我想在已知Y坐标的情况下（即水平线位置），放置一个新点，使其尽可能靠近中心，但不在任何现有圆内。在示例图像中，红色的点将是结果。

圆圈具有已知的半径和Y轴属性，因此易于计算它们与已知Y值的水平线相交的点。效率很重要，我不想尝试大量X坐标并将它们全部与圆形阵列中的每个项进行测试。是否有一种方法可以通过数学方式计算出这个最佳的X坐标？非常感谢您的帮助。顺便说一下，我正在使用Raphael.js库（因为它是唯一支持IE8的库）编写JavaScript - 但这更多的是一个逻辑问题，因此语言并不真的重要。

- Dave

---

在左图中，为什么红点不会位于第四个圆（从左数）的两个交点之一？在我看来，那些点比指示点更接近右圆的中心。或者，“中心”是指其他东西吗？如果是这样，是什么？ - Ted Hopp

抱歉 - 我所说的中心是图表中的垂直线（为简单起见，将其视为X = 0） - Dave

“尝试一堆X坐标”是什么意思？你只需要尝试交点即可。 - Bergi

Answer 1

我会按照以下步骤来解决你的问题：

1. 初始化一个由X坐标排序的区间集合S为空集
2. 对于每个圆c，计算其与X轴相交的区间I_c。如果c没有相交，则继续下一个圆。否则，测试I_c是否与S中任何区间重叠（这很快因为S已经排序）；如果是，则从S中删除所有相交的区间，将I_c和所有删除的区间合并成一个新的区间I'_c，并将I'_c添加到S中。如果没有相交，则将I_c添加到S中。
3. 检查S中是否有任何区间包含中心点（因为S已经排序，所以很快）。如果有，则选择距离中心点最近的区间端点；如果没有，则选择中心点作为最近点。

- Ted Hopp

---

+1 对于合并区间的建议很好，这似乎是 OP 没有考虑到的。顺便说一下，在计算所有交集之前，您可以检查任何区间是否包含中心，甚至在对它们进行排序之前。 - Bergi

@Bergi - 关于跟踪哪个间隔（如果有）包含中心的优秀观点。由于合并，最多只能有一个这样的间隔。 - Ted Hopp

谢谢Ted，这看起来很有前途，明天我会试着用JS。请原谅我的无知，当您提到“一组区间”时，是指Xstart和Xend值的数组（即沿x轴的范围）吗？当您说“折叠Ic…”时，您是否意味着，例如，如果一个是1 < x < 5，另一个是4 < x < 10，则将其折叠成单个1 < x < 10间隔？ - Dave

@Dave - 是的，每个间隔应该是沿x轴的连续范围的表示。关于折叠，你所描述的正是我所说的。另一个术语可能是“合并”这些间隔。 - Ted Hopp

Answer 2

基本上，圆的方程是 (x - c_x)² + (y - c_y)² = r²。因此，您可以通过用 y 替换为 0 来轻松找到圆和 X 轴之间的交点。然后你只需要解一个简单的二次方程：x² - 2c_xx + c_x² + c_y² - r² = 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;
}

- Chavdar Slavov

---

这大致是我提出的方法，但它不是_O(n)_复杂度。在生成间隔后，您需要对它们进行排序，然后再合并，这是一个_O(n log n)_操作。此外，使用delta悲观地（实际上是扩大间隔）并不明智。计算误差同样可能是正数或负数，因此可以轻松地得出这样的论点：应该通过delta缩小间隔而不是扩大间隔。从概率上讲，最好只使用平均delta值，即零。 - Ted Hopp

感谢您的指针，我完全忽略了复杂度评估中的排序，现在已经更新了。我可能把“delta”角色表述错误了，它用于将点放在圆形区域之外，因为如果您取间隔边缘，您将会在圆与轴相交的点处，据我所理解，这并不满足条件。 - Chavdar Slavov

总的来说，这是一个不错的解决方案（包括代码，我毫不怀疑，赢得了您应得的勾选）。关于“delta”，OP想要一个“不在”任何圆内的点。我理解为不在任何圆的内部，这将允许点位于周长上。您还使用“delta”来扩展间隔，以测试是否合并，这让我觉得无法证明。我会简单地消除它，因为它增加了复杂性，并且具有（最好）可疑的理论基础。 - Ted Hopp

如果允许圆周上的点，则我同意需要删除delta。但是，如果不允许，则存在一种极为罕见但可能的情况，即两个区间之间的差可以恰好为delta（或更小，如果delta不是系统可以区分的最小单位），这将给我们带来错误的解决方案。 - Chavdar Slavov

我认为使用“delta”存在同样（如果不是更大）的风险，会导致错误解决方案（其中两个间隔之间的距离在数学和计算上都是正的，但计算上小于delta）。在这种情况下，使用“delta”将导致本应保持分离的间隔被合并。 - Ted Hopp

Answer 3

1. 创建intersect_segments数组（在x=0 y=0处进行归一化）

2. 按upperlimit对intersectsegments进行排序，并删除upperlimit<0的元素

3. 初始化point1 = 0和segment = 0

4. 当point1在intersectsegment [segment]内时循环执行

   4.1. 将point1增加intersectsegment [segment]的上限

   4.2. 增加segment

5. 按lowerlimit对intersectsegments进行排序，并删除lowerlimit>0的元素

6. 初始化point2 = 0和segment = 0

7. 当point2在intersectsegments [segment]内时循环执行

   7.1. 将point2减去segment的下限

   7.2. 减少segment

8. 该点是p1和p2的最小绝对值

- PA.

---

我认为在第二步中删除上限小于0的交集段是无效的。它们可能与包含中心的段重叠，最近的点可能是这些段之一的左边缘。（我还没有分析您算法的正确性，但这一点立即引起了我的注意。） - Ted Hopp