Last active
October 21, 2016 02:00
-
-
Save sharpobject/8022862 to your computer and use it in GitHub Desktop.
Collision functions for closed circles, lines, and closed segments. When a collision is detected, a point contained in both objects is returned.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function SegmentCircleIntersect(a, b, c) | |
local ac2 = (c.x - a.x)^2 + (c.y - a.y)^2 | |
local cr2 = c.r * c.r | |
if ac2 <= cr2 then | |
return a | |
end | |
local bc2 = (c.x - b.x)^2 + (c.y - b.y)^2 | |
if bc2 <= cr2 then | |
return b | |
end | |
local abx = b.x-a.x | |
local aby = b.y-a.y | |
local e = {x = c.x - aby, y = c.y + abx} | |
local f = {x = c.x + aby, y = c.y - abx} | |
local point = SegmentLineIntersect(a, b, e, f) | |
if point and (point.x - c.x)^2 + (point.y - c.y)^2 <= cr2 then | |
return point | |
end | |
end | |
function LineCircleIntersect(a, b, c) | |
local abx = b.x-a.x | |
local aby = b.y-a.y | |
local e = {x = c.x - aby, y = c.y + abx} | |
local f = {x = c.x + aby, y = c.y - abx} | |
local point = LineLineIntersect(a, b, e, f) | |
if point and (point.x - c.x)^2 + (point.y - c.y)^2 <= c.r^2 then | |
return point | |
end | |
end | |
function LineLineIntersect(p, p2, q, q2) | |
local rx,ry = p2.x-p.x, p2.y-p.y | |
local sx,sy = q2.x-q.x, q2.y-q.y | |
local qmpx,qmpy = q.x -p.x, q.y -p.y | |
local rxs = rx*sy - ry*sx | |
local qmpxs = qmpx*sy - qmpy*sx | |
if rxs == 0 then | |
if qmpxs == 0 then | |
-- then the lines are equal! | |
return p | |
end | |
else | |
-- then the lines intersect at exactly one point | |
local t = qmpxs / rxs | |
return {x=p.x+t*rx, y=p.y+t*ry} | |
end | |
end | |
function SegmentLineIntersect(p, p2, q, q2) | |
local rx,ry = p2.x-p.x, p2.y-p.y | |
local sx,sy = q2.x-q.x, q2.y-q.y | |
local qmpx,qmpy = q.x -p.x, q.y -p.y | |
local rxs = rx*sy - ry*sx | |
local qmpxs = qmpx*sy - qmpy*sx | |
if rxs == 0 then | |
if qmpxs == 0 then | |
-- then the segment is collinear with the line! | |
return p | |
end | |
else | |
-- then the segments is not collinear or parallel with the line | |
local t = qmpxs / rxs | |
if 0 <= t and t <= 1 then | |
return {x=p.x+t*rx, y=p.y+t*ry} | |
end | |
end | |
end | |
function SegmentSegmentIntersect(p, p2, q, q2) | |
local rx,ry = p2.x-p.x, p2.y-p.y | |
local sx,sy = q2.x-q.x, q2.y-q.y | |
local qmpx,qmpy = q.x -p.x, q.y -p.y | |
local rxs = rx*sy - ry*sx | |
local qmpxs = qmpx*sy - qmpy*sx | |
if rxs == 0 then | |
if qmpxs == 0 then | |
-- then the segments are collinear! | |
-- do something dumb! | |
local which = "x" | |
-- this fails in some cases where p has length 0 | |
-- segments should have positive length, please | |
if p.x == p2.x then which = "y" end | |
if p[which] > p2[which] then p,p2 = p2,p end | |
if q[which] > q2[which] then q,q2 = q2,q end | |
if p[which] > q[which] then p,p2,q,q2 = q,q2,p,p2 end | |
if p[which] <= q[which] and q[which] <= p2[which] then | |
return q | |
end | |
end | |
else | |
-- then the segments are not collinear or parallel | |
local qmpxr = qmpx*ry - qmpy*rx | |
local t = qmpxs / rxs | |
local u = qmpxr / rxs | |
if 0 <= t and t <= 1 and 0 <= u and u <= 1 then | |
return {x=p.x+t*rx, y=p.y+t*ry} | |
end | |
end | |
end | |
function CircleCircleIntersect(a, b) | |
local abx = b.x-a.x | |
local aby = b.y-a.y | |
local dist2 = abx^2 + aby^2 | |
local tr = a.r + b.r | |
if dist2 <= tr^2 then | |
local scale = a.r/tr | |
return {x=a.x+scale*abx, y=a.y+scale*aby} | |
end | |
end | |
-- Find out which side of a->b c lies on. | |
-- left = 1 | |
-- right = -1 | |
-- on the line = 0 | |
function LinePointSide(a, b, c) | |
local ret = ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) | |
if ret > 0 then | |
return 1 | |
elseif ret < 0 then | |
return -1 | |
else | |
return 0 | |
end | |
end | |
function DotProduct(a, b) | |
return a.x * b.x + a.y * b.y | |
end | |
-- must have rp != rp2, rr > 0 | |
function WideRayAABBIntersect(rp, rp2, rr, aabb) | |
-- A "wide ray" is basically 2 rays and all the space in between. | |
-- So before anything let's calculate those 2 rays. | |
-- For convenience, move the 2nd point used to define the ray | |
-- so that it is the "ray radius" from the first point. | |
-- couldn't figure out how to avoid this sqrt sorry. | |
local rdist = ((rp2.x - rp.x)^2 + (rp2.y - rp.y)^2)^.5 | |
rp2.x = rp.x + (rp2.x - rp.x) * rr/rdist | |
rp2.y = rp.y + (rp2.y - rp.y) * rr/rdist | |
-- Now we can offset the original ray to find the 2 "outer rays" | |
-- that form the bounds of the "wide ray". | |
local dx = rp2.y - rp.y | |
local dy = rp.x - rp2.x | |
local outer_rays = { {{x=rp.x + dx, y=rp.y + dy}, {x=rp2.x + dx, y=rp2.y + dy}}, | |
{{x=rp.x - dx, y=rp.y - dy}, {x=rp2.x - dx, y=rp2.y - dy}} } | |
-- TODO: handle the case where the origin of the wide ray intersects with the AABB | |
-- You can do this with SegmentAABBIntersect(outer_rays[1][1], outer_rays[2][1], aabb) | |
-- To have our "wide ray" intersect the AABB, there must be some point in the | |
-- AABB that is not on the same side of both "outer rays" | |
-- Being on the same side of both "outer rays" is also called "not being in the wide way" ok | |
-- So let's have a look at the corners. | |
-- If all corners are on the same side of both outer rays, we're done and there's no intersection. | |
-- If any corner is on different sides of the two outer rays, it lies within the wide ray. | |
-- If no corner is on different sides of the two outer rays, but some corner is on another side from | |
-- other corners, then the ray intersects the AABB but does not touch any of the AABB's corners. | |
-- Gosh. | |
local corners = {{x=aabb.x1, y=aabb.y1}, | |
{x=aabb.x1, y=aabb.y2}, | |
{x=aabb.x2, y=aabb.y2}, | |
{x=aabb.x2, y=aabb.y1}} | |
corners[5] = corners[1] | |
local candidates = {} | |
local side_sum = 0 | |
for i=1,4 do | |
local side_a = LinePointSide(outer_rays[1][1], outer_rays[1][2], corners[i]) | |
local side_b = LinePointSide(outer_rays[2][1], outer_rays[2][2], corners[i]) | |
-- This corner is inside the wide ray, so it might be the first point we encounter! | |
if side_a ~= side_b then | |
candidates[#candidates+1] = corners[i] | |
end | |
-- Add sides to the side_sum | |
side_sum = side_sum + side_a + side_b | |
end | |
-- If the entire AABB is on the same side, we lose | |
if side_sum == 8 or side_sum == -8 then | |
return nil | |
end | |
-- Add intersections between outer rays and AABB bounding segments to list of candidates | |
for i=1,4 do | |
for j=1,2 do | |
local point = SegmentLineIntersect(corners[i], corners[i+1], outer_rays[j][1], outer_rays[j][2]) | |
if point then | |
candidates[#candidates+1] = point | |
end | |
end | |
end | |
-- pretty sure this shouldn't happen but w/e | |
if #candidates == 0 then | |
return nil | |
end | |
-- Now we have a list of candidates, we can find the one that is the least far along. | |
-- Just minimize the dot product with the original ray to find that ok. | |
local best = candidates[1] | |
local best_dot = DotProduct({x=rp2.x-rp.x, y=rp2.y-rp.y}, {x=candidates[1].x-rp.x, y=candidates[1].y-rp.y}) | |
for i=2,#candidates do | |
local dot = DotProduct({x=rp2.x-rp.x, y=rp2.y-rp.y}, {x=candidates[i].x-rp.x, y=candidates[i].y-rp.y}) | |
if dot < best_dot then | |
best = candidates[i] | |
best_dot = dot | |
end | |
end | |
if best_dot >= 0 then | |
return best | |
else | |
-- can't go returning a point BEHIND the damn ray now can we!!!! | |
return nil | |
end | |
end |
I added another sqrt but it's in some weird shit so it doesn't count thanks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Removed the last sqrt.