Algorytmy 2D poziomu szczegółowości (LOD)

Question

Zbadałem w sieci algorytm, który umożliwia tworzenie poziomów szczegółowości (LOD) reprezentacji wieloboków 2D, ale nie jestem w stanie znaleźć ŻADNYCH przyzwoitych referencji. Być może używam złych terminów wyszukiwania, ale wszystkie wyniki wyszukiwania są dla algorytmów 3D LOD, które, jak sądzę, nie mogą (?) Naprawdę być stosowane w 2D.

Jestem pewien, że przed atakiem grafiki 3D wiele osób pracowałoby nad algorytmami 2D LOD. Jakieś wskazówki lub wskazówki, skąd mogę uzyskać więcej informacji? Dzięki!

Answer 1

Oprócz oczywistego najgłupszego algorytmu, jakim byłoby zajęcie każdego N-tego wierzchołka z wielokąta (zmniejszenie liczby wierzchołków o N), mamy pomysł zainspirowany niektórymi algorytmami 3D.

Zwykle w 3D wymagane jest usunięcie ścian, które przyczyniają się mniej do całkowitej głośności. Aby to zrobić, staramy się uprościć "najlżejsze" obszary modelu.

Teraz w 2D, można przetłumaczyć na „uproszczenie segmenty, które mają najmniejszy kąt pomiędzy nimi Pierwsza naiwna realizacja może być:.

1. Compute wszystkie kąty między segmentami Si i Si + 1 wielokąt
2. Wszystkie kąty poniżej danego progu (lub przyjmuj najmniejsze kąty)
3. Uprość zidentyfikowane segmenty w 2. (zamień [Pi, Pi + 1] i [Pi + 1, Pi + 2 ] przez [Pi, Pi + 2])
4. Powtórz od 1 do momentu, aż wystarczająco zmniejszysz nasz polyg na

Oczywiście nie jest to optymalne, ale powinno to być dobre połączenie jakości i szybkości. Zamiast kąta, można przyjąć minimalną odległość między środkowym punkcie dwa segmenty (Pi + 1) oraz potencjalnie uproszczonej segmencie ([Pi, Pi + 2])

Edit:

inny algorytm I próbowałby gdybym nie trzeba zbyt dużo wydajność:

1. Rozważmy orginału wielokąta jako punkty kontrolne splajnu Catmull-Rom
2. Tesselate to spline na żądanej liczby punktów

Wreszcie znalazłem trochę kodu źródłowego dla was na ten link: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, jak również powiązanych algorytmów: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

Answer 2

Szukaj Douglas-Peucker algorithm który jest stosowany w celu uproszczenia polilinie, ale może zostać przedłużony do wspierania wielokątów. To jest to, czego użyłem. Istnieją również topologicznie stabilne rozszerzenia, jeśli tego potrzebujesz.