Задача - Принадлежат ли точки кривой Безье?

[Humanoid]

Дано: Последовательность точек на плоскости, описывающая контур фигуры. Некоторые подпоследовательности точек из неё могли принадлежать ранее кубическим кривым Безье. Остальные точки - просто абсолютно произвольная ломанная линия. Точность входных данных очень хорошая, но не идеально алгебраическая (задача вычислительная).

Найти: Само наличие кривых и их параметры.

Задача технически распадается на подзадачи:

1) Какое количество N точек, лежащих на самой кривой, однозначно задаёт кубическую кривую Безье на плоскости? (это вообще разрешимо?)
2) Как определить, что эти N точек лежат на какой либо кривой Безье?
3) Найти коэффициенты полиномов Бернштейна для этих N точек.
4) Найти две опорные точки кривой исходя из K > N точек, доказано лежащих на самой кривой. (K точек последовательно лежат на одной и той же кривой)

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

[Алексей К.]

Готовых ответов на 1) и 2) у меня нет, но, если угодно, давайте порешаем, поисследуем.
Надеюсь, наши точки упорядочены, и можно выбрать начало и конец, и тогда перейти в прилично-симметричную систему координат, где всякие выражения будут попроще. Хорду поворотами и переносами можно наложить на ось абсцисс.
Т.е. кривую я предлагаю записать через стандартный контрольный полигон в виде

$$P_0=(-c,0),\quad P_1=(a_1,b_1),\quad P_2=(a_2,b_2),\quad P_3=(c,0).$$

Далее из двух полиномов исключить параметр и посмотреть на неявное уравнение $F(x,y;a_1,b_1,a_2,b_2)=0$
(обозначения $x_i,y_i$ я оставил для точек, лежащих на кривой, которые мы будем подставлять в неявное уравнение; $c$ как бы известно, в список свободных параметров функции $F(\ldots)$ не включено).
Возможно, мы тут же поймём, почему эта полезная задачка нигде не описана. Типа тупичок увидим. Думаю, была бы простая, была бы хорошо известной.
Самому интересно, но лень, откладываю на пенсию.

Если Вам не так лень, выпишите неявное уравнение... посмотрим на него. А я поищу на чердаке свои юношеские тетрадки, много я про Безьюхи думал когда-то, и чо-то записывал.

[Алексей К.]

Алексей К. в сообщении #836044 писал(а):

поворотами и переносами

Впрочем, ежели мы имеем дел с кривыми Безье, то в нашем распоряжении не только это, но и аффинное преобразование координат. Посмотрел в Википедии --- три точки можно совместить с их тремя заданными образами (при неколлинеарности). Значит, можем положить $a_1+a_2=0$ и, например, $\frac12(b_1+b_2)=c$ (т.е. точки $P_0$, $P_3$ оставляем неподвижными, а середину отрезка $P_1P_2$ сажаем в положение $(0,c)$; на скорую руку только это придумалось). Но это потом, если дело в таком духе пойдёт.

[Humanoid]

Есть ответ по пункту 1. Точек четыре, кривая задаётся однозначно, но при этом вычислить опорные точки кривой A B' C' D получится только если знать $t(B')$ и $t(C')$. Например:

$B=(-5A + 18B`- 9C`+ 2D)/6 $
$C=(2A - 9B`+ 18C`- 5D)/6$

где B и C опорные точки, а B' и C' - точки на кривой. $t(B')=1/3$ и $t(C')=2/3$

Отсюда вопрос - можно ли из этого что-то полезное выжать? Ведь параметрическую координату я не знаю.

-- менее минуты назад --

Хотя нет, стоп! Ошибка!
Получается что при заданных $t(B')$ и $t(C')$ кривая однозначна, но при любых других $t(B')$ и $t(C')$ будет уже другая кривая. Семейство ажно по двум параметрам...

Но... Ура! Меня это устраивает, так как дискретизация изначальной кривой шла с фиксированным шагом по t, так что как раз вышеприведённые формулы и пойдут в бой напрямую! Дело движется... :)

-- менее минуты назад --

Ну вот, собственно, и всё. Меня спас фиксированный шаг дискретизации по t. Конечно, это не общее решение, но мне сойдёт. Просто получаю кривую по четырём точкам как описано выше, и проверяю, лежит ли следующая, пятая точка на этой кривой. Если да, то вот оно, Безье. Дальше со сдвигом на точку вперёд повторять процедуру, пока кривая не кончится. :)

А вот для общего вида, с неизвестным t я решения не вижу... :( Но с меня его, слава богу, и не спрашивают. :)

