Пересечение Кубической Кривой Безье и отрезка

[Виталий]

Меня очень итересует именно пример решения с нахождением перпендикуляра к пересечению и самой точки пересечения, как показано на рисунке :

Кликните для увеличения:


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

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

Что-то Вы непонятное пишите. Судя по рисунку, Вас интересуют точки пересечения и перпендикуляры к касательным в оных точках.

С точки зрения математики, проблем нет. Выписываете уравнение прямой, проходящей через концы отрезка: $ a x + b y = c$. Подставляете в него параметрическое представление кривой Б.: $a B_x(t) + b B_y(t) = c$. Получаете кубическое уравнение относительно параметра $t$, кое и решаете в своё удовольствие. Полученные вещественные корни (числом от одного до трёх) проверяете на принадлежность области параметра $t \in [0,1]$. Дальше вычисляете координаты точки (точек) персечения, и проверяете, что они лежат на отрезке, а не только на прямой. Ну, теперь, зная координаты точки и значение параметра, уравнения касательной и перпендикуляра не напишет только ленивый (не сдавший по аналитической геометрии за первый курс).

Это теория. Если же Вы пытаетесь найти эффективное решение задачи, то, наверное, вопросу место в Computer Science. Там схожий вопрос как-то обсуждался.

[Виталий]

Хорошё, а по каким формулам рассчитать коэффициэнты a,b,c для подстановки в кубическое уравнение? Просто я что-то не помню чтобы сталкивался с ax+by=c
при наличии точек кривой, и начала/конца отрезка?
Мне кто -то говорил что:
Кривая это
X(t) = A(t), Y(t) = B(t)
где:
A(t), B(t) полиномы третьей степени, а вот прямая это тоже некие X'(t), Y'(t) и можно получить уравнение третьего порядка приравняв
X'(t) = X(t); Y'(t) = Y(t);
Но вот какое дело, у меня есть решалка кубических уравнений, 4 опорные точки кривой, и точки начала/конца отрезка, но по скольку я не секу в полиномах и кубических уравнениях так хорошё, чтобы запросто ими оперировать то мне нужно как-то вывести 3 коэффициэнта a,b,c для решалки кубических уравнений чтобы работать дальше...

И еще вопросец:
Что потом делать с полученными корнями?
Проверить все полученные корни на принадлежность промежутку [0,1], а
потом, проверить на принадлежность точки кривой полученной c помощью формулы кривой Безье B(t) отрезку , и если нашлось несколько то сделать выборку по ближайшей к началу отрезка?

Или как-то еще?

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

Виталий писал(а):

Хорошё, а по каким формулам рассчитать коэффициэнты a,b,c для подстановки в кубическое уравнение? Просто я что-то не помню чтобы сталкивался с ax+by=c

А как Вы пишите уравнение прямой, проходящей через две точки?

Ключ к происходящему — это то, что точка пересечения лежит одновременно и на отрезке, и на к.Б., а значит, её координаты удовлетворяют обоим уравнениям.

[Виталий]

>А как Вы пишите уравнение прямой, проходящей через две точки?

y=kx+b что плохо для вертикальных линий...

[Алексей К.]

А как сделать хорошё --- не знаете???
$x(t)=x_0+t\cos\alpha,\quad y(t)=y_0+t\sin\alpha$.
Где $x_0,y_0$ --- начало отрезка.
Исключив $t$, получите вожделенное $ax+by=c$.
С Безьями работаем, а про прямые не выучили ни фега?

Добавлено спустя 11 минут 30 секунд:

Виталий писал(а):

Мне кто -то говорил что:
Кривая это
X(t) = A(t), Y(t) = B(t)
где:
A(t), B(t) полиномы третьей степени, а вот прямая это тоже некие X'(t), Y'(t) и можно получить уравнение третьего порядка приравняв
X'(t) = X(t); Y'(t) = Y(t);
Но вот какое дело, у меня есть решалка кубических уравнений, 4 опорные точки кривой, и точки начала/конца отрезка, но по скольку я не секу в полиномах и кубических уравнениях так хорошё, чтобы запросто ими оперировать то мне нужно как-то вывести 3 коэффициэнта a,b,c для решалки кубических уравнений чтобы работать дальше...

