Обработка сплайнов и кривых Безье

[VLarin]

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

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

[незваный гость]

VLarin писал(а):

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

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

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

VLarin писал(а):

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

Речь, видимо, идет объ этой кривой:

Цитата:

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

VLarin писал(а):

И эти оценки касаются кривых Безье.

Сплайн суть совокупность кривых Безье со специальными правилами согласования. Посему вместо того, чтобы искать 5120 перпендикуляров к сплайну о 1024 сегментах, мы рассматривая кривые по отдельности (и выбрасывая бесперспективные) зело уменьшаем работу. Критериев выбраковки два - расстояние до выпуклого охватывающего многоугольника (по сравнению с уже найденым) и перпендикуляры. После такой селекции 2-3 перспективных кривых остаться должно. Их уже можно анализировать детально...

[[ Сравните с поиском экстремума в одномерном случае. Сплайн распадается на набор кубических полиномов на отрезках. И каждый из них можно анализировать отдельно. Но если мы используем их представление через полиномы Берштейна $p_j(x)=\sum\limits_{k} a_{j,k} B_k(x)$, и мы уже нашли $p_j(x_0)=M$, то коли все $a_{i,k} < M$, мы можем $p_i(x)$ не анализировать... ]]

[незваный гость]

Аки post scriptum к предыдущему:

незванный гость писал(а):

[[ ... то коли все $a_{i,k} < M$ ... ]]

Есть, кстати, и более тонкие (и, вестимо, более точные) оценки, основанные на использовании Чебышевских многочленов.

[VLarin]

То-то и оно. Задача нетривиальная.
Спасибо за советы, буду думать.

[незваный гость]

VLarin писал(а):

Спасибо за советы, буду думать.

То есть у Вас есть практический интерес? Вы уже разрабатываете что-то?

[VLarin]

Я писал контрол а-ля XYGraph. Исходные точки интерполируются обычными сплайнами 3-порядка.
Курсор данных сделал простым способом - при перемещении мыши определяю координату X, и по ней значение в точке на сплайне. Но это дело работает плохо, когда кривая почти вертикальна - т.е. небольшое изменение X приводит к большому изменению величины Y. А такие вещи в комерческих программах как раз решены с помощью определения значения не при текущем X, а в точке пересечения перпендикуляра из текущей точки на сплайн. Просто появилось немного времени и хотел сделать для графика небольшой апгрейд.

[незваный гость]

Пара иллюстраций:

(координаты {(-6, 0), (-6, 5), (-1, 7), (0, 7)} )
и

(координаты {(-6, 0), (-6, 5), (-5, 7), (0, 7)} ).

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

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

[незваный гость]

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

[VLarin]

На днях опять занялся сплайнами и построением графиков.
По поводу нахождения перпендикуляра к сплайну - пришла такая идея - заменить эту задачу поиском кратчайшего расстояния D(t) = (x(t) - x0)^2 + (y(t) - y0)^2.

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

В итоге пришел к следующему - по исходным точкам рассчитываю нормальзованный сплайн (x(t) и y(t)), рисую его с помощью WinGDI функции PolyBezier, для чего рассчитываю при создании сплайна также контрольные точки Безье-сплайна (которые при масштабировании просто пересчитываются), а выделение + курсор данных - это в чистом виде поиск наименьшего расстояния до сплайна с помощью метода Ньютона - в лоб по всем сплайнам.

Так что - с вопросом, почему в других прогах (тот же AutoCAD) нахождение перпендикуляра или кратчайшего расстояния к сплайну летает - вопрос решен. Чудес не бывает

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