Étant donné 2 points et une ligne, est-ce que les points coupent la ligne? : algorithme/pseudo-code

Question

Un collègue m'a donné ce problème pour essayer mes connaissances:

Considérons deux points, 1 et 2, ayant des coordonnées (x1, y1) et (x2, y2), respectivement. Dans le même plan que ces deux points est une ligne verticale dont le haut et le bas sont représentés par (xTop, yTop) et (xBot, yBot), respectivement. Les deux points peuvent être sur les côtés opposés du mur, du même côté du mur, ou directement au-dessus/en dessous du mur. Pour la simplicité, aucun des points ne peut être directement sur le mur. Une ligne est tracée du point 1 au point 2; Si une intersection sur le mur (la ligne verticale) se produit, elle se produira au point (xInt, yIint). Étant donné deux points et un mur, écrivez un algorithme pour déterminer si les deux points peuvent se voir les uns les autres. Cela ne peut se produire que si la ligne tracée du point 1 au point 2 ne touche pas le mur.

J'ai correctement identifié que si les valeurs x des deux points sont inférieures/supérieures à celles des murs, ils peuvent se voir les uns les autres. La même chose vaut pour les valeurs y. Je crois qu'il y a beaucoup de géométrie impliquée dans ce problème. Mais, je suis un vieil homme, je reviens juste à la programmation pour m'amuser et c'est vraiment ce que j'essaie de comprendre. Toute aide serait grandement appréciée. Je vous remercie.

-Jon N.

Answer 1

l'équation d'une ligne est y = mx + b, où m est la pente, et b est l'ordonnée à l'origine.

Pour déterminer si une ligne entre deux points croise une autre ligne (dans votre cas verticale), déterminez d'abord la pente de la ligne qui relie les deux points.

m = pente = (montée/descente) = (y2 - y1)/(x2 - x1)

suivant, déterminer l'ordonnée à l'origine.

étant donné que (x1, y1) est sur la ligne, et y = mx + b est l'équation pour une ligne, alors y1 = mx1 + b. Puisque nous connaissons y1, x1 et m, nous pouvons résoudre pour b.

b = ordonnée à l'origine = y1 - MX1 = y1 - ((Y2 - Y1)/(x2 - x1)) x1

Maintenant, afin de déterminer si la ligne intercepte la paroi, il suffit de mettre en x -coordonner pour le mur dans l'équation de la ligne reliant les deux points, et si le résultat est en dehors de la plage des valeurs y pour le mur, alors il n'intercepte pas le mur (les deux points peuvent se voir).

Y @ mur = mxbot + b

Si YBot < = mur Y @ < = YTop, le mur est entre les deux points.

Espérons que ce soit utile!

Answer 2

Comme beaucoup d'algorithmes géométriques, il y a un tas de cas spéciaux. Faisons une table. L signifie à gauche du mur, A signifie ci-dessus, B signifie ci-dessous, et R signifie à droite. Y signifie oui, ? signifie peut-être, n signifie non (existence d'une intersection).

L A B R 
L n n n ? 
A n n Y n 
B n Y n n 
R ? n n n 

Quand un point est à gauche et l'autre à droite, on calcule l'intersection avec la ligne contenant le mur et vérifier si elle est dans le mur.

code:

def intersects(x1, y1, x2, y2, wallx, wallymin, wallymax): 
    if (x1 < wallx and x2 > wallx) or (x1 > wallx and x2 < wallx): 
     iy = ((x2 - wallx) * y1 + (wallx - x1) * y2)/(x2 - x1) 
     return iy >= wallymin and iy <= wallymax 
    elif x1 == wallx and x2 == wallx: 
     return (y1 < wallymin and y2 > wallymax) or (y1 > wallymax and y2 > wallymin) 
    else: 
     return False