Discussion :

[littleqi]

Bonjour,
Je voudrais savoir s'il existe une fonction (de la class Polygon ou autre) qui retournerait "true" si il y a intersection entre 2 polygones.
Après de miltiples recherches sur google je n'ai rien trouvé

Merci de votre aide.

[eclesia]

http://java.sun.com/j2se/1.4.2/docs/...t/Polygon.html

je me demande si tu as vraiment cherché?

methodes :
contains
intersects

si tu cherche plus de precision dans le calcul, JTS : http://www.vividsolutions.com/jts/jtshome.htm

[littleqi]

La methode intersect existe effectivement seulement elle ne fonctionne que entre un rectangle et un polygon, alors que je veux entre polygon et polygon.
Je vais regarder le lien que tu m'as donné, merci.

[sinok]

Tu peux voir ça en utilisant la classe Area et ses méthodes intersects et isEmpty

[littleqi]

Supeeeeeeer impeccable, ça marche.
Je donne mon code au cas ou quelqu'un en aurait besoin:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
//on crée les 2 polygon sur lequels on fait la verif d'intersection
Polygon polygon1 = new Polygon(...);
Polygon polygon2 = new Polygon(...);
 
//on crée une area avec le premier polygon
Area monArea = new Area(polygon1);
//on fait l'intersection avec le deuxieme polygon
monArea.intersect(new Area(polygon2));
 
//Si mon Area est vide c'est qu'il n'y avait pas d'intersection entre les 2 polygons
if(monPolygon.isEmpty()) System.out.println("Pas d'intercection");
else System.out.println("intercection");

Merci beaucoup, j'ai passé toute la matinée a essayé de faire des formules mathématiques sans succès (je suis pas très bon en math) et la solution etait en fait beaucoup moins compliquée.

Merci encore

[sinok]

Euh sinon c'est intersection et non intercection ^^

++

[littleqi]

ah, les joies du copier/coller, on fait une erreur a un endroit on la retrouve partout

[bouye]

Avant de partir dans des caculs couteux d'intersection d'aire, il est bon de verifier que les boites englobantes rectangulaires des formes ne se chevauchent pas. Cela tombe bien justement : toutes les formes heritant de Shape disposent des methodes getBounds() et getBounds2D().

[kerinel]

Bonjour,
je souhaite aussi faire en sorte que deux Polygon ne puisse être superposer et je viens donc de trouver ce post.
Je voudrais un tout petit peu plus de précision sur la remarque de bouye. Est-il vraiment économique de d'abord calculer une éventuelle intersection des rectangles englobants ? Sachant que si il y a intersection des rectangles englobant il faudra tester l'intersection des aires.
L'autre méthode que je voyais était de tester l'intersection des deux arrêtes du Polygon que je modifie (je ne permet de modifier un Polygon que par un angle à la fois) avec les cotés des autres Polygons. J'ai la possibilité de stocker un tableau (une ArrayList en fait) de Line2D et de le mettre à jour à chaque modification. Dans ce cas, qu'elle est la solution la moins gourmande en terme de calcul : l'aire ou la recherche d'intersection 1 à 1 ? Avec avant une recherche sur l'intersection des rectangles englobants avant ou pas ?
Sachant que je dois aussi tester que les arrêtes du Polygon que je viens de modifier ne se croisent pas (et là je ne vois pas d'autre moyen que de confronter les nouvelles arrêtes à toutes les anciennes donc mon tableau de Line2D est indispensable).

Bon code,
kerinel

[bouye]

Une intersection de rectangles ne demande aucun calcul couteux, juste des comparaisons entre des valeur. Une intersection d'aire demande des calculs tres couteux.

La methode classique de collisions de sprites, c'est :
- intersection des boites englobantes (dans la plupart des cas "normaux" getBounds() suffit par rapport a getBounds2D()).
- si intersection, calcul de la collision des sprites ou de l'aire. Parfois, dans le cas de sprites, on se facilite egalement la tache en utilisant des images masques indiquant les parties vides.
Ensuite il est egalement possible d'optimiser encore plus en stockant les formes dans un arbre en fonction de leur position a l'ecran (par exemple) plutot que dans une simple liste.

Pour l'intersection d'arretes, la je ne sais pas, il faut tester sur un grand nombre de cas. J'aurai tentande a dire a priori que le calcul de colision de segments est plus long que celui des boites enblobantes. Ca peut etre une bonne idee pour realiser le calcul des colisions de l'aire ceci dit.

[kerinel]

OK je vais donc tester l'intersection des rectangles englobant avant et au cas où c'est positif, l'intersection des arrêtes (si j'ai bien compris vu que je ne passe pas par une histoire d'aire et que j'ai déjà un tableau d'arêtes pour mes polygones, le calcul de l'intersection ne devrait pas prendre beaucoup de temps non plus). En fait je pensais que le calcul intersection de rectangle englobant était quand même un peu couteux, mais après un peu de réflexion c'est évident que non et donc que cela peut aller plus vit que de faire toutes les arêtes. surtout si il y a beaucoup d'arêtes.
Sachant que il n'y aura pas 15 000 polygones (normalement 1 plus 1 ou deux) je ne pense pas qu'un arbre soit d'un grand intérêt. Par contre les Polygones pourront être assez complexes et couvrir une bonne partie de la surface. Donc je vais garder ma liste, mais merci de la suggestion.

