2D Collision Detection

Question

This challenge is based on actual collision detection I had to write for a simple game recently.

Write a program or function which, given two objects, returns a truthy or falsy value depending on whether the two objects are in collision (i.e. intersect) or not.

You need to support three types of objects:

• Line segments: represented by 4 floats, indicating the two endpoints, i.e. (x₁,y₁) and (x₂,y₂). You may assume that the endpoints are not identical (so the line segment is not degenerate).
• Discs: i.e. filled circles, represented by 3 floats, two for the centre (x,y) and one (positive) for the radius r.
• Cavities: these are a disc's complement. That is, a cavity fills all of 2D space, except a circular region, specified by a centre and radius.

Your program or function will receive two such objects in the form of an identifying integer (of your choice) and their 3 or 4 floats. You can take input via STDIN, ARGV or function argument. You may represent the input in any convenient form that is not preprocessed, e.g. 8 to 10 individual numbers, two comma-separated list of values or two lists. The result can be returned or written to STDOUT.

You may assume that the objects are either at least 10^-10 length units apart or intersect by that much, so you don't need to worry about the limitations of floating point types.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

Representing line segments with 0, discs with 1 and cavities with 2, using a list-based input format, the following should all produce a truthy output:

[0,[0,0],[2,2]], [0,[1,0],[2,4]]        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1]       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1]        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1]   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1]       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1]        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1]   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2]                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1]            # Intersecting discs
[1,[3,0],1], [2,[0,0],1]                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1]              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1]                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1]                # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1]               # Any two cavities intersect

while the following should all result in a falsy output

[0,[0,0],[1,0]], [0,[0,1],[1,1]]        # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]]      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]]        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]]        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1]           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1]            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1]  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5]             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity

Answer 1

APL, 279 208 206 203

s←1 ¯1
f←{x←⊣/¨z←⍺⍵[⍋⊣/¨⍺⍵]
2 2≡x:∧/0∧.=⌊(2⊃-⌿↑z)⌹⍣(≠.×∘⌽/x)⍉↑x←s×-/2⊢/↑z
2≡2⌷x:∨/((2⊃z)∇2,x[1]×(2⌷⊃z)+,∘-⍨⊂y÷.5*⍨+.×⍨y←⌽s×⊃-/y),x[1]=(×⍨3⊃⊃z)>+.×⍨¨y←(s↓⌽↑z)-2⌷⊃z
~x∨.∧x[1]≠(.5*⍨+.×⍨2⊃-⌿↑z)<-/⊢/¨z×s*1⌷x}

Line breaks in the function f are for clarity. They should be replaced with the statement separator ⋄

It has been so long since I last made such a complex APL program. I think the last time was this but I am not even sure that was as complex.

Input format
Basically same as the OP, except using 0 for cavity, 1 for disc and 2 for line segment.

Major update

I managed to golf a lot of chars using a different algorithm. No more g bulls**t!!

The main function f is divided into cases:

---

2 2≡x: Segment-segment

In this case, calculate the vector from the end points of each line and solve a system of linear equations to check if the intersection is contained within the vectors.

Caveats:

• The end point of a vector is not considered as a part of the vector (while its origin is). However, if only the tip of a vector is on the other one, the input is invalid according to spec.
• Non-degenerate parallel segments always returns false, regardless of collinearity.
• If one of the segments is degenerate, always return false. If both segments are degenerate, always return true.

Examples: (Note caveat 1 in action in the figure on the right)

---

2≡2⌷x: Segment-other

In this case, the other object is a circular one. Check if the end points of the segment is within the circle using distance check.

In the disc case, also construct a line segment of the diameter perpendicular to the given segment. Check if the segments collide by recursion.
In the cavity case, sneak in a "times 0" in the construction of the said segment to make it degenerate. (See why I use 0 for cavity and 1 for disc now?) As the given segment is not degenerate, the segment-segment collision detection always return false.

Finally combine the results of the distance checks and the collision detection. For the cavity case, negate the results of the distance checks first. Then (in both cases) OR the 3 results together.

Regarding the segment-segment caveats, numbers 3 is addressed (and exploited). Number 2 is not a problems as we are intersecting perpendicular segments here, which are never parallel if they are not degenerate. Number 1 takes effect only in the disc case, when one of the given end points is on the constructed diameter. If the end point is well inside the circle, the distance checks would have taken care of it. If the end point is on the circle, since the constructed diameter is parallel to the given segment, the latter must be tangent to the circle with only one point touching the disc, which is not valid input.

Examples:

---

Default case: Other-other

Calculate the distance between the centers. Disc-disc collision occurs if and only if the distance is smaller than the sum of radii. Disc-cavity collision occurs if and only if the distance is greater than the difference in radii.

To take care of the cavity-cavity case, negate the result of the distance check, AND with each of the identifying integers and then OR them together. Using some logic, one can show that this process returns true if and only if both identifying integers are falsy (Cavity-cavity case), or if the distance check returned true

Answer 2

Javascript - 393 bytes

