Biblioteka Tesselacja C++ 2D?

Question

Mam kilka wypukłych wielokątów przechowywanych jako wektor punktów STL (więcej lub mniej). Chcę je bardzo szybko, najlepiej w dość równomiernie rozłożone kawałki i bez "sliver".

Zamierzam użyć tego do wybicia niektórych obiektów na małe kawałki. Czy ktoś wie o dobrej bibliotece do mozaiki wielokątów (dzieli je na siatkę o mniejszych wypukłych wielokątach lub trójkątach)?

Spojrzałem na kilka, które już znalazłem w Internecie, ale nie mogę ich nawet skompilować. Te akademickie typy nie przywiązują dużej wagi do łatwości użytkowania.

Answer 1

CGAL ma pakiety, aby rozwiązać ten problem. Najlepiej byłoby użyć pakietu 2D Polygon Partitioning. Na przykład można wygenerować y monotonia podział wielokąta (pracuje non-wypukłych wielokątów, jak również) i można dostać coś takiego:

y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif

Czas runnning wynosi O (n log n).

Pod względem łatwości obsługi jest to mały przykład kod generujący losowe wielokąta i partycjonowanie go (na podstawie this manual example):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef CGAL::Partition_traits_2<K>       Traits; 
typedef Traits::Point_2          Point_2; 
typedef Traits::Polygon_2         Polygon_2; 
typedef std::list<Polygon_2>        Polygon_list; 
typedef CGAL::Creator_uniform_2<int, Point_2>    Creator; 
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator; 


int main() 
{ 
    Polygon_2 polygon; 
    Polygon_list partition_polys; 

    CGAL::random_polygon_2(50, std::back_inserter(polygon), 
         Point_generator(100)); 

    CGAL::y_monotone_partition_2(polygon.vertices_begin(), 
           polygon.vertices_end(), 
           std::back_inserter(partition_polys)); 

    // at this point partition_polys contains the partition of the input polygons 
    return 0; 
} 

Aby zainstalować CGAL, jeśli jesteś na windows można użyć instalatora aby uzyskać wstępnie skompilowaną bibliotekę i istnieją instrukcje instalacji dla każdej platformy na this page. Instalacja może nie być najłatwiejsza, ale otrzymujesz najczęściej używaną i niezawodną bibliotekę geometrii obliczeniowej tam, gdzie jest, a cgal mailing list jest bardzo pomocny w udzielaniu odpowiedzi na pytania ...

Answer 2

Nieco więcej szczegółów na temat żądanego wejścia i wyjścia może być pomocne.

Na przykład, jeśli próbujesz ustawić wielokąty w trójkąty, prawdopodobnie działa wentylator trójkątów. Jeśli próbujesz wyciąć wielokąt na małe kawałki, możesz zaimplementować jakieś maszerujące kwadraty.

---

OK, źle się domyśliłem - założyłem, że maszerujące kwadraty będą bardziej podobne do maszerujących kostek. Okazuje się, że to coś zupełnie innego, a nie to, co miałem na myśli ...: |

W każdym razie, aby bezpośrednio odpowiedzieć na twoje pytanie, nie znam żadnej prostej biblioteki, która robi to, czego szukasz. Zgadzam się co do użyteczności CGAL.

Algorytm, o którym myślałem, to w zasadzie dzielenie wielokątów liniami, gdzie linie są siatkowe, więc najczęściej dostajesz quady. Jeśli masz skrzyżowanie z wielokątem, implementacja będzie prosta. Innym sposobem na rozwiązanie tego problemu jest traktowanie wieloboku 2d jak funkcji i nakładanie siatki punktów. Następnie po prostu zrób coś podobnego do maszerujących kostek. Jeśli wszystkie 4 punkty znajdują się w wielokącie, wykonaj quad, jeśli 3 tworzą trójkąt, 2 tworzą prostokąt itp. Prawdopodobnie jest to przesada. Jeśli chcesz mieć nieregularnie wyglądające wielokąty, możesz losowo określić położenie punktów siatki.

