Tracer un segment dans un rectangle

Version imprimable

13/05/2014, 20h03
olibara

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 !

Je vois un algo comme cela :mrgreen:

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

2) Déterminer la direction D:

Code:

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 :mrgreen:

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 :mrgreen: : l'équation d'un côté du rectangle est de type X= ou Y=

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;
}

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:

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);
 
 
    }
    // ****************************************************************

14/05/2014, 17h29
Invité

Hello,

doublon avec ce site...
14/05/2014, 18h18
bertry
Citation:

Envoyé par olibara

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

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.
14/05/2014, 21h51
foetus

Il manque les cas particuliers: si O est un coin du rectangle :langue2: :langue2:

Citation:

Envoyé par bertry

Citation:

Envoyé par foetus

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 :whistle:
Mais effectivement avec le point O on calcule b facilement.
C'est peut-être cette notion de vecteur qui m'a perdu :aie:

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 :mrgreen:

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