Как рассчитать ближайшую точку линии и кривой?.. или кривая и кривая?

Question

С учетом точек линии и квадратичной кривой Безье, как рассчитать их ближайшую точку?

Answer 1

Существует научная статья по этому вопросу от INRIA: Вычисление минимального расстояния между двумя кривыми Безье ( PDF здесь )

Answer 2

Я однажды написал инструмент для выполнения аналогичной задачи. Сплайны Безье обычно являются параметрическими кубическими полиномами. Чтобы вычислить квадрат расстояния между кубическим сегментом и линией, это просто квадрат расстояния между двумя полиномиальными функциями, сам по себе просто еще одна полиномиальная функция! Обратите внимание, что я сказал квадрат расстояния, а не квадратный корень.

По существу, для любой точки на кубическом отрезке можно вычислить квадрат расстояния от этой точки до линии. Это будет полином 6-го порядка. Можем ли мы минимизировать этот квадрат расстояния? Да. Минимум должен иметь место, когда производная этого многочлена равна нулю. Так дифференцируем, получая полином 5-го порядка Используйте ваш любимый инструмент поиска корней, который генерирует все корни в числовом виде. Дженкинс и Трауб, что угодно. Выберите правильное решение из этого набора корней, исключая любые решения, которые являются сложными, и выбирая решение, только если оно лежит внутри рассматриваемого кубического сегмента. Убедитесь, что вы исключаете точки, которые соответствуют локальным максимумам расстояния.

Все это может быть эффективно выполнено, и нет необходимости использовать итеративный оптимизатор, кроме полиномиального корневого искателя, поэтому не требуется использовать инструменты оптимизации, которые требуют начальных значений, находя только решение, близкое к этому начальному значению.

Например, на 3-м рисунке я показываю кривую, сгенерированную набором точек на 3-м (красным цветом), затем я взял другой набор точек, лежащих снаружи по кругу, я вычислил ближайшую точку на внутренней кривой от каждого, рисуя линию вниз к этой кривой. Эти точки минимального расстояния были получены по схеме, описанной выше.

Answer 3

В случае кривой Безье и линии

Есть три кандидата на ближайшую точку к линии:

1. Место на отрезке кривой Безье, параллельное прямой (если такое место существует),
2. Один конец сегмента кривой,
3. Другой конец сегмента кривой.

Проверьте все три; кратчайшее расстояние побеждает.

В случае двух кривых Безье

Зависит от того, хотите ли вы получить точный аналитический результат или достаточно хороший оптимизированный числовой результат.

Аналитический результат

С учетом двух кривых Безье A ( t ) и B ( с * 1040) *), вы можете вывести уравнения для их локальной ориентации A ' ( t ) и B ' ( s ). Точки пары, для которых A ' ( t ) = B ' ( s ) являются кандидатами, т. е. ( t , s ), для которых кривые локально параллельны. Я не проверял, но я предполагаю, что A ' ( t ) - B ' ( s ) = 0 можно решить аналитически. Если ваши кривые похожи на те, которые вы показываете в своем примере, должно быть либо только одно решение, либо никакого решения для этого уравнения, но их может быть два (или бесконечное множество в случае, когда кривые идентичны, но переведены - в этом случае Вы можете игнорировать это, потому что победителем всегда будет одна из конечных точек сегмента кривой).

В подходе, аналогичном описанному выше описанию случая линии кривой, проверьте каждую из этих пар точек, а также конечные точки сегмента кривой. Самое короткое расстояние побеждает.

Числовой результат

Допустим, точки на двух кривых Безье определены как A ( t ) и B ( s ). Вы хотите минимизировать расстояние d ( t , s ) = | A ( t ) - B ( с ) |. Это простая задача оптимизации с двумя параметрами: найдите s и t , которые минимизируют d ( t , s ) с ограничениями 0 ≤ t ≤ 1 и 0 ≤ s ≤ 1.

Поскольку d = SQRT ((xA - xB) ² + (yA - yB) ²), вы также можете просто свернуть функцию f ( t , s ) = [ d ( t , s )] ² для сохранения вычисления квадратного корня.

Для таких задач оптимизации существует множество готовых методов . Тщательно выбирать.

---

Обратите внимание, что в обоих вышеупомянутых случаях все, что более высокого порядка, чем квадратичные кривые Безье, может дать вам более одного локального минимума, так что на это стоит обратить внимание. Из приведенных вами примеров видно, что ваши кривые не имеют точек перегиба, поэтому эта проблема может быть неприменима в вашем случае.

Answer 4

Я просто хочу дать вам несколько советов, для случая Q.B.Curve // ​​сегмент: чтобы получить достаточно быстрое вычисление, я думаю, что вы должны сначала подумать об использовании своего рода «ограничивающей рамки» для вашего алгоритма. Скажем, P0 - первая точка Q. B. Кривая, P2 - вторая точка, P1 - контрольная точка, а P3P4 - сегмент:

1. Вычислить расстояние от P0, P1, P2 до P3P4
2. , если P0 ИЛИ P2 - ближайшая точка -> это ближайшая точка кривой от P3P4. конец: =).
3. если P1 является ближайшей точкой, а Pi (i = 0 или 1) второй ближайшей точкой, расстояние между PiPC и P3P4 является оценкой искомого расстояния, которое может быть достаточно точным, в зависимости от на ваши нужды.
4. если вам нужно быть более точным: вычислите P1 ', которая является точкой на Q.B.Curve, ближайшей к P1: вы обнаружите, что она применяет формулу BQC с t = 0,5. -> расстояние от PiP1 'до P3P4 является еще более точной оценкой, но более дорогостоящим.
5. Обратите внимание, что если линия, определенная P1P1 ', пересекает P3P4, P1' является ближайшей точкой QBC от P3P4.
6. если P1P1 'не пересекает P3P4, значит, вам не повезло, вы должны идти нелегким путем ...

