Ще один алгоритм визначення перетину двох відрізків

Ще один алгоритм визначення перетину двох відрізків +6

  • 29.09.15 12:31 •
  • SemenovVV •
  • # 267461 •
  • Хабрахабр •
  • 19 •
  • 12414

- такий же як Forbes, тільки краще.

Нещодавно була публікація «Простий алгоритм визначення перетину двох відрізків». Я вирішив спробувати вирішити задачу перетину двох відрізків трохи по-іншому, більш геометрично.

Знаходження точки перетину двох відрізків.

Маємо 2 відрізка і, де P0, P1, P2, P3 точки на площині. Будемо позначати x y координати точки P як P.x і P.y
Маємо координати 4 точок в масиві P (0..3) структури point (x float, y float):

Крок 1 - Перенесення початку координат.


Крок 2 - Поворот початку координат
Повернемо систему координат так, щоб відрізок прийняв вертикальне положення (ліг на вісь Y). Обчислимо довжину відрізка як:
L1 = SQRT ((P (1) .x) ^ 2 + (P (1) .y) ^ 2)
Синус і косинус кута alfa повороту осей координат:


Знову перераховуємо координати точок P1, P2, P3:


Крок 3 - Пошук точки перетину відрізків.

Запишемо рівняння відрізка і знайдемо точку його перетину CR з віссю Y:

P23X = P (2) .x + (P (3) .x - P (2) .x) * beta
P23Y = P (2) .y + (P (3) .y - P (2) .y) * beta
де 0 <= beta <= 1

У точці CR перетину відрізка з віссю Y:
P (2) .x + (P (3) .x - P (2) .x) * beta = 0
Далі можливі 2 варіанти в залежності від значення P (3) .x - P (2) .x:

Якщо P (2) .x = P (3) .x, то це означає, що відрізок вертикальний і паралельний відрізку. Перетин відрізків можливо тільки якщо другий відрізок теж лежить на осі Y, і один з його кінців лежить в першому відрізку (або стосується) або відрізок накриває. Будемо вважати що для результату нам достатньо однієї точки. Це буде одна з точок P0..P3.

Якщо точка перетину CR знайдена за варіантом 1 кроку 3, то її координати перераховуємо для вихідної системи координат. Використовуємо змінні збережені на 1 і 2 кроці. Поворот на кут -alfa:


Якщо точка перетину CR знайдена за умовою 2 кроку 3 перерахунок координат не потрібен. Приклад коду на golang під катом. Golang му я тільки зловживаю, тому до коду прошу бути поблажливим. Код можна запустити на golang.org:

Зараз буквально на коліні прикинув метод перевірки наявності перетину.
Якщо в рівняння прямої, підставити точку, то знак результату покаже нам, в який полуплоскости знаходиться ця точка щодо цієї прямої.

Щоб відрізки, що не лежать на одній прямій, перетиналися, потрібно, щоб кінці кожного з них знаходилися в різних півплощинах щодо прямої, що включає інший відрізок.

Обчислювальну складність не прикидав, але, думаю, при належній оптимізації повинно вийти добре.

Так, це хороший спосіб. Але потрібно ще врахувати випадок, коли точка кінця одного відрізка буде лежати на прямій іншого.
Якщо формалізувати, то отримаємо:
1. Дано два відрізки (x11, y11) - (x12, y12) і (x21, y21) - (x22, y22)
2. Проведемо через ці відрізки прямі a1 * x + b1 * y + c1 = 0 і a2 * x + b2 * y + c2 = 0
3. Тоді відрізки перетинаються, якщо (a1 * x21 + b1 * y21 + c1) * (a1 * x22 + b1 * y22 + c1) <= 0 и
(A2 * x11 + b2 * y11 + c2) * (a2 * x12 + b2 * y12 + c2) <= 0
Все просто і логічно

Схожі статті