Много не так.
Что за обозначенния --- $X(t) = A(t)$, а потом $ X'(t) = X(t)$?
Это можно и так записать: $X(t) = A(t)=X'(t) = X(t)$.
Ежели параметр кривой назван $t$, то параметр прямой надо назвать $u$. Или $v$. Или $\xi$. А то при решении уравнений самообман случиться может...
Правьте...

Виталий писал(а):

Хорошё, а по каким формулам рассчитать коэффициэнты a,b,c для подстановки в кубическое уравнение? Просто я что-то не помню чтобы сталкивался с ax+by=c

По сколько задачек по геометрии в день решаете?

[Виталий]

Ну вот, значит беру через полиномы так?

Получаются такие коэффициэнты:

N = Normalize(B-A); // нормализованный вектор разницы конца отрезка и начала

Формулирую 4 коэффициэнта через уравнение прямой ax+by+c=0

$c = A_yN_x - A_xN_y$
$D_0 = N_yP_{0_x} + N_xP_{0_y} + c$
$D_1 = N_yP_{1_x} + N_xP_{1_y} + c$
$D_2 = N_yP_{2_x} + N_xP_{2_y} + c$
$D_3 = N_yP_{3_x} + N_xP_{3_y} + c$

Где $P_n контрольная точка кривой.


Далее, беру через полиномы пишу коэффициэнты для уравнения $a x^3 + b x^2 + c x + d = 0

$a = (D_3 - 3D_2 + 3D_1 - D_0)$
$b = 3(D_2 - 2D_1 + D_0)$
$c = 3(D_1 - D_0)$
$d = D_0$

Проверяю на $a \neq 0 $ Если всё так, то решаю методом Кардано:
$b^3 + cx^2 + d = 0$ предварительно поделив всё на $a$
Иначе решаю квадратное с такими кофами:
$b x^2 + c x + d = 0$

Потом смотрю на полученные вещественные корни...
Сначала смотрю чтобы из имеющихся все корни :
$x_n \in [0,1] $ где $x_n$ один из вещественных корней.

Потом если нашлись такие корни, подставляю в функцию Безье,
смотря чтобы полученная точка принадлежала отрезку
$ B(x_n) \in AB $
Если из полученных результатов несколько точек и они принадлежат отрезку, то беру ту которая ближе к $A$ через длину вектора (как пример: случай для двух подходящих под условие корней):
Сначала считаю дельта вектор:
$M_0 = A - B(x_0)$
$M_1 = A - B(x_1)$
Потом считаю длины
\varphi_1 = \sqrt { M_{0_x}^2 + M_{0_y}^2 }
\varphi_2 = \sqrt { M_{1_x}^2 + M_{1_y}^2 }

Потом проверяю : \varphi_1 \geqslant \varphi_2 и беру ту, у которой длина вектора меньше...


Может я и что-то пропустил, однако работает нормально только для вертикальных отрезков...
Для горизонтальных почему-то всегда получается два комплексных корня, а для случайного отрезка который не горизонтален и не вертикален, получается 1,2,3 вещественных корня, но они не попадают в промежуток x_n \in [0,1]

И в чём дело? Помогите исправить ошибки...

поправил формулы. Сэр! не пишите _ без надобности. Это знак перехода к индексам, а не пробел. // нг

[Виталий]

Подправил текст и формулировки с формулами, смотрим постом выше...
Очень нужна любая помощь...

[Алексей К.]

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


Уравнение прямой:
$(x-x_1)\sin\alpha-(y-y_1)\cos\alpha=0$, или

$$x\underbrace{\sin\alpha}_a-y\underbrace{\cos\alpha}_b+\underbrace{y_1\cos\alpha-x_1\sin\alpha}_c=0,$$

где $\alpha=\mbox{\tt arctan}(y_2-y_1,x_2-x_1)$. Функцию arctan я написал в компьютерном смысле.


Ежели буковки $a,b,c$ уже использованы в уравнении прямой, то НЕЛЬЗЯ их же использовать в уравнении кривой Безье!

Виталий писал(а):

