Кривая по двум точкам и касательным векторам

[Алексей К.]

8bit в сообщении #485295 писал(а):

У меня практическая задача, и точки расположены достаточно близко друг от друга.

Я вот подумал: а если далеко друг от друга (скажем, первая в Женеве, вторая около Рима) — что-нибудь изменится?

[8bit]

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

8bit в сообщении #485295 писал(а):

У меня практическая задача, и точки расположены достаточно близко друг от друга.

Я вот подумал: а если далеко друг от друга (скажем, первая в Женеве, вторая около Рима) — что-нибудь изменится?

это был ответ на:

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

Ваши фокусы с эллипсами можно заменить рациональной кривой (тоже иногда называемой Безье) второго порядка. Приличное решение будет не всегда: например, бесконечно удалённая точка может затесаться в кривую. Но если граничные условия допускают эллипс, то он и будет найден. Хоть наклонный, хоть круглый.

не понял, что Вы имели в виду, но на всякий случай пояснил, что бесконечно удаленные точки не рассматриваются

[8bit]

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

[Алексей К.]

Та знаменатель обнулился — и ушла в бесконечность. И плевать ей, что кто-то кого-то не рассматривает...
Кстати, эллипс с (анти)параллельными касательными: контрольная точка в бесконечности, $w_1=0$, но типа $w_1P_1\not=0$. Т.е., по-честному, $w_1P_1$ надо подменить чем-то нормальным (ни нулём, ни "бесконечностью").

[8bit]

странно, biarc придумали в 70-х, а нормальной формулы нигде не нашел.
Алексей, можете помочь?

[Алексей К.]

8bit в сообщении #485777 писал(а):

это был ответ на:

Это был ответ на Ваше замечание "У меня практическая задача, и точки расположены достаточно близко друг от друга." Для данной задачи близость точек ни на что не влияет, никакой "практичности" не добавляет. Вы можете решать задачу с точками, например, $A=(-1,0)$, $B=(1,0)$, а потом подобием получить из найденного решения нужное расстояние $AB$, большое ли, маленькое ли --- всё равно. И второй случай будет, когда точки совпадают (бидуга здесь не катит).

-- 24 сен 2011, 11:25 --

ЗЫ: В литературе задача Ваша называется "two-point G1 ($G^1$) Hermite interpolation". Что здесь делает слово "эрмитовый" --- я не помню. Но это только описание граничных условий: никаких методов это название не навязывает. Будет $G^2$, если в граничных точках заданы ещё и кривизны.

-- 24 сен 2011, 11:32 --

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

Об остальном попозже.

[Алексей К.]

8bit в сообщении #485795 писал(а):

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

Потому что Вы мыслите о контрольных точках в полиномиальной модели кривой, той самой, по которой (в любом графичеком редакторе) хватаешь за грудки одну точку, двигаешь её, и любуешься, как Безьюха вслед извивается.
Наверное, что-то похожее будет и в рациональной модели, если запретить случаи $w_2=-1$ или $w_1<0$ (ну, формула где-то выше написана; вопрос этот не изучал).

[AKM]

АКМ:

По мотивам обсуждения поправил заголовок.

[Алексей К.]

8bit в сообщении #485808 писал(а):

странно, biarc придумали в 70-х, а нормальной формулы нигде не нашел

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

x0 y0 r phi1 phi2 arc       % arcn для отрицательной кривизны,

и оно само тебе всё запараметризует и отрисует.
Там нужно только определить кривизны и характеристики в желаемой точке сопряжения. В той теме всё это расписано (формулы (2), (3), и перед ними, без номера).

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

[8bit]

Да, придется самому выводить формулу.
В статье A two-point G1 Hermite interpolating family of spirals, D.S. Meek, D.J. Walton нашел параметрическую формулу $I(t, \lambda)$ (стр. 7), но просто построить не получилось, вторая дуга получается повернутой на 180 градусов при некоторых входных данных (может некорректных), а во-вторых, кривая строится в другой системе координат, нужно вникать.

