Jest funkcja dwóch zmiennych, powiedzmy taka (w C/C++):

double f(double x, double y);

Powiedzmy, że mam jakiś zbiór sampli, czyli wartości tej funkcji dla kilku wybranych
x,y.
Chciałbym zrobić interpolację tej funkcji, czyli taką fukcję g(x,y), która *z
grubsza* wygładzi znane sample z f(x,y).

Sample mogę mieć posortowane, np. leksykograficznie po x i y. W szczególności mogą
być w takiej mapie:

std::map<std::pair<double, double>, double>
^ ^ ^
x y wartość

albo w czymś innym.

Pierwsze przybliżenie jest takie, żeby znaleźć 3 sample, które są najbliżej szukanego
punktu, zrobić na nich (i na wartościach funkcji w tych samplach) płaszczyznę i
poszukać gdzie na tej płaszczyźnie (w sensie wartości z) wypada szukany punkt x,y.
Wadą tego pierwszego przybliżenia jest ilość obliczeń przy każdym szukaniu. Chciałbym
jak najmniej.

Potencjalnym rozwiązaniem (zakładając, że wszystkie wartości są fizyczne i mają jakiś
akceptowany błąd pomiaru) jest ograniczenie dziedziny z góry i wyliczenie jakiegoś
akceptowalnego rastra (powiedzmy NxM) off-line, interpolowanego choćby jak wyżej na
podstawie sampli i użycie tego wyliczonego rastra jako gotowego słownika w run-time.
Jestem gotów zapłacić większym zużyciem pamięci za mniejszy czas obliczeń.
Ktoś ma inny pomysł?

--
Maciej Sobczak * http://www.inspirel.com

do góry

Choroba, po raz pierwszy się głupio nie pytam, tylko podpowiadam... ;-)



> Chciałbym jak najmniej.


Panie, a kto by nie chciał!

https://pl.wikipedia.org/wiki/Triangulacja_Delone
Węzły w kd drzewie. Pasuje?

Jako zatwardziałego inżyniera, kłuje mnie w oczy "interpolacja"... bez przymiotników.
;-)

do góry

W dniu 2018-12-12 o 09:00, Maciej Sobczak pisze:
> Jest funkcja dwóch zmiennych, powiedzmy taka (w C/C++):
>
> double f(double x, double y);
>

Przeszedłbym na raster wartosci w regularnych oczkach, rozmieszczonych
w odstepach (dx, dy) - taka siatka węzłów. Z marszu nie wiem jak to
zgrabnie zrobic. Problemem moze byc ocena jakie ma byc dx, dy.

Majac taki raster, aby dostac wartosc funkcji w punkcie (x, y) wezmiesz
mieszanke wartosci z kazdego z 4-rech najblizszych węzłów, wagami będą
odległości od tychze węzłów. Taka aproksymacja płachty czworokatami.
Jakby co mam to zrobione.

pozdr serd
--
A S

do góry

On Wednesday, December 12, 2018 at 9:00:02 AM UTC+1, Maciej Sobczak wrote:
> Jest funkcja dwóch zmiennych, powiedzmy taka (w C/C++):
>
> double f(double x, double y);
>
> Powiedzmy, że mam jakiś zbiór sampli, czyli wartości tej funkcji dla kilku
wybranych x,y.
> Chciałbym zrobić interpolację tej funkcji, czyli taką fukcję g(x,y), która *z
grubsza* wygładzi znane sample z f(x,y).
>
> Sample mogę mieć posortowane, np. leksykograficznie po x i y. W szczególności mogą
być w takiej mapie:
>
> std::map<std::pair<double, double>, double>
> ^ ^ ^
> x y wartość
>
> albo w czymś innym.
>
> Pierwsze przybliżenie jest takie, żeby znaleźć 3 sample, które są najbliżej
szukanego punktu, zrobić na nich (i na wartościach funkcji w tych samplach)
płaszczyznę i poszukać gdzie na tej płaszczyźnie (w sensie wartości z) wypada szukany
punkt x,y.
> Wadą tego pierwszego przybliżenia jest ilość obliczeń przy każdym szukaniu.
Chciałbym jak najmniej.
>
> Potencjalnym rozwiązaniem (zakładając, że wszystkie wartości są fizyczne i mają
jakiś akceptowany błąd pomiaru) jest ograniczenie dziedziny z góry i wyliczenie
jakiegoś akceptowalnego rastra (powiedzmy NxM) off-line, interpolowanego choćby jak
wyżej na podstawie sampli i użycie tego wyliczonego rastra jako gotowego słownika w
run-time. Jestem gotów zapłacić większym zużyciem pamięci za mniejszy czas obliczeń.
> Ktoś ma inny pomysł?
>
> --
> Maciej Sobczak * http://www.inspirel.com

Jak możesz sobie policzyć f dla danej siatki, to bym poszedł
w powierzchnie NURBS. Tam możesz sobie dobrać stopień wielomianów, liczbę przedziałów
itp. tak żeby mieć wybór
między dokładnością, a złożonością obliczeniową.

w.

do góry

> Przeszedłbym na raster wartosci w regularnych oczkach, rozmieszczonych
> w odstepach (dx, dy) - taka siatka węzłów. Z marszu nie wiem jak to
> zgrabnie zrobic. Problemem moze byc ocena jakie ma byc dx, dy.

Oceną może być dokładność pomiaru x,y, bo to i tak są wartości fizyczne, więc nie ma
potrzeby, żeby dx,dy było mniejsze, niż rozdzielczość pomiaru. Potem można przy
każdym wywołaniu zaokrąglić do najbliższego oczka.

> Majac taki raster, aby dostac wartosc funkcji w punkcie (x, y) wezmiesz
> mieszanke wartosci z kazdego z 4-rech najblizszych węzłów, wagami będą
> odległości od tychze węzłów.

I tego ostatniego pomysłu mi brakowało. Tzn. mając już ten raster nie trzeba robić
mieszanek, tylko zaokraglić do najbliższego x,y i wziąć gotową jedną wartość z rastra
- natomiast mieszanka z wagami pomoże wyliczyć off-line sam raster na podstawie
zmierzonych sampli.
Oczywiście "wagami będą odległości" to skrót myślowy - chcemy, żeby najmniejsza (być
może zerowa) odległość miała największą (być może 100%) wagę.

Dziekuję,

--
Maciej Sobczak * http://www.inspirel.com

do góry