21
\$\begingroup\$

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. (x1,y1) and (x2,y2). 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
\$\endgroup\$
  • \$\begingroup\$ Trickier than I thought at first. Starting with the line/line case, I come upon a surprising number of edge cases. Couldn't you disallow collinear segments? Would make things much easier. ;) \$\endgroup\$ – Emil Oct 8 '14 at 21:06
  • \$\begingroup\$ @Emil Sorry, but 9 hours after posting, I'll have to assume that others might have started working on the challenge, and changing the spec (apart from fixing breaking problems) doesn't seem like a good idea to me. Depending on how you do it, parallel line segments should be the only edge case you need to worry about for the line-line collisions, though, I think. \$\endgroup\$ – Martin Ender Oct 8 '14 at 21:12
  • \$\begingroup\$ Sure, I wasn't really expecting you change it. I was just a tiny bit frustrated that handling the different variants of collinear line segments doubled the length of my code so far. :) (A great challenge, by the way!) \$\endgroup\$ – Emil Oct 8 '14 at 21:30
  • \$\begingroup\$ Doesn't collinear points fall under "doesn't collide by 10^-10"? \$\endgroup\$ – TwiNight Oct 10 '14 at 1:01
  • \$\begingroup\$ @TwiNight Not if the two lines are collinear but don't overlap. E.g. [0,[-2,0],[-1,0]], [0,[1,0],[2,0]] \$\endgroup\$ – Martin Ender Oct 10 '14 at 8:36
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ My understanding is that if your program is written using characters that span Unicode rather than ASCII, the byte count needs to acknowledge the 2-bytes-per-character nature of Unicode. \$\endgroup\$ – COTO Oct 11 '14 at 13:23
  • \$\begingroup\$ @COTO I did not specify Unicode. As far as I'm aware, the APL character set does fit into a byte, and there are single-byte code pages which contain all the APL characters, so using that encoding, the byte count is fine. The counting by bytes is mostly relevant for people who encoding stuff in multi-byte strings in "normal" languages, or who use Mathematica's Unicode shortcuts. \$\endgroup\$ – Martin Ender Oct 11 '14 at 14:19
  • \$\begingroup\$ @MartinBüttner: So you're saying that even though nobody could reasonably or practically represent the 1-byte-per-char version of the string in any text editor besides one explicitly designed for APL, it counts as 1-byte-per-char because there are 256 or fewer allowed characters in the language spec? \$\endgroup\$ – COTO Oct 11 '14 at 15:59
  • \$\begingroup\$ @COTO Well and because encodings do exist according to which a single-byte encoded file could be interpreted. I don't think I'd be willing to go down that route if people had to make up their encoding. Otherwise any program that uses less than 257 distinct characters could claim that (which would be almost any answer on PPCG, I think). I just think we shouldn't penalise APL for predating Unicoding by several decades - back then it made sense to interpret the bytes you had as weird funky characters that work as mnemonics. \$\endgroup\$ – Martin Ender Oct 11 '14 at 16:04
  • 1
    \$\begingroup\$ @COTO There's J, which is based on APL and uses only ASCII characters. They usually score similarly, so that would probably beat you as well, even if scored by Unicode. And I should add that neither language was designed for golfing, and AFAIK both are actually used professionally. And the golfing challenges here aren't so much about getting the green checkmark, but more about squeezing every last little byte out of your program with your language's means and beating everyone in the same "weight category", which will usually earn you more upvotes than using a terse language anyway. ;) \$\endgroup\$ – Martin Ender Oct 11 '14 at 16:11
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Ah, thanks for mentioning those two edge cases. Zero-radius circles don't have to be handled (the post says positive radius), and I'll also clarify that the ends of the line segment will be distinct. \$\endgroup\$ – Martin Ender Oct 8 '14 at 23:20
4
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.