Легче самому построить 2 дуги параметрически.

Нашел еще один способ - интерполяция с помощью сплайнов Эрмита. pdf (стр. 102)
Решение ищется вида
$x=a_0 + a_1 t + a_ 2 t^2 + a_3 t^3$
$y=b_0 + b_1 t + b_ 2 t^2 + b_3 b^3$
коэффициенты находятся из 8 уравнений
$x(0), x'(0), x(1), x'(1), y(0), y'(0), y(1), y'(1)$
$x'=\Delta x \frac {du}{dx}$
$y'=\Delta y \frac {du}{dx}$
$\Delta x, \Delta y$ - компоненты касательного вектора (в каждой из точек A, B разные)
$\frac{du}{dx} = \frac {1-0}{x_B - x_A}$
$\frac {du}{dy} = \frac {1-0}{y_B - y_A}$
Если у граничных точек $A(x_A, y_A), B(x_B, y_B)$ какие-либо координаты совпадают, то это производные не существуют.
И еще один минус - длины касательных векторов нужно регулировать, чтобы кривая имела "хорошую кривизну", а не была похожа на прямую с повернутыми концами.

(Оффтоп)

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

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

не трек для олимпиады строю пойдет без непрерывности гладкости

[Алексей К.]

8bit в сообщении #486113 писал(а):

Да, придется самому выводить формулу

Какой формулы Вам не хватает (если Вы имеете в виду бидуги)? Центр окружности не можете найти?

8bit в сообщении #486113 писал(а):

Нашел еще один способ - интерполяция с помощью сплайнов Эрмита

PDF не изучал, но то, что Вы пишете в своём комментарии --- обычная кубическая кривая Безье (предствленная в виде полинома, т.е. в $c_0t^3+3c_1t^2(1-t)+\ldots$ просто раскрыли скобки и привели подобные члены). Где-то выше я о ней заикался, в терминах кривизны. А здесь кривизна переведена в длину касательного вектора. Соответствующие формулы легко ищутся (наверняка есть где-то у меня на чердаке). Почему это обозвали сплайном Эрмита (а не кубической кривой Безье в форме Фергюссона, как раньше) - не знаю; ночь, мне пока лень смотреть текст.

-- 25 сен 2011, 00:18 --

8bit в сообщении #486113 писал(а):

$\frac{du}{dx} = \frac {1-0}{x_B - x_A}$
$\frac {du}{dy} = \frac {1-0}{y_B - y_A}$
Если у граничных точек $A(x_A, y_A), B(x_B, y_B)$ какие-либо координаты совпадают, то это производные не существуют.

Ну да, кто-то зачем-то перевернул естественные $\frac{d(x,y)}{du}$, сделал из них $\frac{du}{d(x,y)}$, и вполне нормальные нулевые производные "перестали существовать". А всего-то --- кривая из точки $A$ выходит горизонтально или вертикально. А повернём чуть-чуть, и всё "существует", всё ОК. Ерунда какая-то, на первый взгляд. И производные подозрительно выглядят (на первый взгляд).

-- 25 сен 2011, 00:19 --

И, кстати, у Вас был параметр $t$, а тут какое-то $u$ объявилось. Это что? Я думал про это, как про $t$.

-- 25 сен 2011, 00:28 --

(Оффтоп)

Ой, Вы так легко добываете статьи, за которые с меня 39 баксов требуют (и потом скучняк какой-то оказывается). Платить за эту я пожадничал --- по аннотации вижу, что знаю больше чем они (и всё на форуме написано, в той теме про бидуги).
Может, Вы можете мне её добыть?
(Я, конечно, не прошу платить за меня эти 39 баксов!!! )

-- 25 сен 2011, 00:32 --

8bit в сообщении #486113 писал(а):

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

Ничо не понял. Вы сформулировали слишком общую задачу, о чём я уже писал, на примере тех же бидуг. Что для Вас есть "хорошая кривизна" --- никому до сих пор не понятно.

[8bit]

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

