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

» опубликован
» Способ реализации: vJass
» Тип: Алгоритм
Функия проверяет отрезки на пересечения, если они пересекаются, то функция возвращяет true и устанавливает в глобалке точку пересечения.
globals
    real x
    real y
endglobals

function linecrossline takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4 returns boolean
    local real i = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
    local real lx = 0.00
    local real ly = 0.00
    if i == 0.00 then
    else
        set lx = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/i
        set ly = ((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/i
        if lx <= 0.00 and ly <= 0.00 and lx >= 1.00 and ly >= 1.00 then
        set x = x1+lx*(x2-x1)
        set y = y1+ly*(y2-y1)
        return true
        endif
    endif
    return false
endfunction


Просмотров: 1 605

» Лучшие комментарии


МрачныйВорон #1 - 8 месяцев назад 0
эта функция работает?
например здесь вернет false, ибо i == 0.00:
отрезок x1= 0; y1=0; x2=0; y2=100
отрезок x3=50; y3=50; x4=-50; y4=50
большая часть вычислении возвращает false, наверн просто в координатах нули


» алгоритм: проверка на пересечение отрезков
function CrossLines takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4 returns boolean
return (((x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)) * ((x4-x1)*(y2-y1) - (y4-y1)*(x2-x1)) <= 0) and (((x1-x3)*(y4-y3) - (y1-y3)*(x4-x3)) * ((x2-x3)*(y4-y3) - (y2-y3)*(x4-x3)) <= 0)
endfunction
» алгоритм: точка пересечения
function LineIntersect  takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4 returns nothing

local real LDetLineA = x1*y2 - y1*x2
local real LDetLineB = x3*y4 - y3*x4
local real LDiffLAx = x1 - x2
local real LDiffLAy = y1 - y2
local real LDiffLBx = x3 - x4
local real LDiffLBy = y3 - y4
local real LDetDivInv = 1 / ((LDiffLAx*LDiffLBy) - (LDiffLAy*LDiffLBx))
local real x = ((LDetLineA*LDiffLBx) - (LDiffLAx*LDetLineB)) * LDetDivInv
local real y = ((LDetLineA*LDiffLBy) - (LDiffLAy*LDetLineB)) * LDetDivInv

call DisplayTextToForce( GetPlayersAll(), "точка пересечения: " + R2S(x) + " , " + R2S(y) )
endfunction
кому надо сам на глобалки x,y перепишет, тк вар не может возвращать два значения
ссылка

МрачныйВорон #2 - 5 месяцев назад 0
эх... почему-то у меня алгоритмы точек пересечения работают не стабильно
quq_CCCP #3 - 5 месяцев назад 2   
Есть функция в worm war - от близардов, там работает.
МрачныйВорон #4 - 5 месяцев назад (отредактировано ) 1   
вот пример хотел показать
тфу четвертый случай, ладно посмотрю карту червей

» в карте worm war вот такая функция (вполне рабочая)
function InterLineLine takes real x1, real y1, real x2, real y2, real a1, real b1, real a2, real b2, location loc returns boolean
    local real p = (x2-x1)*(b2-b1)-(y2-y1)*(a2-a1)
    local real x
    local real y

    if ( p == 0 ) then
        return false
    endif

    set x =  ((x2-x1)*(a2-a1)*(y1-b1)+(x2-x1)*(b2-b1)*a1-(y2-y1)*(a2-a1)*x1)/p
    set y = -((y2-y1)*(b2-b1)*(x1-a1)+(y2-y1)*(a2-a1)*b1-(x2-x1)*(b2-b1)*y1)/p
    call MoveLocation( loc, x, y )
    return true
endfunction
Прикрепленные файлы
PT153 #5 - 5 месяцев назад 0
Потому что векторы нужно использовать.
МрачныйВорон #6 - 5 месяцев назад (отредактировано ) 0
это тоже не работает как надо (
PT153 #7 - 5 месяцев назад 0
Steal nerves, а как надо?
МрачныйВорон #8 - 5 месяцев назад (отредактировано ) 0
функция InterLineLine дает больше точек пересечения, чем должны быть.
если отверстия застраивать, то нечестный обуз игры будет
карту пример скинул
Прикрепленные файлы
PT153 #9 - 5 месяцев назад 0
Steal nerves, я думал, ты про векторы сказал. А ты, видимо, про алгоритм из карты близов.
МрачныйВорон #10 - 5 месяцев назад (отредактировано ) 0
PT153, как векторы помогут найти точку пересечения? и разве до этого не векторы юзали

удлиняется отрезок подобно лучу
» подкрутил условие
if((a1<=x and x <=a2)or(a1>=x and x >=a2))and((b1<=y and y<=b2)or (b1>=y and y>=b2))then

endif
Прикрепленные файлы
PT153 #11 - 5 месяцев назад (отредактировано ) 1   
С векторами я перепутал с другой задачей, но тут тоже можно.
Можно воспользоваться вот этим сайтом.
Перед всем этим нужно убедиться, что отрезки действительно пересекаются, причём точка пересечения одна.

x = ((-x3 + x4) * (-x2 * y1 + x1 * y2) + (x1 - x2) * (-x4 * y3 + x3 * y4)) / (-(-x3 + x4) * (y1 - y2) + (-x1 + x2) * (y3 - y4))
y = (-(-x2 * y1 + x1 * y2) * (y3 - y4) + (y1 - y2) * (-x4 * y3 + x3 * y4)) / (-(-x3 + x4) * (y1 - y2) + (-x1 + x2) * (y3 - y4))
Прикрепленные файлы
GetLocalPlayer #12 - 5 месяцев назад (отредактировано ) 5   
как векторы помогут найти точку пересечения?
Что же, давай рассмотрим этот вопрос подробнее
» Прелюдия
Проилюстрируем два отрезка, один образованный точками A, B и второй, образованный точками C и D
Нам необходимо найти точку пересечения этих отрезков (если существует). Как это делается? Делается это путем низведения задачи до минимально возможных примитивов, решения задачи на этих примитивах и последующей проверкой полученного ответа в рамках исходной задачи.
В нашем случае, примитивами двух отрезков являются прямые. То есть, нам необходимо найти точку пересечения прямых, на которых лежат наши отрезки, а затем проверить, лежит ли найденная точка в пределах отрезков.
Пунктиром обозначены прямые, на которых лежат отрезки. Я так же буду использовать термин "прямые, пораждаемые отрезками".
» Шаг 1
Нам необходимо построить параметрическое уравнение для каждой из наших прямых. Параметрическое уравнение прямой выглядит следущим образом:
P = P1 + k * n
Где P - любая точка на прямой, описанная уравнением, P1 - известная точка на прямой, n - вектор, параллельный прямой, n - произвольный параметр.
Я не знаю, как можно в данном текстовом виде обозначить вектор, ибо форма записи со стрелочкой над буковкой мне недоступна, поэтому придется держать в уме, что вектора и параметры обозначаются строчными буками, а точки - прописными. Чтобы было проще отличить вектора от параметров, условимся, что параметр я всегда буду записывать слева, а вектор справа.
Как мы можем построить аналогичное уровнение для наших прямых? Для начала, было бы неплохо получить вектора, параллельные нашим прямым. Это может быть сделано путем вычитания координат точек наших отрезков. То есть, для отрезка AB, вектор будет иметь вид (B - A), а для отрезка CD (D - C)
В таком случае, мы можем составить уровнение для каждой прямой
A + k * (B - A)
C + n * (D - C)
Для простоты записи, обозначим вектор (B - A) как вектор a, и вектор (D - C) как вектор b
A + k * a
C + n * b
Таким образом мы можем составить систему уравнений
P = A + k * a
P = C + n * b
Где P, есть точка пересечения двух прямых, порожденных нашими отрезками. Осталось решить эту систему уравнений.
» Шаг 2
Итак, дана система уравнений
P = A + k * a
P = C + n * b
Чтобы найти точку пересечения P, нам необходимо найти неизвестный параметр k первой прямой, либо параметр n второй прямой. Я буду искать параметр k:
P = A + k * a
P = C + n * b

// Составим уравнение
A + k * a = C + n * b

// Решаем
k * a = C + n * b - A

// Видим, в правой половине у нас образуется вектор (C - A),
// для простоты записи, дадим ему имя c
k * a = n * b + c
Необходимо найти параметр k, для этого избавимся от n * b во второй половине уравнения. Сделать это можно путем скалярного произведения вектора b, на другой, перпендикурярный ему вектор (одно из определений скалярного произведения векторов гласит - произведение длин векторов на косинус угла между ними - следовательно, скалярное произведение перпендикулярных векторов дает 0, поскольку косинус 90 градусов равен нулю). Найти этот вектор мы можем путем простой перестановки координат x и y вектора b и изменением знака одной из этих координат. Назовем новый вектор b' (читать "б штрих") = (-b[y], b[x]).
k * a = n * b + c

// Находим скалярное произведение с обеих сторон
// на перпендикулярный вектор b'
k * (a • b') = (n * b + c) • b'
k * (a • b') = n * (b • b') + c • b'
k * (a • b') = c • b'

// Находим параметр k
k = (c • b') / (a • b')
Символ • есть символ скалярного произведения векторов, найдеюсь он корректно отображается в браузере.
Показанные выше вычисления могут показаться немного неожиданными для начинающего, как я тут выражаю ПАРАМЕТР, через ВЕКТОРА, да еще ДЕЛЮ вектора на вектора? Лишь напомню, что результатом скалярного произведения векторов есть скаляр (почему оно так и называется).
Готово, мы нашли формулу вычесления параметра k для прямой, поражденной отрезком AB. Теперь мы можем подставить этот параметр в изначальную формулу A + k * (B - A) и получить точку пересечения наших прямых.
» Шаг 3 (есть прямые, а нужны отрезки)
Изначальная задача требовала от нас поиска пересечения отрезков, а не прямых, мы же нашли точку пересечения прямых - бесконечных прямых, бесконечно длинных прямых. Теперь нам нужно проверить, принадлежит ли найденная точка обоим отрезкам. Как это сделать?
Если мы снова взглянем на параметрическое уравнение прямой
P = P1 + k * n
Мы сможем сделать следующий вывод - точка P1, это известная нам точка на прямой, вектор n, есть направляющий вектор до точки P, а параметр k, будет выступать длинной вектора n (или есть говорить совсем твердолобо - количество векторов n, которое помещается между точкой P1 и точкой P).
Вернемся к формуле прямой, поражденной отрезком AB
P = A + k * (B - A)
Где P - найденная нами точка пересечения прямых, A - начальная точка отрезка, k - найденный параметр, а (B - A) вектор из точки A в точку B. Поскольку, в нашем случае, вектор (B - A) был получен из координат точек отрезка, его длина соответствует длине отрезка. Это значит, что параметр k будет принимать значение от 0.0 до 1.0, если найденная точка пересечения P, лежит на отрезке. В противном случае, мы можем завершить наши вычисления, поскольку, хоть прямые и пересекаются, точка пересечения не лежит в пределах обоих отрезков одновременно.
Из этого можно сделать простой вывод, что необходимо решить систему уравнений повторно, выразив параметр n второй прямой, и проверив его на вхождение в диапазон от 0.0 до 1.0
P = A + k * a
P = C + n * b

C + n * b = A + k * a
n * b = A + k * a - C

// Запишем образующийся вектор (A - C) как d
n * b = k * a + d

// Избавимся от параметра k путем скалярного
// произведения вектора a на вектор a' = (-a[y], a[x])
n * (b • a') = (k * a + d) • a'
n * (b • a') = d • a'
n = (d • a') / (b • a')
Готово, теперь остается проверить параметр n на интервал от 0.0 до 1.0.
if k >= 0 and k <= 1 and n >= 0 and n <= 1 then
    // Точка пересечения прямых лежит в пределах
    // обоих отрезков.
    return true
else
    return false
endif
» Пара оговорок
В финале, хотелось бы добавить
  1. Мы могли бы отказаться от скалярного произведения на перпендикулярный вектор в пользу векторного произведения, но мне показалось, что это лишь усложнит понимание для неопытных пользователей.
  2. В процессе решения системы уравнений в первый раз, нам необходимо добавить проверку скалярного произведения вектора b' с обоими векторами (B - A) и (D - C), ведь если произведение вектора b' на вектор (B - A) дает нуль и на вектор (D - C) дает нуль, это значит что оба вектора перпендекулярны вектору b', а значит они параллельны и пересекаться не могут.
  3. Реализуя данный алгоритм в программе, помните о неточности чисел с плавающией точкой и вместо сравнения с нулем используйте сравнение модуля числа с каким-то минимильным значением, например Abs(x) < 0.0001
quq_CCCP #13 - 5 месяцев назад 1   
Кстати автору нужна IsLineCrossCircle ? То я как то выкладывал рельно рабочую функцию.
ScorpioT1000 #14 - 5 месяцев назад 1   
А можно было просто dgui vector взять, где всё уже реализовано
МрачныйВорон #15 - 5 месяцев назад 0
GetLocalPlayer, спасибо. интересный материал. Если что пригодиться =))
quq_CCCP, да я помню скидывал мне. К сожалению, я пока не нашел применения ему. Взаимодействую со прямыми сторонами многоугольника. но думаю мб пригодиться
» алгоритм пересечения круга
function Is2cc takes real r, real cx, real cy, real px1, real py1, real px2, real py2 returns boolean
        local real dx = 0.00 
        local real dy =  0.00 
        local real a =  0.00 
        local real b = 0.00  
        local real c = 0.00 
        
        set px1 = px1 - cx
        set py1 = py1 - cy
        set px2 = px2 - cx
        set py2 = py2 - cy
        set dx = px2 - px1
        set dy = py2 - py1
        set a = dx * dx + dy * dy
        set b = 2.00 * ( px1 * dx + py1 * dy )
        set c = px1 * px1 + py1 * py1 - r * r
        
        if ( -b < 0.00 ) then
            return ( c < 0.00 )
        elseif ( -b < ( 2.00 * a ) ) then
            return ( ( 4.0 * a * c - b * b ) < 0 )
        endif
        return ( a + b + c < 0 )
    endfunction
ScorpioT1000, что то действительно не знал, что в дгуи все это есть. включая пересечение векторов.