Finding out if a line hits a circle.

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
SamPerson12345
Prole
Posts: 41
Joined: Sat Aug 30, 2008 5:35 pm

Finding out if a line hits a circle.

Post by SamPerson12345 »

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. :3
User avatar
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.

Post by bartbes »

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:

Code: Select all

((line.y2-line.y1)/(line.x2-line.x1))*(X-line.x1)+line.y1
(with x1 being the lowest x and X being the NON-relative-x)
emonk
Prole
Posts: 24
Joined: Tue Aug 12, 2008 11:43 am

Re: Finding out if a line hits a circle.

Post by emonk »

With a line segment and a circle there are three broad categories of situations:
  • Both endpoints inside the Circle
  • One endpoint inside the Circle and one outside
  • Neither endpoint inside the circle
You can figure out which of those is applicable by calculating the distance of each endpoint from the center of the circle using math.sqrt(dx^2 + dy^2). It's the third category that needs more work, but eliminating the first two cases (which are either hit or not depending on your definitions) helps later on.

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.
So far I've found two ways to answer this question...

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)
We can use this angle to rotate the line into alignment with the x axis and so on.

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 p1-p2 intersects circle with radius 'r' at location 'pc'
function LineIntersectCircle(p1, p2, pc, r)
-- translate points to circle-relative
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 X-axis
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;
Not extensively tested so no guarantees.
Mr. Strange
Party member
Posts: 101
Joined: Mon Aug 11, 2008 5:19 am

Re: Finding out if a line hits a circle.

Post by Mr. Strange »

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
Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 48 guests