Algorytmy do kreślenia funkcji (adaptacyjnych?)

Szukam algorytmów do rysowania standardowych wykresów 2D dla funkcji, które mogą, ale nie muszą mieć osobliwości. Celem jest napisanie „Mini-CAS”, więc nie mam a priori wiedzy na temat rodzajów funkcji, które użytkownicy chcą wyświetlać.

Ten problem jest bardzo stary, więc wyobrażam sobie, że w literaturze muszą być pewne standardowe algorytmy. Po raz pierwszy nie odnalazłem referencji za pośrednictwem Google.

Znalazłem jeden interesujący algorytm, mianowicie ten z „YACAS - Księga algorytmów” o nazwie „ Rysowanie funkcji adaptacyjnych”.

W skrócie:

• Czy istnieją standardowe algorytmy?
• Czy istnieje zestaw testów dla znanych trudnych do wykreślenia funkcji?
• Jakie są interesujące artykuły do ​​przeczytania?

W GitHub zaimplementowałem adaptacyjną procedurę próbkowania Mathematiki (jest to pojedynczy plik C, przejdź do drzewa źródłowego pliku nagłówkowego). Opis rutyny znalazłem w dużej książce o Mathematica już dawno temu i od jakiegoś czasu używam różnych wersji tej implementacji. Zasadniczo wykonuje zgrubną próbkę liniową w zakresie zainteresowań, a następnie wraca do udoskonalenia obszarów o wysokiej krzywiźnie. Możliwe, że brakuje niektórych bardzo ostrych funkcji, ale w praktyce uważam to za niezwykle rzadkie. Ten plik zawiera również wersję równoległą.

Wiedza o tym, jak robią to inne CAS, może ci pomóc.

$f(x)$$(x(t), y(t))$$f(x)$

1. Zacznij od regularnie rozmieszczonej siatki punktów w domenie kreślarskiej. （W Mathematica istnieje parametr kontrolujący liczbę pobranych, nazywany PlotPoints).

2. $(x_1, f(x_1)),\; (x_2, f(x_2)),\; (x_3, f(x_3))$$\frac{x_1+x_2}{2}$$\frac{x_2+x_3}{2}$

3. Jeśli nie osiągnęliśmy jeszcze limitu iteracji (ustawionego MaxRecursionw Mathematica), powtórz od kroku 2.

Niektóre z nich omówiono w książce Stan Matagonica w działaniu, którą można zobaczyć tutaj w Google Books .

Wcześniej zaimplementowałem ten algorytm, aby mieć lepszą kontrolę nad tym, ile razy oceniana była moja kosztowna funkcja obliczeniowa. Oto kod Mathematica dla kroku 2:

nd[{points_, values_}] :=
Transpose@{(Drop[points, 1] + Drop[points, -1])/2,
Differences[values]/Differences[points]}

subdivide1d[result_, resolution_, maxAngle_: 10] :=
  Module[
    {deriv, angle, dangle, pos, nf},
    deriv = nd[result\[Transpose]];
    angle = ArcTan[#2] & @@@ deriv;
    dangle = Differences[angle];
    pos = Flatten@Position[dangle, d_ /; Abs[d] > maxAngle/180 Pi];
    pos = Union[pos, pos + 1];
    nf = Nearest[result[[All, 1]]];
    Select[deriv[[pos, 1]], Abs[# - First@nf[#]] > resolution &]
  ]

Strona internetowa MathWorld na temat wykresów funkcyjnych zawiera odniesienia do kilku artykułów, które wydają się być istotne w przypadku wykresów funkcji adaptacyjnych. Cytując stronę:

Dobre procedury rysowania wykresów wykorzystują algorytmy adaptacyjne, które wykreślają więcej punktów w regionach, w których funkcja zmienia się najszybciej (Wagon 1991, Math Works 1992, Heck 1993, Wickham-Jones 1994). Tupper (1996) opracował algorytm [...]

Z drugiej strony w Google natknąłem się na gazetę

www.cs.uic.edu/~wilkinson/Publications/plotfunc.pdf

to wyjaśnia, jak właściwie wybrać domenę i inne rzeczy. Mam nadzieję, że ci się przydadzą.

Znalazłem ten temat i pomyślałem, że powinienem udostępnić stronę z problemami dla programistów, aby dodać go do biblioteki Julia Plots.jl. Wypróbowaliśmy wiele technik, aby zobaczyć, co da dobre wyniki, zaczynając od notatek na temat implementacji Mathematica. Dodanie trochę przycinania, niewielka perturbacja, aby nie zaczynać się dokładnie w punktach końcowych interwału, limit rekurencji i podwójny estymator błędu siatki były konieczne, aby „zrobić to dobrze”. Wątek wskazuje również na otwarty kod źródłowy do implementacji. Zajęło to trochę ulepszenia, ale dodanie tych funkcji uczyniło go dość solidnym (zgodnie z testami, jak pokazano w wątku).