[Алексей К.]

Humanoid в сообщении #836104 писал(а):

но при этом вычислить опорные точки кривой A B' C' D получится только если знать $t(B')$ и $t(C')$. (выделение моё, А.К.)

Слово только сильно смущает. Как будто кто-то всё перепробовал, проверил, и оказалось, что только если знать...
Откуда это можно знать, не решив задачу без всяких $t$ (никому, похоже не нужных)? Это слишком чайниковский подход.
Только решив её, хотя бы так, как я предложил попробовать_её_решить, можно эти $t$ определить. Я сразу предложил от $t$ избавиться.

-- 12 мар 2014, 23:43:36 --

Humanoid в этом сообщении писал(а):

(не очень у меня с математикой, увы...)

Да, тогда нам будет трудно разобраться (надежда на то, что мы здесь не одни, остаётся). Но если Вы умеете пользовать матпакеты, то для исключения параметра там служит функция типа resultant(f(t),g(t),t).
Поскольку она предполагает функции $f(t)=0$, $g(t)=0$, то применять её следует в виде типа resultant(x(t)-X,y(t)-Y,t).

-- 12 мар 2014, 23:54:27 --

Humanoid в сообщении #836104 писал(а):

Ну вот, собственно, и всё.

Правильно ли я понял, что вопрос исчерпан снимается?

[Humanoid]

Да и я уже взгрустнул... Не учёл одного простого вопроса: Если мы изначально интерполировали кривую с фиксированным шагом по t, а потом взяли четыре последовательные точки изнутри получившейся последовательности (то есть теперь для первой из них t=0, для четвёртой t=1), то можно ли считать, что шаг остался фиксированным, и две промежуточные точки лежат на одной и двух третях по параметру?

-- менее минуты назад --

Цитата:

Правильно ли я понял, что вопрос исчерпан снимается?

Увы, ещё нет.

[svv]

Допустим, известно, что при $t=0$ кривая Безье проходит через точку $A$, а при $t=1$ через точку $D$. Кроме того, она проходит через точки $B'$ и $C'$, но неизвестно, при каких значениях параметра $t$.

Вопрос: а какими могут быть эти значения, $t(B')$ и $t(C')$? Насколько свободен их выбор?

Ответ: можно потребовать, чтобы значения $t(B')$ и $t(C')$ были какими угодно, со следующими ограничениями:
$\bullet$ если $B'\neq A$, то $t(B')\neq 0$;
$\bullet$ если $B'\neq D$, то $t(B')\neq 1$;
$\bullet$ если $C'\neq A$, то $t(C')\neq 0$;
$\bullet$ если $C'\neq D$, то $t(C')\neq 1$;
$\bullet$ если $B'\neq C'$, то $t(B')\neq t(C')$.
Всё это получается, если составить систему из двух линейных алгебраических уравнений (правда, с двумя неизвестными векторами $B$ и $C$, и векторными же правыми частями).
Понятно, что, выбирая по-разному $t(B')$ и $t(C')$, мы будем получать разные опорные точки $B$ и $C$.

[Алексей К.]

Ну да, с двумя заданными внутренними точками мы имеем аж двухпараметрическое семейство решений (среди них, наверное, куча "плохих", "некрасивых"). $T_1=t(B')$ и $T_2=t(C')$ --- параметры семейства.
Интересности/трудности начнутся с третьей внутренней точкой (т.е. всего 5).

[iifat]

Humanoid в сообщении #836129 писал(а):

можно ли считать, что шаг остался фиксированным

Вот так, навскидку — нет. Разве что кривая Безье вырождается в прямую. Явно ж зависит от кривизны, а она переменная.

[Humanoid]

iifat в сообщении #836208 писал(а):

Humanoid в сообщении #836129 писал(а):

можно ли считать, что шаг остался фиксированным

Вот так, навскидку — нет. Разве что кривая Безье вырождается в прямую. Явно ж зависит от кривизны, а она переменная.

