Эта задача основана на фактическом обнаружении столкновений, которое мне недавно пришлось написать для простой игры.

Напишите программу или функцию, которая, учитывая два объекта, возвращает истинное или ложное значение в зависимости от того, находятся ли два объекта в столкновении (то есть пересекаются) или нет.

Вам необходимо поддерживать три типа объектов:

• Сегменты линии : представлены 4 числами с плавающей запятой, указывающими две конечные точки, т.е. (x ₁ , y ₁ ) и (x ₂ , y ₂ ) . Вы можете предположить, что конечные точки не идентичны (поэтому отрезок не является вырожденным).
• Диски : т.е. заполненные круги, представленные 3-мя поплавками, два для центра (x, y) и один (положительный) для радиуса r .
• Полости : это дополнение диска. Таким образом, полость заполняет все пространство 2D, кроме круглой области, определенной центром и радиусом.

Ваша программа или функция получит два таких объекта в виде идентифицирующего целого числа (по вашему выбору) и их 3 или 4 числа с плавающей точкой. Вы можете получить ввод через STDIN, ARGV или аргумент функции. Вы можете представить ввод в любой удобной форме, которая не была предварительно обработана, например, от 8 до 10 отдельных чисел, два списка значений через запятую или два списка. Результат может быть возвращен или записан в STDOUT.

Вы можете предположить, что объекты находятся на расстоянии не менее 10 ^-10 единиц или слишком сильно пересекаются, поэтому вам не нужно беспокоиться об ограничениях типов с плавающей запятой.

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

Тестовые случаи

Представляя линейные сегменты с 0дисками и с 1полостями 2, используя формат ввода на основе списка, все следующее должно давать достоверный вывод:

[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

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}

Разрывы строк в функции fприведены для ясности. Они должны быть заменены разделителем операторов⋄

Прошло так много времени с тех пор, как я последний раз делал такую ​​сложную программу APL. Я думаю, что в прошлый раз было это, но я даже не уверен, что это было так сложно.

Формат ввода
В основном такой же, как у OP, за исключением использования 0для полости, 1для диска и 2для линейного сегмента.

Основное обновление

Мне удалось сыграть много символов, используя другой алгоритм. Нет больше gбыков ** т!

Основная функция fделится на случаи:

2 2≡x: Сегмент-сегмент

В этом случае рассчитайте вектор из конечных точек каждой линии и решите систему линейных уравнений, чтобы проверить, содержится ли пересечение в векторах.

Предостережения:

• Конечная точка вектора не рассматривается как часть вектора (тогда как его начало). Однако, если на другом участке находится только верхушка вектора, входные данные недопустимы в соответствии со спецификацией.
• Невырожденные параллельные сегменты всегда возвращают false, независимо от коллинеарности.
• Если один из сегментов вырожден, всегда возвращайте false. Если оба сегмента вырождены, всегда возвращайте true.

Примеры: (Обратите внимание на предостережение 1 в действии на рисунке справа)

2≡2⌷x: Сегмент-другой

В этом случае другой объект является круглым. Проверьте, находятся ли конечные точки сегмента внутри круга, используя проверку расстояния.

В случае с диском также строят отрезок линии диаметром, перпендикулярным данному отрезку. Проверьте, сталкиваются ли сегменты по рекурсии.
В случае с полостью крадитесь в «0 раз» в конструкции указанного сегмента, чтобы сделать его вырожденным. (Смотрите, почему я сейчас использую 0для резонатора и 1для диска?) Поскольку данный сегмент не вырожден, обнаружение столкновений сегментов и сегментов всегда возвращает false.

Наконец, объедините результаты проверки расстояния и обнаружения столкновений. Для случая с полостью сначала отмените результаты проверки расстояния. Затем (в обоих случаях) ИЛИ 3 результата вместе.

Что касается предостережений сегмента-сегмента, номера 3 адресованы (и эксплуатируются). Число 2 не является проблемой, поскольку мы пересекаем здесь перпендикулярные отрезки, которые никогда не параллельны, если они не вырождены. Номер 1 вступает в силу только в случае диска, когда одна из заданных конечных точек находится на расчетном диаметре. Если конечная точка находится в пределах круга, проверки расстояния позаботятся об этом. Если конечная точка находится на окружности, так как построенный диаметр параллелен данному сегменту, последний должен касаться окружности только с одной точкой, касающейся диска, что не является допустимым вводом.

Примеры:

Случай по умолчанию: Другое-Другое

Рассчитайте расстояние между центрами. Столкновение диска с диском происходит тогда и только тогда, когда расстояние меньше суммы радиусов. Столкновение диска с полостью происходит тогда и только тогда, когда расстояние больше, чем разница в радиусах.

Чтобы позаботиться о случае полость-полость, отмените результат проверки расстояния И с каждым из идентифицирующих целых чисел, а затем ИЛИ их вместе. Используя некоторую логику, можно показать, что этот процесс возвращает истину тогда и только тогда, когда оба идентифицирующих целых числа являются ложными (случай с полостью резонатора) или если проверка расстояния вернула истину

Javascript - 393 байта

уменьшенная:

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]);

Заметки:

• определяет функцию, Fкоторая принимает требуемые аргументы и возвращает требуемое значение
• Формат ввода идентичен формату в OP, за исключением того, что код целочисленного типа для каждого примитива отделен от кортежа. Например, F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )или F( 1,[[3,0],1], 2,[[0,0],1] ).
• код подтвержден на всех тестовых примерах, представленных в OP
• должен обрабатывать все ребра и углы, включая отрезки нулевой длины и окружности нулевого радиуса

Питон, 284

Я использую симпатичный алгоритм мусора по сравнению со всеми этими геометрическими уловками, но он получает правильные ответы, хотя и проходит более минуты, чтобы пройти тестовые случаи. Большим преимуществом является то, что мне нужно написать только три функции подсчета очков, а Hillclimbing заботится обо всех крайних случаях.

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

И, наконец, тестовый скрипт на тот случай, если кто-то захочет попробовать это на 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)