$D_0 = N_yP_{0_x} + N_xP_{0_y} + c$
$D_1 = N_yP_{1_x} + N_xP_{1_y} + c$
$D_2 = N_yP_{2_x} + N_xP_{2_y} + c$
$D_3 = N_yP_{3_x} + N_xP_{3_y} + c$

Этого ни понил.

Виталий писал(а):

Далее, беру через полиномы пишу коэффициэнты для уравнения $a x^3 + b x^2 + c x + d = 0

$a = (D_3 - 3D_2 + 3D_1 - D_0)$
$b = 3(D_2 - 2D_1 + D_0)$
$c = 3(D_1 - D_0)$
$d = D_0$

$$\{X,Y\}(t)=(1-t)^3\{P_1,Q_1\} + 3t(1-t)^2\{P_2,Q_2\}+3t^2(1-t)\{P_3,Q_3\}+t^3\{P_4,Q_4\}.$$

Где $P_iQ_i$ --- координаты контрольных точек. Наверное, Ваши $a,b,c,d$ сосчитаны из этих соображений.

Уравнение, которое мы собираемя теперь решать, имеет вид --- "какая из точек $X(t),Y(t)$ принадлежит прямой $ax+by+c=0$?", или, иными словами,

$$aX(t)+bY(t)+c=0.$$

Виталий писал(а):

Ну вот, значит беру через полиномы так?
$b^3 + cx^2 + d = 0$ предварительно поделив всё на $a$

Лажа какая-то. Аккуратнее надо писать.

Виталий писал(а):

Потом смотрю на полученные вещественные корни...
Сначала смотрю чтобы из имеющихся все корни :
$x_n \in [0,1] $.

Разумно. Только $t_n \in [0,1]$, t, а не x.

Виталий писал(а):

Потом если нашлись такие корни, подставляю в функцию Безье, (я бы сказал --- вычисляю координаты точки на кривой)
смотря чтобы полученная точка принадлежала отрезку
$ B(x_n) \in AB $ (вот опять одинаковые обозначения: B справа и B слева --- разные объекты; Вы-то знаете, о чём пишете, и Вам всё понятно, а читатель не знает, как раз хочет понять, а Вы его своею неаккуратностию запутываете)
Если из полученных результатов несколько точек и они принадлежат отрезку, то беру ту которая ближе к $A$.

Зачем? Если несколько точек принадлежат отрезку, то мы имеем несколько точек пересечения дуги кривой и отрезка прямой. Несколько решений --- за что одно лучше другого? Близость к А определяется значанием $t$. Близость в смысле вдоль кривой.

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

Алексей К. писал(а):

Ежели буковки $a,b,c$ уже использованы в уравнении прямой, то НЕЛЬЗЯ их же использовать в уравнении кривой Безье!

В уравнении к.Б. нельзя, в ур-е для точки пересечения — можно. Как это не странно, происходящее (с точностью до путаницы в обозначениях) имеет смысл. То есть, есть прямая $ a x + b y + c = 0$. Точка на к.Б., лежащая на пересечении, будет удовлетворять $a B_x(t) + b B_y(t) + c = $. Теперь Виталий выражает B(t) через опорные точки, и получает уравнение для $t$ (которое он, чтобы нас запутать, называет $x$). До этого места вроде правильно. Дальше — хуже. Коэффициенты кубического уравнения снова обозначены теми же буквами $a, b, c, d$. Если не повезло, то используются те же переменные в программе. Далее, вместо кубического $t^3 + b t^2 + c t + d$ написана какая-то чушь, не поддающаяся расшифровке:

Виталий писал(а):

$b^3 + cx^2 + d = 0$

. В общем, концов не найти.


Виталий, с практической точки зрения лучше пользоваться методом Ньютона. Он хоть и не точный, но ответ даст быстрее.

[Виталий]

Всё я понял свою ошибку, не правильно подставлял значения в уравнение прямой...

$c = A_yN_x - A_xN_y$
$D_0 = N_yP_{0_x} - N_xP_{0_y} + c$
$D_1 = N_yP_{1_x} - N_xP_{1_y} + c$
$D_2 = N_yP_{2_x} - N_xP_{2_y} + c$
$D_3 = N_yP_{3_x} - N_xP_{3_y} + c$

как видите a - b + c вместо a + b + c