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

Mathématiques Discussion :

Tracer un segment dans un rectangle


Sujet :

Mathématiques

  1. #1
    Membre émérite
    Profil pro
    Mangeur de gauffre
    Inscrit en
    Octobre 2007
    Messages
    4 413
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Mangeur de gauffre

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 413
    Points : 2 498
    Points
    2 498
    Par défaut Tracer un segment dans un rectangle
    Bonjour

    Je dispose des coordonnées d'un rectangle ABCD A(x,y), B(x,y),C(x,y),D(x,y)

    Pour simplifier le point inférieur gauche A est (0,0) le point supérieur droit C est X,Y

    Je connais un point d'origine O x1,y1 qui se trouve quelque part sur le perimetre du rectangle
    J'ai deux vecteurs vX et vY donnant un coefficient de force en X et en Y (les valeurs peuvent etre positives ou negatives et indépendante de mon rectangle)

    ces Deux vecteurs me permettent de calculer le coefficient a d'une droite de forme Y=aX+b
    a= vY/vX

    Je dois trouver le point le point d'intesection avec un coté du rectangle d'une droit passant par le point O ayant le coefficient a.

    J'avoue que je seche
    je travaille en programation cSharp mais je n'ai pas encore trouvé d'algorithme discret pour faire cela.
    Je travaille a coup de calcul conditionnel if, else ca va plus ou moins mais je tombe souvent sur une exception qui me faire repartir dans la mauvaise direction sans traverser mon rectangle

    Exemple de valeurs
    A=(0,0)
    C=(46,41)
    vY=5.259999
    vX=-5.940001

    O=(38,41)

    Merci pour votre aide !
    « Ils ne savaient pas que c'était impossible, alors ils l'ont fait ». (Twain)

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Je vois un algo comme cela

    1) Déterminer a quel côté appartient le point: côté droit, gauche, haut, bas
    Le point 1 est assez simple à faire

    2) Déterminer la direction D:
    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
       si côté droit:
          si vY == 0 Direction vers côté gauche
          si vX < 0 -> Peut-être inversé vX????
          si vY < 0 Direction vers côté haut sinon vers côté bas
       si côté gauche:
          si vY == 0 Direction vers côté droit
          si vX > 0 -> Peut-être inversé vX????
          si vY < 0 Direction vers côté haut sinon vers côté bas
       si côté haut:
          si vX == 0 Direction vers côté bas
          si vX < 0 Direction vers côté droit sinon vers côté gauche
          si vY < 0 -> Peut-être inversé vY????
       si côté bas:
          si vX == 0 Direction vers côté haut
          si vX < 0 Direction vers côté droit sinon vers côté gauche
          si vY > 0 -> Peut-être inversé vY????
    Édit: Il faut peut-être géré le cas où soit vX soit vY vaut 0

    3) Adaptation de l'algo Bresenham pour déterminer, en partant du point O, vers la direction D, le moment lorsqu'on a dépassé le côté du rectangle.

    4) Intersection des 2 segments: le côté du rectangle et [OE], E étant le point d'arrêt du point 3

    Édit: Dans ce problème, il nous manque b de l'équation: Y=aX + b.
    Parce que sinon c'est simple : l'équation d'un côté du rectangle est de type X= ou Y=

    Trouvé sur cette page: Intersection of segments in 2D

    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
    /**
     * Computes the intersection between two segments. 
     * @param x1 Starting point of Segment 1
     * @param y1 Starting point of Segment 1
     * @param x2 Ending point of Segment 1
     * @param y2 Ending point of Segment 1
     * @param x3 Starting point of Segment 2
     * @param y3 Starting point of Segment 2
     * @param x4 Ending point of Segment 2
     * @param y4 Ending point of Segment 2
     * @return Point where the segments intersect, or null if they don't
     */
    public Point intersection(
        int x1,int y1,int x2,int y2, 
        int x3, int y3, int x4,int y4) {
     
        int d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
     
        if (d == 0) return null;
     
        int xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
        int yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
     
        Point p = new Point(xi,yi);
     
        if (xi < Math.min(x1,x2) || xi > Math.max(x1,x2)) return null;
     
        if (xi < Math.min(x3,x4) || xi > Math.max(x3,x4)) return null;
     
        return p;
    }

  3. #3
    Membre émérite
    Profil pro
    Mangeur de gauffre
    Inscrit en
    Octobre 2007
    Messages
    4 413
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Mangeur de gauffre

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 413
    Points : 2 498
    Points
    2 498
    Par défaut
    Merci foetus

    Mais je ne suis pas convaincu que ce soit la bonne approche

    L'algo de Bresenham ne me semble pas vraiment approprié ici

    À priori l'exercice semble simple (il s'agit de la résolution d'une équation de droite Y=aX+b)

    étant donné par vY / vX

    La problématique étant qu'ayant un point d'origine connu il faut trouver un autre point dans le domaine du périmetre du rectangle
    Avec un cas particulier si vX ou vX valent zéro

    N.B. : j'ai réussi à faire quelque chose qui donne un résultat pas trop mauvais mais qui foire quand même sur certains cas et qui me semble de toute façon trop compliqué

    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
        // *************************************************************
        private void DrawOneStreamSegment(Graphics GR, Rectangle R, C_StreamCell SC)
        {
     
          int SignX = Math.Sign(SC.uV);
          int SignY = Math.Sign(SC.vV);
     
          Point Origin = SC.TraceFrom;
     
          double oY = 0;
          double oX = 0;
     
          // on se remet dans un systeme d'axe normal
          if (!Origin.IsEmpty)
          {
            oY = R.Bottom - Origin.Y;
            oX = Origin.X - R.Left;
          }
          else 
          {
            SC.TraceFrom = new Point(R.Left, R.Bottom);
            if (SignX != SignY)
            {
              oY = R.Height;
              SC.TraceFrom.Y = R.Top;
            }
          }
     
          double nX = R.Width;
          double nY = oY;
     
          if (SC.uV != 0)
          {
            double A = SC.vV / SC.uV;
     
            nY = ((nX - oX) * A) + oY; //  (R.Width) est aussi R.Right-R.Left
     
            if (oX == R.Width)
            {
              double C = oY - (oX * A);
              C = oY - (A * oX);
              nY = C;
              nX = 0;
              if (C > R.Height)
              {
                nY = R.Height;
                nX = (nY - C) / A;
              }
              if (C < 0)
              {
                nY = 0;
                nX = (nY - C) / A;
              }
            }
            if (nY < 0)
            {
              int uu = 5;
            }
     
            // TODO Verifier ce test d'exception
            if (oY == R.Height && (oX != 0) && A > 0)
            {
              double C = oY - (oX * A);
              C = oY - (A * oX);
              nY = C;
              nX = 0;
              if (C > R.Height)
              {
                nY = R.Height;
                nX = (nY - C) / A;
              }
              if (C < 0)
              {
                nY = 0;
                nX = (nY - C) / A;
              }
            }
     
            if (nY > R.Height)
            {
              nY = R.Height;
              nX = ((nY - oY) / A) + oX;
            }
            if (nY < 0)
            {
              if (SignX < 0) 
              {
                nY = 0;
                nX = ((nY - oY) / A) + oX;
              }
              else
              {
                nY = R.Height;
                nX = ((nY - oY) / A) + oX;
                if (nX < 0)
                {
                  nX = 0;
                  nY = ((nX - oX) * A) + oY;
                }
              }
            }
          }
     
          nX = Math.Round(nX, MidpointRounding.AwayFromZero);
          nY = Math.Round(nY, MidpointRounding.AwayFromZero);
     
          oX += R.Left;
          nX += R.Left;
          oY = R.Bottom - oY;
          nY = R.Bottom - nY;
     
     
          Point p0 = new Point((int)oX, (int)oY);
          Point p1 = new Point((int)nX, (int)nY);
     
     
          int ColorId = 0;
          if (SC.F > 15) ColorId = 1;
          if (SC.F > 25) ColorId = 2;
          GR.DrawLine(StreamPens[ColorId], p0, p1);
     
     
          SC.Done = true;
          SC.TraceTo = p1;
     
          // Il faut determiner l'offset del'indice de la cellule sortante
          SC.XTo = 0;
          SC.YTo = 0;
     
          if (p1.X == R.Right) SC.XTo = 1;
          if (p1.X == R.Left) SC.XTo = -1;
          if (p1.Y == R.Top) SC.YTo = -1;
          if (p1.Y == R.Bottom) SC.YTo = 1;
     
     
          GR.DrawRectangle(pg, R);
     
     
        }
        // ****************************************************************
    « Ils ne savaient pas que c'était impossible, alors ils l'ont fait ». (Twain)

  4. #4
    Invité
    Invité(e)
    Par défaut
    Hello,

    doublon avec ce site...

  5. #5
    Membre éclairé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    426
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Puy de Dôme (Auvergne)

    Informations forums :
    Inscription : Octobre 2008
    Messages : 426
    Points : 827
    Points
    827
    Par défaut
    Citation Envoyé par olibara Voir le message
    Je dispose des coordonnées d'un rectangle ABCD A(x,y), B(x,y),C(x,y),D(x,y)

    Pour simplifier le point inférieur gauche A est (0,0) le point supérieur droit C est X,Y

    Je connais un point d'origine O x1,y1 qui se trouve quelque part sur le perimetre du rectangle
    J'ai deux vecteurs vX et vY donnant un coefficient de force en X et en Y (les valeurs peuvent etre positives ou negatives et indépendante de mon rectangle)

    ces Deux vecteurs me permettent de calculer le coefficient a d'une droite de forme Y=aX+b
    a= vY/vX
    Tu as a= vY/vX.
    Tu obtiens b à partir de O(x1,y1) et de l'équation de la droite: y1 = a*x1 + b ce qui donne: b = y1 - a*x1

    On connait donc tous les paramètre de la droite: y = a*x + b

    Ensuite:
    On sait que les équations des droites formant les cotés du rectangle sont:
    1. x = xA
    2. y = yA
    3. x = xC
    4. y = yC

    On calcule l'intersection de la droite avec chacunes des droites formant le rectangle, on obtient respectivement:
    1. y = a*xA+b
    2. x = (yA-b)/a
    3. y = a*xC+b
    4. x = (yC-b)/a

    puis finalement, cherche lesquelles de ces intersections sont sur les segments constituant le rectangle, respictivement:
    1. y = a*xA+b: test si y Formule mathématique [yA, yC] si oui: point ( xA, a*xA+b )
    2. x = (yA-b)/a: test si x Formule mathématique [xA, xC] si oui: point ( (yA-b)/a, yA )
    3. y = a*xC+b: test si y Formule mathématique [yA, yC] si oui: point ( xC, a*xC+b )
    4. x = (yC-b)/a: test si x Formule mathématique [xA, xC]si oui: point ( (yC-b)/a, yC )

    J'ai testé sur un petit exemple, ça a l'air de marcher...

    PS:
    Citation Envoyé par foetus Voir le message
    3) Adaptation de l'algo Bresenham pour déterminer, en partant du point O, vers la direction D, le moment lorsqu'on a dépassé le côté du rectangle.
    Je ne comprends pas trop ce que Bresenham apporte ici.

  6. #6
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Il manque les cas particuliers: si O est un coin du rectangle

    Citation Envoyé par bertry Voir le message
    Citation Envoyé par foetus Voir le message
    3) Adaptation de l'algo Bresenham pour déterminer, en partant du point O, vers la direction D, le moment lorsqu'on a dépassé le côté du rectangle.
    PS: Je ne comprends pas trop ce que Bresenham apporte ici.
    Comme je l'ai dit, pour moi le problème c'est la recherche du b .... parce que sinon c'est simple
    Mais effectivement avec le point O on calcule b facilement.
    C'est peut-être cette notion de vecteur qui m'a perdu

    Dès le début je cherche le côté C1 dont O appartient et le côté C2 que l'on va rejoindre (toi tu le fais à la fin), et pour faire l’intersection de notre droite Y = aX +b avec C2, je trace notre droite pour trouver le point "après" C2 et ensuite faire le calcul d'intersection

    Voila, c'est l'algo "4x4"

Discussions similaires

  1. Dégradé de couleur dans un rectangle
    Par macoute dans le forum 2D
    Réponses: 3
    Dernier message: 10/01/2006, 17h30
  2. [AWT] repérer un clic dans un Rectangle
    Par bigVinz dans le forum AWT/Swing
    Réponses: 2
    Dernier message: 19/12/2005, 10h42
  3. Dessin de la partie d'une ligne passant dans un rectangle
    Par Invité dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 13/06/2005, 10h35
  4. [MFC]Ecrire du texte dans un rectangle
    Par zaz16 dans le forum MFC
    Réponses: 8
    Dernier message: 29/07/2003, 11h31
  5. Comment centrer un Texte dans un rectangle ...
    Par Djedjeridoo dans le forum Composants VCL
    Réponses: 3
    Dernier message: 16/06/2003, 22h56

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