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. #21
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    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
    28
    29
    30
    31
    32
    	bool QuadEdge::inCircle(Point& a, Point& b, Point& c, Point& 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|
     
    		*/
    		long a2 = a.x*a.x + a.y*a.y;
    		long b2 = b.x*b.x + b.y*b.y;
    		long c2 = c.x*c.x + c.y*c.y;
    		long d2 = d.x*d.x + d.y*d.y;
     
    		long 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;
    	}
     
    	long QuadEdge::det33(long m0, long m1, long m2, long m3, long m4, long m5, long m6, long m7, long m8) {
    		long det33=0;
    		det33 += m0 * (m4*m8 - m5*m7);
    		det33 -= m1 * (m3*m8 - m5*m6);
    		det33 += m2 * (m3*m7 - m4*m6);
    		return det33;
    	}
    Et moi pour ces points il me renvoie det -471 078 406 donc true...

  2. #22
    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 Java:1 / C++:0
    J'obtiens cela:

    a2 = 9325
    b2 = 133832
    c2 = 175012
    d2 = 7642

    det44 = 0 + (412362320) - (5266563450) + (-222207280) - (-8900297300)

    --> det44 = 3823888890
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #23
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Ah oui, mais en java les long sont sur 8 octets et en C++ les long sont seulement sur 4 octets, j'ai dépassé les 2 147 483 647 de valeur max...

    Comment vais je résoudre ce problème ...
    (Merci pseudoCode)

  4. #24
    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 Rumpel Voir le message
    Ah oui, mais en java les long sont sur 8 octets et en C++ les long sont seulement sur 4 octets, j'ai dépassé les 2 147 483 647 de valeur max...
    Arf ! essaye "long long", ou au pire "float" / "double" ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #25
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Merci pseudocode, je connaissais pas les long long.
    Bon tout semble rentrer dans l'ordre maintenant

  6. #26
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Ah oui encore une chose,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    this.quadEdge.remove(e.onext());
    Ne faut il pas enlever aussi l'arête symétrique ?
    Ca me paraitrait logique...

  7. #27
    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 Rumpel Voir le message
    Ah oui encore une chose,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    this.quadEdge.remove(e.onext());
    Ne faut il pas enlever aussi l'arête symétrique ?
    Ca me paraitrait logique...
    Heu oui. Tout à fait.

    Gros oubli dans mon code que je vais aller corriger de ce pas. Merci !
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #28
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Moi ca m'intéresse, spécialement la partie construction de la liste des triangles à partir des quadedges.

    Dans l'implémentation Java que j'ai postée, cette partie là est une création originale. Je me suis assez cassé la tête dessus pour avoir quelque chose d'efficace, mais je n'ai jamais démontré rigoureusement son exactitude. J'ai juste lancé plusieurs milliers de triangulations et comparé les résultats avec d'autre implémentations.

    Pour info, j'ai posté le code C ici

    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  9. #29
    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 souviron34 Voir le message
    Pour info, j'ai posté le code C ici

    Oui, j'ai vu. Tu travailles directement sur les triangles donc pas de problème pour les énumérer . Moi je travaille avec la structure QuadEdge donc l'extraction des triangles/régions nécessite une opération supplémentaire.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #30
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Oui, j'ai vu. Tu travailles directement sur les triangles donc pas de problème pour les énumérer . Moi je travaille avec la structure QuadEdge donc l'extraction des triangles/régions nécessite une opération supplémentaire.
    quelle horreur les maths

    ( c'est vrai, je vais toujours au plus simple... Dès que j'ai besoin d'une notion supplémentaire par rapport au problème, ça m'énerve et je tente d'éviter)



    PS : par contre j'ai réfléchi au handicap que j'avais trouvé, et en fait il est général : dès qu'un triangle est très aplati, la méthode IsInCircle ne suffit pas... J'avais fait un "patch" qui était de vérifier par rapport aux sommets. On pourrait aussi vérifier en prenant le cercle dont le centre est le plus proche du point considéré, ou de rayon le plus petit, ou dont la "corde" est la plus petite...

    PS2 : toutes les méthodes que j'ai vu se basent sur le fait que l'enveloppe extérieure est convexe. J'avais là aussi développé un "patch" (en utilisant ma méthode d'enveloppe non-convexe) pour des enveloppes concaves, mais je ne sais pas si il existe des méthodes "générales" traitant ce problème..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  11. #31
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Hello,

    Je regarde ça en fin de semaine, histoire de ne pas me mélanger avec mon propre code . Merci à toi souviron, je te dirais ce que j'en pense bientôt...

  12. #32
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    		if ( p.x<=bbox.minx || p.x>=bbox.maxx || p.y<=bbox.miny || p.y>=bbox.maxy ) {
    C'est mieux, parce que si un point arrive juste sur la ligne de la Bounding box, tu vas avoir mal, c'est arrivé juste pendant ma démo

    Sinon encore des problème avec inCircle
    a (50,90)
    b (70,50)
    c (50,10)
    d (60,30)

    A vu de nez d est dans le cercle, pourtant ça renvoit faux...
    Et je suis passé en double cette fois ci...

  13. #33
    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 Rumpel Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    		if ( p.x<=bbox.minx || p.x>=bbox.maxx || p.y<=bbox.miny || p.y>=bbox.maxy ) {
    C'est mieux, parce que si un point arrive juste sur la ligne de la Bounding box, tu vas avoir mal, c'est arrivé juste pendant ma démo
    Dans mon cas, la surrounding-box est beaucoup plus grande que la Bounding box. Donc pas de problèmes.

    Sinon encore des problème avec inCircle
    A vu de nez d est dans le cercle, pourtant ça renvoit faux...
    Et je suis passé en double cette fois ci...
    La routine "inCircle" ne fonctionne que si les points (a,b,c) sont dans le sens trigo:
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    if (QuadEdge.isAtRightOf(e,t.dest()) && QuadEdge.inCircle(e.orig(), t.dest(), e.dest(), p)) {
    	// flip triangles
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #34
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Ah ok merci Pseudocode, j'avais pas noté, ça...

  15. #35
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Dans locate :

    J'ai modifié comme ça :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    		else
    		{
    			if (QuadEdge::isOnEdge(*(e->getOnext()),p))
    				e = e->getOnext();
    			if (QuadEdge::isOnEdge(*(e->dprev()),p))
    				e = e->dprev();
    			return e;
    		}
    A mettre en relation avec insertPoint

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    		if (QuadEdge::isOnEdge(*e,*p)) {
    Sinon p peut être sur une des 3 arêtes du triangle, pas forcément sur e...

  16. #36
    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
    heu... si tu le dis. J'avoue que je ne vois pas trop où est le problème dans le code original...

    locate() renvoie juste l'un des 3 quadedges du triangle contenant le point p.

    Ou alors je n'ai pas compris le problème.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  17. #37
    Membre du Club
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 77
    Points : 66
    Points
    66
    Par défaut
    Oui, mais c'est pour traiter le cas où le point P est sur l'une des 3 edges du triangle (sur le triangle, pas à l'intérieur strictement). Forcément dans ce cas, tu dois détruire l'edge sur lequel P est tombé. Mais dans ton code tu as 2 chances sur 3 de te tromper
    Toi ça ne doit pas t'arriver souvent, mais moi dans mon problème j'ai souvent des points qui doivent tomber pile sur les edges...

  18. #38
    Nouveau Candidat au Club
    Inscrit en
    Juillet 2009
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Juillet 2009
    Messages : 1
    Points : 1
    Points
    1
    Par défaut supression des fonctions isOnEdge, distanceToSegment et squaredistance
    Cela a peut-être été évoqué avant, mais on peut remplacer la ligne
    "if (QuadEdge.isOnEdge(e,p)) {" de la fonction insertPoint

    par "if ((p.x-e.orig().x)*(p.y-e.dest().y)==(p.y-e.orig().y)*(p.x-e.dest().x)){"
    et supprimer les 3 fonction nommées ci-dessus. J'ai fait des tests avec des 200, 500 et 1000 points aléatoires, et ça a l'air de fonctionner.
    En plus, cela retire le "d>0.01"

    La relation ci-dessus signifie que lorsque A, B et C sont sur la même droite, le produit vectoriel de AB et AC vaut zéro. On augmente artificiellement l'espace d'une dimension pour calculer le produit vectoriel, mais on peut fixer la composante z de chaque point à 0. On ne s'intéresse qu'à "B appartient au segment [AC]", par exemple, mais dans notre cas, on peut se contenter de "B est sur la droite (AC)" car locate nous confirme déjà que si "B est sur (AC)" alors il est forcément sur le segment.

  19. #39
    Candidat au Club
    Inscrit en
    Février 2008
    Messages
    2
    Détails du profil
    Informations forums :
    Inscription : Février 2008
    Messages : 2
    Points : 2
    Points
    2
    Par défaut Problèmes sur une génération de régions de voronoi
    Bonjour pseudocode,
    J'essaie d'utiliser ton algo java pour déterminer la zone la plus proche des villes sur la France. J'ai du l'adapter un peu pour avoir plus de précision donc j'ai passé tous les Point en Point2D.Double et tous les int en double.

    J'obtiens 2 problèmes :
    - Le premier, un peu incompréhensible, c'est que sur certains ajouts de points, l'aglo reste indéfiniment bloqué dans l'insertPoint car les valeurs next des QuadEdge rebouclent...

    - Le 2ème problème, je vais l'illustrer sur les villes du Rhône. Sur ce département, aucun ajout de point ne bloque par contre j'obtiens quelques zones complètement incohérentes puisqu'elles se superposent à d'autres zones correctes.
    J'ai joint l'image obtenu sous google earth grâce à ma génération.
    J'ai également joint à ce message le positionnement de mes villes.

    Pensez vous que le passage en Point2D puisse provoquer ces erreurs ? Est-ce qu'il pourrait y avoir une autre anomalie ?

    Merci
    Bastien
    Images attachées Images attachées  
    Fichiers attachés Fichiers attachés

  20. #40
    Candidat au Club
    Inscrit en
    Février 2008
    Messages
    2
    Détails du profil
    Informations forums :
    Inscription : Février 2008
    Messages : 2
    Points : 2
    Points
    2
    Par défaut A ben non ça marche! :)
    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

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