Tester si un point est présent dans un polygone

Version imprimable

19/09/2007, 19h31
habasque

Tester si un point est présent dans un polygone

Salut à tous,

Je cherche à implémenter une fonction ayant pour but de tester la présence d'un point à l'intérieur d'un polygone.

Le point est défini par une latitude et une longitude.
Exemple : -15.8933; 67,4433

Le polygone quand à lui est défini par toute une série de points définis comme ci-dessus.

Si quelqu'un a une idée de comment procéder ?

Merci d'avance.
19/09/2007, 19h43
the-gtm

Avec la classe java.awt.Polygon et sa méthode contains()
19/09/2007, 19h57
ced-29

Citation:

Envoyé par the-gtm

Avec la classe java.awt.Polygon et sa méthode contains()

Souvent il est plus intéressant de recréer une classe Polygon il me semble, par exemple dans ce cas où les coordonnées sont réelles et non entières, mais aussi dans le cas où on veut gérer les polygones de façon dynamique avec des listes.

Cette question de déterminer l'apparenance d'un point à un polygone m'intéresse car je risque d'y être confronté.
Personnellement je pense qu'on peut le faire en calculant, comme c'est dit dans d'autres sujets, le nombre d'intersection du segment (a,b),(x,y) avec les arêtes du polygone, mais il faut connaitre un point (a,b) qui n'appartient pas au polygone, donc cela ne s'applique peut-être pas avec les latitudes et longitudes selon comment tu les utilises.

Il y a peut-être de meilleures façons de faire, plus optimales...
19/09/2007, 20h32
the-gtm

