Задача вот какая. 
В пространстве дано куча точек, располагаются черт зная как на разном расстоянии друг от друга. 
Необходимо выполнить интерполяцию, чтоб обрисовать карту (содержащею значение поверхности на регулярной сетки) и выгрузить ее в специальный формат.
У нас смеются спец. ПО, которая делает это. Позволяет использовать много алгоритмов (Global B-Spline, Local B-Spline,Converging average...), но о них кроме формул, я ничего не найду, а если и находится, то алгоритмы только для функции одной переменной. Бикубическая интерполяция дает результат только в случае одинокого шага всех точек по сетки...
У кого есть может готовые алгоритмы, без кучи формул, а то долго возиться не хочется...


Это сообщение отредактировал(а) Zakhar_Shan - 22.12.2012, 14:41

http://www.alglib.net/interpolation/

1) Без формул -- никак, это вполне себе нетривиальная задача.
2) Кстати, в OpenGL этого тожэ нет.
3) Самое мне подходящее что я пока что видел из этого разряде -- ABOS, реализованный в SurGE. Но исходников не дают (почему-то), только описание, по которому, впрочем, вполне реально реализовать.
Но там есть довольно много ссылок, в т.ч. и на OpenSource утилиты, и на приличное введение в проблемы.
4) Для начала попробовать и что-нибудь простое. Например, присвоить каждой точке данных в каждой точке сетки вес, в зависимости от расстояния между точкой сетки и точкой данных. Уменьшающийся с расстоянием вес, разумеется. Удобно -- нелинейно уменьшающийся (ну, там пропорцыонально минус второй-третьей степени расстояния).
И затем взять среднее значение в данной точке сетки с учётом весов (т.е. сумма по всем точкам данных вес*значение, и поделить на сумму весов). Для более-менее гладких и нечастых данных нормально работает. 

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

Это сообщение отредактировал(а) baldina - 22.12.2012, 23:05

Читал, только все там для функции одной переменной, а у меня x,y,z ....

1) Да ни то что бы совсем без формул, просто библиотеку хочется простенькую...
2)Жаль, думал как ни будь соберусь, изучу и все мне по плечу будет....
3) Спасибо, почитаю:)
4)Это линейная интерполяция, ее тоже нашел, но вот она не гладкая совсем  

Не совсем рельеф, но что-то сходное есть, спасибо, почитаю:)

от первой до второй один шаг. линейная определяется по двум точкам полиномом первой степени. квадратичная - по трем точкам полиномом второй степени и т.д.
если точки интерполировать регулярной сеткой (любым подходящим способом), на регулярной сетке можно строить поверхности желаемой гладкости (NURBS например)

Бикубик, насколько я знаю, делается по 4м точкам. При помощи метода наименьших квадратов строиться парабола наилучшим образом проходящая через 4 точки. Искомая же точка должна находиться между 2й и 3й точками (счет от единицы). Подставляем координаты Х в уравнение параболы и получаем Y .
 Для случая 3D сначала ведется интерполяция в одной плоскости (например XZ), затем второй (YZ) . Если же это задача графики, то интерполировать нужно не только координаты, но и нормали каждой точки. В принципе, нормаль ни чем от координат не отличается. 

Ну, RBF по приведённой ссылке -- из того, что надо. Это последний раздел как раз. Если нужна гладкость -- то как раз, медленно, зато вполне гладко. Но шумы по-моему будут валить сходимость.

Добавлено через 2 минуты и 1 секунду


Кстати, про почитаю -- исходников-то не дают, а бинарники -- пожалуйста. Так что можно сравнительно быстро проверить, подойдёт ли этот метод.
Впрочем, если вещь не особенно отчуждаемая (не будет стоять вопросов про копирайты) -- то сравнительно просто surgef.exe использовать в своей программе. Подготовил файл с точками, запустил, получил выходной grid.

Добавлено через 3 минуты и 36 секунд


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

нэмного заметил ;) речь о том, что для регулярной может быть использована нерегулярная (если например её заведомо проще строить)