What is a good algorithm to use to check whether the finite line SEGMENT intersects the circle?

Suppose we know the start point (x1,y1), the end point (x2,y2) and the circle center and its radius .

How to make a collisionfree alogrithm to check whether the line segment passes through the circle or not.

I am asking this for the RRT (rapidly exploring random trees) algorithm.

[Ameer Hamza]

Given the line segment, center of the circle and its radius. You can develop a deterministic algorithm to check if they intersect or not. Why do you need RRT in this case?

[Wai Han]

I am writing the code for RRT algorithm as an assignment..

According to wikipedia, in the algorithm part Rapidly-exploring random trees algorithm,

"NEW_CONF" selects a new configuration qnew by moving an incremental distance Δq from qnear in the direction of qrand.

I have already found a way to find the new_conf.

The problem is that

Only if the line from new_conf to the nearest_node is collision free, the new_conf is set.

I am needing help how to check the line is collision free.

I tried this out and is not working properly.

circle-line-segment-collision-detection-algorithm

Here is the code implemented in matlab.

function collision = collisioncheck(nearest_node,new_q,obstacles)
E = [nearest_node(2),nearest_node(3)];
L = [new_q(2),new_q(3)];

    C = [obstacles(1,1),obstacles(1,2)];
    r = obstacles(1,3);
    d = L - E;
    f = E - C;
    
    a = dot(d,d);
    b = dot(2*f,d);
    c = dot(f, (f)-r^2);
    discriminant = b*b-r*a*c;
    if discriminant < 0
        collision = false;   % no collision
    else
        discriminant = sqrt(discriminant);
        t1 = (-b - discriminant)/(2*a);
        t2 = (-b + discriminant)/(2*a);
        if t1 >=0 && t1 <=1
            collision = true;
            return
        end
        if t2 >=0 && t2 <=1
            collision = true;
            return
        end        
        collision = false;
        return
    end
end

I have tried this code, the problem here is that.. the segment is working in only one direction.

For eg. if the end points of the segment are (x1,y1) and (x2,y2), the code is returning me as if the end points are (x1,y1) and (inf,inf)

Here is the simplify diagram to understand what I mean.

Thank you!

Answer 1

[Image Analyst]

See attached point-line distance demo.

Basically you need to see if the distance of the circle center to the line is less than the circle radius. If it is, there is an intersection. The code will show you how to do that.

[Wai Han]

The code is using viscircles which is part of the Image Processing Tool.

Do you have any other idea?

I am a student so I can't use the Image Processing Tool.

By the way, can you explain me whether the function you provided is used for an infinite line or just a line segment with finite start and end points?

[Image Analyst]

You don't need to use viscircles - that's just for visualization and you can skip using it.

The formula is for infinite lines. The two points on the lin can be anywhere and don't need to have the segment be perpendicular to the point-to-line line. It acts like the line is infinite in extent so it will find the distance even if the point is way far away from the line segment end points. It's completely general.

[Wai Han]

Hi Image Analyst, I tried to implement the code. Unfortunately, I am facing problem with the infinite lines.

I think, the lines need to be finite segments, so that a segment line in the same direction as the infinite line is free from collision.

If I use infinite lines, the segment lines which are actually free from collision return that they are in collision.

Thanks for your help!

[Image Analyst]

Using the right math, you can determine if the line from the point perpendicular to the infinite line intersects the line in the segments where you defined the line. So if (xi,yi) is the intersection point of the perpendicular line with the infinite line, and (x1,y1) and (x2,y2) are the segment endpoints, it seems like you could just do

isInsideSegment = (x1<xi) && (xi<x2) && (y1<yi) && (yi<y2);

Right? Does that make sense?

[Wai Han]

Ohh yes, I got it now.

I was really struggling with this code. You help me out.

Thank you so much...