Bibliothèque de tessellation C ++ 2D?

Question

J'ai des polygones convexes stockés en tant que vecteur STL de points (plus ou moins). Je veux les tessellate les commander très rapidement, de préférence en morceaux de taille assez uniforme et sans "slivers". ;.

Je vais l'utiliser pour faire éclater des objets en petits morceaux. Est-ce que quelqu'un connaît une belle bibliothèque pour tesseller des polygones (les partitionner en un maillage de polygones convexes ou de triangles plus petits)?

J'ai regardé quelques-uns que j'ai trouvés en ligne, mais je ne parviens même pas à les compiler. Ces types académiques ne tiennent pas beaucoup compte de la facilité d'utilisation.

Answer 1

CGAL propose des packages pour résoudre ce problème. Le mieux serait probablement d'utiliser le Partitionnement de polygones 2D forfait. Par exemple, vous pouvez générer une partition y monotone d'un polygone (fonctionne également pour les polygones non convexes) et obtenir quelque chose comme ceci:

Le temps d'exécution est O (n log n).

En termes de facilité d'utilisation, il s'agit d'un petit exemple de code générant un polygone aléatoire et le partitionnant (basé sur cet exemple de manuel ):

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

Pour installer cgal, si vous êtes sur Windows, vous pouvez utiliser le programme d’installation pour obtenir la bibliothèque précompilée. Des guides d’installation existent pour chaque plate-forme sur cette page . L’installation n’est peut-être pas la plus simple, mais vous obtenez la bibliothèque de géométrie de calcul la plus utilisée et la plus robuste qui existe, ainsi que le La liste de diffusion cgal est très utile pour répondre aux questions ...

Answer 2

poly2tri ressemble à une très jolie bibliothèque C ++ légère pour Delaunay 2D triangulation.

Answer 3

Comme balint.miklos l'a mentionné dans un commentaire ci-dessus, le triangle le paquet est assez bon. Je l'ai utilisé moi-même plusieurs fois; il s’intègre parfaitement dans les projets et il existe l’interface triangle ++ . Si vous souhaitez éviter les éclats, autorisez le triangle à ajouter des points Steiner (intérieurs), afin de générer un maillage de qualité (généralement une triangulation de Delaunay conforme contrainte).

Answer 4

Si vous ne souhaitez pas intégrer l'ensemble de GCAL dans votre application, sa mise en œuvre est probablement plus simple.

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

Answer 5

Je viens tout juste de commencer à examiner le même problème et je songe à la tessellation de voronoï. Le polygone d'origine aura une dispersion de points semi-aléatoires qui seront les centres des cellules de voronoï. Plus elles seront réparties de manière égale, plus les cellules seront dimensionnées de manière régulière, mais elles ne devraient pas être dans une grille parfaite, sinon les polygones intérieurs seront tous les mêmes. La première chose à faire est donc de pouvoir générer ces points centraux de cellules. En les générant sur le cadre du polygone source, un test intérieur / extérieur ne devrait pas être trop difficile.

Les arêtes de voronoï sont les lignes pointillées de cette image et sont en quelque sorte le complément de la triangulation de Delaunay. Tous les points de triangle pointus s’émoussent:

Boost a quelques fonctionnalités voronoi: http://www.boost.org/doc/ libs / 1_55_0 / libs / polygon / doc / voronoi_basic_tutorial.htm

L'étape suivante consiste à créer les polygones de voronoï. Voro ++ http://math.lbl.gov/voro++/ est orienté 3D, mais suggéré ailleurs cette structure approximativement 2d fonctionnera, mais sera beaucoup plus lente que les logiciels orientés vers voronoi 2D. https://github.com/ est un autre package qui semble bien meilleur qu'un projet orphelin de page d'accueil universitaire aléatoire. aewallin / openvoronoi .

Il semblerait que OpenCV prenne en charge quelque chose dans ce sens, mais il est obsolète (mais c-api fonctionne toujours?). cv :: distTransform est toujours maintenu, mais fonctionne sur les pixels et génère une sortie en pixels, et non des sommets et des structures de données de polygone de bord, mais peut suffire à mes besoins si ce n'est le vôtre.

Je mettrai à jour ceci une fois que j'en aurai appris plus.

Answer 6

Un peu plus de détails sur l’entrée et la sortie souhaitées peuvent être utiles.

Par exemple, si vous essayez simplement de convertir les polygones en triangles, un éventail de triangles fonctionnerait probablement. Si vous essayez de couper un polygone en petits morceaux, vous pouvez mettre en place une sorte de carré de défilement.

D'accord, j'ai formulé une mauvaise hypothèse - j'ai supposé que les carrés de défilé seraient plus similaires aux cubes de défilé. Il s'avère que c'est assez différent, et pas ce que je voulais dire du tout.: |

En tout cas, pour répondre directement à votre question, je ne connais aucune bibliothèque simple qui fasse ce que vous cherchez. Je suis d'accord sur la convivialité de CGAL. ??

L’algorithme auquel je pensais consistait essentiellement à scinder des polygones avec des lignes, où les lignes étaient une grille, de sorte que vous obteniez généralement des quadruples. Si vous aviez une intersection polygonale, l'implémentation serait simple. Une autre façon de poser ce problème consiste à traiter le polygone 2D comme une fonction et à superposer une grille de points. Ensuite, vous faites quelque chose de similaire aux cubes en marche. Si les 4 points sont dans le polygone, créez un quad, si 3 sont dans un triangle, 2 dans un rectangle, etc. Probablement exagéré. Si vous voulez des polygones légèrement irréguliers, vous pouvez randomiser les emplacements des points de la grille.

D'autre part, vous pouvez créer une subdivision de style Catmull-Clark, mais omettre le lissage. L'algorithme consiste essentiellement à ajouter un point au centre de la surface et au milieu de chaque bord. Ensuite, pour chaque coin du polygone d'origine, vous créez un nouveau polygone plus petit qui relie le point médian du bord précédant le coin, le coin, le point milieu du bord suivant et le centroïde. Cela juxtapose l'espace et aura des angles similaires à ceux de votre polygone d'entrée.

Donc, beaucoup d'options et j'aime bien les solutions de brainstorming, mais je n'ai toujours aucune idée de ce pour quoi vous comptez l'utiliser. Est-ce que cela crée des mailles destructibles? Faites-vous une sorte de traitement de maillage qui nécessite des éléments plus petits? Vous essayez d'éviter les artefacts d'ombrage de Gouraud? Est-ce quelque chose qui fonctionne en pré-processus ou en temps réel? Quelle est l'importance de l'exactitude? Plus d'informations donneraient de meilleures suggestions.

Answer 7

Si vous avez des polygones convexes et que vous n'êtes pas trop attaché à la qualité, c'est très simple: il vous suffit de faire coupure d'oreille . Ne vous inquiétez pas, ce n'est pas O (n ^ 2) pour les polygones convexes. Si vous le faites naïvement (c’est-à-dire que vous coupez les oreilles au fur et à mesure que vous les trouvez), vous obtiendrez un éventail en forme de triangle, ce qui est un peu fastidieux si vous essayez d’éviter les éclats. Deux heuristiques triviales pouvant améliorer la triangulation sont

1. Triez les oreilles, ou si c'est trop lent
2. Choisissez une oreille au hasard.

Si vous souhaitez un triangulateur plus robuste basé sur l'écrêtage d'oreille, consultez FIST .