Наименьшее расстояние между двумя кривыми, определяемыми функциями

Question

У меня есть две функции, описывающие две кривые в 2D.

p1 = f1(t1) 
p2 = f2(t2) 

, где p1 и p2 являются векторами, t1 и t2 скаляры со значением между 0,0 и 1,0.

Кривые оба выпуклые с «животами», обращенными друг к другу. Они могут быть повернуты и могут быть определены новые функции y = h(x), так что их производные на x будут монотонно увеличиваться/уменьшаться.

Пример:

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

Возможный подход, я думаю, можно было бы определить функцию расстояния:

g(t1, t2) = |f1(t1) - f2(t2)| 

, а затем использовать обобщение Newton's method для решения системы уравнений

0 = ∂g(t1, t2)/∂t1 // partial derivative of g for t1 
0 = ∂g(t1, t2)/∂t2 // partial derivative of g for t2 

Но я не уверен, что это правильно, и это немного неудобно, потому что мне понадобятся первая и вторая производные от g, которые мне пришлось бы вычислить численно.

Есть ли более простой, возможно более быстрый алгоритм для этого?

Answer 1

Проблема заключается в том, чтобы найти минимум z на 3-мерном участке площадью 0<=x<=1 и 0<=y<=1. В этом случае z является ошибкой | и x - t1, y - t2.

Вместо того, чтобы использовать |f1(t1) - f2(t2)|, предложите z= pow(f1(t1) - f2(t2),2) для более плавных характеристик и ищите минимум.

Поскольку характеристики f1(t1) и f2(t2), похоже, не сильно контролируется, предложить бинарный поиск в 2-х измерениях, как

https://stackoverflow.com/a/6910155/2410359 или
https://stackoverflow.com/a/6909573/2410359

Answer 2

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

Если допустимость допустима, количество дуг будет довольно умеренным (обычно 10-20), и вы можете полностью проверить расстояния дуги/дуги.

Поиск «ПРИБЛИЖЕНИЕ КУБИЧЕСКОЙ КРИВОЙ БИЗНЕСА С ЦИРКУЛЯРНЫМИ АРКСАМИ И ВИЦЕ-ВЕРСА», чтобы получить вдохновение.

---

Для наглядности, участки ниже три дискретизаций на кривой Лиссажу, с допусками 2, 0,5 и 0,125 соответственно (за 21, 31 и 50 дуг).

Сравните с теми же кривыми с уплощением (те же допуски, 58, 120 и 248 сегментов линии).