Je travaille sur une application, je dois être capable de combiner deux formes arbitraires qui se chevauchent telles que dessinées par l'utilisateur. Ce serait une opération syndicale sur les deux formes. La forme résultante serait la silhouette des deux formes qui se chevauchent.
Les formes sont stockées comme une séquence de points de manière 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 Opérations booléennes sur les polygones 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 la demande dans ActionScript 3 mais je connais le C #, Java et moi pouvons choisir mon chemin à travers C et C ++.
6 Réponses :
Mise en œuvre correctement des opérations booléennes n'est pas triviale; Heureusement, il existe des bibliothèques qui implémentent déjà cette fonctionnalité.
Quelle langue utilisez-vous? Si c'est C ++, consultez CGAL , la bibliothèque d'algorithmes de géométrie informatique.
Merci, je suis en train de mettre en œuvre dans AS3 mais familiarisé avec C #, Java
Ah ... Eh bien, je ne suis pas sûr que si le code source ci-dessus est tellement amusant de choisir et de porter son port, car il exprime ses algorithmes de manière assez générique, modélisé après la STL (IIRC, ça fait un moment). Vous serez peut-être mieux de porter l'une des bibliothèques les plus spécifiques liées au bas de la page Wikipedia. Vous pouvez également vous échapper avec simplement des polygones à un bitmap, puis effectuer les opérations booléennes à ce sujet?
J'ai trouvé ce port (partiel) as3 du port Java de GPC code.google.com/p/gpcas qui soutient les opérations syndicales. Merci pour votre contribution.
Bon Trouvez - On dirait que c'est exactement ce dont vous avez besoin!
donné deux listes de points (A et B)
- [1] Pour chaque ligne dans A, intersectez-t-il une ligne de
-.- [2] si aucune (plus) lignes se croisent, il n'y a pas de chevauchement à
-.- [3] Si une ligne in (a) intersecte une ligne dans B puis
-.-.- [4] Ajoutez le point d'intersection dans la sortie
-.-.- [5] La prochaine ligne d'un intersect b
est-elle
-.-.-.- .- [6] sinon, ajoutez ceci à la sortie (c'est à l'intérieur B) Goto 5
-.-.-.- [7] Si tel est le cas, ajoutez l'intersect à la sortie et aux listes de commutation A & B GOTO 2
Voir aussi point d'intersection de deux lignes . Je ne vais pas écrire le code désolé :)
merci Jon ... devrait aussi dire "Ajouter une logique à éviter une infinie boucle"
Méfiez-vous - ce problème n'est pas aussi facile que vous le pensez. Quelques aliments à réflexion: une ligne (ou un "bord") dans un peut intersecter plus d'un bord en B. Les deux polygones d'origine peuvent être disjoints; ou un peut être entièrement au sein de B; ou B peut être entièrement dans un (bien que ces trois cas semblent identiques si vous regardez simplement des intersections entre les lignes). Les polygones ne doivent pas nécessairement être convexes et l'union de deux polygones non convexes peut avoir des trous. Et ainsi de suite ... La géométrie informatique est notoire pour avoir toutes sortes de cas spéciaux que vous ne pensez pas au début.
Oui Martin - une ligne de groupe A peut traverser plus d'une ligne dans le groupe B. Vous devez donc prendre l'intersection la plus proche du point de départ. J'essayais d'une approche d'algorithme "de remplissage".
Merci pour vos pensées Ian. Je regarde un algorithme très similaire sur mon tampon devant moi. Il commençait à penser à certains points de Martin B qui m'a fait commencer ma recherche d'une bibliothèque pour le faire pour moi.
serait Cet algorithme travaille pour vous?
Cet algorithme calcule l'intersection; Greg B cherche l'union. En outre, cet algorithme ne fonctionne que lorsque les deux polygones ainsi que leur intersection sont convexes; Greg B parle de "formes arbitraires", alors je suppose qu'il veut aussi supporter des polygones non convexes.
Fair Point Martin. J'avais supposé qu'ils étaient des formes convexes et suggèrent cet algorithme comme point de départ pour trouver les deux intersections.
Ce lien est éclaté
Du:
Je pense que si vous continuez à coller le long de la forme de la forme, à la recherche d'intersections, cela devrait faire ce que vous voulez. Je pense que cela devrait aussi faire face aux formes concaves ...
Je suis sûr qu'il y a beaucoup d'optimisations que vous pouvez ajouter une fois que vous avez les bases du travail.
Il semble également y avoir une API JavaScript:
https://github.com/bjornhartell/jsts/
qui semble mettre en œuvre la norme JTS et a plusieurs implémentations différentes:
http://tsusiatsoftware.net/jts/jts-links.html#ports < / a>
Tous devraient pouvoir effectuer un syndicat, etc.:
http://tsusiatsoftware.net/jts/jtsuser/contents.html << / p>
mais csg.js est le projet le plus impressionnant IMO