Algorytmy do kreślenia funkcji (adaptacyjnych?)

21

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?

algorithms visualization

— soegaard
źródło

2

Może to pytanie byłoby lepiej zrozumiałe w przypadku „rysowania funkcji” zamiast „rysowania wykresów”? Na początku źle zinterpretowałem tytuł (teoria grafów).

— astrojuanlu

@ Juanlu001 Dziękuję za sugestię. Zmieniłem tytuł.

— soegaard

Kiedy mówisz 2D, masz na myśli wykreślenie funkcji jednej zmiennej, takiej jak , czy też interesuje Cię funkcja dwóch zmiennych ( ) pokazana w 2D z np. Różnymi kolorami / odcieniami reprezentującymi różne wartości?

f (x)

$f(x)$

f (x, y)

$f(x,y)$

— Szabolcs

Cóż, miałem na myśli wykreślenie funkcji jednej zmiennej. Chciałbym jednak również usłyszeć o algorytmach służących do wybierania punktów do oceny również w ustawieniu dwóch zmiennych. Nie jestem zainteresowany słuchaniem o kolorach i cieniowaniu.

— soegaard

W przypadku funkcji 2D zobacz moje pytanie i odpowiedź tutaj . To, co tam zrobiłem, było dość ograniczone i nie zadziała tak dobrze w przypadku dowolnej funkcji. Ponadto w opisie brakuje kilku istotnych kroków, bez których metoda nie zbiegnie się prawidłowo: musiałem wstawić nowy punkt próbkowania na środku każdej krawędzi siatki, który zniknąłby podczas następnej ponownejangulacji. (ciąg dalszy)

— Szabolcs

10

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łą.

— Victor Liu
źródło

1

Która to książka? Czy to ten, który powiązałem? Czy wiesz, jakie dokładnie zmiany w ich implementacji między wersjami 5 i 6?

— Szabolcs

1

@Szabolcs: Nie, uważam, że było to w tej części 4.1.3 książki . Opis dotyczy bardzo starej wersji Mathematica. Nowsze wersje (być może począwszy od wersji 6) wykrywają pionowe asymptoty i usuwają fałszywe pionowe linie z wykresów. Nowe wersje zdecydowanie wymagają zaawansowanego symbolicznego przetwarzania wstępnego, aby poradzić sobie z nieciągłościami, nieokreślonymi regionami i cięciami gałęzi.

— Victor Liu

Symboliczne przetwarzanie wstępne, o którym mówisz, nazywa się w dokumentacji „wykrywaniem wykluczenia”. Można go wyłączyć albo przez Exclusions -> Noneukrycie struktury funkcji przed Plotzdefiniowaniem jej jako f[x_?NumericQ] := .... Nie o to mi chodziło, kiedy pytałem o zmiany. Myślę, że nastąpiły pewne zmiany w algorytmie, ponieważ próbki v5 i v6 próbkowane były w różnych punktach. W tej chwili nie mogę przetestować na v5, aby porównać ponownie.

— Szabolcs

„The Mathematica Graphics Guidebook” zawierał bardzo dobre omówienie problemu. Szczególnie podobało mi się to, że opisano również niedociągnięcia algorytmu.

— soegaard

Nie mogę już znaleźć pliku GitHub, czy został przeniesiony?

— Andrei

12

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

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

Zacznij od regularnie rozmieszczonej siatki punktów w domenie kreślarskiej. （W Mathematica istnieje parametr kontrolujący liczbę pobranych, nazywany PlotPoints).
$(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}$
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 &]
  ]

— Szabolcs
źródło

7

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ą.

— astrojuanlu
źródło

1

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).

— Chris Rackauckas
źródło