Compute union de deux formes arbitraires

Question

Je travaille sur une application, je dois être en mesure de combiner deux formes arbitraires qui se chevauchent 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.

Les formes sont stockés sous la forme d'une séquence de points d'une manière dans le sens horaire.

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

J'ai lu sur Wikipédia opérations booléennes qui mentionne le algorithme de ligne de balayage mais je ne peux pas faire le lien entre cela et mon objectif, hélas je ne suis pas un Mathématicien.

Je développe l'application dans ActionScript 3 mais je suis familier avec C #, Java et je peux choisir mon chemin à travers C et C ++.

Answer 1

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

Quelle langue utilisez-vous? Si c'est C ++, jetez un oeil à CGAL , la bibliothèque Algorithmes Géométrie informatique.

Answer 2

Étant donné deux listes de points (A et B)
  - [1] pour chaque ligne A-t-il intersecte une ligne B
    -.- [2] si pas de lignes (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] ne la ligne suivante de A recouper B
       -.-.-.- [6] sinon, ajoutez à la sortie (il est à l'intérieur B) goto 5
       -.-.-.- [7] le cas échéant, ajoutez la Intersection à la sortie et le commutateur listes A et B goto 2

Voir aussi point d'intersection, de deux lignes . Je ne vais pas écrire le code désolé:)

Answer 3

Voir aussi GPC .

Answer 4

cet algorithme travail pour vous?

Answer 5

Que diriez-vous:

1. Choisissez le point le plus à gauche des deux formes. Appelez cette forme A et rendre la forme actuelle.
2. dans le sens horaire du vent le long de la forme actuelle au point suivant et vérifier si une ou plusieurs lignes se croisent.
   • Si toutes les lignes ne se croisent, trouver le premier point d'intersection et ajouter à votre nouvelle forme. Passer à 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 de rembobiner le long de la forme actuelle.
3. 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 faire face à des formes concaves et ...

Je suis sûr qu'il ya beaucoup de Optimisations vous pouvez ajouter une fois que vous avez les bases de travail.

Answer 6

Il semble y avoir aussi un javascript api:

https://github.com/bjornharrtell/jsts/

qui semble mettre en œuvre les JTS standard et a plusieurs implémentations differnt:

http://tsusiatsoftware.net/jts/jts-links.html#ports

tous devraient être en mesure d'effectuer l'union etc:

http://tsusiatsoftware.net/jts/JTSUser/contents.html

Mais csg.js est le projet le plus impressionnant de l'OMI

https://github.com/evanw/csg.js