En tout cas c'est comme ça que c'est implémenté dans la classe Polygon (nombre d'intersections)
20/09/2007, 00h22
bouye

Citation:

Envoyé par ced-29

Souvent il est plus intéressant de recréer une classe Polygon il me semble, par exemple dans ce cas où les coordonnées sont réelles et non entières, mais aussi dans le cas où on veut gérer les polygones de façon dynamique avec des listes.

Pour les coordonnees non-entieres, il existe plusieurs autres classes dans Java2D telles que GeneralPath ou Path2D (Java 6+ pour cette derniere). Bien que ce soit academiquement interessant, c'est peu voir pas utile de creer sa propre classe de polygones quand Java2D peut s'en charger.

Cette methode n'est pas complete ; ainsi, suivant comment on configure un PATH ou suivant les besoins, on peut vouloir quand meme rester dans la forme meme si on croise un autre segment avant d'en sortir completement. Voir : WIND_EVEN_ODD (en simplifiant : on sort/entre a chaque nouvelle intersection) et WIND_NON_ZERO (en simplifiant : on rentre a la premiere intersection et on sort a la derniere) dans GeneralPath/Path2D.

De plus certains modules de dessin vectoriel utilisent une troisieme methode qui consiste a egalement caculer le sens/pente du segment intersecte pour savoir si on entre/sort/reste dans la forme. Cela permet de mixer des sous-chemins a l'interieur d'un autre permettant d'avoir a la fois des parties evidees et non-evidees.

Exemple d'utilisation de GeneralPath ou Path2D

Salut à tous et merci pour vos réponses...

Effectivement, les coordonnées de mon Polygone sont des latitudes et longitudes sous forme décimale. Donc, apparemment la classe Polygon ne convient pas à mes besoins mais j'ai tout de même créé ma propre classe Polygone :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 public class Polygone extends Polygon{ private Vector vecteurPoints; /** Creates a new instance of Polygone */ public Polygone() { vecteurPoints = new Vector(); } public void addPoint(Point2D unPoint){ vecteurPoints.addElement(unPoint); } }
Ensuite, j'essaie d'utiliser une fonction VerifPosicion() faisant appel à la méthode Contains de Polygon mais sans succès...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 //Verifie qu'une position ne se situe pas dans la liste des polygones public int verifPosicion(String uneLatitude, String uneLongitude, Vector listePolygones){ System.out.println("lat " + uneLatitude); System.out.println("long " + uneLongitude); Point2D unPoint = new Point2D.Double(Double.parseDouble(uneLatitude), Double.parseDouble(uneLongitude)); //Parcours de la liste des polygones for(int i = 0; i < listePolygones.size(); i++){ Polygone tempPoly = (Polygone)listePolygones.get(i); if (tempPoly.contains(unPoint)){ return 1; } } return 0; }
Est-ce un comportement normal ? A priori oui...

Dois-je utiliser plutôt un GeneralPath et si oui est-ce que quelqu'un pourrait me fournir un exemple de fonction permettant de tester la présence d'un point dans une liste de polygones ?

Merci d'avance...

Je verrais ca comme ca (exemple non-teste) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class MyPolygon extends Shape {
    /** List of points.
    * For convenience only, we should be able to get them out of the PathIterator of the delegated path.
    */
    private List<Point> pointList; 
 
    /** Delegated path.
    */
    private GeneralPath delegated;
 
    /** Creates a new instance.
    */
    public MyPolygon() {
        pointList = new LinkedList<Point2D>();
        delegated = new GeneralPath();
    }
 
    /** Add some more point to the polygon.
    * @param points Points to be added.
    */
    public void addPoint(Point2D... points){
       // Add to convenient list.
       for (Point2D p : points) {
          pointList.add(p);
       }
       // Reset path.
       delegated.reset();
       // Re-create shape.
       Interator<Point2D> it = pointList.interator();
       Point2D p = it.next();
       delegated.moveTo((float)p.getX(), (float)p.getY());
       while (it.hasNext()) {
          p = it.next();
         delegated.lineTo((float)p.getX(), (float)p.getY());
       }
       delegated.close();
    }
 
   // Pour toutes les autres methodes de l'interface Shape, deleger a delegated.
   // ex:
 
   /** {@inheritDoc}
    */
   public boolean contains(Point2D p) {
     return delegated.contains(p);
   }
}

Pourquoi retourner 0/1 alors que tu peux retourner true/false ? On n'est pas en C/C++, les booleans ne sont pas des entiers ici, les booleans ca prend moins de place.

GeneralPath --> problème de Java Heap Space !

Alors voici le code testé :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Polygone implements Shape {
    /** List of points.
     * For convenience only, we should be able to get them out of the PathIterator of the delegated path.
     */
    private List<Point2D> pointList;
 
    /** Delegated path.
     */
    private GeneralPath delegated;
 
    /** Creates a new instance.
     */
    public Polygone() {
        pointList = new LinkedList<Point2D>();
        delegated = new GeneralPath();
    }
 
    /** Add some more point to the polygon.
     * @param points Points to be added.
     */
    public void addPoint(List<Point2D> points){
        // Add to convenient list.
        for (Point2D p : points) {
            pointList.add(p);
        }
 
        // Reset path.
        delegated.reset();
        // Re-create shape.
        Iterator<Point2D> it = pointList.iterator();
        Point2D p = it.next();
        delegated.moveTo((float)p.getX(), (float)p.getY());
        while (it.hasNext()) {
            p = it.next();
            delegated.lineTo((float)p.getX(), (float)p.getY());
        }
        delegated.closePath();
    }
 
    // Pour toutes les autres methodes de l'interface Shape, deleger a delegated.
    // ex:
 
    /** {@inheritDoc}
     */
    public boolean contains(Point2D p) {
        return delegated.contains(p);
    }

Et le message d'erreur obtenu :

Code:

1
2
3
4
5
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Arrays.copyOf(Arrays.java:2906)
        at java.awt.geom.Path2D$Float.needRoom(Path2D.java:283)
        at java.awt.geom.Path2D$Float.lineTo(Path2D.java:354)
        at utilitaires.Polygone.addPoint(Polygone.java:63)

Je précise que je manipule 15 000 points.

Comment faire pour augmenter la mémoire allouée par NetBeans ?

24/09/2007, 23h22
bouye

Regarde dans les proprietes du projet, nottament dans la section qui traite de la classe a executer pour voir si tu ne peux pas y mettre manuellement un paramettre de JVM de style -Xmx512m
Tu peux egalement essayer d'utiliser des Point2D.Float au lieu de Point2D.Double.
25/09/2007, 00h01
habasque

problème de java heap space

j'ai changé Double en Float et mis -Xmx512m en paramètre de JVM...
sans succès...

j'essaie d'externaliser le processus en lançant un script Matlab mais ce n'est pas encore au point...

je sèche...
25/09/2007, 03h55
bouye

Alors d'une part :
- si tu n'as pas besoin d'avoir immediatement les points sous la main la liste de point tu peux ne pas la conserver. Elle sera alors liberee par le GC. Il t'es ensuite possible de la re-creer en parcourant PathIterator (evidement ca risque d'etre long).

- l'erreur semble provenir de la gestion de la re-allocation de la liste de points a l'interieur meme de Path2D. A part allouer encore plus de memoire (via le flag -Xmx), je ne vois pas trop comment nous pouvons regler le probleme. Dans ce cas, pour des raisons de performance, tu devras alors peut-etre utiliser ta liste de points a toi.
26/09/2007, 16h00
eclesia

une librairie faite pour ca :
JTS : Java Topologic Suite
http://www.vividsolutions.com/jts/jtshome.htm

vous eviterez les erreurs dans les calculs et ca supporte les polygones complexes.

un autre point :
Si tu utilise les longitudes latitudes comme s'il s'agissait de coordonnées carthésiennes, tous les calculs de distance seront faux. Il faut passer par une projection si tu veux des résultats correctes.