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

аналитически никак

метод Лобачевского наверно подойдет

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

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

Плюсую.

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

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

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

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

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

а чего стесняться численных методов ?

можно подумать что Безье у вас от физики процесса..от безысходности он

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

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

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

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

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

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

Лучше бы формулу или псевдокод написали. Философствовать можно бесконечно.

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

Что бы искать корни надо разбить на участки где эти корни по одной штуке

можно этим

https://github.com/nrtaylor/CubicSplineClosestPoint

кстати и в cgal.org должно быть что-то похожее.. удивлюсь если нет

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

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

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

Если у гугла по-английски спрашивать, он ищет лучше :)

https://stackoverflow.com/questions/2742610/closest-point-on-a-cubic-bezier-curve

О, я это пропустил, спасибо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

https://github.com/fontello/cubic2quad

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

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

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

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

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

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

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

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

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

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

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

B2 - квадратичный Безье, B3 - кубический.

Да, с экстремумом наглядней. Ну тогда хорошая новость - их там наверное не больше трех;-)

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

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