Finding out if a line hits a circle.

[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.

[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]

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]

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