Comment puis-je vérifier si un point est au-dessous d'une ligne ou pas ?
Comment puis-je vérifier si un point est au-dessous d'une ligne ou pas ?
J'ai les données suivantes:
Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...
J'ai besoin d'écrire un petit algorithme en python de détecter les points d'un côté et de l'autre côté de la ligne.
grâce
Veuillez noter dans vos devoirs avec l' [devoirs] balise.
OriginalL'auteur aneuryzm | 2010-10-01
Vous devez vous connecter pour publier un commentaire.
Vous pouvez essayer d'utiliser un produit croisé -- http://en.wikipedia.org/wiki/Cross_product.
Vous auriez besoin de calibrer ce que chaque côté est. Si vous voulez qu'il soit "en dessous" ou "au-dessus", vous devez vous assurer que les points sur la ligne sont triés à l'horizontale.
Je n'ai pas testé cette.
Modifier j'ai d'abord mis au point un produit de formule. 😮
Heureusement, j'ai trouvé Calcul Vectoriel 2D Croix du Produit.
Bon point! Si je ne sais pas comment vous pouvez trouver la meilleure valeur epsilon.
cos(π/2) doit évaluer à 0, mais
math.cos(math.pi/2)
sur mon système donne6.1230317691118863e-017
, donc je dirais un epsilon dans1e-15
ou1e-16
gamme serait à peu près droit. (Mettre dans votre propre constanteEPS
de sorte que vous pouvez facilement régler en ajustant seulement dans un seul endroit au lieu de partout, vous ne floating point de comparaison.)Ou si vous utilisez Python 3.x, vous pouvez utiliser l'unicode ε comme votre nom de variable pour epsilon.
OriginalL'auteur Edmund
Vous pouvez essayer d'utiliser un produit croisé, mais le truc est de savoir comment choisir le point de former un vecteur, ici j'ai choisi le point le plus proche à partir de points, supposons que j'ai eu pointA(vous pouvez assez les points de boucle pour calculer la distance entre le point de boucle à la Ligne):
OriginalL'auteur blacksunshine
Permet de dire que vous avez donné 2 points A, B et vous voulez savoir où halfplane un troisième point C se trouve. Les termes "inférieur" et "au-dessus" que les critères sont très vague, donc vous avez besoin d'un point de référence, par exemple l'origine. Juste être sûr de ce point de référence n'est pas colinéaire avec A et B.
Ce que vous avez maintenant est un triangle (A, B, C). En utilisant le déterminant, vous pouvez calculer la signature de la zone (voir ici, ou ici). La seule chose intéressante ici est de rappeler les signes.
Prochaine étape: pour un point donné D calculer la signature de l'aire du triangle (A, B, D). Si le résultat a le même signe que la région du triangle de référence -> C et D sont sur le même côté de (A, B). Si le signe diffère -> C et D se trouvent sur les côtés opposés de la ligne. Si la zone (A, B, D) est 0, alors A, B et D sont colinéaires. Remarque: utiliser le Python builtin
cmp
de comparer le triangle domaines.OriginalL'auteur atomocopter