Вижу, вижу... Плакала идейка. :(
Я, конечно, могу задачу алгоритмически, программистскими фокусами решить, но сложность будет не линейной (а ещё умножить на максимально возможное число кривых дробь два). Математикой то шустрее было бы...


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

[Алексей К.]

Humanoid в сообщении #836214 писал(а):

Интуиция подсказывает, что и пять маловато...

С утра (т.е. после ночного замечания svv) мне интуиция подсказывает, что 6: имея при четырёх точках (2+2) двухпараметрическое семейство $F(x,y;T_1,T_2)$, мы для двух дополнительных точек (2+2+2) получаем два уравнения $F(\bar{x},\bar{y};T_1,T_2)=0$ с двумя неизвестными $T_1,T_2$. Но это, естественно, общие соображения, без исследования условий разрешимости системы.

На 6 точек (2 фиксированных + 4 произвольных) намекают и 4 свободных параметра ранее выписанного семейства

Алексей К. в сообщении #836044 писал(а):

$F(x,y;a_1,b_1,a_2,b_2)=0$

[Алексей К.]

Алексей К. в сообщении #836252 писал(а):

Но это, естественно, общие соображения, без исследования условий разрешимости системы.

И даже если всегда разрешится, то не приходится ожидать, что всегда будет $t_1<t_2<\ldots<t_6$: точки придётся переупорядочить (засовывать все эти $t_i$ в отрезок [0;1] вовсе необязательно, перепараметризовать всегда можно).

Очевидно, кубическая кривая Безье не пойдёт по синему варианту, но вполне может пройти по зелёному:

$$\setlength{\unitlength}{.2mm}\begin{picture}(360,100) \color{blue} \put(5,30){\circle*{3}}\put(4,14){1} \put(25,70){\circle*{3}}\put(23,80){2} \put(65,20){\circle*{3}}\put(63,3){3} \put(85,80){\circle*{3}}\put(83,90){4} \put(110,20){\circle*{3}}\put(108,3){5} \put(130,50){\circle*{3}}\put(135,45){6} \color{green} \put(205,30){\circle*{3}}\put(204,14){1} \put(225,70){\circle*{3}}\put(223,80){6} \put(265,20){\circle*{3}}\put(263,3){2} \put(285,80){\circle*{3}}\put(283,90){5} \put(310,20){\circle*{3}}\put(308,3){3} \put(330,50){\circle*{3}}\put(335,45){4}\end{picture}$$

-- 13 мар 2014, 12:03:02 --

Алексей К. в сообщении #836044 писал(а):

Возможно, мы тут же поймём, почему эта полезная задачка нигде не описана. Типа тупичок увидим.

И понял, и увидел.

[Humanoid]

Цитата:

На 6 точек (2 фиксированных + 4 произвольных) намекают и 4 свободных параметра ранее выписанного семейства

Этак у Вас получается, что чем больше точек, то тем больше свободы. Как-то это чудесато...

Цитата:

Очевидно, кубическая кривая Безье не пойдёт по синему варианту, но вполне может пройти по зелёному:

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

Цитата:

И понял, и увидел.

По возможности, в студию. Что там, полином пятой степени в общем виде?

[Алексей К.]

Humanoid в сообщении #836362 писал(а):

Этак у Вас получается, что чем больше точек, то тем больше свободы. Как-то это чудесато...

Это Вы читаете плохо. От того, что Вы возьмёте 100 точек, число (4) свободных (искомых) параметров того семейства кривых не изменится, и "свободы" больше не станет. Именно 4 точки $(x_i,y_i)$ дают систему

$$\Big\{F(x_i,y_i;\underbrace{a_1,b_1,a_2,b_2}_{(4)})=0,\qquad i=1,2,3,4,$$

в которой число неизвестных равно числу уравнений.

-- 13 мар 2014, 18:37:02 --

Humanoid в сообщении #836362 писал(а):

Тут важно, это будет единственный вариант кривой (или никакого), или возможны варианты?

Это не так уж и важно: всё равно неприличное слово.
Их количество будет определяться чем-то вроде степени "финального" уравнения системы.

(Так, мне припоминается, например, что если задавать на границах наклоны касательных и кривизны, то уравнение будет 4-й степени и даст максимум 4 решения. И, кстати, такие граничные условия можно имитировать четырьмя точками, по паре в районе каждого из концов; так что, скорее всего, и в нашем случае возможные варианты --- от 0 до 4-х решений)

[Алексей К.]

Humanoid в сообщении #836362 писал(а):

По возможности, в студию.

Так оно всё в студии: я "понял и увидел", как только написал то сообщение. Типа попытался вообразить себе жуткие алгоритмы, разборки с $t$, и даже не смог. Да и слишком это уж тяжёлая артиллерия для стрельбы по воробьям из компьютерной графики.

(Оффтоп)

Красивая картинка в в этом древнем сообщении для данной темы является, к сожалению, оффтопиком. Но я долго искал...

Да и правда --- на кой Вам эти Безьюхи? Посмотрите, какие ещё бывают замечательные кривульки!