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

Добавлен , опубликован
Алгоритмы, Наработки и Способности
Способ реализации:
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
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
27
4 года назад
0
эх... почему-то у меня алгоритмы точек пересечения работают не стабильно
2
32
4 года назад
2
Есть функция в worm war - от близардов, там работает.
1
27
4 года назад
Отредактирован MpW
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
Загруженные файлы
0
28
4 года назад
0
Потому что векторы нужно использовать.
0
27
4 года назад
Отредактирован MpW
0
это тоже не работает как надо (
0
28
4 года назад
0
Steal nerves, а как надо?
0
27
4 года назад
Отредактирован MpW
0
функция InterLineLine дает больше точек пересечения, чем должны быть.
если отверстия застраивать, то нечестный обуз игры будет
карту пример скинул
Загруженные файлы
0
28
4 года назад
0
Steal nerves, я думал, ты про векторы сказал. А ты, видимо, про алгоритм из карты близов.
0
27
4 года назад
Отредактирован MpW
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
Загруженные файлы
2
28
4 года назад
Отредактирован PT153
2
С векторами я перепутал с другой задачей, но тут тоже можно.
Можно воспользоваться вот этим сайтом.
раскрыть
Перед всем этим нужно убедиться, что отрезки действительно пересекаются, причём точка пересечения одна.

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))
Загруженные файлы
5
17
4 года назад
Отредактирован GetLocalPlayer
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
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.