Na wstępie powiem, że nie szukam rozwiązania w postaci kodu w C++ czy jakimkolwiek języku lecz opisu jad dokonać podobnego działania do opisanego poniżej.
Mam punkty, w równym odstępie mierząc po osi X znajdujące się na różnej wysokości Y - chcę uzyskać efekt podobny do tego jaki jest znany z arkusza kalkulacyjnego Excel - linia krzywa (nie łamana) aproksymowana dokładnie przez podane punkty. Pytanie brzmi, jak tego dokonać, jakiego algorytmu (opis) oni używają lub jaki polecacie do tej czynności.
Uzyskany efekt - krzywa przechodząca przez wskazane punkty lecz bez tworzenia dodatkowych przegięć pomiędzy nimi.
Właściwie to jak przegniesz z punktami w Excelu to też Ci wyrysuje z oscylacjami i przegięciami, numeryka to numeryka :)
Btw. jedno uściślenie które ułatwi Ci szukanie informacji - przybliżanie funkcji inną, która przechodzi przez wszystkie zadane punkty, to interpolacja. Wada jest taka, że im więcej punktów, tym więcej oscylacji bo funkcja (zwykle wielomian) dopasowuje się na siłę do punktów i powstają oscylacje. Aproksymacja daje funkcję zadanego typu (np. wielomian tego i tego rzędu czy np. eksponenta) która daje najmniejszy błąd dla zbioru punktów (tj. najmniejsze średnie, a na ogół średnio-kwadratowe odchylenia od punktów które aproksymuje) ze wszystkich możliwych funkcji tego typu. Wyznacza się ją tak, że bierzesz wzór na błąd (zwykle suma po kwadratach odchyleń w punktach) i różniczkujesz po kolei po parametrach funkcji aproksymującej (np. współczynnikach wielomianu). Z racji tego, że współczynniki występują w pierwszej potędze, to po zróżniczkowaniu błędu po wszystkich współczynnikach dostaniesz układ równań liniowych mający tyle zmiennych, ile masz parametrów :) Była chyba jeszcze jakaś inna metoda, ale w sumie już jej nie pamiętam. Może Ci się przyda jakbyś chciała wyznaczać linię trendu albo coś :)
Z opcji masz jeszcze interpolację ale wykonywaną nie na wszystkich punktach wykresu, a tylko wybranym podzbiorze (dla danego punktu), np. wspominany tu B-splines to w sumie interpolacja krzywej parametrycznej z "okolicznych punktów". Dzięki temu, że B-splines (i NURBS) interpolują krzywą także z punktów sąsiadujących z dwoma punktami, które ma połączyć krzywa, pozwalają uzyskać gładkie przejścia (ciągła pierwsza pochodna) między poszczególnymi "przedziałami". Gdyby z kolei zrobić interpolację jak funkcjami kształtu z MES tj. podzielić przedziały na grupy po np. 3 (4 punkty, graniczne są wspólne) i interpolować całość krzywej przechodzącej przez dane 4 punkty, mielibyśmy też wielomiany 3 stopnia, ale nie byłyby zapewne gładkie na granicach, a miały mniejsze lub większe załamania :)
Brzydkie rysunki poglądowe - ten ilustruje jak to wygląda w przypadku pojedynczego fragmentu B-spline'a - bierzemy 4 punkty, ale krzywa łączy tylko dwa:
Tutaj interpolacja funkcjami kształtu 3 rzędu - widać że na granicy (w punkcie p2) mamy "załamanie" zamiast gładkiego przejścia:
Jeśli potrzebujesz tego po prostu aby narysować wykres, to w sumie nie masz chyba po co zawracać sobie głowy funkcjami kształtu, bo efekt nie będzie aż tak ładny, szczególnie dla małej liczby punktów. Z drugiej strony, jeśli potrzebujesz tej interpolacji do jakichś konkretniejszych obliczeń, a nie po to, by wyglądało ładnie, to w sumie funkcje kształtu mogą być lepszym wyborem. Słyszałem wprawdzie o kimś, kto kombinuje nad wykorzystaniem NURBS w MES, ale nie znam zbyt wielu szczegółów, nie chcę zgadywać, a nie spotkałem się jeszcze z wykorzystaniem jakichkolwiek krzywych sklejanych w sofcie symulacyjnym, choć może za mało się interesowałem :)
Nieważne, popłynąłem. Możesz przyjąć, że bierzesz w zasadzie dowolną liczbę punktów w otoczeniu punktu, w którym interpolujesz. Im więcej, tym wyższy rząd wielomianu uzyskasz. W B-splinach każdą współrzędną interpolujesz ze współrzędnych 4 punktów, więc dostajesz wielomian 3 rzędu - wystarczająco wysokiego, by uzyskać gładkie krzywe dobrze przybliżające większość kształtów, ale na tyle niskiego, że raczej nie ma jakichś dziwnych oscylacji - no chyba, że masz jakiś znaczny skok wartości między dwoma punktami, wtedy w pobliżu mogą się i tak pojawić niechciane przegięcia. Gdybyś wzięła 6 punktów do interpolacji, miałabyś wielomian 5 rzędu (i pewnie te niechciane oscylacje). Dla 2 punktów interpolujesz po prostu odcinkiem. Ogólnie dla n punktów istnieje dokładnie 1 wielomian n-1 rzędu, który przez wszystkie te punkty przechodzi. Możesz poeksperymentować z różnymi rzędami wielomianów i zobaczyć, który da Ci najbardziej zadowalający rezultat :) Zarówno z krzywymi sklejanymi, jak i trochę bardziej uproszczonym wariantem z podziałem
I jeszcze łap materiały o interpolacji do poduszki, tylko uprzedzam, że nie jest to napisane językiem przyjaznym ludziom biorącym wszystko "na chłopski rozum" (jak ja na przykład):
http://home.agh.edu.pl/~szeliga/dydaktyka/MN/main-Interpolacja.pdf
A tu masz dla przykładu opisane (od strony 5) funkcje kształtu, które wykorzystywane są do takiego "lokalnego" interpolowania wartości funkcji na pewnym zadanym podobszarze (w elemencie skończonym). To te, które nie dają gładkich przejść:
http://www.metal.agh.edu.pl/~milenin/Dydaktyka/MES/MileninGL7-8_pl.pdf