Par contre pour que le polygone ne se croise pas lui même, le coups des arrêtes ne fonctionne pas tel quel, et pour cause: deux arêtes consécutives ont un point commun...donc il me sort que c'est pas bon à chaque fois. Je dois faire d'abord une copie des deux arêtes à tester et ensuite une modification (retirer le point commun) avant de faire le test.
Je poste le code demain si ça fonctionne (pas eu le temps de finir hier soir) et qu'il y en a qui sont intéressés

merci pour les précisions,

Bon code.
kerinel

[Sepia]

Bonjour Kerinel,

Non, il ne faut pas tester les bounding box car intersect le fait déjà et renvoit false, si l'intersection est vide.

Ce type de code existe depuis Java 0.1 (avant swing) donc on peut penser que la communauté a été relativement efficace pour penser à ce type d'algo (surtout lorsque les plates-formes étaient super lentes).

[tutyy-uy]

Bonjour,

j'aurais une question svp, je bosse actuellement sur une petit programme de sprite et je fais quelques essais là sur les area. J'ai un petit problème au niveau des intersections.

En gros j'ai un tableau d'objets Rectangle2D, et une boule se déplace, si elle touche un élements du tableau, il se passe tel, sinon il se passe tel.

Mais je ne sais pas comment m'y prendre au niveau des area, si j'ai un tableau d'objet rectangle2D je dois donc avoir un tableau d'Area ?

Quand je teste un truc on me renvoi :

Exception in thread "main" java.lang.NullPointerException

Peut-être auriez vous un petit exemple ? Ou voudriez vous mon code ?


Merci d'avance

[Nico02]

Comme le dit bouye, le calcul d'intersection entre deux rectangles n'est pas très couteux, donc dans ton cas tutyy-uy si tu veux tester la collision entre un cercle et un rectangle, tu n'est pas obliger de passer par les Area, il te suffit de considérer tes cercles comme des rectangles et de faire le calcul comme ça. Tu te ramènes donc à un problème de collision rectangle - rectangle que tu peux résoudre avec la méthode contains(). C'est une technique qui marche très bien et qui est beaucoup utilisé dans les jeux. Le seul problème viens d'une collision par les angles. Dans ce cas, une méthode consiste à utiliser un rectangle de 95% (par exemple) de la taille du rectangle englobant le cercle. Après il faut tester pour trouver la meilleure valeur.

[bouye]

Pour Area, on peut en construire une nouvelle à partir d'une Shape quelconque (Rectangle, Rectangle2D, Ellipse, ...) via son constructeur et ensuite avoir l'intersection via sa méthode intersects(Rectangle2D).

Un test plus avancé, mais plus lourd, serait d'appeler la méthode intersect(Area) qui construit l'aire résultante de l'intersection de l'aire A et l'aire B (et la stocke dans l'aire A) et vérifier que sa bounding box n'est pas vide ou infinitésimalement petite.
En effet si A n'intersecte pas B, l'appel de cette fonction crée une aire vide (puisque les deux zones ne se rencontrent jamais).
Attention sur le papier ça marche mais comme quelqu'un l'a soulevé dernièrement à propos de la boite englobante des cercles sur lesquels on applique une rotation, il y a parfois des bugs de boite englobante en Java2D. Donc à vérifier.

Quand à l'exception, sans trace ni code on ne peut pas aider (et ça serait à poster dans un nouveau sujet de toute manière).