Libreria di tassellatura 2D C ++?

Question

Ho alcuni poligoni convessi memorizzati come un vettore di punti STL (più o meno). Voglio tessellate molto rapidamente, preferibilmente in pezzi di dimensioni abbastanza uniformi e senza "scaglie" ;.

Lo userò per far esplodere alcuni oggetti in piccoli pezzi. Qualcuno sa di una bella biblioteca per tessere poligoni (dividerli in una rete di poligoni o triangoli convessi più piccoli)?

Ne ho visti alcuni che ho già trovato online, ma non riesco nemmeno a farli compilare. Questo tipo accademico non tiene in grande considerazione la facilità d'uso.

Answer 1

CGAL ha pacchetti per risolvere questo problema. Il migliore sarebbe probabilmente usare 2D Polygon Partitioning pacchetto. Ad esempio potresti generare una partizione y-monotona di un poligono (funziona anche per poligoni non convessi) e otterrai qualcosa del genere:

Il tempo di esecuzione è O (n log n).

In termini di facilità d'uso, questo è un piccolo codice di esempio che genera un poligono casuale e lo partiziona (basato su questo esempio di manuale ):

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;
}

Per installare cgal, se sei su Windows puoi usare il programma di installazione per ottenere la libreria precompilata e ci sono guide di installazione per ogni piattaforma su questa pagina . Potrebbe non essere il più semplice da installare, ma ottieni la libreria di geometria computazionale più usata e robusta che ci sia là fuori e il cgal mailing list è molto utile per rispondere alle domande ...

Answer 2

poly2tri sembra una libreria C ++ leggera davvero piacevole per Delaunay 2D triangolazione.

Answer 3

Come menzionato balint.miklos in un commento sopra, il triangolo di Shewchuk pacchetto è abbastanza buono. L'ho usato io stesso molte volte; si integra perfettamente nei progetti e c'è l'interfaccia triangle ++ C ++. Se vuoi evitare schegge, consenti al triangolo di aggiungere punti (interni) di Steiner, in modo da generare una mesh di qualità (di solito una triangolazione delaunay vincolata e conforme).

Answer 4

Se non vuoi integrare l'intero GCAL nella tua app, probabilmente è più semplice da implementare.

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

Answer 5

Ho appena iniziato a esaminare questo stesso problema e sto prendendo in considerazione la tassellatura voronoi. Il poligono originale otterrà una dispersione di punti semi casuali che saranno i centri delle cellule voronoi, più uniformemente saranno distribuiti, più le celle saranno dimensionate regolarmente, ma non dovrebbero essere in una griglia perfetta altrimenti i poligoni interni sarà tutto uguale. Quindi la prima cosa è essere in grado di generare quei punti del centro della cella, generandoli sopra il riquadro di delimitazione del poligono sorgente e un test interno / esterno non dovrebbe essere troppo difficile.

I bordi del voronoi sono le linee tratteggiate in questa immagine e sono una sorta di complemento della triangolazione delaunay. Tutti i punti del triangolo taglienti diventano smussati:

Boost ha alcune funzionalità voronoi: http://www.boost.org/doc/ libs / 1_55_0 / librerie / poligono / doc / voronoi_basic_tutorial.htm

Il prossimo passo è creare i poligoni voronoi. Voro ++ http://math.lbl.gov/voro++/ è orientato al 3D ma è suggerito altrove che funzionerà approssimativamente con la struttura 2D, ma sarà molto più lento del software orientato verso il voronoi 2D. L'altro pacchetto che sembra essere molto meglio di un progetto orfano di homepage accademica casuale è https://github.com/ aewallin / openvoronoi .

Sembra che OpenCV sia usato per supportare qualcosa in questo senso, ma è stato deprecato (ma il c-api funziona ancora?). cv :: distTransform è ancora gestito ma funziona su pixel e genera output di pixel, non vertici e strutture di dati poligonali del bordo, ma può essere sufficiente per le mie esigenze se non le tue.

Lo aggiornerò dopo aver appreso di più.

Answer 6

Un po 'più di dettaglio sull'input e l'output desiderati potrebbe essere utile.

Ad esempio, se stai solo cercando di trasformare i poligoni in triangoli, probabilmente una ventola triangolare funzionerebbe. Se stai cercando di tagliare un poligono in piccoli pezzi, potresti implementare una sorta di quadrati in marcia.

---

Okay, ho fatto una brutta ipotesi - ho pensato che i quadrati in marcia sarebbero stati più simili ai cubi in marcia. Si scopre che è abbastanza diverso, e non è quello che volevo dire ..: |

In ogni caso, per rispondere direttamente alla tua domanda, non conosco nessuna semplice libreria che fa quello che stai cercando. Sono d'accordo sull'usabilità di CGAL. ??

L'algoritmo a cui stavo pensando era fondamentalmente di dividere i poligoni con le linee, in cui le linee sono una griglia, quindi ottieni principalmente quad. Se avessi un incrocio poligonale, l'implementazione sarebbe semplice. Un altro modo per porre questo problema è trattare il poligono 2d come una funzione e sovrapporre una griglia di punti. Quindi fai semplicemente qualcosa di simile ai cubi in marcia .. se tutti e 4 i punti sono nel poligono, crea un quadrupolo, se 3 sono in un triangolo, 2 in un rettangolo, ecc. Probabilmente eccessivo. Se volevi poligoni dall'aspetto leggermente irregolare, potresti randomizzare le posizioni dei punti della griglia.

D'altra parte, potresti fare una suddivisione in stile catmull-clark, ma omettere il livellamento. L'algoritmo è fondamentalmente si aggiunge un punto al centroide e al punto medio di ciascun bordo. Quindi per ogni angolo del poligono originale si crea un nuovo poligono più piccolo che collega il punto medio del bordo precedente all'angolo, l'angolo, il punto medio del bordo successivo e il centroide. Questo piastrella lo spazio e avrà angoli simili al tuo poligono di input.

Quindi, molte opzioni e mi piacciono le soluzioni di brainstorming, ma non ho ancora idea di cosa tu stia pianificando di utilizzare per questo. È questo per creare maglie distruttibili? Stai eseguendo una sorta di elaborazione mesh che richiede elementi più piccoli? Cerchi di evitare artefatti di ombreggiatura di Gouraud? È qualcosa che funziona come pre-processo o in tempo reale? Quanto è importante l'esattezza? Ulteriori informazioni porterebbero a suggerimenti migliori.

Answer 7

Se hai poligoni convessi e non sei troppo impiccato dalla qualità, allora questo è davvero semplice - fai ear clipping . Non preoccuparti, non è O (n ^ 2) per i poligoni convessi. Se lo fai in modo ingenuo (cioè, ritagli le orecchie mentre le trovi), otterrai una ventola a triangolo, che è un po 'trascinata se stai cercando di evitare le schegge. Due euristiche banali che possono migliorare la triangolazione sono

1. Ordina le orecchie, o se è troppo lento
2. Scegli un orecchio a caso.

Se vuoi un triangolatore più robusto basato sul ritaglio dell'orecchio, dai un'occhiata a FIST .