Finding out if a line hits a circle.
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
 SamPerson12345
 Prole
 Posts: 41
 Joined: Sat Aug 30, 2008 5:35 pm
Finding out if a line hits a circle.
I can't figure it out. All I have is the starting position and the ending position of a line and where the circle is. Help would be greatly appreciated.
 bartbes
 Sex machine
 Posts: 4946
 Joined: Fri Aug 29, 2008 10:35 am
 Location: The Netherlands
 Contact:
Re: Finding out if a line hits a circle.
With some basic math you can figure out the y for the x of the line, so if a line goes from x=1 to x=5, you can calculate the y at x=3 (or somewhere else).
Try:
(with x1 being the lowest x and X being the NONrelativex)
Try:
Code: Select all
((line.y2line.y1)/(line.x2line.x1))*(Xline.x1)+line.y1
Re: Finding out if a line hits a circle.
With a line segment and a circle there are three broad categories of situations:
If neither endpoint is inside the circle then we have two more cases:
Answer #1: Apply mathematics!
To figure out which is the case we need to find the point on the line that is closest to the center of the circle, then test to see if that is inside the radius. Here's a page with some relatively simple explanations of the problem and solutions:
http://local.wasp.uwa.edu.au/~pbourke/g ... phereline/
The Line Segment section of that page gives an equation for testing whether the closest point on the line to the circle's center is between the two endpoints. For our purposes we can throw away ones where the closes point is outside our endpoints, since we've already tested for endpoints inside the circle.
For lines that pass the first test you calculate the actual position of the closest point and check if it falls inside the radius of the circle. The result of the first test is the fraction of the line from P1 to P2 where the closest point is located. I'll leave it to you to figure the math for finding the position of the closest point and testing it for being inside the circle.
Answer #2: Cheat with Trig!
All of the above is very interesting, but math isn't really my strong point. I know how to rotate points though, and I can find the angle of a line... and that leads to an interesting idea that's probably going to take forever to actually operate but is conceptually very simple.
The idea is that you can rotate the endpoints of the line around the center of the circle until the line is horizontal (or vertical if you prefer), then find the distance of the closest point by simple subtraction. Figuring out if the rotated points are inside the circle is a simple too, so we can do this to solve the entire problem.
To find the angle of the line you use the math.atan2 function:
We can use this angle to rotate the line into alignment with the x axis and so on.
Here's the code:
Not extensively tested so no guarantees.
 Both endpoints inside the Circle
 One endpoint inside the Circle and one outside
 Neither endpoint inside the circle
If neither endpoint is inside the circle then we have two more cases:
 Line passes through, or is tangent to, the circle.
 Line does not pass through the circle.
Answer #1: Apply mathematics!
To figure out which is the case we need to find the point on the line that is closest to the center of the circle, then test to see if that is inside the radius. Here's a page with some relatively simple explanations of the problem and solutions:
http://local.wasp.uwa.edu.au/~pbourke/g ... phereline/
The Line Segment section of that page gives an equation for testing whether the closest point on the line to the circle's center is between the two endpoints. For our purposes we can throw away ones where the closes point is outside our endpoints, since we've already tested for endpoints inside the circle.
For lines that pass the first test you calculate the actual position of the closest point and check if it falls inside the radius of the circle. The result of the first test is the fraction of the line from P1 to P2 where the closest point is located. I'll leave it to you to figure the math for finding the position of the closest point and testing it for being inside the circle.
Answer #2: Cheat with Trig!
All of the above is very interesting, but math isn't really my strong point. I know how to rotate points though, and I can find the angle of a line... and that leads to an interesting idea that's probably going to take forever to actually operate but is conceptually very simple.
The idea is that you can rotate the endpoints of the line around the center of the circle until the line is horizontal (or vertical if you prefer), then find the distance of the closest point by simple subtraction. Figuring out if the rotated points are inside the circle is a simple too, so we can do this to solve the entire problem.
To find the angle of the line you use the math.atan2 function:
Code: Select all
local lineangle = math.atan2(p2.y  p1.y, p2.x  p1.x)
Here's the code:
Code: Select all
 distance between two points
function distance(x1, y1, x2, y2)
return math.sqrt((x1  x2)^2 + (y1  y2)^2);
end;
 rotate [x,y] around [0,0] by 'a' radians
function rotate(x, y, a)
local sina, cosa = math.sin(a), math.cos(a);
return x * cosa  y * sina, x * sina + y * cosa;
end;
 return true if line p1p2 intersects circle with radius 'r' at location 'pc'
function LineIntersectCircle(p1, p2, pc, r)
 translate points to circlerelative
local tp1, tp2 = { x = p1.x  pc.x, y = p1.y  pc.y }, { x = p2.x  pc.x, y = p2.y  pc.y };
 check points inside...
if distance(tp1.x, tp1.y, 0, 0) < r then return true; end;
if distance(tp2.x, tp2.y, 0, 0) < r then return true; end;
 rotate points to make line parrallel to Xaxis
local lineangle = math.atan2(p2.y  p1.y, p2.x  p1.x);
local rp1 = {}; rp1.x, rp1.y = rotate(tp1.x, tp1.y, lineangle);
local rp2 = {}; rp2.x, rp2.y = rotate(tp2.x, tp2.y, lineangle);
 should have: rp1.y == rp2.y
assert(math.abs(rp1.y  rp2.y) <= math.abs(rp1.y / 10000));
if math.abs(rp1.y) > r then return false; end;  line doesn't cross circle
 check for both points on same side...
if rp1.x * rp2.x > 0 then return false; end;
 none of the above... line intersects
return true;
end;

 Party member
 Posts: 101
 Joined: Mon Aug 11, 2008 5:19 am
Re: Finding out if a line hits a circle.
Marc LeBlanc wrote an excellent lecture on this subject. You can find it at his website:
http://8kindsoffun.com/
Lots of other good resources there for designers and programmers. Plus Marc is a good guy.
Mr. Strange
http://8kindsoffun.com/
Lots of other good resources there for designers and programmers. Plus Marc is a good guy.
Mr. Strange
Who is online
Users browsing this forum: No registered users and 36 guests