union Compute de deux formes arbitraires

je travaille sur une application, je dois être en mesure de combiner deux chevauchement des formes arbitraires comme dessiné par l'utilisateur. Ce serait une opération de l'Union sur les deux formes. La forme résultante serait la silhouette des deux formes qui se chevauchent.union Compute de deux formes arbitraires

Les formes sont stockées comme une séquence de points dans le sens des aiguilles d'une montre.

Idéalement, je voudrais un algorithme qui prendra deux tableaux de points (x, y) et retourner un seul tableau de la forme résultante.

J'ai lu Wikipedia sur Boolean operations on polygons qui mentionne le Sweep line algorithm mais je ne peux pas faire le lien entre ceci et mon objectif, hélas je ne suis pas un mathématicien.

Je développe l'application en ActionScript 3 mais je connais C#, Java et je peux choisir mon chemin en C et C++.

Source

2010-01-26 Greg B

La mise en œuvre des opérations booléennes n'est pas trivial correctement; Heureusement, il existe des bibliothèques qui implémentent déjà cette fonctionnalité.

Quelle langue utilisez-vous? Si c'est en C++, jetez un oeil à CGAL, la bibliothèque d'algorithmes de géométrie computationnelle.

Source

2010-01-26 14:48:47

Merci, je suis mise en œuvre en AS3, mais familier avec C#, Java –

Ah ... eh bien, je ne suis pas sûr si le code source du CGAL est si amusant à décoder et à mettre en communication, puisqu'il exprime ses algorithmes de façon assez générique, calqué sur le STL (IIRC, ça fait longtemps). Vous feriez mieux de porter l'une des bibliothèques les plus spécifiques en bas de la page Wikipédia. Alternativement, pouvez-vous vous en tirer simplement en rendant les deux polygones à un bitmap, puis en effectuant les opérations booléennes sur cela? –

J'ai trouvé ce port AS3 (partiel) du port Java de GPC http://code.google.com/p/gpcas/ qui supporte les opérations UNION. Merci pour votre contribution. –

Étant donné deux listes de points (A et B)
- lignes [1] pour chaque ligne dans une t-il se coupent en une ligne B
-.- [2] si pas (plus) se croisent, il n'y a pas de chevauchement
-.- [3] si une ligne (a) coupe une ligne dans B alors
-.-.- [4] ajouter le point d'intersection en sortie
-.-.- [5] est-ce que la ligne suivante de A se croisent B
-.-.-.- [6] sinon, ajoute ceci à la sortie (c'est à l'intérieur de B) goto 5
-.-.- .- [7] si oui, ajoutez l'intersection avec les listes de sortie et de commutation A & B goto 2

Voir aussi Intersection Point Of Two Lines. Je ne vais pas écrire le code désolé :)

Source

2010-01-26 15:07:04

+1: Semble comme une approche décente à moi –

merci Jon ... devrait également dire "ajouter de la logique pour éviter la boucle infinie" –

Méfiez-vous - ce problème n'est pas aussi facile que vous le pensez. Quelques éléments de réflexion: Une ligne (ou «arête») dans A peut croiser plus d'une arête dans B. Les deux polygones d'origine peuvent être disjoints; ou A peut se trouver entièrement dans B; ou B peut se situer entièrement dans A (bien que ces trois cas se ressemblent si vous regardez simplement les intersections entre les lignes). Les polygones n'ont pas besoin d'être convexes, et l'union de deux polygones non convexes peut avoir des trous. Et ainsi de suite ... la géométrie computationnelle est connue pour avoir toutes sortes de cas particuliers auxquels vous ne pensez pas au début. –

Le this algorithm fonctionnerait-il pour vous?

Source

2010-01-26 15:10:04

+1 Je donnerais un premier essai tbh! –

Cet algorithme calcule l'intersection; Greg B cherche le syndicat. En outre, cet algorithme ne fonctionne que lorsque les deux polygones ainsi que leur intersection sont convexes; Greg B parle de "formes arbitraires", donc je suppose qu'il veut être capable de gérer des polygones non-convexes, aussi. –

Fair point Martin. J'avais supposé qu'ils étaient des formes convexes et proposais cet algorithme comme point de départ pour trouver les deux intersections. –

Que diriez-vous:

gauche Choisissez le point le plus des deux formes. Appelez cette forme A et faites-en la forme actuelle.
dans le sens horaire de vent le long de la forme actuelle au point suivant et vérifier pour voir si une ou plusieurs lignes se croisent.
- Si des lignes DO se croisent, trouvez le premier point d'intersection et ajoutez-le à votre nouvelle forme. Passez à l'enroulement le long de l'autre forme.
- Si aucune ligne se croisent passer au point suivant de forme A et ajouter que le point dans votre nouvelle forme. Continuez à enrouler le long de la forme actuelle.
Répétez l'étape 2.

Je pense que si vous continuez à serpentant le long selon la forme est en cours, la recherche d'intersections, qui devrait faire ce que vous voulez. Je pense que cela devrait également faire face à des formes concaves ...

Je suis sûr qu'il y a beaucoup d'optimisations que vous pouvez ajouter une fois que vous avez les bases de travail.

Source

2010-01-26 17:22:13