Find line segment that intersects the most circles from a list in 2D (SOLVED)-CodePudding

I have a list of circles (x, y, radius) and a line origin (x, y), I want to be able to determine a line segment that intersects as many circles as possible with one of it's points being the line origin, the line is completely straight. This is all in 2D.

Circles have a fixed radius and can overlap. There is no minimum distance that the line has to intersect with the circle.

An image of what I want: https://i.imgur.com/RNgQlh5.png

Psuedocode is fine.

UPDATE:

With some help and ideas from the comments and answer(s) I have figured out how to do this, it could probably do with some optimization though.

I have created two codepens, one of them has code that tries to center the angle, but is more resource intensive, and one that doesn't.

No Centering: https://codepen.io/joshiegemfinder/pen/gOXzXOq

With Centering: https://codepen.io/joshiegemfinder/pen/abVGLRJ

I'll write my code examples in javascript, as that's probably the easiest understood language

To find the line segment that intersects the most circles, you have to take the two tangents of each circle (that pass through the line origin) like this:

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}

This results in an "Interval" (name by @Stef), any angle less than angle1, but greater than angle2 (angle1 <= angleX <= angle2) will intersect the circle if the line segment is long enough

Then, for each intersection, you check both angles against every other interval, checking if the angle is in the interval's range, if it is, increase its count, repeat this for all intervals, (you will also want to store the largest distance that this interval intersects) when you've got a count of intersections, save the angle and number of intersections, and repeat for every other interval (this is a loop nested within another loop, sadly), replacing the variables with your angle, distance and intersection count if it intersects more than the current stored interval.

Eventually, you'll end up with the angle that intersected the most circles, and the distance of the furthest circle it intersects, and the line segment can now be calculated via sin and cos.

Why check only the tangents? Couldn't there be a circle further out that won't get detected because it's inside the tangents? No, there couldn't, this is because the tangents of the further out circle will ALSO be checked, meaning it'll be detected.

Final Code (there may be typos):

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 x1 = origin.x   Math.cos(angle) * maxDist
    let y1 = origin.y   Math.sin(angle) * maxDist
    
    return {origin.x, origin.y, x1, y1}
}

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

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

CodePudding user response：

As suggested by @Stef, compute the angles (on fourquedrants) of all tangents to the circle from the line origin. Tag the angles with 1 and -1 in the trigonometric rotation order, and sort them increasingly. Ignore the circles that surround that origin.

Now form the prefix sum of the ±1 tags and consider the angular interval that yields the largest value.

To get the angles for a circle, compute the polar argument of the center and add plus or minus the half aperture, the sine of which is the ratio of the circle radius over the distance center-origin.