Учитывая точки линии и квадратичную кривую Безье, как рассчитать их ближайшую точку? .... Точно так же, учитывая точки 2 кривых, как вы получите ближайшую точку?
Вот моя попытка. Следующие алгоритмы далеки от совершенства , но они просты, и я считаю, что вам следует начать с этого, проверить, работают ли они в вашей ситуации, и переключиться на что-то более быстрое и / или более точное позже.
Идея заключается в следующем:
Пример кривой Безье, найти ближайшую точку на этом образце
Пример окрестности вокруг найденной точки, найти новую ближайшую точку
Продолжайте, пока точка больше не изменится
Алгоритм расстояния от кривой Безье до линии
Кривая Безье параметризуется функцией, F(t)использующей набор контрольных точек и переменный параметр t. Количество генерирующих очков неважно.
Линия параметризуется двумя точками Aи B.
Пусть SAMPLES = 10например
Начните с t0 = 0иt1 = 1
Позволять dt = (t1 - t0) / SAMPLES
Если dt < 1e-10(или любое другое условие точности вы посчитаете нужным), алгоритм закончен и ответF(t0) .
Вычислить список SAMPLES + 1точек на кривой Безье:
L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
...
L[SAMPLES] = F(t0 + SAMPLES * dt)
Найти, какая точка Lс индексом iближе всего к линии. Используйте любой метод расстояния между точками и линиями, который вы знаете, например, квадратное расстояние, ||AB^L[i]A||² / ||AB||²где ^обозначает перекрестное произведение и ||…||является расстоянием.
Если i == 0установить i = 1; если i == SAMPLESустановитьi = SAMPLES - 1
Пусть t1 = t0 + (i + 1) * dtиt0 = t0 + (i - 1) * dt
Вернитесь к шагу 3.
Алгоритм расстояния от кривой Безье до кривой Безье
На этот раз у нас есть две кривые Безье, параметризованные F(t)и G(t).
Пусть SAMPLES = 10например
Начните с t0 = 0, t1 = 1, s0 = 0иs1 = 1
Позволять dt = (t1 - t0) / SAMPLES
Позволять ds = (s1 - s0) / SAMPLES
Если dt < 1e-10(или любое другое условие точности вы посчитаете нужным), алгоритм закончен и ответF(t0) .
ЕСЛИ это первый запуск цикла:
6.1. Вычислить список SAMPLES + 1точек F( см. Выше ).
6.2. Вычислить список SAMPLES + 1точек наG .
6.3. Найдите, какая пара точек ближе всего друг к другу.
6.4. Обновление t0, t1, s0, s1как показано выше.
ELSE : в качестве альтернативы вычислить список точек на FOR список точек G, а затем найти какой точке Fнаходится ближе всего к G(s0)и обновлению t0и t1, ИЛИ какая точка Gнаходится ближе всего к F(t0)и обновлению s0и s1.
Вернитесь к шагу 3.
вопросы
По своей структуре эти алгоритмы всегда будут сходиться к локальному минимуму. Тем не менее, нет никакой гарантии, что они сойдутся к лучшему решению. В частности, алгоритм кривой Безье совсем не очень хорош, и в случае, когда две кривые находятся близко друг к другу во многих местах, вы, к сожалению, можете пропустить решение в долгосрочной перспективе.
Но, как я уже сказал, прежде чем начать думать о более надежных решениях, вы должны сначала поэкспериментировать с этими простыми.
1) Переведите все на одну ось, поэтому вместо необходимости вычислять длину одной точки, «линия», «линия» - это, скажем, ось Y.
Тогда, учитывая кривую Безье, я бы сказал, что все зависит от количества контрольных точек.
Если их три (начало, «контроль» и конец), я бы сделал какое-то сканирование (скажем, каждый на пару процентов, а затем уточнил бы между ближайшими (скажем, «двоичный» подход).
Больше очков я бы опробовал пару, которая была ближе всего к (переводится по оси Y).
Я уверен, что математик может дать вам точное решение (по математике), но если вы хотите найти решение / в видеоигре, вам может быть лучше, если решение будет немного нормальным, поскольку реальное решение может содержать несколько ответов ( Я даже не говорю о вычислительной мощности).
пс. 2 кривых, даже не думайте об этом (вы можете получить что-нибудь (по крайней мере, так же, как и ..) в зависимости от количества контрольных точек)
Valmond
0
Некоторые ответы со страницы блога Algorithmist , которая правильно находит ближайшую точку на заданной квадратичной кривой Безье.
Для кривой Безье - случай прямой линии, наиболее точный способ найти ответ заключается в следующем:
Преобразуйте задачу так, чтобы прямая линия всегда была горизонтальной при Y = 0. Это делается путем умножения всех контрольных точек на соответствующую аффинную матрицу. (Я предполагаю, что вы знакомы с представлением аффинных преобразований плоскости с матрицами 3x3 с 3 фиксированными записями.)
Проверьте координаты Y контрольных точек. Если они не имеют одинаковый знак, может быть пересечение с линией. Вычислить корни Y части кривой Безье. Вы можете использовать любой метод поиска корней для полиномов, их много в литературе. Например, гугл «выпуклый корпус» - это достаточно хороший метод для полиномов, используемых в кривых Безье. Каждый корень, который вы найдете, является значением времени пересечения с линией, где расстояние равно нулю - ваша работа выполнена.
Если все координаты Y имеют один и тот же знак, вычислите производную части Y кривой Безье. Вы можете игнорировать координаты X точек, поскольку они не имеют значения - линия цели горизонтальна. Найти корни этой производной. Это значения времени, в которые кривая локально находится ближе всего к линии.
Точно оцените кривую Безье для всех корней, которые вы нашли в предыдущем шаге, и сообщите корень, который дает наименьшее расстояние от линии. Вам также необходимо проверить конечные точки - они могут дать меньшее расстояние, чем любой корень.
Ответы:
Вот моя попытка. Следующие алгоритмы далеки от совершенства , но они просты, и я считаю, что вам следует начать с этого, проверить, работают ли они в вашей ситуации, и переключиться на что-то более быстрое и / или более точное позже.
Идея заключается в следующем:
Алгоритм расстояния от кривой Безье до линии
Кривая Безье параметризуется функцией,
F(t)
использующей набор контрольных точек и переменный параметрt
. Количество генерирующих очков неважно.Линия параметризуется двумя точками
A
иB
.Пусть
SAMPLES = 10
напримерНачните с
t0 = 0
иt1 = 1
Позволять
dt = (t1 - t0) / SAMPLES
Если
dt < 1e-10
(или любое другое условие точности вы посчитаете нужным), алгоритм закончен и ответF(t0)
.Вычислить список
SAMPLES + 1
точек на кривой Безье:L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
L[SAMPLES] = F(t0 + SAMPLES * dt)
Найти, какая точка
L
с индексомi
ближе всего к линии. Используйте любой метод расстояния между точками и линиями, который вы знаете, например, квадратное расстояние,||AB^L[i]A||² / ||AB||²
где^
обозначает перекрестное произведение и||…||
является расстоянием.Если
i == 0
установитьi = 1
; еслиi == SAMPLES
установитьi = SAMPLES - 1
Пусть
t1 = t0 + (i + 1) * dt
иt0 = t0 + (i - 1) * dt
Вернитесь к шагу 3.
Алгоритм расстояния от кривой Безье до кривой Безье
На этот раз у нас есть две кривые Безье, параметризованные
F(t)
иG(t)
.Пусть
SAMPLES = 10
напримерНачните с
t0 = 0
,t1 = 1
,s0 = 0
иs1 = 1
Позволять
dt = (t1 - t0) / SAMPLES
Позволять
ds = (s1 - s0) / SAMPLES
Если
dt < 1e-10
(или любое другое условие точности вы посчитаете нужным), алгоритм закончен и ответF(t0)
.ЕСЛИ это первый запуск цикла:
6.1. Вычислить список
SAMPLES + 1
точекF
( см. Выше ).6.2. Вычислить список
SAMPLES + 1
точек наG
.6.3. Найдите, какая пара точек ближе всего друг к другу.
6.4. Обновление
t0
,t1
,s0
,s1
как показано выше.ELSE : в качестве альтернативы вычислить список точек на
F
OR список точекG
, а затем найти какой точкеF
находится ближе всего кG(s0)
и обновлениюt0
иt1
, ИЛИ какая точкаG
находится ближе всего кF(t0)
и обновлениюs0
иs1
.Вернитесь к шагу 3.
вопросы
По своей структуре эти алгоритмы всегда будут сходиться к локальному минимуму. Тем не менее, нет никакой гарантии, что они сойдутся к лучшему решению. В частности, алгоритм кривой Безье совсем не очень хорош, и в случае, когда две кривые находятся близко друг к другу во многих местах, вы, к сожалению, можете пропустить решение в долгосрочной перспективе.
Но, как я уже сказал, прежде чем начать думать о более надежных решениях, вы должны сначала поэкспериментировать с этими простыми.
источник
1) Переведите все на одну ось, поэтому вместо необходимости вычислять длину одной точки, «линия», «линия» - это, скажем, ось Y.
Тогда, учитывая кривую Безье, я бы сказал, что все зависит от количества контрольных точек.
Если их три (начало, «контроль» и конец), я бы сделал какое-то сканирование (скажем, каждый на пару процентов, а затем уточнил бы между ближайшими (скажем, «двоичный» подход).
Больше очков я бы опробовал пару, которая была ближе всего к (переводится по оси Y).
Я уверен, что математик может дать вам точное решение (по математике), но если вы хотите найти решение / в видеоигре, вам может быть лучше, если решение будет немного нормальным, поскольку реальное решение может содержать несколько ответов ( Я даже не говорю о вычислительной мощности).
источник
Некоторые ответы со страницы блога Algorithmist , которая правильно находит ближайшую точку на заданной квадратичной кривой Безье.
Demo .
источник
Для кривой Безье - случай прямой линии, наиболее точный способ найти ответ заключается в следующем:
источник