Discussion :

[Gregory.M]

Bonjour,

Dans tableau j'ai une ligne tracée dont j'ai connaissance des deux points d'origine.

Dans ce tableau j'ai aussi carré dont j'ai connaissance des coordonnées du coin gauche. Je peux facilement calculer la position des quatres coins puisque que je connais la taille des cotés du carré.

Dans l'exemple en piece jointe, ce carré est traversé par la ligne. J'aurais aimé trouver une formule me permettant de déterminer si mon carré est coupé par cette ligne ou non.

Auriez vous une piste?

[pseudocode]

Bonsoir,

L'algorithme de clipping de Cohen–Sutherland semble bien s'appliquer à ton problème.

[Gregory.M]

Bonsoir,

L'algorithme de clipping de Cohen–Sutherland semble bien s'appliquer à ton problème.

Merci pour ta réponse, je regarde ça

[Invité]

Bonjour,
La solution qui me parait à première vue la plus simple est de calculer la distance du centre du carré à la droite.
Si cette distance est inférieure au demi-côté, la droite coupe le carré. Si elle est supérieure à la demi-diagonale la droite ne coupe pas le carré.
Sinon, il faut prendre ...

Encore plus simple, si les 4 angles sont du même côté de la droite, elle ne coupe pas le carré.
Le signe est celui du produit vectoriel
(xp - xa) * (yb - ya ) - (xb - xa) * (yp - ya ) (sauf faute de frappe)

[plegat]

L'algorithme de clipping de Cohen–Sutherland semble bien s'appliquer à ton problème.

J'ai un peu de mal à voir l'applicabilité... à moins de vérifier pour les points de la droite en clippant sur le carré, mais ça risque de prendre du cycle...

Encore plus simple, si les 4 angles sont du même côté de la droite, elle ne coupe pas le carré.
Le signe est celui du produit vectoriel
(xp - xa) * (yp - ya ) - (xb - xa) * (yb - ya ) (sauf faute de frappe)

(xp - xa) * (yb - ya ) - (xb - xa) * (yp - ya )

dans le même style, faire ce calcul pour les 4 points du carré, prendre le min et le max, faire le produit des deux (ou au moins garder le signe du produit si on a peur que la valeur soit trop grande)
Si c'est négatif, ça coupe.
Si c'est égal à 0, ça passe par un des points (donc à décider si ça coupe ou pas...)
Si c'est positif, ça passe au loin.

Pour l'explication technique, le produit vectoriel donné par Pierre intervient dans le calcul de la distance d'un point à une droite (voir wikipedia par exemple pour les détails), distance qui est signée si on ne prend pas le résultat en valeur absolue et qui permet donc de savoir si le point est d'un côté ou de l'autre de la droite.
Prendre le min et le max sur les quatre points consiste à garder les distances mini et maxi, et donc si le produit est négatif, ça signifie qu'un des points est d'un côté de la droite, et l'autre est de l'autre côté... et que donc le carré est à cheval sur la droite.

[pseudocode]

J'ai un peu de mal à voir l'applicabilité... à moins de vérifier pour les points de la droite en clippant sur le carré, mais ça risque de prendre du cycle...

C'est vrai que l'algo calcule les points d'intersection ligne/carré, ce qui n'est pas demandé ici.

Si on veut juste savoir s'il y a intersection on peut simplifier les choses. Une fois qu'on a passé le test des outcodes, il suffit d'appliquer la technique de Pierre Dolez.

[Gregory.M]

Bonjour,

Encore plus simple, si les 4 angles sont du même côté de la droite, elle ne coupe pas le carré.

Oula je ne comprends pas trop. Ca veut dire quoi "les 4 angles sont du meme coté de la droite"?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Le signe est celui du produit vectoriel
(xp - xa) * (yp - ya ) - (xb - xa) * (yb - ya )    (sauf faute de frappe)

Je ne comprends pas à quoi correspondent tes données.

[pseudocode]

Oula je ne comprends pas trop. Ca veut dire quoi "les 4 angles sont du meme coté de la droite"?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Le signe est celui du produit vectoriel
(xp - xa) * (yp - ya ) - (xb - xa) * (yb - ya )    (sauf faute de frappe)

Je ne comprends pas à quoi correspondent tes données.

(xa,ya) et (xb,yb) sont les points de la droite.
(xp,yp) sont les coordonnées d'un des 4 coins du carré.

Si le signe du produit vectoriel est le meme pour les 4 coins, alors tous les points sont du meme coté de la droite. Et donc il n'y a pas d'intersection.

[Invité]

Oui, merci plegat, mais là j'ai vraiment honte.
(j'ai corrigé ma formule)
(xp - xa) * (yb - ya ) - (xb - xa) * (yp - ya )
Donc (xp, yp) est le pont testé, chacun des sommets du carré,
(xa,ya) et (xb,yb) sont les extrémités de la droite.
Donc on le fait pour les 4 sommets du carré, il suffit d'en trouver 2 qui donnent un signe opposé et on est sûr que la droite coupe le carré.
Il ne devrait pas y avoir de débordement de flottant, puisque ou fait de soustractions.
La valeur == 0 signifie que ce point est sur la droite. Dans la pratique, il vaut mieux comparer le produit vectoriel à une valeur petite.

[Gregory.M]

Merci pour les explications

[Gregory.M]

Je ne sais pas si j'ai fait une érreur dans la formule mais je n'ai pas de résultat opposé alors qu'il y a bien intersection entre la ligne et le carré.

Les deux premières lignes sont les coordonnées de ma droite.
La troisieme est la position du coin supérieur gauche de mon carré.
Puis les lignes suivantes sont les résultats de la formule pour chaque coin du carré.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
215.08161877691535, 368.4745234591661
189.4453620006758, 728.4627526968143
Carré: 190.69428162836516, 586.6024367966953
Sup. gauche-3187.171119541871
Inf. gauche-13986.817996671318
Sup. droit:-3187.171119541871
Inf. droit':-14755.905699958505
---------------------------------

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(xp - xa) * (yb - ya ) - (xb - xa) * (yp - ya )