Какой формулы Вам не хватает (если Вы имеете в виду бидуги)? Центр окружности не можете найти?

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

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

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

точно, тогда не буду рассматривать такое представление, тем более решение не всегда существует.

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

И, кстати, у Вас был параметр t, а тут какое-то u объявилось. Это что? Я думал про это, как про t.

просто в pdf'ке такое обозначение параметра

(Оффтоп)

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

Может, Вы можете мне её добыть?

ссылку на препринт в теме запостил

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

Ничо не понял. Вы сформулировали слишком общую задачу, о чём я уже писал, на примере тех же бидуг. Что для Вас есть "хорошая кривизна" --- никому до сих пор не понятно.

раз сплайн Эрмита оказался другим представлением, тогда этот вопрос снимается.

Остановился на трех кривых
[*]кривой Безье
[*]рациональной кривой (Безье)
[*]бидуге

[Алексей К.]

8bit в сообщении #486145 писал(а):

точно, тогда не буду рассматривать такое представление, тем более решение не всегда существует.

Так это эквивалентное представление (скобки раскрыли), и существование решений не зависит от этого факта. Если Вы имеете в виду моё замечание

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

задача решабельна (вопрос лишь в том, будет ли решений 4,3,2,1, или 0),

то оно касалось G2-задачи (и там это явно указано). Для Вашей G1-задачи решений прорва (щас попробую нарисовать). Рассматривать не надо, раз уж Вы эквивалентный вариант включили первым номером списка.

-- 25 сен 2011, 12:26 --

Вот упомянутая прорва решений (обычные кубические кривые Безье). Там несколько страниц, листать надо (GsView). Углы в подсвеченной строке можно поменять.

1. %! 
2. /Alpha 110 def /Beta -60 def % angles 
3. /c 150 def % half-chord 
4. 25 25 400 {/p exch def 
5. save 
6. 300 200 translate 
7. /Helvetica findfont 16 scalefont setfont 
8. c neg 0 2 copy 2 0 360 arc closepath fill 
9. c 0 2 copy 2 0 360 arc closepath fill 
10. 4 copy moveto -3 -16 rmoveto (B) show 
11. moveto -3 -16 rmoveto (A) show 
12. moveto lineto stroke  
13. 1 0 0 setrgbcolor 
14. 25 25 400 {/q exch def 
15. c neg p Alpha cos mul add p Alpha sin mul 
16. c q Beta cos mul sub q Beta sin mul neg c 0 6 copy 
17. 1.2 setlinewidth c neg 0 moveto curveto stroke 
18. .4 setlinewidth moveto lineto lineto c neg 0 lineto stroke 
19. currentrgbcolor 3 1 roll setrgbcolor % 0 20 translate 
20. } for 
21. showpage 
22. restore 
23. } for 
24. %%EOF 

[Алексей К.]

8bit в сообщении #486145 писал(а):

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

Известна ещё и кривизна! Никаких уравнений не надо.

$$X_{center}= x_A - \frac{\sin\alpha}{k},\quad Y_{center}=y_A + \frac{\cos\alpha}{k}.$$

Точка сопряжения понадобится лишь для определения границ дуги.

[8bit]

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

8bit в сообщении #486145 писал(а):
точно, тогда не буду рассматривать такое представление, тем более решение не всегда существует.
Так это эквивалентное представление (скобки раскрыли), и существование решений не зависит от этого факта. Если Вы имеете в виду моё замечание

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

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

Вот упомянутая прорва решений (обычные кубические кривые Безье). Там несколько страниц, листать надо (GsView). Углы в подсвеченной строке можно поменять.

Еще не смотрел, но вижу, что хорошая штука postscript, раз можно в виде программы рисовать кривые. А я обычно мучаюсь с visio, а там и кривых Безье нет, по крайней мере я не нашел. А Безье рисую в векторном редакторе или mathcad, когда нужна точность.

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

Известна ещё и кривизна! Никаких уравнений не надо.
Точка сопряжения понадобится лишь для определения границ дуги.

Спасибо, на днях попробую построить.