Сплайны Безье

[Debugger]

Есть последовательность точек. Назовем их исходными.
Необходимо соединить их кривой так, чтобы она проходила через исходные точки.
Для этого я беру каждые две соседние исходные точки и пытаюсь построить по ним кривую Безье. Соответственно, для этого дела ещё нужно и 2 (или одна) дополнительные точки.
Итак, вопрос: как найти координаты дополнительных точек, если известны исходные? Википедия говорит, для того, чтобы все было зашибись, необходимо, чтобы одна исходная и две соседние дополнительные точки лежали на одной прямой.
P.S. Так как это все таки не программирование, размещаю в Трепе.

[Хакер]

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

Так что задача нерешаема при данных условиях.

[Debugger]

Под "кривой" я подразумеваю последовательность кривых Безье.
Added:
А решений задачи будет бесконечное множество, да.

[Хакер]

Понял, что задача поставлена некорректно?

[MIT]

Как через одинаковый набор точек можно провести бесконечное количество кривых Безье? Формулы дают совершенно определенное и единственное положение любой точки кривой.

[Хакер]

Пожалуйста: набор точек (4 точки) одинаков, на картинке 4 разных варианта сплайна Безье, проходящих через заданные точки.

[MIT]

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

Т.е. либо у тебя просто какие-то кривые, проведенные через 4 точки, либо это сплайн Безье, но опорных точек намного больше.

Вот простенькая программа, рисующая сплайн по формулам Безье с десятью опорными точками:

B.rar

сначала Randomize, затем Draw

(8.32 Кб) Скачиваний: 201

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

[Хакер]

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

А программа твоя вообще не запускается.

[Александр Дмитриев]

как найти координаты дополнительных точек, если известны исходные?

Их не нужно искать, они должны быть заданы. В исходной постановке задачи рисования безье-сплайна. Чтобы нарисовать безье-сплайн, тебе нужны набор точек, через которые он должен проходить, и для каждой точки две дополнительные точки, которые будут определять то, как этот сплайн будет идти через эту точку.

Если тебе нужно провести линию без дополнительной инфы, просто имея только те точки, через которые нужно провести кривую, то это уже не Безье, а кубический сплайн или аналогичное http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%81%D0%BF%D0%BB%D0%B0%D0%B9%D0%BD. Но в общем-то в большинстве случаев это будет выглядеть некрасиво.

Ой, или ты спрашиваешь про то, как без дополнительной инфы самостоятельно найти эти две точки и построить кривую Безье так, чтобы в конечном итоге получилось красиво?

[Хакер]

Ой, или ты спрашиваешь про то, как без дополнительной инфы самостоятельно найти эти две точки и построить кривую Безье так, чтобы в конечном итоге получилось красиво?

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

[Александр Дмитриев]

Так. Придумал способ. Линию, которая проходит через две доп. точки (и через исходную точку) нужно рисовать параллельно линии, проходящей через две исходные точки, соседние с нашей исходной. Расстояние от исходной точки до доп. точки класть равным половине расстояния до соседней исходной точки или меньшее. Например, ввести этакий "коэффициент угловатости", на который умножать половину расстояния до соседней исходной точки. При малом коэффициенте кривая будет более угловатая. При коэффициенте 0 получится ломаная линия, при коэффициенте 1 будет максимально округлая линия, при значениях больше 1 получатся "завихрения". Можно не один коэффициент для всех точек ставить, а для разных областей разные.

Вообще, по-моему, здесь нужно знать, для чего конкретнее это нужно, потому что от этого сильно зависит понятие "красиво".

А программа твоя вообще не запускается.

Для неё нужен Framework 2.0.

[Хакер]

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

[Александр Дмитриев]

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

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

[Хакер]

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

[Александр Дмитриев]

Ты дай побольше картинок, мы, может быть, догадаемся, как он рисует.

А если софт не ты писал, может быть там не Безье, из картинки так не очень следует.

Противоречишь сам себе:

У них своё понятие о красивом сплайне. У меня понятия нет.

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

[MIT]

Я вот тут немного дописал программку, и пришел к выводу, что рисование искомой кривой-сплайна по формулам Безье через заданные точки - не такая и сложная задача. При этом её можно сделать красивой.
Отрисованный сплайн:


Сплайн с обозначением заданных точек:


Сплайн с обозначением точек построения, линий построения и линий сглаживания (совмещения кривых):



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



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

[Хакер]

Ну и?

[MIT]

Да и не ну и. Просто высказал свое мнение, что это не очень сложно, и показал как оно по-моему должно выглядеть.

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

[Александр Дмитриев]

Применил к сплайну MIT'а свой метод (рисовал в фотошопе на глаз):

Коэффициент угловатости 1:



Коэффициент угловатости 0,5:



Для второго случая у Хакера получается почти попиксельная копия его картинки:

[Хакер]

Вы постинги накручиваете?

[Debugger]

В .NET линия создается легко и непринуждённо, вызовом AddCurves класса GraphicsPath. Результат меня удовлетворяет: получившаяся кривая проходит через все точки и получается плавная кривая (без углов).
Все здорово, но как в принципе такое делается?

[Debugger]

Отрисованный сплайн:

То, что доктор прописал! А как ты подбирал координаты дополнительных точек?

[MIT]

А как ты подбирал координаты дополнительных точек?

Куча тригонометрии (хотя и простой), если хочешь, могу сфоткать листок с расчетами.
Ну или возьми Рефлектор, да посмотри.

[Proxy]

Эмммм. Ну как бы поворотом на 180 градусов точки, предшествующей первой точке (отн. первой точки) и поворотом на 180 градусовпоследующей, после второй точки, относительно второй точки.

Дополнительные - P1 и P2. Они же получены поворотом на 180 градусов предыдущей точки последовательности относительно P0 и поворотом последующей точки последовательности относительно P3.
Вот как-то так.

[Debugger]

Гм)
Тогда не у тебя получившиеся точки не будут удовлетворять условию, взятой из википедии. То есть, P2 (рассчитывается), P3 (дана) и P4 (рассчитывается) могут и не лежать на одной прямой.

[Proxy]

Как две точки могут не лежать на одной прямой? Через две точки одна прямая по-любому проходит. И какая P4? Где?
P0 и P3 даны, P1 и P2 вычисляются из предшествующей и последующей точки соответственно.
Т.е. дан к примеру массив точек P(), тогда чтобы построить часть кривой между P(1) и P(2) нужно за первую дополнительную (опорную) взять точку, полученную поворотом на 180 градусов точки P(0) относительно P(1); за вторую доп. - поворотом на 180 градусов точки P(3) отн. P(2). И из таких промежуточных частей сложить искомую кривую.

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

[Mikle]

Debugger

как в принципе такое делается?

Когда-то я этим занимался. Вот пример:
http://tuapse-mikle.narod.ru/SmoothCoord.zip

[Хакер]

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

[Proxy]

Натяжение - отношение числа шагов к длине кривой?

[Debugger]

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

Ты прав, тут бесконечно много решений. Хотелось бы увидеть хотя бы одно.