Теперь, если (и когда) вам нужна точность:

Подумайте об использовании алгоритма «разделяй и властвуй» для параметра кривой: который ближайший от P3P4 ?? P0P1 'или P1'P2 ??? если это P0P1 '-> t находится между 0 и 0,5, то вычислите Pm для t = 0,25. Теперь, что является ближайшим от P3P4 ?? P0Pm или PmP1 '?? если это PmP1 '-> вычислить Pm2 для t = 0,25 + 0,125 = 0,375, то какой из них ближайший? PmPm2 или Pm2P1 '??? так далее Вы сразу же получите точное решение, например, 6 итераций, а ваша точность на t равна 0,004 !! Вы можете остановить поиск, когда расстояние между двумя точками станет ниже заданного значения. (а не разница между двумя параметрами, так как для небольшого изменения параметра точки могут быть далеко) на самом деле принцип этого алгоритма состоит в том, чтобы каждый раз аппроксимировать кривую с сегментами все более и более точно.

Для случая кривой / кривой я бы сначала «поставил» их в квадрат, чтобы избежать ненужных вычислений, поэтому сначала используйте вычисление сегмента / сегмента, а затем (возможно) вычисление сегмента / кривой и только при необходимости вычисление кривой / кривой.

Для кривых / кривых, разделяй и властвуй также труднее объяснить, но вы можете понять это. : =)

надеюсь, вы сможете найти хороший баланс для скорости / точности с этим: =)

Edit: думаю, я нашел для общего случая хорошее решение :-) Вы должны перебрать (внутренние) ограничивающие треугольники каждого B.Q.C. Таким образом, у нас есть треугольник T1, точки A, B, C, имеющие параметр «t» tA, tB, tC. и треугольник T2, точки D, E, F, имеющие t-параметр tD, tE, tF. Первоначально имеем tA = 0 tB = 0,5 tC = 1,0 и то же самое для T2 tD = 0, tE = 0,5, tF = 1,0 Идея состоит в том, чтобы рекурсивно вызывать процедуру, которая разделит T1 и / или T2 на более мелкие прямоугольники, пока мы не будем в порядке с достигнутой точностью. Первым шагом является вычисление расстояния от T1 до T2, отслеживая, чтобы сегменты были ближайшими в каждом треугольнике. Первый «трюк»: если на T1 сегмент AC, то остановите рекурсивность на T1, ближайшая точка на кривой 1 - это A или C. Если на T2 ближайший сегмент - DF, то остановите рекурсивность на T2, ближайшая точка на Кривая 2 - это либо D, либо F. Если мы остановили рекурсивность для обоих -> расстояние возврата = min (AD, AF, CD, CF). тогда, если у нас есть рекурсивность на T1, и сегмент AB ближайший, новый T1 становится: A '= AB = точка кривой с tB = (tA + tC) / 2 = 0,25, C = старая B. То же самое относится и к T2: применить рекурсивность, если необходимо, и вызвать тот же алгоритм на новом T1 и новом T2 Остановите алгоритм, когда найденное расстояние между T1 и T2 минус расстояние, найденное между предыдущими T1 и T2, ниже порогового значения. функция может выглядеть как ComputeDistance (curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance), где точки хранят также свои t-параметры.

обратите внимание, что расстояние (кривая, сегмент) является лишь частным случаем этого алгоритма, и что вы должны реализовать расстояние (треугольник, треугольник) и расстояние (сегмент, треугольник), чтобы он работал. Веселитесь.

Answer 5

Сформулируйте вашу проблему в терминах стандартного анализа: у вас есть величина для минимизации (расстояние), поэтому вы формулируете уравнение для этой величины и находите точки, где первые производные равны нулю.Параметризация осуществляется с помощью одного параметра, используя параметр кривой p, который находится между 0 для первой точки и 1 для последней точки.

В случае линии уравнение довольно простое: получить координаты x / y из уравнения сплайна и вычислить расстояние до данной линии с помощью векторных уравнений (скалярное произведение с нормалью линии).

В случае кривой аналитическое решение может быть довольно сложным.Возможно, вы захотите использовать метод числовой минимизации, такой как Nelder-Mead или, поскольку у вас есть одномерная непрерывная задача, простой деление пополам.

Answer 6

1.Простой неверный метод - путем итерации переходите по точке от первой кривой и переходите по точке от второй кривой и получайте минимум. 2. Определите математическую функцию расстояния между кривыми и предел вычисления этой функции, например:

| Fcur1 (т) -Fcur2 (т) |-> 0

Fs - вектор.

Я думаю, что мы можем вычислить производную этого для определения экстремумов и получить ближайшие и самые отдаленные точки

Я думаю об этом через некоторое времяи отправьте полный ответ.

Answer 7

Точка, в которой совпадают нормали, является их ближайшей точкой.Я имею в виду, вы рисуете линию, ортогональную к линии.. если эта линия также ортогональна кривой, то точка пересечения является ближайшей точкой