Как найти, пересекаются ли два отрезка (не две прямые линии)

Question

Я хочу найти способ проверить, пересекаются ли два сегмента линий или нет. Я использую программирование Xlib для его реализации.

Я проверил в Интернете, но я нашел способы найти точку пересечения двух линий, но не двух сегментов линии.

Как я могу реализовать это с помощью программирования X lib?

Answer 1

Для этого вам не нужен Xlib. Пусть два сегмента будут

• A1 = (x1, y1) ->B1 = (x1 + dx1, y1 + dy1) и
• A2 = (x2, y2) ->B2 = (x2 + dx2, y2 + dy2).

Пусть

• vp = dx1 * dy2 - dx2 * dy1

Если vp == 0 сегменты параллельны и нет никакого пересечения.

В противном случае, пусть v = (vx, vy) быть вектор между A1 и A2

• vx = x2 - x1
• vy = y2 - y1

Compute

• k1 = (vx * dy2 - vy * dx2)/vp
• k2 = (vx * dy1 - vy * dx1)/vp

Если какая-либо k1 или k2 выходят за пределы интервала [0, 1], отрезки не пересекаются (но основные линии пересекаются). В противном случае, пересечение в

(x1 + k1 * dx1, y1 + k1 * dy1)

который, кстати, если вам интересно, о симметрии, будет та же точка, как

(x2 + k2 * dx2, y2 + k2 * dy2)

Эти формулы в основном аналогично ответу на How do you detect where two line segments intersect? за исключением кодирование оттуда не обязательно было бы тривиальным ни для новичков, ни для кого-то в спешке (например, я был сам много раз).