» WarCraft 3 / 3д камера как в WoW

» Dune the Endless Wars / Обновлениям - быть

» Dune the Endless Wars / Обновлениям - быть

» WarCraft 3 / Глобальные переменные и их количество

Save Handle of Unit as StringHash("Target") of StringHash("MyDickLightning") in AbilityTable

» WarCraft 3 / Hashtable 8000

» WarCraft 3 / Пересечение двух отрезков

Steal nerves:

как векторы помогут найти точку пересечения?

Что же, давай рассмотрим этот вопрос подробнее

Прелюдия

Проилюстрируем два отрезка, один образованный точками 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

» Dota 2 / Dota 2 Classic

» WarCraft 3 / Проблема с картой

» WarCraft 3 / Warcraft 3 Reforged: Патч 1.32.9

» WarCraft 3 / Warcraft 3 Reforged: Патч 1.32.9

» WarCraft 3 / Warcraft 3 Reforged: Патч 1.32.9

» WarCraft 3 / Warcraft 3 Reforged: Патч 1.32.9

» WarCraft 3 / Reforged - мышь в центре экрана

» WarCraft 3 / Reforged - мышь в центре экрана

» WarCraft 3 / Релиз Warcraft 3: Reforged

replaceabletextures\commandbuttons\

_hd.w3mod:replaceabletextures\commandbuttons\

» WarCraft 3 / Unseen (клип) (цветной)

» WarCraft 3 / [Lua] Универсальный каст

» WarCraft 3 / Редактор кода vJass в рефоржеде

//! import "my_script.j"

» WarCraft 3 / Изменение сопротивления магии в 1.32?

» WarCraft 3 / Изменение сопротивления магии в 1.32?