Z drugiej strony można zrobić podziały w stylu catmull-clark, ale pominąć wygładzanie. Algorytm polega w zasadzie na dodaniu punktu w środku ciężkości i na środku każdej krawędzi. Następnie dla każdego rogu oryginalnego wielokąta tworzysz nowy mniejszy wielokąt, który łączy środkowy punkt krawędzi przed rogiem, rogiem, następnym środkiem krawędzi i środkiem ciężkości.Spowoduje to wyłożenie przestrzeni i będzie mieć kąty podobne do wielokąta wejściowego.

Tak więc, wiele opcji i lubię burzę mózgów, ale wciąż nie mam pojęcia, co planujesz użyć. Czy to tworzy destruktywne siatki? Czy wykonujesz jakieś przetwarzanie siatki, które wymaga mniejszych elementów? Próbujesz uniknąć cieniowania artefaktów Gourauda? Czy jest to coś, co działa jako proces wstępny lub w czasie rzeczywistym? Jak ważna jest dokładność? Więcej informacji dałoby lepsze sugestie.

Answer 3

Jeśli nie chcesz tworzyć całego GCAL w swojej aplikacji - jest to prawdopodobnie łatwiejsze do wdrożenia.

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 4

Jak balint.miklos wymienionych powyżej w komentarzu, triangle pakiecie Shewchuk jest dość dobre. Używałem go sam wielokrotnie; dobrze integruje się z projektami i istnieje interfejs C++ o nazwie triangle++. Jeśli chcesz uniknąć pasków, pozwól trójkątowi dodać (wewnętrzne) punkty Steinera, aby wygenerować siatkę jakości (zwykle ograniczoną triangulację delaunay).

Answer 5

Jeśli masz wypukłe wielokąty i nie jesteś zbytnio powściągliwy w kwestii jakości, to jest to naprawdę proste - po prostu wykonaj ear clipping. Nie martw się, to nie O (n^2) dla wypukłych wielokątów. Jeśli zrobisz to naiwnie (tzn. Zatniesz uszy tak, jak je znajdziesz), otrzymasz wentylator trójkątny, który jest lekkim hamulcem, jeśli chcesz uniknąć pasków. Dwa trywialne heurystyki, które mogą poprawić triangulacji są

1. Sortuj uszy, lub jeśli to zbyt powolne
2. Wybierz ucho w sposób losowy.

Jeśli potrzebujesz bardziej wytrzymałego triangulatora opartego na przycinaniu uszu, sprawdź FIST.

Answer 6

poly2tri wygląda jak naprawdę ładna lekka biblioteka C++ do dwuangażowej delaunay 2D.

Answer 7

Właśnie zacząłem zaglądać w ten sam problem i rozważam tesselację voronoi. Oryginalny wielokąt otrzyma rozproszenie punktów pół-losowych, które będą centrami komórek voronoi, im bardziej równomiernie rozłożone będą bardziej regularne wymiary komórek, ale nie powinny być w doskonałej siatce, inaczej wewnętrzne wielokąty wszystkie będą wyglądać tak samo. Pierwszą rzeczą jest, aby móc wygenerować te punkty środkowe komórek, generując je ponad ramką ograniczającą wielokąta źródłowego, a test wnętrza/na zewnątrz nie powinien być zbyt trudny.

Krawędzie voronoi są przerywanymi liniami na tym obrazku i stanowią rodzaj uzupełnienia triangulacji delaunay. Wszystkie ostre trójkąt stać stępione:

doładowania ma jakąś funkcjonalność Voronoi: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

Następnym krokiem jest tworzenie wielokątów Voronoi. Voro ++ http://math.lbl.gov/voro++/ jest zorientowany na 3D, ale sugeruje się, że w przybliżeniu struktura 2d będzie działać, ale będzie znacznie wolniejsza niż oprogramowanie zorientowane na 2D voronoi. Drugi pakiet, który wygląda dużo lepiej niż losowy projekt strony domowej osieroconej, to https://github.com/aewallin/openvoronoi.

Wygląda na to, że OpenCV służy do obsługi czegoś podobnego, ale jest przestarzałe (ale c-api nadal działa?).cv :: distTransform jest nadal utrzymywany, ale działa na pikselach i generuje piksel, a nie wierzchołki i struktury danych wielokątów, ale może być wystarczający dla moich potrzeb, jeśli nie twój.

Zaktualizuję to, gdy dowiem się więcej.