Intersection d'un segment avec un rectangle

[Anonyme]

Bonjour,

Ayant les coordonnées dans un repaire orthonormé de :
- un segment (les 2 coordonnées des extremmitées)
- un rectangle (soit les 4 coordonnées des 4 coins, même si seulement 2
sont utiles)

J'ai beau me creuser la tête, je ne trouve pas de technique (algorithme
en fait) "pas trop tirée par les cheuveux" pour vérifier que le segment
croise le rectangle quand les deux extremmitées du segment sont en
dehors du rectangle.

Si quelqu'un a une idée ...

Merci d'avance


Sylvain

[Anonyme]

Sylvain Ross a écrit :
> Bonjour,
>
> Ayant les coordonnées dans un repaire orthonormé de :
> - un segment (les 2 coordonnées des extremmitées)
> - un rectangle (soit les 4 coordonnées des 4 coins, même si seulement 2
> sont utiles)
>
> J'ai beau me creuser la tête, je ne trouve pas de technique (algorithme
> en fait) "pas trop tirée par les cheuveux" pour vérifier que le segment
> croise le rectangle quand les deux extremmitées du segment sont en
> dehors du rectangle.
>
> Si quelqu'un a une idée ...

Juste une idée à creuser : prendre les points d'intersection des droites
portées par les diagonales du rectangle avec la droite portée par le
segment (équation des droites avec les coordonées connues puis résoudre
le système d'équations). Vérifier ensuite que les points obtenus (ou le
point si le segment est parallèle à l'une des diagonales) est bien dans
le segment et à l'intérieur du rectangle (avec des coordonnées
barycentriques ou un truc dans ce goût là).
Enfin je suis fatigué alors je dis peut-être des conneries.

Bon courage,
--
Gabriel Kerneis.

[Anonyme]

Sylvain Ross wrote in message news:...
> Bonjour,
>
> Ayant les coordonnées dans un repaire orthonormé de :
> - un segment (les 2 coordonnées des extremmitées)
> - un rectangle (soit les 4 coordonnées des 4 coins, même si seulement 2
> sont utiles)
>
> J'ai beau me creuser la tête, je ne trouve pas de technique (algorithme
> en fait) "pas trop tirée par les cheuveux" pour vérifier que le segment
> croise le rectangle quand les deux extremmitées du segment sont en
> dehors du rectangle.
>
> Si quelqu'un a une idée ...
>
> Merci d'avance
>
>
> Sylvain

Bonjour Sylvain,

Si tu sais que les extrémités du segment sont à l'extérieur du
rectangle, il suffit de vérifier que le segment coupe au moins une
diagonale.
Soit ABCD le rectangle et MN le segment. Les droites support des
diagonales et du segment ont pour équation:
D1(A,C): d1(x,y)=0 D2(B,D): d2(x,y)=0 S(M,N): s(x,y)=0
(il est assez simple d'établir ces équations en fonction des
coordonnées des points)
-il y a intersection entre la diagonale AC et le segment si les 2
conditions suivantes sont vérifiées:
d1(xm,ym) et d1(xn,yn) sont de signes différents (N et M situés de
chaque coté de la droite)
s(xa,ya) et s(xc,yc) sont de signes différents (A et B situés de
chaque coté du segment)
(avec quelques cas particuliers si certaines valeurs sont nulles)
-idem avec l'autre diagonale.

Bon courage,
Eric

[Anonyme]

Sylvain Ross wrote:
> Bonjour,
> Ayant les coordonnées dans un repaire orthonormé de :
> - un segment (les 2 coordonnées des extremmitées)
> - un rectangle (soit les 4 coordonnées des 4 coins, même si seulement 2
> sont utiles)
> J'ai beau me creuser la tête, je ne trouve pas de technique (algorithme
> en fait) "pas trop tirée par les cheuveux" pour vérifier que le segment
> croise le rectangle quand les deux extremmitées du segment sont en
> dehors du rectangle.
> Si quelqu'un a une idée ...
> Merci d'avance
> Sylvain

Soient {xr1,yr1},{xr2,yr2} un côté du rectangle
et {xs1,ys1},{xs2,ys2} le segment intercepteur.
On exprime qu'il y a deux déterminants nuls et deux produits scalaires
négatifs.
Solution préparée avec Mathematica :
test[{xr1_,yr1_},{xr2_,yr2_},{xs1_,ys1_},{xs2_,ys2_}]:=
(xr1^2-2*xr1*xr2+xr2^2+yr1^2-2*yr1*yr2+yr2^2)*(-(xs1*yr1)+
xs2*yr1+xr1*ys1-xs2*ys1-xr1*ys2+xs1*ys2)*(-(xs1*yr2)+xs2*yr2+
xr2*ys1-xs2*ys1-xr2*ys2+xs1*ys2) <= 0
&&
(xr2*yr1-xs1*yr1-xr1*yr2+xs1*yr2+xr1*ys1-xr2*ys1)*(xr2*yr1-xs2*yr1-xr1*yr2+xs2*yr2+xr1*ys2-xr2*ys2)*(xs1^2-2*xs1*xs2+xs2^2+ys1^2-2*ys1*ys2+ys2^2)
<= 0;

En général deux des côtés répondent True au test s'il y a intersection.
Exemple :

test[{1,3},{5,3},{0,0},{3,5}]
True
test[{1,1},{1,3},{0,0},{3,5}]
True
test[{1,1},{5,1},{0,0},{3,5}]
False
test[{5,1},{5,3},{0,0},{3,5}]
False
--
0% de pub! Que du bonheur et des vrais adhérents !
Vous aussi inscrivez-vous sans plus tarder!!
Message posté à partir de http://www.gyptis.org, BBS actif depuis 1995.

[Anonyme]

astanoff wrote:

> Sylvain Ross wrote:[color=green]
>> Bonjour,
>> Ayant les coordonnées dans un repaire orthonormé de :
>> - un segment (les 2 coordonnées des extremmitées)
>> - un rectangle (soit les 4 coordonnées des 4 coins, même si seulement 2
>> sont utiles)
>> J'ai beau me creuser la tête, je ne trouve pas de technique (algorithme
>> en fait) "pas trop tirée par les cheuveux" pour vérifier que le segment
>> croise le rectangle quand les deux extremmitées du segment sont en
>> dehors du rectangle.
>> Si quelqu'un a une idée ...
>> Merci d'avance
>> Sylvain[/color]

> Soient {xr1,yr1},{xr2,yr2} un côté du rectangle
> et {xs1,ys1},{xs2,ys2} le segment intercepteur.
> On exprime qu'il y a deux déterminants nuls et deux produits scalaires
> négatifs.[...]
Le test pour un côté se simplifie encore car il contient des carrés :
test[{xr1_,yr1_},{xr2_,yr2_},{xs1_,ys1_},{xs2_,ys2_}]:=
-((xs1*yr1-xs2*yr1-xr1*ys1+xs2*ys1+xr1*ys2-
xs1*ys2)*(-(xs1*yr2)+xs2*yr2+xr2*ys1-xs2*ys1-xr2*ys2+
xs1*ys2)) <= 0
&&
( xr2*yr1-xs1*yr1-xr1*yr2+xs1*yr2+
xr1*ys1-xr2*ys1)*(xr2*yr1-xs2*yr1-xr1*yr2+xs2*yr2+xr1*ys2-
xr2*ys2) <= 0;
--
0% de pub! Que du bonheur et des vrais adhérents !
Vous aussi inscrivez-vous sans plus tarder!!
Message posté à partir de http://www.gyptis.org, BBS actif depuis 1995.