Построение кривых линий по заданным точкам

[rockclimber]

Здравствуйте.

У меня есть пара вопросов, надеюсь на помощь в виде направления "куда копать".
Мне нужно по заданным точкам строить кривую линию. Реализовано будет все в виде программы, где пользователь будет задавать точки, а программа по ним строить линию. Почему не устраивают готовые графические пакеты и т. п.: мне нужны "внутренности" алгоритма и промежуточные данные, получающиеся в процессе вычисления координат точек при выводе на экран (я пока полагаю, что мне это пригодится). Почему не устраивает готовый код: мне все равно нужно разобраться в геометрических основах методов построения, разбираться я все равно буду дольше, чем свой код писать.
Пока мне удалось найти следущее:
1. Кривые Безье. Просто и понятно. Алгоритм рисования написал буквально за считанные минуты, разобраться - очень просто (достаточно было посмотреть gif анимацию в Википедии в статье про них). Но есть ряд особенностей, которые мне не нравятся. Например то, что изменение координат одной точки изменяет форму всей кривой. Я пробовал разбивать кривую на несколько кривых (плюс пара ухищрений для сохранения гладкости в местах разбиения) - в принципе, выглядит неплохо, но объяснить пользователю, что я намалевал и как оно работает, в таком варианте выглядит непростой задачей.
2. Сплайны. Немного сложнее, но одной Википедии уже не достаточно. Пока вдумчиво не читал.
3. NURBS (подвид сплайнов, как я понимаю). Какая-то мозголомная математика, я нашел один сайт с объяснением, как строить кривую, там было десять страниц трехэтажных формул. Либо я нашел не то, что нужно, либо NURBS мне не подходит.
При этом разных видов сплайнов, как я понимаю, вагон и маленькая тележка, просто понять, чем они друг от друга отличаются, уже не просто.
Хотелось бы совета, что попробовать (и что про это почитать). Главное пожелание к алгоритму - простота (и для понимания, и для вычисления). Еще хотелось бы, чтобы кривая проходила через опорные точки, и изменение положения точки не затрагивало всю кривую. Английский немного знаю, можно ссылки на английские источники.

[ИСН]

Это ложное противопоставление.
Ваша кривая либо обязана быть функцией от x, либо не обязана. Третьего не дано. В первом случае надлежит делать по сплайнам, во втором - по Безье с ухищрениями, как обычные кривые в графических редакторах. Друг с другом эти варианты не конкурируют. Совсем.

[rockclimber]

Понятно, спасибо. А какие-нибудь стоящие "ухищрения" для кривых Безье можете посоветовать? Я пока придумал на каждом втором отрезке делать промежуточную точку. Пользователь задает точки 1, 2, 3, 4, 5, ..., дополнительные точки вставляются после 1, 3, 5, ... (1', 3', 5'), затем строятся кривые третьего порядка 1' - 2 - 3 - 3', 3' - 4 - 5 - 5' и т. д. Выглядит довольно гладко.

[Aritaborian]

rockclimber в сообщении #707931 писал(а):

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

Всё это (и много чего ещё) умеет Wolfram Mathematica. Справка доступна онлайн. Поищите там по ключевым словам «spline», «Bezier» etc.

[_Ivana]

Простите, но рискну не согласиться с ув. ИСН. Сплайны могут быть построены так - весь массив точек помещаем в какую-то систему координат, точки нумеруем по порядку желаемого прохождения кривой, получаем нумерованный набор иксов и игреков. Вводим сетку параметра, хоть равномерную (для простоты) и интерполируем одномерную задачу - иксы от параметра и игреки от параметра, хотя бы самым простым сплайном Катмулла-Рома. Получаем пару функций - иксы и игреки от параметра, строим кривую. Если сплайн локальный, например по 4 точкам, то изменение одной точки затрагивает кривую только в +-3 точках от нее. Если непонятно - спрашивайте, постараюсь пояснить.

[Алексей К.]

rockclimber в сообщении #707931 писал(а):

Мне нужно по заданным точкам строить кривую линию.

Что значит "по заданным точкам"? Чтобы кривая проходила через эти точки? Тогда кривые Безье, за которые Вы так страстно зацепились, совсем ни при чём.

Задал пользователь две точки. Какую кривую Вы через них собираетесь проводить?

$$\begin{picture}(100,100) \put(50,0){\circle*{8}} \put(60,100){\circle*{8}} \color{red}\bezier(50,0)(100,50)(60,100) \color{blue}\bezier(50,0)(30,50)(60,100) \color{green}\bezier(50,0)(30,20)(50,50)\bezier(50,50)(70,80)(60,100) \end{picture}$$

Красную? Синюю? Зелёную? Малиновую? Чёрную? (все нарисовать не успел)
Причём тут какие-то пакеты? Задачу надо поставить нормально.

Вы же, наверное, понимаете, что через заданные 5 (всего лишь пять) точек проходит около трёх миллионов разных кривых (это я только гладкие щитал)!

[_Ivana]

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

[Алексей К.]

Было бы полезно, чтобы автор это понимал и сумел объяснить свои пожелания. Не только сумел, а счёл бы это своим долгом. Нпример, такие мелочи, как кривая типа функция $y=f(x)$, или как юзеру вздумается. И не мелочи тоже.

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

-- 09 апр 2013, 23:53:28 --

(Оффтоп)

rockclimber в сообщении #707931 писал(а):

3. NURBS (подвид сплайнов, как я понимаю). Какая-то мозголомная математика

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

[rockclimber]

_Ivana в сообщении #707962 писал(а):

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

Я не могу поставить задачу четче в силу отсутствия соответствующих знаний. Надо точки соединить линией. Чтобы алгоритм был понятен (мне) и прост в реализации (программной, моими силами). Чтобы линия проходила либо через точки, либо как можно ближе. Чтобы было интуитивно понятно (как расположить точки, чтобы кривая совпала с задуманной). Что тут еще можно уточнять? Я не знаю. Все, что я знал, я написал.
За наводку на сплайн Катмулла-Рома - спасибо, почитаю. Вы вроде меня поняли, что я хочу.

[ИСН]

_Ivana в сообщении #707960 писал(а):

интерполируем одномерную задачу - иксы от параметра и игреки от параметра

Дак это и есть Безье.

rockclimber в сообщении #707969 писал(а):

Все, что я знал, я написал.

Вы не написали, должна ли кривая быть графиком функции от x.

[rockclimber]

ИСН в сообщении #707970 писал(а):

rockclimber в сообщении #707969 писал(а):

Все, что я знал, я написал.

Вы не написали, должна ли кривая быть графиком функции от x.

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

[Алексей К.]

rockclimber в сообщении #707969 писал(а):

Я не могу поставить задачу четче в силу отсутствия соответствующих знаний

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

[_Ivana]

rockclimber

(Оффтоп)

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

ИСН ну не знаю, у меня наверное свои извращенные представления о Безье Насколько я понял, Алексей К тоже про Безье отличного мнения.

[ИСН]

Ну ОК, значит, делайте Безье. А почему Вы говорите, что изменение координат одной точки изменяет форму всей кривой? Конечно, кривая должна быть из гладко стыкующихся кусков. Тогда каждая точка тянет только два соседних куска. Да Вы посмотрите, как в Ворде сделано, ну или вообще где угодно.

[rockclimber]

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

(Оффтоп)

_Ivana, а вы злопамятный человек, однако