Minified:

F=(s,a,t,b,e,x)=>(x=e||F(t,b,s,a,1),[A,B]=a,[C,D]=b,r=(p,l)=>([g,h]=l,[f,i]=y(h,g),[j,k]=y(p,g),m=Math.sqrt(f*f+i*i),[(f*j+i*k)/m,(f*k-i*j)/m]),u=(p,c)=>([f,g]=c,[i,j]=y(p,f),i*i+j*j<g*g),y=(p,c)=>[p[0]-c[0],p[1]-c[1]],[n,o]=r(C,a),[q,v]=r(D,a),w=(v*n-o*q)/(v-o),z=r(B,a)[0],Y=u(A,b),Z=u(B,b),[v*o<0&&w*(w-z)<0,Y||Z||o<D&&o>-D&&n*(n-z)<0,!Y||!Z,x,u(A,[C,D+B]),B>D||!u(A,[C,D-B]),x,x,1][s*3+t])

Expanded:

F = (s,a,t,b,e,x) => (
    x = e || F(t,b,s,a,1),
    [A,B] = a,
    [C,D] = b,
    r = (p,l) => (
        [g,h] = l,
        [f,i] = y(h,g),
        [j,k] = y(p,g),
        m = Math.sqrt( f*f + i*i ),
        [(f*j + i*k)/m, (f*k - i*j)/m] ),
    u = (p,c) => (
        [f,g] = c,
        [i,j] = y(p,f),
        i*i + j*j < g*g ),
    y = (p,c) => [p[0] - c[0], p[1] - c[1]],
    [n,o] = r(C,a),
    [q,v] = r(D,a),
    w = (v*n - o*q)/(v - o),
    z = r(B,a)[0],
    Y = u(A,b), Z = u(B,b),
    [   v*o < 0 && w*(w-z) < 0,
        Y || Z || o < D && o > -D && n*(n-z) < 0,
        !Y || !Z,
        x,
        u(A,[C,D+B]),
        B > D || !u(A,[C,D-B]),
        x,
        x,
        1
    ][s*3+t]);

Notes:

• defines function F that accepts the required arguments and returns the required value
• input format is identical to format in the OP, with the exception that the integer type code for each primitive is separate from the tuple. For example, F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] ) or F( 1,[[3,0],1], 2,[[0,0],1] ).
• code validated on all test cases supplied in the OP
• should handle all edge and corner cases, including zero-length line segments and zero-radius circles

Answer 3

Python, 284

I'm using a pretty garbage algorithm compared to all these geometric tricks, but it gets the right answers even though it takes a over a minute to get through the test cases. The big advantage is that I only have to write the three scoring functions, and the hillclimbing takes care of all the edge cases.

Golfed:

import math,random as r
n=lambda(a,c),(b,d):math.sqrt((a-b)**2+(c-d)**2)
x=lambda(t,a,b),p:max(eval(["n(b,p)-n(a,b)+","-b+","b-"][t]+'n(a,p)'),0)
def F(t,j):
q=0,0;w=1e9
 for i in q*9000:
    y=x(t,q)+x(j,q)
    if y<w:p,w=q,y
    q=(r.random()-.5)*w+p[0],(r.random()-.5)*w+p[1]
 return w<.0001

Ungolfed:

import math
import random as r
def norm(a, b):
 return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def lineWeight(a, b, p):
 l1 = norm(a, p)
 l2 = norm(b, p)
 return min(l1, l2, l1 + l2 - norm(a, b))

def circleWeight(a, r, p):
 return max(0, norm(a, p) - r)

def voidWeight(a, r, p):
 return max(0, r - norm(a, p))

def weight(f1, f2, s1, s2, p):
 return f1(s1[1], s1[2], p) + f2(s2[1], s2[2], p)

def checkCollision(s1, s2):
 a = [lineWeight, circleWeight, voidWeight]
 f1 = a[s1[0]]
 f2 = a[s2[0]]
 p = (0.0, 0.0)
 w = 0
 for i in a*1000:
  w = weight(f1, f2, s1, s2, p)
  p2 = ((r.random()-.5)*w + p[0], (r.random()-.5)*w + p[1])
  if(weight(f1, f2, s1, s2, p2) < w):
   p = p2
 if w < .0001:
  return True
 return False

And finally, a test script in case anyone else wants to try this in python:

import collisiongolfedbak
reload(collisiongolfedbak)

tests = [
[0,[0,0],[2,2]], [0,[1,0],[2,4]],        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1],       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1],        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1],   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1],       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1],        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1],   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2],                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1],            # Intersecting discs
[1,[3,0],1], [2,[0,0],1],                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1],              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1],                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1] ,               # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1] ,              # Any two cavities intersect
[0,[0,0],[1,0]], [0,[0,1],[1,1]] ,       # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]],      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]],        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]],        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1],           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1],            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1],  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5],             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity
]

for a, b in zip(tests[0::2], tests[1::2]):
 print collisiongolfedbak.F(a,b)