从二维列表中查找与最多圆相交的线段

Question

我有一个圆列表 (x, y, radius) 和一条线原点 (x, y)，我希望能够确定一条线段，该线段与尽可能多的圆与其中一个点相交作为线的原点，这条线是完全直的。这都是二维的。

圆有固定的半径并且可以重叠。线与圆相交没有最小距离限制。

一张我想要的图片：

伪代码很好。

更新：

在评论和回答的一些帮助和想法的帮助下，我已经想出了如何做到这一点，不过它可能需要一些优化。

我创建了两个 codepen，其中一个有试图使角度居中的代码，但更耗费资源，而另一个则没有。

无居中： https://codepen.io/joshiegemfinder/pen/gOXzXOq

居中： https://codepen.io/joshiegemfinder/pen/abVGLRJ

我将使用 javascript 编写代码示例，因为这可能是最容易理解的语言

要找到与最多圆相交的线段，您必须像这样取每个圆的两条切线（通过线原点）：

let diffX = circle.x - origin.x
let diffY = circle.y - origin.y
let dist = Math.sqrt(diffX ** 2 + diffY**2)
let asine = Math.asin(circle.radius / dist)
let angle = Math.atan2(diffY, diffX)

let tangent1 = angle - asine
let tangent2 = angle + sinAngle

let pos1 = {x: circle.x + circle.radius * Math.sin(tangent1), y: circle.y + circle.radius * -Math.cos(tangent1)}
let pos2 = {x: circle.x + circle.radius * -Math.sin(tangent2), y: circle.y + circle.radius * Math.cos(tangent2)}

let dist1 = Math.sqrt((pos1.x - origin.x)**2 + (pos1.x - origin.y)**2)
let dist2 = Math.sqrt((pos2.x - origin.x)**2 + (pos2.x - origin.y)**2)

return {pos1: pos1, pos2: pos2, angle1: Math.atan2(pos1.y - origin.y, pos1.x - origin.x), angle2: Math.atan2(pos2.y - origin.y, pos2.x - origin.x), dist1: dist1, dist2: dist2, circle: circle, dist: dist}

这会产生一个“间隔”（由@Stef 命名），如果线段足够长，任何小于角度 1 但大于角度 2 (angle1 <= angleX <= angle2) 的角度都将与圆相交

然后，对于每个交叉点，您检查两个角度与其他间隔的对比，检查角度是否在间隔范围内，如果是，则增加其计数，对所有间隔重复此操作，（您还需要存储这个区间相交的最大距离）当你得到交叉点的计数时，保存交叉点的角度和数量，并每隔一个间隔重复一次（不幸的是，这是一个嵌套在另一个循环中的循环），将变量替换为如果相交超过当前存储的间隔，您的角度、距离和交点将被计算在内。

最终，您将得到与最多圆相交的角度，以及与它相交的最远圆的距离，现在可以通过 sin 和 cos 计算线段。

为什么只检查切线？难道不能有一个更远的圆因为它在切线内而不会被检测到吗？不，不可能，这是因为还将检查更远的圆的切线，这意味着它会被检测到。

最终代码（可能有错别字）：

function getSegment(circles, origin) {
    //Get all of the intervals
    let intervals = getIntervals(circles, origin)
    
    let maxDist = 0
    let maxIntersections = 0
    let angle = 0
    
    for(interval of intervals) {
        let data1 = getIntersectionData(interval.angle1, intervals)
        let intersections1 = data1.count
        let distance1 = data1.dist
        //if this angle intersects more than the current amount, store this angle's data instead
        //(or this angle intersects the same, but is shorter, feel free to remove this)
        if(intersections1 > maxIntersections || (intersections1 == maxIntersections && distance1 <= maxDist)) {
            maxIntersections = intersections1
            maxDist = distance1
            angle = interval.angle1
        }
        
        let data2 = getIntersectionData(interval.angle2, intervals)
        let intersections2 = data2.count
        let distance2 = data2.dist
        if(intersections2 > maxIntersections || (intersections2 == maxIntersections && distance2 <= maxDist)) {
            maxIntersections = intersections2
            maxDist = distance2
            angle = interval.angle2
        }
    }
    
    let x2 = origin.x + Math.cos(angle) * maxDist
    let y2 = origin.y + Math.sin(angle) * maxDist
    
    return {x1: origin.x, y1: origin.y, x2: x2, y2: y2}
}

function getInterval(circle, origin) {
    let diffX = circle.x - origin.x
    let diffY = circle.y - origin.y
    let dist = Math.sqrt(diffX ** 2 + diffY**2)
    //for asine, you might need to add a catch for when the origin is inside the circle, for JavaScript it just returns NaN and no error is thrown
    let asine = Math.asin(circle.radius / dist)
    let angle = Math.atan2(diffY, diffX)

    let tangent1 = angle - asine
    let tangent2 = angle + asine

    let pos1 = {x: circle.x + circle.radius * Math.sin(tangent1), y: circle.y + circle.radius * -Math.cos(tangent1)}
    let pos2 = {x: circle.x + circle.radius * -Math.sin(tangent2), y: circle.y + circle.radius * Math.cos(tangent2)}

    let dist1 = Math.sqrt((pos1.x - origin.x)**2 + (pos1.x - origin.y)**2)
    let dist2 = Math.sqrt((pos2.x - origin.x)**2 + (pos2.x - origin.y)**2)

    return {pos1: pos1, pos2: pos2, angle1: Math.atan2(pos1.y - origin.y, pos1.x - origin.x), angle2: Math.atan2(pos2.y - origin.y, pos2.x - origin.x), dist1: dist1, dist2: dist2, circle: circle, dist: dist}
}

function getIntervals(circles, origin) {
    //Initialize the array of intervals
    let intervals = []
    
    //Append the interval of each circle to an array
    for(let circle of circles) {
        intervals.push(getInterval(circle))
    }
    
    //Sort the array clockwise by interval.angle1 (Not neccesary or useful)
    intervals.sort((a, b) => a.angle1 - b.angle1)
    
    return intervals
}

function getIntersectionData(angle, intervals) {
    let count = 0
    let dist = 0
    //for each interval:
    for(let inter of intervals) {
        //if the angle is inside the interval (if it'll intersect the circle)
        flag = inter.angle1 <= angle && inter.angle2 >= angle
        //or if the origin is inside the circle (i talked about this at getInterval())
        if((inter.angle1 == NaN || inter.angle2 == NaN) || (flag)) {
            //increase the number of intersections
            count++
            //and if the inteval IS valid, update the distance if it's bigger than the current one
            //(basically get the interval with the largest distance from origin
            if(flag) {
                dist = Math.max(dist, inter.dist)
            }
        }
    }
    return {count: count, dist: dist}
}

Answer 1

按照@Stef 的建议，计算从直线原点到圆的所有切线的角度（在四个象限上）。按三角旋转顺序用 +1 和 -1 标记角度，并将它们递增排序。忽略原点周围的圆圈。

现在形成±1个标签的前缀和，考虑产生最大值的angular区间

要获得圆的角度，请计算圆心的极坐标并加上正负半孔径，其正弦值是圆半径与距离之比 center-origin。

从二维列表中查找与最多圆相交的线段

Find line segment that intersects the most circles from a list in 2D

javascript

math

geometry

pseudocode

更新：