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

Algorithmes et structures de données Discussion :

[perfs] intersections droite/rectangle


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut [perfs] intersections droite/rectangle
    Tout est dans le titre: je connais différents algos d'intersection d'un point et d'un rectangle quelconque dans le plan (y a eu un sujet pas longtemps par ailleurs).

    Quel algo performant d'après vous permet de trouver l'intersection d'un segment et d'un rectangle quelconque dans le plan?

  2. #2
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Je crois qu'il suffit de mettre bout à bout tout deux d'algos présentés ici-même il n'y a pas longtemps.
    • Test d'appartenance d'un point à un rectangle.
    • Intersection de deux segments (proposition récente de Pseudocode).

    On teste l'appartenance de chaque extrémité du segment au rectangle.
    OUI-OUI --> le segment tout entier.
    NON-NON --> Intersections du segment avec chacun des 4 côtés (on peut trouver 0 points ou 2 éventuellement confondus. Donc rien ou un sous-segment, selon.
    OUI-NON --> Intersections du segment avec chacun des 4 côtés (on trouve un point, ou éventuellement deux confondus). Sous segment joignant le sommet inclus au point intersection.
    Cela dit, on peut peut-être mieux faire.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  3. #3
    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 : 52
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Pour reprendre l'idée de Zavonen, on peut faire 4 intersections Ligne / segment (chaque segment représente un coté du rectangle).

    Chaque intersection est soit vide, 1 point ou 1 segment:
    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
     
    // Intersection entre le segment [A,B] et la droite O+t.V
    static Intersection intersectionLineSegment(Point A, Point B, Point O, Point V) {
    	// cas ou AB et V sont colineaires
    	double den = (B.x-A.x)*(V.y)-(B.y-A.y)*(V.x);
    	if (den==0)  { 
    		// O est sur la droite (A,B) -> intersection = tout le segment
    		double det = (B.x-A.x)*(O.y-A.y)-(B.y-A.y)*(O.x-A.x);
    		if (det==0) return new IntersectionSegment(A,B);	
     
    		// sinon pas d'intersection
    		return null;     
    	}
     
    	// calcul l'intersection entre les 2 droites (A,B) et O+t.V
    	double num = (A.y-O.y)*(V.x)-(A.x-O.x)*(V.y);
    	if (den<0) {num=-num; den=-den;}
     
    	// l'intersection est avant A ou après B -> pas d'intersection
    	if (num<0)   return null;
    	if (num>den) return null;
     
    	// l'intersection est le point A
    	if (num==0) return new IntersectionPoint(A); 
     
    	// l'intersection est le point B
    	if (num==den) return new IntersectionPoint(B); 
     
    	/* note: on peut ignorer le cas ou l'intersection est le
    	 * point B car, dans le cas du rectangle, ce point sera
    	 * l'origine d'un autre segment.		
    	 */
     
    	// sinon l'intersection est entre A et B
    	double r = num/den;
    	Point p = new Point(A.x+r*(B.x-A.x), A.y+r*(B.y-A.y) );
    	return new IntersectionPoint(p);
    }

    Le résultat final est l'union des 4 intersections.

    (je vous laisse écrire le code )
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Expert confirmé

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

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    [un petit peu HS]

    ca me fait penser, je ne sais pas si vous connaissez cette excellente et simplissime routine pour effectuer des calculs de contours , CONREC, de P.Burke (http://local.wasp.uwa.edu.au/~pbourke/papers/conrec/)...

    Explication simple, application egalement...

    Si il y a des valeurs attribuees aux sommets du rectangle et aux extremtites du segment, application pour le cas present.

    Mais sinon, j'ai ete tellement ebloui par la beaute et simplicite de cette methode que je voulais la faire partager...

    [/un petit peu HS]

  5. #5
    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 : 52
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    [un petit peu HS]une variante du marching square ?[/un petit peu HS]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    On peut aussi raisonner ainsi.
    Commencer par traiter le problème de l'intersection d'une droite avec un rectangle. Cela a déjà été fait ici il n'y a pas longtemps. Le critère d'intersection est simple si on compare la distance du centre de gravité du rectangle avec la demi-diagonale.
    On peut donc déjà faire une première discrimination presque immédiate:
    La droite (AB) coupe-t-elle le rectangle ?
    Si NON problème terminé.
    Si OUI determiner le segment intersection (problème à priori plus simple que le problème initial, cela peut se faire juste avec ce bon vieux Pythagore).
    Ensuite il ne reste plus qu'à déterminer l'intersection de deux segments d'une même droite, ce qui revient à des comparaisons de coordonnées.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  7. #7
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    double den = (B.x-A.x)*(V.y)-(B.y-A.y)*(V.x);
    if (den==0) {
    // O est sur la droite (A,B) -> intersection = tout le segment
    Au fait, CA, c'est fô...


    Maintenant, ma soluce (crade , sous excel) proche de celle de Pseudocode (segment (x1,y1)--->(x2,y2), et les cotés du rectangle sont donnés par o(i,j)).

    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
    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
    nbsol = 0
     
    For i = 0 To 3
        ok = False
        u(1) = x1 - o(i, 1)
        u(2) = y1 - o(i, 2)
        v(1) = x2 - o(i, 1)
        v(2) = y2 - o(i, 2)
        w(1) = o(i + 1, 1) - o(i, 1)
        w(2) = o(i + 1, 2) - o(i, 2)
     
        den = u(1) * v(2) - v(2) * u(1)
        det = w(1) * u(2) - w(2) * u(1)
     
       If den = 0 And det = 0 And det <> den Then '====== (O(i)O(i+1)) = (AB)
            ta = u(1) / w(1)
            tb = v(1) / w(1)
            If Not ((ta < 0 Or ta >= 1) And (tb < 0 Or tb >= 1)) Then
                If ta > tb Then
                    tc = tb
                    tb = ta
                    ta = tc
                End If
                If ta < 0 Then ta = 0
                If tb > 1 Then tb = 1
                sol(1) = ta
                sol(2) = tb
                nbsol = 2
                i = 4
            End If
        Else
            det1 = w(1) * ab(2) - w(2) * ab(1)
            If det1 <> 0 Then
                mu = -det / det1
            Else
                mu = -1
            End If
            sol(nbsol) = mu
            nbsol = nbsol + 1
        End If
    Next i
    For i = 0 To nbsol - 1
        If (sol(i) >= 0 And sol(i) <= 1) Then
            solgood(nbgood) = sol(i)
            nbgood = nbgood + 1
        End If
    Next i
    If nbgood = 1 Then
        If isinside(x1, y1, lx, ly, rx, ry, tx, ty, bx, by) Then
            solgood(nbgood) = 0
            nbgood = nbgood + 1
        End If
        If isinside(x2, y2, lx, ly, rx, ry, tx, ty, bx, by) Then
            solgood(nbgood) = 1
            nbgood = nbgood + 1
        End If
    End If
    If nbgood = 2 Then
        intersect = Abs(solgood(1) - solgood(0))
    Else
        intersect = 0
    End If

  8. #8
    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 : 52
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    Au fait, CA, c'est fô...
    ?

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    // cas ou AB et V sont colineaires
    	// O est sur la droite (A,B) -> intersection = tout le segment
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    ?

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    // cas ou AB et V sont colineaires
    	// O est sur la droite (A,B) -> intersection = tout le segment
    ? ?

    Tu calcules le determinant des vecteurs AB et V: ça te dis juste effectivement que AB et V sont colinéaires, mais pas que 0 est sur (AB) !

    Nàn?

Discussions similaires

  1. Intersection droite et plan
    Par declencher dans le forum Mathématiques
    Réponses: 6
    Dernier message: 22/12/2008, 13h56
  2. Intersection droite cercle
    Par morind79 dans le forum Mathématiques
    Réponses: 3
    Dernier message: 03/09/2008, 12h50
  3. Réponses: 2
    Dernier message: 24/05/2008, 21h54
  4. Calculer point intersection droite
    Par cetiop dans le forum C
    Réponses: 7
    Dernier message: 21/01/2008, 22h26
  5. Intersection droite-plan
    Par Finch dans le forum OpenGL
    Réponses: 2
    Dernier message: 25/04/2005, 13h05

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