I have a line from A to B and a circle positioned at C with the radius R.
What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?
- 7Hmm. One question: are you talking about the infinite line through A and B, or the finite line segment from A to B?Jason S– Jason S2009-07-02 19:07:20 +00:00Commented Jul 2, 2009 at 19:07
- 2In this case, its the finite line segment. Is "line" called something else depending on if its finite or infinite?Mizipzor– Mizipzor2009-07-03 13:19:42 +00:00Commented Jul 3, 2009 at 13:19
- 1Is there a performance requirement ? Should it be a fast method ?chmike– chmike2009-07-07 06:32:52 +00:00Commented Jul 7, 2009 at 6:32
- At this point, no, all the algorithms here that Ive tried doesnt slow the application down noticeably.Mizipzor– Mizipzor2009-07-07 10:53:04 +00:00Commented Jul 7, 2009 at 10:53
- 20@Mizipzor yes, they are called something else: line segments. If you just say "line" it's implied an infinite one.MestreLion– MestreLion2014-08-06 07:59:08 +00:00Commented Aug 6, 2014 at 7:59
| Show 1 more comment
31 Answers
It looks like oval-point collision detection algorithm:
Its' collision, when distance from point C to line AB is less than radius r.
Lua code:
function pointToOvalOverlap (ax, ay, bx, by, r, px, py) -- ax, ay, bx, by - points A and B -- r - radius of oval -- px, py - point inside/outside oval local dx, dy = bx - ax, by - ay local function getDistance(x1, y1, x2, y2) return math.sqrt((x2 - x1)^2 + (y2 - y1)^2) end local t = ((px - ax) * dx + (py - ay) * dy) / (dx^2 + dy^2) t = math.max(0, math.min(1, t)) -- Clamp t to [0, 1] -- nearest point on line AB: local tx, ty = ax + t * dx, ay + t * dy -- distance from point P to nearest point T: local distance = getDistance(px, py, tx, ty) local overlapDistance = math.max (r - distance, 0) if overlapDistance == 0 then -- no overlap return false, 0, 0 else -- overlap -- push-vector to resolve collision: local nx = overlapDistance*(px-tx)/distance local ny = overlapDistance*(py-ty)/distance return true, nx, ny end end 
