IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

[java] Triangulation de Delaunay (incrémentale)


Sujet :

Contribuez

  1. #41
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par bastiien Voir le message
    Rebonjour,

    J'avais pas fait attention au dernier poste de Commander Keen et je viens d'ajouter sa modification à l'algo... Et magie, plus de blocage dans la génération et plus d'erreur sur celle-ci non plus!

    Ha la journée commence bien!

    Bastien
    Oui, Commander Keen a raison. Il n'est pas nécessaire de tester si le point est sur le segment. Il suffit de savoir s'il est sur la ligne qui porte le segment.

    U un simple calcul de produit vectoriel est donc suffisant (et bien plus simple/robuste). Je modifie le code en conséquence.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #42
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Janvier 2010
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Voronoi en C#
    Ce code pour le calcul des diagrammes de voronoi existe-t-il en c# ?

  3. #43
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par harcz Voir le message
    Ce code pour le calcul des diagrammes de voronoi existe-t-il en c# ?
    Ce code en particulier ? Non. En tous cas, je ne l'ai pas porté en C#.

    Mais ca ne doit pas être bien compliqué à faire car il n'y a rien de spécifique a Java, et les 2 langages se ressemblent beaucoup.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #44
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Bonjour,

    Tout d'abord, merci pour cette implémentation très utile, super travail.

    Ensuite, pour ma part, en utilisant exactement ton code source, j'obtiens ceci en attaché (tous les points en voronoi sont reliés entre eux aussi).
    Je vais jeter un oeil sur tes boucles mais c'était juste pour savoir si j'étais le seul à obtenir ceci?

    Cordialement.

  5. #45
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par mickeynad Voir le message
    Bonjour,

    Tout d'abord, merci pour cette implémentation très utile, super travail.

    Ensuite, pour ma part, en utilisant exactement ton code source, j'obtiens ceci en attaché (tous les points en voronoi sont reliés entre eux aussi).
    Je vais jeter un oeil sur tes boucles mais c'était juste pour savoir si j'étais le seul à obtenir ceci?

    Cordialement.
    Ah oui. J'avais rajouté une ligne pour debugguer le code et je l'ai laissée. Voila, c'est modifié.

    C'est dans la méthode "computeVoronoi"
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    	// new region start
    	List<Point> poly = new ArrayList<Point>();
    	//poly.add(qstart.orig());  <--- LA LIGNE FAUTIVE
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #46
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Super ça marche nickel maintenant

    Merci pour ce super travail

    Michael.

  7. #47
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Bonsoir,

    J'ai une petite question qui me chiffonne depuis plusieurs heures. J'ai intégré ton implémentation sur imagej en utilisant les centroides de mes régions d'intérêts (obtenus par analyse de particule) et cela marche très bien (je dois juste écrire en plus une classe Point qui prenne des coordonnées en double et non en int):

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
           ResultsTable rt = ResultsTable.getResultsTable();
           int N = rt.getCounter();
           Point[] points = new Point[N];
           for (int i=0; i<N; i++){
               points[i] = new Point( (int) rt.getValue("X", i), (int) rt.getValue("Y", i));
          }

    En revanche, dès que je pose une condition avant l'insertion de mes points (centroides) alors pour des raisons qui m'échappent, beaucoup de mes points sont remplacés par un "null" lors de la construction de Delaunay (alors que lorsque je fais un simple print de ces points, ils sont bien là et sont donc sensés être retenus):

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
           ResultsTable rt = ResultsTable.getResultsTable();
           int N = rt.getCounter();
           Point[] points = new Point[N];
           for (int i=0; i<N; i++){
              //Condition que je pose
              if ( rt.getValue("Circ.", i) > 0.5){
              points[i] = new Point( (int) rt.getValue("X", i), (int) rt.getValue("Y", i));
             //Vérification par un print que j'ai bien tous mes points 
             //(là tous mes points sont affichés donc tout est ok dans la condition)
            	System.out.println("x=" + (int) rt.getValue("X", i));
            	System.out.println("y=" + (int) rt.getValue("Y", i));
            	System.out.println("circularity" + rt.getValue("Circ.", i));
              }
          }
     
           /* ...... suite*/
     
     
    		Delaunay_ delaunay = new Delaunay_();
     
                    //Je vérifie la taille du tableau des points 
                    //avant la construction du Delaunay
                    //(ici tout est bon, c'est bien la bonne taille)
    		System.out.println("tableau " + points.length);
     
    		for(Point p : points)
     
    		    {
                           //Je vérifie que j'ai bien les mêmes points 
                           //que précédémment lors du print
                           //et là il y a un bug 
                           //(beaucoup de mes points de mes centroides sont 
                           //remplacés par un null alors que par un print, j'ai bien 
                            //ces points et je ne sais pas pourquoi)
    			System.out.println("points : "+ p);
     
    			delaunay.insertPoint(p);
     
    		    }

    Et voila un exemple de ce que j'obtiens (en termes de points) :

    Avant la construction du Delaunay :


    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    [x=258,y=4]
    [x=595,y=13]
    [x=708,y=14]
    [x=810,y=7]
    [x=201,y=21]
    [x=91,y=22]


    Après la construction du Delaunay:


    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    java.awt.Point[x=258,y=4]
    java.awt.Point[x=595,y=13]
    java.awt.Point[x=708,y=14]
    java.awt.Point[x=810,y=7]
    null
    null

    ce qui bien sûr me donne une erreur NullPointerException.
    Est-ce que quelqu'un pourrait m'expliquer ce bug svp?

    Une dernière question. Est-ce que cette implémentation renvoit la longueur des segments svp, je ne le vois nulle part?

    Merci bien à l'avance.

  8. #48
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par mickeynad Voir le message
    ce qui bien sûr me donne une erreur NullPointerException.
    Est-ce que quelqu'un pourrait m'expliquer ce bug svp?
    C'est normal. Tu definis un tableau de N points, mais tu ne remplis pas toutes les cases du tableau (a cause de ton critère).

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Point[] points = new Point[N];
     
    for (int i=0; i<N; i++){
        if ( condition ){
            points[i] = new Point( ... );
        }
     
       // et si la condition est fausse, la case points[i] reste vide (= null)
    }

    Donc, lorsque tu parcours le tableau ( for(Point p : points) ) tu tombes sur des cases vides, c'est à dire p=null


    Une dernière question. Est-ce que cette implémentation renvoit la longueur des segments svp, je ne le vois nulle part?
    Heu... Tu parles de la longueur des 3 cotés du triangle ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #49
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Bonjour pseudocode et merci pour ta réponse.

    Citation Envoyé par pseudocode
    C'est normal. Tu definis un tableau de N points, mais tu ne remplis pas toutes les cases du tableau (a cause de ton critère).

    Donc, lorsque tu parcours le tableau ( for(Point p : points) ) tu tombes sur des cases vides, c'est à dire p=null
    Justement non. Les points affichés en 'null' sont des points qui remplissent la condition et qui doivent être gardés et affichés. Je fais d'ailleurs un print à l'intérieur de ma condition et ces points, via le print, sont bien affichés alors que dans le tableau de points, ils sont remplacés par un 'null'. Est-ce que tu vois ce que je veux dire? Je vais afficher un exemple plus concret dans 5 minutes.


    Citation Envoyé par pseudocode
    Heu... Tu parles de la longueur des 3 cotés du triangle ?
    Pardon oui je voulais dire la distance des segments qui relie les points entre eux.

  10. #50
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Voila un exemple plus concret. Ma condition est d'afficher des points dont la région correspondante a une circularité < 0.5:

    Voici ce que j'obtiens par un simple print :
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    x=258, y=4, circularity=0.9216268707820511
    x=358, y=13, circularity=0.7266673404243095
    x=788, y=12, circularity=0.8871520529283592
    x=672, y=13, circularity=0.9739898868533604

    Et voici ce que j'obtiens dans le tableau des points :
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    [x=258,y=4]
    [x=358,y=13]
    [x=788,y=12]
    null //Point remplacé par null alors que circularity =0.97 < 0.5

    On voit que le dernier point x=672, y=13 avec circularity =0.97 est remplacé par "null" alors que sa circularité est bien < à 0.5. Et cela me fait ça sur plus d'une vingtaine de points et je ne comprends vraiment pas pourquoi puisque le test par print les affiche bien.

  11. #51
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Ah c'est bon j'ai réglé le problème. En effet, tu avais raison. Les points 'null' correspondant aux 'mauvais points' s'intercalaient entre mes points 'candidats' et comme j'avais une exception NullPointer, je n'ai pas pu voir que les points remplissant la condition avaient bien été pris en compte puisque le programme s'arrêtait là. Je fais un petit check lors de la construction du delaunay et voronoi pour voir si le point est non nul et c'est bon, tout rentre dans l'ordre

  12. #52
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut Conversion en double
    Bonjour,

    J'ai une autre question svp. Est-ce que les polygones pour les doubles existent en java ainsi que les méthodes fillRect(double, double, double, double)?
    J'ai remplacé tous les Point en Point2D.double et les int en double (pour plus de précisions). En revanche, pour les polygones et rectangle, c'est plus compliqué car je n'ai pas trouvé leur "équivalence en double" (comme dans Graphics2D avec Line2D).
    Avant de faire la méthode, je voulais juste m'assurer si elles existaient ou pas.

    Par ailleurs, j'ai dû remplacer la méthode long det33 par double det33. Est-ce que cela n'aura pas trop d'incidence?

    Merci d'avance.

    QuadEdge.java

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
     
     
    import java.awt.Point;
    import java.awt.geom.Point2D;
     
    public class QuadEdge {
     
    	// pointer to the next (direct order) QuadEdge
    	private QuadEdge onext;
     
    	// pointer to the dual QuadEdge (faces graph <-> edges graph)
    	private QuadEdge rot;
     
    	// origin point of the edge/face
    	private Point2D.Double orig;
     
    	// marker for triangle generation
    	public boolean mark=false;
     
    	/**
             * (private) constructor. Use makeEdge() to create a new QuadEdge
             *
             * @param onext pointer to the next QuadEdge on the ring
             * @param rot   pointer to the next (direct order) crossing edge
             * @param orig  Origin point
             */
    	private QuadEdge(QuadEdge Onext, QuadEdge rot, Point2D.Double orig) {
    		this.onext = Onext;
    		this.rot = rot;
    		this.orig = orig;
    	}
     
    	// ----------------------------------------------------------------
    	//                             Getter/Setter
    	// ----------------------------------------------------------------
     
    	public QuadEdge onext() {
    		return onext;
    	}
     
    	public QuadEdge rot() {
    		return rot;
    	}
     
    	public Point2D.Double orig() {
    		return orig;
    	}
     
    	public void setOnext(QuadEdge next) {
    		onext = next;
    	}
     
    	public void setRot(QuadEdge rot) {
    		this.rot = rot;
    	}
     
    	public void setOrig(Point2D.Double p) {
    		this.orig = p;
    	}
     
    	// ----------------------------------------------------------------
    	//                      QuadEdge Navigation
    	// ----------------------------------------------------------------
     
    	/**
             * @return the symetric (reverse) QuadEdge
             */
    	public QuadEdge sym() {
    		return rot.rot();
    	}
     
    	/**
             * @return the other extremity point
             */
    	public Point2D.Double dest() {
    		return sym().orig();
    	}
     
    	/**
             * @return the symetric dual QuadEdge
             */
    	public QuadEdge rotSym() {
    		return rot.sym();
    	}
     
    	/**
             * @return the previous QuadEdge (pointing to this.orig)
             */
    	public QuadEdge oprev() {
    		return rot.onext().rot();
    	}
     
    	/**
             * @return the previous QuadEdge starting from dest()
             */
    	public QuadEdge dprev() {
    		return rotSym().onext().rotSym();
    	}
     
    	/**
             * @return the next QuadEdge on left Face
             */
    	public QuadEdge lnext() {
    		return rotSym().onext().rot();
    	}
     
    	/**
             * @return the previous QuadEdge on left Face
             */
    	public QuadEdge lprev() {
    		return onext().sym();
    	}
     
     
    	// ************************** STATIC ******************************
     
     
    	/**
             * Create a new edge (i.e. a segment)
             *
             * @param  orig origin of the segment
             * @param  dest end of the segment
             * @return the QuadEdge of the origin point
             */
    	public static QuadEdge makeEdge(Point2D.Double orig, Point2D.Double dest) {
    		QuadEdge q0 = new QuadEdge(null, null, orig);
    		QuadEdge q1 = new QuadEdge(null, null, null);
    		QuadEdge q2 = new QuadEdge(null, null, dest);
    		QuadEdge q3 = new QuadEdge(null, null, null);
     
    		// create the segment
    		q0.onext = q0; q2.onext = q2; // lonely segment: no "next" quadedge
    		q1.onext = q3; q3.onext = q1; // in the dual: 2 communicating facets
     
    		// dual switch
    		q0.rot = q1; q1.rot = q2;
    		q2.rot = q3; q3.rot = q0;
     
    		return q0;
    	}
     
    	/**
             * attach/detach the two edges = combine/split the two rings in the dual space
             *
             * @param q1,q2 the 2 QuadEdge to attach/detach
             */
    	public static void splice(QuadEdge a, QuadEdge b) {
    		QuadEdge alpha = a.onext().rot();
    		QuadEdge beta  = b.onext().rot();
     
    		QuadEdge t1 = b.onext();
    		QuadEdge t2 = a.onext();
    		QuadEdge t3 = beta.onext();
    		QuadEdge t4 = alpha.onext();
     
    		a.setOnext(t1);
    		b.setOnext(t2);
    		alpha.setOnext(t3);
    		beta.setOnext(t4);
    	}
     
    	/**
             * Create a new QuadEdge by connecting 2 QuadEdges
         *
             * @param e1,e2 the 2 QuadEdges to connect
             * @return the new QuadEdge
             */
    	public static QuadEdge connect(QuadEdge e1, QuadEdge e2) {
    		QuadEdge q = makeEdge(e1.dest(), e2.orig());
    		splice(q, e1.lnext());
    		splice(q.sym(), e2);
    		return q;
    	}
     
    	public static void swapEdge(QuadEdge e) {
    		QuadEdge a = e.oprev();
    		QuadEdge b = e.sym().oprev();
    		splice(e, a);
    		splice(e.sym(), b);
    		splice(e, a.lnext());
    		splice(e.sym(), b.lnext());
    		e.orig = a.dest();
    		e.sym().orig = b.dest();
    	}
     
    	/**
             * Delete a QuadEdge
             *
             * @param q the QuadEdge to delete
             */
    	public static void deleteEdge(QuadEdge q) {
    		splice(q, q.oprev());
    		splice(q.sym(), q.sym().oprev());
    	}
     
    	// ----------------------------------------------------------------
    	//                      Geometric computation
    	// ----------------------------------------------------------------
     
    	/**
             * Test if the Point p is on the line porting the edge
             *
             * @param e QuadEdge
             * @param p Point to test
             * @return true/false
             */
    	public static boolean isOnLine(QuadEdge e, Point2D.Double p) {
    		// test if the vector product is zero
    		if ((p.x-e.orig().x)*(p.y-e.dest().y)==(p.y-e.orig().y)*(p.x-e.dest().x))
    			return true;
    		return false;
    	}
     
    	/**
             * Test if the Point p is at the right of the QuadEdge q.
             *
             * @param QuadEdge reference
             * @param p Point to test
             * @return true/false
             */
    	public static boolean isAtRightOf(QuadEdge q, Point2D.Double p) {
    		return isCounterClockwise(p, q.dest(), q.orig());
    	}
     
    	/** return true if a, b and c turn in Counter Clockwise direction
             *
             * @param a,b,c the 3 points to test
             * @return true if a, b and c turn in Counter Clockwise direction
             */
    	public static boolean isCounterClockwise(Point2D.Double a, Point2D.Double b, Point2D.Double c) {
    		// test the sign of the determinant of ab x cb
    		if ( (a.x - b.x)*(b.y - c.y) > (a.y - b.y)*(b.x - c.x) ) return true;
    		return false;
    	}
     
    	/**
             * The Delaunay criteria:
             *
             *   test if the point d is inside the circumscribed circle of triangle a,b,c
             *
             * @param a,b,c triangle
             * @param d point to test
             * @return  true/false
             */
    	public static boolean inCircle(Point2D.Double a, Point2D.Double b, Point2D.Double c, Point2D.Double d) {
    		/*
    		 if "d" is strictly INSIDE the circle, then
     
    		     |d² dx dy 1|
                 |a² ax ay 1|
    		 det |b² bx by 1| < 0
    		     |c² cx cy 1|
     
    		*/
    		double a2 = a.x*a.x + a.y*a.y;
    		double b2 = b.x*b.x + b.y*b.y;
    		double c2 = c.x*c.x + c.y*c.y;
    		double d2 = d.x*d.x + d.y*d.y;
     
    		double det44 = 0;
    		det44 += d2  * det33( a.x,a.y, 1,  b.x,b.y, 1,  c.x,c.y, 1 );
    		det44 -= d.x * det33( a2 ,a.y, 1,  b2 ,b.y, 1,  c2 ,c.y, 1 );
    		det44 += d.y * det33( a2 ,a.x, 1,  b2 ,b.x, 1,  c2 ,c.x, 1 );
    		det44 -= 1   * det33( a2,a.x,a.y,  b2,b.x,b.y,  c2,c.x,c.y );
     
    		if (det44<0) return true;
    		return false;
    	}
     
    	private static double det33( double... m ) {
    		double det33=0;
    		det33 += m[0] * (m[4]*m[8] - m[5]*m[7]);
    		det33 -= m[1] * (m[3]*m[8] - m[5]*m[6]);
    		det33 += m[2] * (m[3]*m[7] - m[4]*m[6]);
    		return det33;
    	}
    }


    Delaunay.java

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
     
     
    import ij.IJ;
    import ij.plugin.PlugIn;
     
    import java.awt.Color;
    import java.awt.Graphics2D;
    import java.awt.Point;
    import java.awt.Polygon;
    import java.awt.geom.Point2D;
    import java.awt.image.BufferedImage;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Random;
     
    import javax.swing.ImageIcon;
    import javax.swing.JFrame;
    import javax.swing.JLabel;
    import javax.swing.JPanel;
    import javax.swing.JScrollPane;
    import javax.swing.WindowConstants;
     
    public class Delaunay{
     
    	// starting edge for walk (see locate() method)
    	private QuadEdge startingEdge = null;
     
    	// list of quadEdge belonging to Delaunay triangulation
    	private List<QuadEdge> quadEdge = new ArrayList<QuadEdge>();
     
    	// Bounding box of the triangulation
    	class BoundingBox {
    		double minx,miny,maxx,maxy;
    		Point2D.Double a = new Point2D.Double(); // lower left
    		Point2D.Double b = new Point2D.Double(); // lower right
    		Point2D.Double c = new Point2D.Double(); // upper right
    		Point2D.Double d = new Point2D.Double(); // upper left
    	}
    	private BoundingBox bbox = new BoundingBox();
     
    	/**
             * Constuctor:
             */
    	public Delaunay() {
     
    		bbox.minx = Double.MAX_VALUE;
    		bbox.maxx = Double.MIN_VALUE;
    		bbox.miny = Double.MAX_VALUE;
    		bbox.maxy = Double.MIN_VALUE;
     
    		// create the QuadEdge graph of the bounding box
    		QuadEdge ab = QuadEdge.makeEdge(bbox.a,bbox.b);
    		QuadEdge bc = QuadEdge.makeEdge(bbox.b,bbox.c);
    		QuadEdge cd = QuadEdge.makeEdge(bbox.c,bbox.d);
    		QuadEdge da = QuadEdge.makeEdge(bbox.d,bbox.a);
    		QuadEdge.splice(ab.sym(), bc);
    		QuadEdge.splice(bc.sym(), cd);
    		QuadEdge.splice(cd.sym(), da);
    		QuadEdge.splice(da.sym(), ab);
     
    		this.startingEdge = ab;
    	}
     
    	/**
             * update the dimension of the bounding box
             *
             * @param minx,miny,maxx,maxy summits of the rectangle
             */
    	public void setBoundigBox(double minx,double miny,double maxx,double maxy) {
    		// update saved values
    		bbox.minx=minx; bbox.maxx=maxx;
    		bbox.miny=miny; bbox.maxy=maxy;
     
    		// extend the bounding-box to surround min/max
    		double centerx = (minx+maxx)/2;
    		double centery = (miny+maxy)/2;
    		double x_min = ((minx-centerx-1)*10+centerx);
    		double x_max = ((maxx-centerx+1)*10+centerx);
    		double y_min = ((miny-centery-1)*10+centery);
    		double y_max = ((maxy-centery+1)*10+centery);
     
    		// set new positions
    		bbox.a.x = x_min;	bbox.a.y = y_min;
    		bbox.b.x = x_max;	bbox.b.y = y_min;
    		bbox.c.x = x_max;	bbox.c.y = y_max;
    		bbox.d.x = x_min;	bbox.d.y = y_max;
    	}
     
    	// update the size of the bounding box (cf locate() method)
    	private void updateBoundigBox(Point2D.Double p) {
    		double minx = Math.min(bbox.minx, p.x);
    		double maxx = Math.max(bbox.maxx, p.x);
    		double miny = Math.min(bbox.miny, p.y);
    		double maxy = Math.max(bbox.maxy, p.y);
    		setBoundigBox(minx, miny, maxx, maxy);
    		//System.out.println("resizing bounding-box: "+minx+" "+miny+" "+maxx+" "+maxy);
    	}
     
    	/**
             * Returns an edge e of the triangle containing the point p
             * (Guibas and Stolfi)
             *
             * @param p the point to localte
             * @return the edge of the triangle
             */
    	private QuadEdge locate(Point2D.Double p) {
     
    		/* outside the bounding box ? */
    		if ( p.x<bbox.minx || p.x>bbox.maxx || p.y<bbox.miny || p.y>bbox.maxy ) {
    			updateBoundigBox(p);
    		}
     
    		QuadEdge e = startingEdge;
    		while (true) {
    			/* duplicate point ? */
    			if(p.x==e.orig().x && p.y==e.orig().y) return e;
    			if(p.x==e.dest().x && p.y==e.dest().y) return e;
     
    			/* walk */
    			if (QuadEdge.isAtRightOf(e,p))
    				e = e.sym();
    			else if (!QuadEdge.isAtRightOf(e.onext(),p))
    				e = e.onext();
    			else if (!QuadEdge.isAtRightOf(e.dprev(),p))
    				e = e.dprev();
    			else
    				return e;
    		}
    	}
     
    	/**
             *  Inserts a new point into a Delaunay triangulation
             *  (Guibas and Stolfi)
             *
             * @param p the point to insert
             */
    	public void insertPoint(Point2D.Double p) {
    		QuadEdge e = locate(p);
     
    		// point is a duplicate -> nothing to do
    		if(p.x==e.orig().x && p.y==e.orig().y) return;
    		if(p.x==e.dest().x && p.y==e.dest().y) return;
     
    		// point is on an existing edge -> remove the edge
    		if (QuadEdge.isOnLine(e,p)) {
    			e = e.oprev();
    			this.quadEdge.remove(e.onext().sym());
    			this.quadEdge.remove(e.onext());
    			QuadEdge.deleteEdge(e.onext());
    		}
     
    		// Connect the new point to the vertices of the containing triangle
    		// (or quadrilateral in case of the point is on an existing edge)
    		QuadEdge base = QuadEdge.makeEdge(e.orig(),p);
    		this.quadEdge.add(base);
     
    		QuadEdge.splice(base, e);
    		this.startingEdge = base;
    		do {
    			base = QuadEdge.connect(e, base.sym());
    			this.quadEdge.add(base);
    			e = base.oprev();
    		} while (e.lnext() != startingEdge);
     
    		// Examine suspect edges to ensure that the Delaunay condition is satisfied.
    		do {
    			QuadEdge t = e.oprev();
     
    			if (QuadEdge.isAtRightOf(e,t.dest()) &&
    					QuadEdge.inCircle(e.orig(), t.dest(), e.dest(), p)) {
    				// flip triangles
    				QuadEdge.swapEdge(e);
    				e = e.oprev();
    			}
    			else if (e.onext() == startingEdge)
    				return; // no more suspect edges
    			else
    				e = e.onext().lprev();  // next suspect edge
    		} while (true);
    	}
     
    	/**
             *  compute and return the list of edges
             */
    	public List<Point2D.Double[]> computeEdges() {
    		List<Point2D.Double[]> edges = new ArrayList<Point2D.Double[]>();
    		// do not return edges pointing to/from surrouding triangle
    		for(QuadEdge q:this.quadEdge) {
    			if ( q.orig()==bbox.a || q.orig()==bbox.b || q.orig()==bbox.c || q.orig()==bbox.d ) continue;
    			if ( q.dest()==bbox.a || q.dest()==bbox.b || q.dest()==bbox.c || q.dest()==bbox.d ) continue;
    			edges.add(new Point2D.Double[]{q.orig(),q.dest()});
    		}
    		return edges;
    	}
     
    	/**
             *  compute and return the list of triangles
             */
    	public List<Point2D.Double[]> computeTriangles() {
    		List<Point2D.Double[]> triangles = new ArrayList<Point2D.Double[]>();
     
    		// do not process edges pointing to/from surrouding triangle
    		// --> mark them as already computed
    		for(QuadEdge q:this.quadEdge) {
    			q.mark = false; q.sym().mark=false;
    			if ( q.orig()==bbox.a || q.orig()==bbox.b || q.orig()==bbox.c || q.orig()==bbox.d ) q.mark = true;
    			if ( q.dest()==bbox.a || q.dest()==bbox.b || q.dest()==bbox.c || q.dest()==bbox.d ) q.sym().mark=true;
    		}
     
    		// compute the 2 triangles associated to each quadEdge
    		for(QuadEdge qe:quadEdge) {
    			// first triangle
    			QuadEdge q1 = qe;
    			QuadEdge q2 = q1.lnext();
    			QuadEdge q3 = q2.lnext();
    			if (!q1.mark && !q2.mark && !q3.mark) {
    				triangles.add(new Point2D.Double[] { q1.orig(),q2.orig(),q3.orig() });
    			}
     
    			// second triangle
    			QuadEdge qsym1 = qe.sym();
    			QuadEdge qsym2 = qsym1.lnext();
    			QuadEdge qsym3 = qsym2.lnext();
    			if (!qsym1.mark && !qsym2.mark && !qsym3.mark) {
    				triangles.add(new Point2D.Double[] { qsym1.orig(),qsym2.orig(),qsym3.orig() });
    			}
     
    			// mark as used
    			qe.mark=true;
    			qe.sym().mark=true;
    		}
     
    		return triangles;
    	}
     
    	public List<Point2D.Double[]> computeVoronoi() {
    		List<Point2D.Double[]> voronoi = new ArrayList<Point2D.Double[]>();
     
    		// do not process edges pointing to/from surrouding triangle
    		// --> mark them as already computed
    		for(QuadEdge q:this.quadEdge) {
    			q.mark = false; q.sym().mark=false;
    			if ( q.orig()==bbox.a || q.orig()==bbox.b || q.orig()==bbox.c || q.orig()==bbox.d ) q.mark = true;
    			if ( q.dest()==bbox.a || q.dest()==bbox.b || q.dest()==bbox.c || q.dest()==bbox.d ) q.sym().mark=true;
    		}
     
    		for(QuadEdge qe:quadEdge) {
     
    			// walk throught left and right region
    			for(int b=0;b<=1;b++) {
    				QuadEdge qstart = (b==0)?qe:qe.sym();
    				if (qstart.mark) continue;
     
    				// new region start
    				List<Point2D.Double> poly = new ArrayList<Point2D.Double>();
     
    				// walk around region
    				QuadEdge qregion = qstart;
    				while(true) {
    					qregion.mark=true;
     
    					// compute CircumCenter if needed
    					if (qregion.rot().orig()==null) {
    						QuadEdge q1 = qregion;		Point2D.Double p0=q1.orig();
    						QuadEdge q2 = q1.lnext();	Point2D.Double p1=q2.orig();
    						QuadEdge q3 = q2.lnext();	Point2D.Double p2=q3.orig();
     
    						double ex=p1.x-p0.x, ey=p1.y-p0.y;
    						double nx=p2.y-p1.y, ny=p1.x-p2.x;
    						double dx=(p0.x-p2.x)*0.5, dy=(p0.y-p2.y)*0.5;
    						double s=(ex*dx+ey*dy)/(ex*nx+ey*ny);
    						double cx=(p1.x+p2.x)*0.5+s*nx;
    						double cy=(p1.y+p2.y)*0.5+s*ny;
     
    						Point2D.Double p = new Point2D.Double( (int)cx,(int)cy );
    						qregion.rot().setOrig(p);
    					}
     
    					poly.add(qregion.rot().orig());
     
    					qregion = qregion.onext();
    					if (qregion==qstart) break;
    				}
     
    				// add region to output list
    				voronoi.add(poly.toArray(new Point2D.Double[0]));
    			}
    		}
    		return voronoi;
    	}
     
     
     
    }

    L'appel:

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    		List<Point2D.Double[]> edges = delaunay.computeEdges();
     
    		List<Point2D.Double[]> triangles = delaunay.computeTriangles();
    		List<Point2D.Double[]> voronoi  = delaunay.computeVoronoi();
     
    		Delaunay_ delaunay = new Delaunay_();
     
    		for(Point2D.Double p : pnt)
     
    		    {
    			if(p !=null) {
    			delaunay.insertPoint(p);
    			}
     
    		    }
     
    		for(Point2D.Double[] poly : voronoi) {
    		    Polygon polygon = new Polygon();
    		    for(Point2D.Double p : poly) {
    		    	if(p !=null) {
    		    	polygon.addPoint((int)p.x, (int)p.y);
    		    	}
    		    }
                   }
     
    		for(Point2D.Double[] tr : triangles) {
    		    Polygon polygon = new Polygon();
    		    for(Point2D.Double p : tr) {
    		    	if(p !=null){
    		    	polygon.addPoint((int)p.x, (int)p.y);
     
    		    	}
    		    }
     
    		for(Point2D.Double p : pnt) { 
    			if (p !=null){
    		    g2d.fillRect((int)p.x-2,(int)p.y-2,4,4);
    		    g3d.fillRect((int)p.x-2,(int)p.y-2,4,4);
    		    g4d.fillRect((int)p.x-2,(int)p.y-2,4,4);
    			}
    		}

  13. #53
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Pour utiliser des représentions double, il faut passer par les classes "Shape" du package java.awt.geom

    Rectangle2D.Double pour le rectangle
    Path2D.Double pour le polygone

    Le remplissage se fait alors avec Graphics2D.fill(Shape)

    Par ailleurs, j'ai dû remplacer la méthode long det33 par double det33. Est-ce que cela n'aura pas trop d'incidence?
    Heu, non. J'avais utilisé un long car toutes les coordonnées étaient des entiers, et donc le résultat était aussi un entier.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #54
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Bonjour et merci pour ta réponse.
    Alors j'ai utilisé les méthodes ci-dessus. Mais seuls les points sont dessinés. Le voronoi et le delaunay ne se dessinent pas. Je crois que cela vient de l'initialisation du polygone, je ne dois pas bien utiliser le Path2D.Double.
    Je vais faire encore quelques tests et posterai dès que je trouve.

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
                    //
    		for(Point2D.Double[] poly : voronoi) {
    			Path2D.Double polygon = new Path2D.Double();
    		    for(Point2D.Double p : poly) {
    		    	if(p !=null) {
    		    	polygon.moveTo(p.x, p.y);
    		    	polygon.lineTo(p.x, p.y);
    		    	}
    		    g2d.fill(polygon);
    		    g4d.fill(polygon);		    
    		}
    		}
     
    		for(Point2D.Double[] tr : triangles) {
    			Path2D.Double polygon = new Path2D.Double();
    		        for(Point2D.Double p : tr) {
    		    	if(p !=null){
    		    		polygon.moveTo(p.x, p.y);
    		    		polygon.lineTo(p.x, p.y);
     
    		    	}
    		    }
    		    g2d.fill(polygon);
    		    g3d.fill(polygon);
    		    g4d.fill(polygon);		    
     
    		}
     
    		for(Point2D.Double p : pnt) {
    			if (p !=null){
    				Rectangle2D rect2 = new Rectangle2D.Double(p.x-2,p.y-2,4,4);
    				g2d.fill(rect2);
     
    				Rectangle2D rect3 = new Rectangle2D.Double(p.x-2,p.y-2,4,4);
    				g3d.fill(rect3);
     
    				Rectangle2D rect4 = new Rectangle2D.Double(p.x-2,p.y-2,4,4);
    				g4d.fill(rect4);
     
    			}
    		}

    EDIT: ** modifications **

    Alors voici ce que j'ai fait :

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     
    //Voronoi
    		for(Point2D.Double[] poly : voronoi) {
    			Path2D.Double polygon = new Path2D.Double();
    			boolean isFirst = true; 
    		        for(Point2D.Double p : poly) {
    		    	     if(p !=null) {
    		    		 if (isFirst) {
    		    	              polygon.moveTo(p.x, p.y);
    		    	               isFirst = false;
    		    		 }
    		    		 else {polygon.lineTo(p.x, p.y);}
    		    	      }
     
    		    	//polygon.closePath();
    		    g2d.draw(polygon);
    		    g4d.draw(polygon);		    
    		}
    		}

    Mais en revanche, il y a toujours 2 points qui ne sont jamais reliés. Je vous joins un screenshot de ce que j'obtiens.
    Je continue à rechercher l'erreur possible.

  15. #55
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    En java, un Path2D n'est pas fermé par nature. Pour fermer le Path2D, il faut tracer une ligne jusqu'au premier point, ce qui se fait simplement en appelant la méthode closePath().

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(Point[] poly : voronoi) {
    	Path2D.Double path = new Path2D.Double();
     
    	path.moveTo(poly[0].getX(), poly[0].getY());
    	for(int i=1;i<poly.length;i++)
    		path.lineTo(poly[i].getX(), poly[i].getY());
    	path.closePath();
     
    	g2d.draw(path);
    }

    Pour le fun, une triangulation de la spirale d'or.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #56
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    ahh bien vu pseudocode. L'algo en double marche nickel maintenant

    Juste une dernière question stp. Est-ce qu'il y a un moyen plus simple que ça pour avoir les distance des segments de delaunay entre les points :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    		for(Point2D.Double[] tr : triangles) 
    			for(int i=1;i<tr.length;i++)
    				tr[i].distance(tr[i-1].getX(), tr[i-1].getY());

    ce qui m'obligerait à créer une HashMap pour chaque coordonnée pour avoir toutes les distances correspondantes?

    PS: joli joli la spirale d'or Les couleurs sont aléatoires?

  17. #57
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par mickeynad Voir le message
    Juste une dernière question stp. Est-ce qu'il y a un moyen plus simple que ça pour avoir les distance des segments de delaunay entre les points :

    ce qui m'obligerait à créer une HashMap pour chaque coordonnée pour avoir toutes les distances correspondantes?
    Non, je ne vois pas comment on pourrait faire autrement que de calculer la distance entre 2 points pour avoir... la distance entre 2 point.

    Cela dit tu peux récupérer la liste des segments directement par la méthode computeEdges(), plutot que de passer par computeTriangles().

    PS: joli joli la spirale d'or Les couleurs sont aléatoires?
    Oui. Pour être exact, elle sont choisies dans une liste cyclique de 64 couleurs.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  18. #58
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    44
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 44
    Points : 30
    Points
    30
    Par défaut
    Merci bien pour ta réponse.

  19. #59
    Membre actif Avatar de seb.49
    Profil pro
    ljgdfgdf
    Inscrit en
    Octobre 2002
    Messages
    290
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : ljgdfgdf

    Informations forums :
    Inscription : Octobre 2002
    Messages : 290
    Points : 200
    Points
    200
    Par défaut
    Bonjour,

    Désolé de ressortir ce post assez vieux mais j'essaie de le convertir en C# ce qui ne devrait pas poser de problème et pourtant, j'ai un souci dans la méthode locate

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    private QuadEdge locate(Point p)
            {
     
                /* outside the bounding box ? */
                if (p.X < bbox.minx || p.X > bbox.maxx || p.Y < bbox.miny || p.Y > bbox.maxy)
                {
                    updateBoundigBox(p);
                }
     
                QuadEdge e = startingEdge;
                while (true)
                {
                    /* duplicate point ? */
                    if (p.X == e._orig().X && p.Y == e._orig().Y) return e;
                    if (p.X == e.dest().X && p.Y == e.dest().Y) return e;
     
                    /* walk */
                    if (QuadEdge.isAtRightOf(e, p))
                        e = e.sym();
                    else if (!QuadEdge.isAtRightOf(e._onext(), p))
                        e = e._onext();
                    else if (!QuadEdge.isAtRightOf(e.dprev(), p))
                        e = e.dprev();
                    else
                        return e;
                }
            }
    je ne sors jamais du while

    Pouvez vous m'aider

  20. #60
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par seb.49 Voir le message
    je ne sors jamais du while

    Pouvez vous m'aider
    Hum... c'est curieux. Ca voudrait dire que le point n'est dans aucun des triangles déjà construits.

    Donc:
    - soit il y a une erreur lors de l'update de la taille de la bounding-box
    - soit les quadEdge sont construits avec une mauvaise orientation
    - soit il y a une erreur lors du calcul de "isAtRightOf()"

    Regarde s'il n'y a pas un dépassement de capacité dans "isAtRightOf()" ou "inCircle()".
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Réponses: 2
    Dernier message: 22/02/2009, 18h55
  2. Triangulation de Delaunay : stockage
    Par Mayhem555 dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 22/11/2006, 14h36
  3. Triangulation de Delaunay pour des carreaux troués
    Par Laurent Gomila dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 27/07/2005, 23h14
  4. triangulation de delaunay
    Par Smuk dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 08/04/2005, 15h15

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo