Comment savoir si un point est à droite ou à gauche d’une ligne

J’ai un ensemble de points. Je veux les séparer en 2 ensembles distincts. Pour ce faire, je choisis deux points ( a et b ) et trace une ligne imaginaire entre eux. Maintenant, je veux avoir tous les points qui restnt de cette ligne dans un ensemble et ceux qui sont directement de cette ligne dans l’autre ensemble.

Comment puis-je dire z pour un point donné, que ce soit à gauche ou à droite? J’ai essayé de calculer l’angle entre azb – les angles inférieurs à 180 sont du côté droit, supérieur à 180 du côté gauche – mais en raison de la définition d’ArcCos, les angles calculés sont toujours inférieurs à 180 °. Existe-t-il une formule pour calculer des angles supérieurs à 180 ° (ou toute autre formule pour choisir le côté droit ou le côté gauche)?

Utilisez le signe du déterminant des vecteurs (AB,AM) , où M(X,Y) est le point d’interrogation:

 position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax)) 

Il est 0 sur la ligne et +1 d’un côté, -1 de l’autre côté.

Essayez ce code qui utilise un produit croisé :

 public bool isLeft(Point a, Point b, Point c){ return ((bX - aX)*(cY - aY) - (bY - aY)*(cX - aX)) > 0; } 

a = sharepoint ligne 1; b = sharepoint ligne 2; c = point à vérifier.

Si la formule est égale à 0, les points sont colinéaires.

Si la ligne est horizontale, cela renvoie true si le point est au-dessus de la ligne.

Vous regardez le signe du déterminant de

 | x2-x1 x3-x1 | | y2-y1 y3-y1 | 

Il sera positif pour les points d’un côté et négatif pour les points d’un côté (et zéro pour les points sur la ligne elle-même).

Le vecteur (y1 - y2, x2 - x1) est perpendiculaire à la ligne et toujours orienté vers la droite (ou toujours orienté vers la gauche si l’orientation de votre plan est différente de la mienne).

Vous pouvez alors calculer le produit scalaire de ce vecteur et (x3 - x1, y3 - y1) pour déterminer si le point se trouve du même côté de la ligne que le vecteur perpendiculaire (produit scalaire> 0 ).

Je l’ai implémenté en Java et j’ai effectué un test unitaire (source ci-dessous). Aucune des solutions ci-dessus ne fonctionne. Ce code réussit le test unitaire. Si quelqu’un trouve un test unitaire qui ne réussit pas, faites-le moi savoir.

Code: NOTE: nearlyEqual(double,double) renvoie true si les deux nombres sont très proches.

 /* * @return integer code for which side of the line ab c is on. 1 means * left turn, -1 means right turn. Returns * 0 if all three are on a line */ public static int findSide( double ax, double ay, double bx, double by, double cx, double cy) { if (nearlyEqual(bx-ax,0)) { // vertical line if (cx < bx) { return by > ay ? 1 : -1; } if (cx > bx) { return by > ay ? -1 : 1; } return 0; } if (nearlyEqual(by-ay,0)) { // horizontal line if (cy < by) { return bx > ax ? -1 : 1; } if (cy > by) { return bx > ax ? 1 : -1; } return 0; } double slope = (by - ay) / (bx - ax); double yIntercept = ay - ax * slope; double cSolution = (slope*cx) + yIntercept; if (slope != 0) { if (cy > cSolution) { return bx > ax ? 1 : -1; } if (cy < cSolution) { return bx > ax ? -1 : 1; } return 0; } return 0; } 

Voici le test unitaire:

 @Test public void testFindSide() { assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1)); assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14)); assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6)); assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6)); assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1)); assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1)); assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14)); assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1)); assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20)); assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20)); assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10)); assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10)); assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0)); assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0)); assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0)); assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0)); assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0)); assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0)); assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9)); assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9)); assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2)); assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2)); assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0)); assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0)); assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2)); assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2)); assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2)); assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2)); assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0)); assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0)); assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2)); assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0)); assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2)); } 

En utilisant l’ équation de la ligne ab , obtenez la coordonnée x sur la ligne à la même coordonnée y que le point à sortinger.

  • Si la ligne x> du point est x, le point est à droite de la ligne.
  • Si le point x
  • Si le point x == la ligne x, le point est sur la ligne.

Vérifiez d’abord si vous avez une ligne verticale:

 if (x2-x1) == 0 if x3 < x2 it's on the left if x3 > x2 it's on the right else it's on the line 

Ensuite, calculez la pente: m = (y2-y1)/(x2-x1)

Ensuite, créez une équation de la ligne en utilisant la forme de pente de point: y - y1 = m*(x-x1) + y1 . Pour simplifier mon explication, simplifiez-la en forme de pente-interception (pas nécessaire dans votre algorithme): y = mx+b .

Maintenant, twigz (x3, y3) pour x et y . Voici un pseudo-code détaillant ce qui doit arriver:

 if m > 0 if y3 > m*x3 + b it's on the left else if y3 < m*x3 + b it's on the right else it's on the line else if m < 0 if y3 < m*x3 + b it's on the left if y3 > m*x3+b it's on the right else it's on the line else horizontal line; up to you what you do 

en gros, je pense qu’il existe une solution beaucoup plus simple et directe, pour un polygone donné, disons composée de quatre sumts (p1, p2, p3, p4), trouve les deux sumts opposés dans le polygone, dans un autre mots, trouvez par exemple le sumt le plus en haut à gauche (disons p1) et le sumt opposé qui est situé au plus en bas à droite (disons). Donc, étant donné votre sharepoint test C (x, y), vous devez maintenant faire une double vérification entre C et p1 et C et p4:

si cx> p1x AND cy> p1y ==> signifie que C est inférieur et à droite de p1 suivant si cx signifie que C est supérieur et à gauche de p4

conclusion, C est à l’intérieur du rectangle.

Merci 🙂

En supposant que les points sont (Ax, Ay) (Bx, By) et (Cx, Cy), vous devez calculer:

(Bx – Axe) * (Cy – Ay) – (By – Ay) * (Cx – Ax)

Cela sera égal à zéro si le point C est sur la ligne formée par les points A et B et aura un signe différent en fonction du côté. Le côté dépend de l’orientation de vos coordonnées (x, y), mais vous pouvez insérer des valeurs de test pour A, B et C dans cette formule pour déterminer si les valeurs négatives sont à gauche ou à droite.

@ La réponse d’AVB en ruby

 det = Masortingx[ [(x2 - x1), (x3 - x1)], [(y2 - y1), (y3 - y1)] ].determinant 

Si det est positif, c’est ci-dessus, si négatif c’est ci-dessous. Si 0, c’est sur la ligne.

Voici une version, encore une fois en utilisant la logique de produits croisés, écrite en Clojure.

 (defn is-left? [line point] (let [[[x1 y1] [x2 y2]] (sort line) [x-pt y-pt] point] (> (* (- x2 x1) (- y-pt y1)) (* (- y2 y1) (- x-pt x1))))) 

Exemple d’utilisation:

 (is-left? [[-3 -1] [3 1]] [0 10]) true 

Ce qui veut dire que le point (0, 10) est à gauche de la ligne déterminée par (-3, -1) et (3, 1).

NOTE: Cette implémentation résout un problème qu’aucun des autres (jusqu’à présent) ne fait! L’ordre compte lorsque vous donnez les points qui déterminent la ligne. Ie, c’est une “ligne dirigée”, dans un certain sens. Donc, avec le code ci-dessus, cette invocation produit également le résultat de true :

 (is-left? [[3 1] [-3 -1]] [0 10]) true 

C’est à cause de cet extrait de code:

 (sort line) 

Enfin, comme pour les autres solutions basées sur des produits croisés, cette solution renvoie un booléen et ne donne pas un troisième résultat pour la colinéarité. Mais cela donnera un résultat logique, par exemple:

 (is-left? [[1 1] [3 1]] [10 1]) false