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

Я откопал алгоритмы интерполяции, но все они имеют недостатки:
1. Многочлены Ньютона и Лагражна - ограниеченное количество точек, возрастающая сетка(значение каждого икса должно быть больше предыдущего)
2. Сплайн Катмулла-Рома - постоянная возрастающая сетка
3. Кубический сплайн - возрастающая сетка
4. В-сплайн, NURBS и т.д. - не проходит через заданные точки

Есть ли у кого-нибудь алгоритмы, примеры или хотя бы полезные ссылки, где это можно найти?

STFW. Тебе поможет кубический сплайн. Там нет возрастающей сетки.

captain cobalt
В том алгоритме, что я нашел, кубический сплайн работает только с возрастающей сеткой. Если у тебя есть другой, поделись, plz!

Toxic
А если представить точки (х,у) как функции времени (x(t), y(t)), а t - время, возрастающий параметр.

Сплайн Эрмита тебе тоже может помочь. В исходнике разберешься сам. calcdiff - вычисление производных
Преимущества:
1)Расположение точек произвольное
2)Для изменения положения не нужно пересчитывать весь сплайн
Недостатки: Разрыв в C2

660915078__lpoly.cpp

В догонку. Есть классная книга по сплайнам и не только.
Автор Голованов Н.Н "Геометрическое моделирование". Если где достанешь не пожалеешь

heXone
Спасибо, посмотрю.

Так все-таки, в AutoCAD какой сплайн используется?

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

Не знаю. Может, скорость?

vdk
Toxic
Просто они очень простые в обращении: требуется всего два
направляющих вектора чтобы задать кривую. И с помощью них
можно забацать любую кривую.

Sm_Andrei
Это я читал в MSDN. У меня даже где-то был алгоритм построения по четырем точкам. А вот как с n точек?

0-3 первая, 4-7 вторая и т.д.

heXone
Да, да... Это я тоже читал. Но кажется там вот так считается:
кол-во_точек = (3 * количество_кривых) + 1
Но у нее изломы между кривыми

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

Toxic
Допустим, у тебя такие точки:
A₁,A₂,A₃,A₄,A₅,A₆,A₇
Первая кривая: A₁,A₂,A₃,A₄
Вторая кривая: A₄,A₅,A₆,A₇
Но у нее изломы между кривыми
Если не хочешь чтобы были эти изломы, то у тебя точки A₃,A₄,A₅ должны лежать на одной прямой.
Вот примерчик одной кривой:
управление - (1,2,3,4 изменение координат точек с помощью мыши),(5,6 детализация кривой),(7,8 точками, либо линиями рисовать).
vdk
окружность конечно лучше рисовать не кривой Безье.

1470596526__Bezier.cpp