Discussion :

[Nemerle]

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?

[Zavonen]

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.

[pseudocode]

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 )

[souviron34]

[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]

[pseudocode]

[un petit peu HS]une variante du marching square ?[/un petit peu HS]

[Zavonen]

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.

[Nemerle]

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

[pseudocode]

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

[Nemerle]

?

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?