forum.boolean.name - Формула, нахождения пересечения прямых линий, и их точки пересечения.

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

Формула, нахождения пересечения прямых линий, и их точки пересечения.

Я вот уже давненько ищю хоть концепцию реализации подобной функции, думаю есть и просто формула, но найти пока е удалось.

Мне нужна функция которая будет возвращать, пересекаються ли 2 линии, указав координаты их точек.
И нужна функция нахождения координат точки пересечения.

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

Буду весьма преблагодарен!
Жду с нетерпением :)

Re: Формула, нахождения пересечения прямых линий, и их точки пересечения.

А вот и имплементация:

Код:

Global Px#, Py#



Function LineLineIntersect(L1x1, L1y1, L1x2, L1y2, L2x1, L2y1, L2x2, L2y2)

        Local L2x2_L2x1# = L2x2 - L2x1

        Local L2y2_L2y1# = L2y2 - L2y1

        Local L1x2_L1x1# = L1x2 - L1x1

        Local L1y2_L1y1# = L1y2 - L1y1

        Local Den# = L2y2_L2y1 * L1x2_L1x1 - L2x2_L2x1 * L1y2_L1y1

        If (Den <> 0) Then

                Local L1x1_L2x1# = L1x1 - L2x1

                Local L1y1_L2y1# = L1y1 - L2y1

                Local Ua# = (L2x2_L2x1 * L1y1_L2y1 - L2y2_L2y1 * L1x1_L2x1) / Den

                Local Ub# = (L1x2_L1x1 * L1y1_L2y1 - L1y2_L1y1 * L1x1_L2x1) / Den

                If (Ua > 0) And (Ua < 1.0) And (Ub > 0) And (Ub < 1.0) Then

                        Px = L1x1 + Ua * L1x2_L1x1

                        Py = L1y1 + Ua * L1y2_L1y1

                        Return True

                EndIf

        EndIf

        Return False

End Function



Graphics(640, 480, 16, 2)

SetBuffer(BackBuffer())



Repeat



        If KeyHit(57) Then

                Cls()

                L1x1 = Rand(1, 639)

                L1y1 = Rand(1, 479)

                L1x2 = Rand(1, 639)

                L1y2 = Rand(1, 479)

                Color(0, 0, 255)

                Line(L1x1, L1y1, L1x2, L1y2)

                

                L2x1 = Rand(1, 639)

                L2y1 = Rand(1, 479)

                L2x2 = Rand(1, 639)

                L2y2 = Rand(1, 479)

                Color(0, 255, 0)

                Line(L2x1, L2y1, L2x2, L2y2)

                

                If LineLineIntersect(L1x1, L1y1, L1x2, L1y2, L2x1, L2y1, L2x2, L2y2)

                        Color(255, 0, 0)

                        Oval(Px - 4, Py - 4, 8, 8)

                EndIf

        EndIf

        

        Flip()

Until KeyDown(1)

End

немного нечитабельно из-за оптимизации, но думаю сойдет :)

Re: Формула, нахождения пересечения прямых линий, и их точки пересечения.

Огромное спасибо, домой приду и буду ковырять! :)