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

9 次查看（过去 30 天）
Wai Han
Wai Han 2020-10-10
评论： Wai Han 2020-10-19
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.
  2 个评论
Ameer Hamza
Ameer Hamza 2020-10-10
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
Wai Han 2020-10-10
编辑：Wai Han 2020-10-10
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!

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Image Analyst
Image Analyst 2020-10-10
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.
  5 个评论
显示 3更早的评论
Image Analyst
Image Analyst 2020-10-18
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?

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Object Analysis 的更多信息

标签

产品


版本

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by