LINUX.ORG.RU

Как посчитать аналитически расстояние от точки до безье третьего порядка?

 ,


1

1

Есть сегмент контура, который описывается безье третьего порядка. Без inflextion point. Надо найти минимальное расстояние от произвольной точки до этого сегмента.

  • для квадратичныз безье в гугле формул навалом, для кубических почему-то тухловато.
  • численными методами (бить на 100 отрезков и т.п.) не хочется. Хотелось бы аналитически.
★★★★★

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

Бить на сто отрезков — так себе метод, лучше последовательностями Штурма корни изолировать. Но всё равно численно получится.

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Плюсую.

  1. выписать выражение для расстояния (проще квадрата расстояния), желательно что бы кривая была задана в однопараметрическом виде

  2. продифференцировать по параметру

  3. взять метод половинного деления или Ньютона и решить полученное уравнение. Ньютон работает быстрее но сложнее и иногда глючит, половинное деление дольше работает но проще и надежнее.

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

Если лень морочится, то можно не дифференцировать а искать минимум методом золотого сечения. Но может сойтись не туда.

AntonI ★★ ()
Ответ на: комментарий от AntonI

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

Нет, не рекурсия. Я не зря про последовательности Штурма упомянул.

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Для этого надо искать НОД для многочленов и вообще уметь делить многочлены друг на друга. Это все конечно делается, но рекурсия гораздо проще;-)

AntonI ★★ ()
Последнее исправление: AntonI (всего исправлений: 1)

А нафига тебе бесконечная точность? Сама кривая твоя имеет вполне конечные размеры, строй по кривой точки в нужном разрешении допустим те же 100, между каждыми точками пусть будет линия итого у тебя 99 линий и тебе нужно просто curve_point - world_point проинтерировать и ты получишь расстояние точки до 100 мест на кривой, если надо точнее то интерируешь не по точкам просто, а по отрезкам которые ты построил. сначала выбираешь сегмент (линию) надодишь расстояние то концов отрезка, затем её уже бьёшь на ещё 100 например сегментов или от точки то линии ведёшь луч в 100 шагов получая 100 пересечений с линией и от каждого пересечения curve_point - world_point и всё. Весь вопрос в точности которая тебе нужна если тебе нужна точность как одна стомиллиардная от длинны кривой то тут уже да олгоритмы и всё такое. Но я на 89% уверен что тебе точность нужна на уровне на глаз прикинуть можно

anonymous ()
Ответ на: комментарий от MKuznetsov

Смотря каких методов. Если бить на 100 отрезков - такого метода и правда можно стесняться;-)

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

AntonI ★★ ()
Ответ на: комментарий от Miguel

но если в соседних точках, в которых производная равна нулю, функция имеет разные знаки - гарантия есть;-)

Правда там еще надо края отдельно обрабатывать. Но это несложно.

AntonI ★★ ()
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от AntonI

Из-за ограниченности времени таки сделали численным способом.

Давай я опишу полную задачу. Нужно апроксимировать безье третьего порядка квадратичными безье, с заданной точностью. И как частная задача - вычислять ошибку между безье третьего порядка и второго.

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

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

Вроде хватило, чтобы ошибка не более чем в два раза была.

Надо бы это все конечно нормально переписать, но со временем совсем жопа.

Vit ★★★★★ ()
Ответ на: комментарий от AntonI

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

А чтобы кратные корни вытянуть, нужно считать НОД многочленов.

Правда, с последовательностями Штурма тоже можно наколоться, если считать в вещественных числах. Потому что ошибка округления. Нужно считать в рациональных.

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

в кратных корнях у тебя будет проблема.

подошел экстремумом к оси ближе чем на эпсилон - лови кратный корень.

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

AntonI ★★ ()
Ответ на: комментарий от Vit

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

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

вычислять ошибку между безье третьего порядка и второго.

В какой норме? Максимальное расхождение или среднее? КМК и то и то можно во многом сделать аналитически.

AntonI ★★ ()
Ответ на: комментарий от AntonI

подошел экстремумом к оси ближе чем на эпсилон - лови кратный корень.

Особенно если его там таки нет.

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

Miguel ★★★★★ ()
Ответ на: комментарий от AntonI

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

https://github.com/fontello/cubic2quad

Оно бьется, само собой. Но дальше ведь надо посчитать расхождение, чтобы решить, увеличить разбиение или остановиться. И тут мы переходим к тому, что я описал: есть 2 точки (кусок разбивки), между ними отрисованы квадратичная и кубическая безье.

В какой норме? Максимальное расхождение или среднее? КМК и то и то можно во многом сделать аналитически.

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

Vit ★★★★★ ()
Ответ на: комментарий от Vit

Ну дык в такой постановке не надо искать расстояние от точки до B3 - надо искать расстояние от точки до B2 ;-) А ты сам сказал что эта задача решена.

В качестве точки от которой ищем расстояние берется точка кривой B3, а дальше хошь экстремум (по параметру который в B3) ищи золотым сечением (плохая идея - их там несколько), хошь среднее. Но в такой задаче среднее ИМНО будет робастнее.

AntonI ★★ ()
Последнее исправление: AntonI (всего исправлений: 2)
Ответ на: комментарий от AntonI

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

Ну дык в такой постановке не надо искать расстояние от точки до B3 - надо искать расстояние от точки до B2 ;-)

Я терминологию не вкурил, что ты называешь Bx?

А ты сам сказал что эта задача решена.

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

Vit ★★★★★ ()
Последнее исправление: Vit (всего исправлений: 1)
Ответ на: комментарий от AntonI

inflextion point (видимо B3) точно нет. Точка перегиба проверяется отдельно, и в ней (если есть) бьем кубическую безье пополам, чтобы не было совсем жестилова. Это все до апроксимации.

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

Vit ★★★★★ ()