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

7 views (last 30 days)
Wai Han on 10 Oct 2020
Commented: Wai Han on 19 Oct 2020
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 on 10 Oct 2020
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 on 10 Oct 2020
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.
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! Image Analyst on 10 Oct 2020
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 on 18 Oct 2020
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.
Image Analyst on 18 Oct 2020
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 on 19 Oct 2020
Ohh yes, I got it now.
I was really struggling with this code. You help me out.
Thank you so much...

R2020b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!