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

Ответ 1

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

• Вычислить расстояние от P0, P1, P2 до P3P4
• если P0 OR P2 - ближайшая точка → это ближайшая точка кривой из P3P4. end: =).
• если P1 - ближайшая точка, а Pi (i = 0 или 1) вторая ближайшая точка, расстояние между PiPC и P3P4 - это оценка расстояния, которое вы ищете, которое может быть достаточно точным, в зависимости от ваших потребностей.
• если вам нужно быть более четким: вычислите P1 ', который является точкой на Q.B.curve ближайшей от P1: вы найдете ее применив формулу BQC с t = 0,5. → расстояние от PiP1 'до P3P4 - еще более точная оценка - но более дорогостоящая -.
• Обратите внимание, что если строка, определенная P1P1 ', пересекает P3P4, P1' является ближайшей точкой QBC от P3P4.
• Если 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!! вы можете остановить поиск, когда расстояние между двумя точками становится ниже заданного значения. (а не разница между двумя параметрами, так как для небольшого изменения параметра точки могут быть далеко) на самом деле принцип этого алгоритма состоит в том, чтобы аппроксимировать кривую с сегментами все более точно каждый раз.

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

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

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

Изменить: Думаю, я нашел для общего случая приятное решение:-) Вы должны перебирать (внутренние) ограничивающие треугольники каждого B.Q.C. Таким образом, мы имеем треугольник T1, точки A, B, C с параметром t t t, 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 = old B. То же самое относится к T2: примените рекурсивную систему и вызовите тот же алгоритм на новый T1 и новый T2. Stop, когда расстояние между T1 и T2 за вычетом расстояния между предыдущими T1 и T2 ниже порога. функция может выглядеть как ComputeDistance (curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance), где точки хранят также их t параметров.

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

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Fs - вектор.

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

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

Ответ 5

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

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

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

Ответ 6

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

В ближайшей точке линии есть три кандидата:

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

Проверьте все три; выигрывает самое короткое расстояние.

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

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

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

Учитывая две кривые Безье A (t) и B (s), вы можете получить уравнения для их локальной ориентации 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) |. Это простая двухпараметрическая задача оптимизации: найдите s и t, которые минимизируют d (t, s) с ограничениями 0 ≤ t ≤ 1 и 0 ≤ s ≤ 1.

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

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

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

Ответ 7

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