Пересечение двух отрезков

Fido Themes (ru.algorithms)

От: Pavel Kuprianov <Pavel.Kuprianov@p4.f2096.n5020.z2.fidonet.org>
Тема: пересечение
Дата: 23 марта 2001 г. 20:40

Welcome to Hell o All! Эта сущность приветствует тебя.

Hужен алгоритм сабжа двух отрезков (проверить пересекаются или нет и найти точку пересечения). С прямыми довольно просто, а отрезки? Отрезки задаются в виде координат.

See you All, sooner or later
And now press "CTRL+F15"

От: Andrey Popov <Andrey.Popov@p63.f100.n452.z2.fidonet.org>
Тема: пересечение
Дата: 24 марта 2001 г. 8:13

----¬
¦ -¬¦pивет, Pavel!
L--L+--------------------------------------------------Hа-этом-все-и-началось-

PK> Hужен алгоритм сабжа двух отрезков (проверить пересекаются или нет и
PK> найти точку пересечения). С прямыми довольно просто, а отрезки?
PK> Отрезки задаются в виде координат.

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

До скорых писем, Andrey.
... nr: "Дневной дозоp"

От: homa <homa@f50.n5085.z2.fidonet.org>
Тема: Re: пересечение
Дата: 24 марта 2001 г. 13:26

-= Pavel Kuprianov -> All (03.23.2001, 07:40PM) =-

PK> Hужен алгоритм сабжа двух отрезков (проверить пересекаются или нет и найти
PK> точку пересечения). С прямыми довольно просто, а отрезки? Отрезки задаются
PK> в виде координат.

неужели три минуты школьной математики - подвиг?

даны отрезки (Xa, Ya)-(Xb, Yb) и (Xc, Yc)-(Xd, Yd).

зададим их параметрически:

x = (1-p)*Xa + p*Xb x = (1-q)*Xc + q*Xd
y = (1-p)*Ya + p*Yb (1) y = (1-q)*Yc + q*Yd (2),

где 0<=p<=1, 0<=q<=1 (3)

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

(1-p)*Xa + p*Xb = (1-q)*Xc + q*Xd
(1-p)*Ya + p*Yb = (1-q)*Yc + q*Yd

после несложных преобразований (проверь, а то я в уме их делал) имеем:

(Xd-Xc)(Yc-Ya) - (Yd-Yc)(Xc-Xa) (Xb-Xa)(Yc-Ya) - (Yb-Ya)(Xc-Xa)
p = -------------------------------, q = -------------------------------, (4)
D D

где D = (Xd-Xc)(Yb-Ya) - (Yd-Yc)(Xb-Xa).

если D<>0, то по формулам (1) или (2) находим координаты единственной точки
если D<>пересечения прямых, содержащих отрезки, а условия (3) позволяют
если D<>проверить ее принадлежность отрезкам.

если D=0, то отрезки параллельны. если числители в (4) ненулевые, то пересечений нет. если же они нулевые, то отрезки коллинеарны, и две средних точки из четырех, задающих концы отрезков, определяют начало и конец общей части отрезков. чтобы найти эти две средние точки, достаточно отбросить самую левую и самую правую из четырех (или верхнюю и нижнюю, если все четыре лежат на одной вертикали).