Comment savoir si un point se trouve à droite ou à gauche d'une ligne

130

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 sont à gauche de cette ligne dans un ensemble et ceux qui sont à droite de cette ligne dans l'autre ensemble.

Comment puis-je savoir pour un point z donné s'il se trouve dans l'ensemble de gauche ou de droite? J'ai essayé de calculer l'angle entre azb - les angles inférieurs à 180 sont sur le côté droit, supérieurs à 180 sur le 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 les angles supérieurs à 180 ° (ou toute autre formule pour choisir le côté droit ou gauche)?

Aaginor
la source
Comment la droite ou la gauche sont-elles définies? A) en termes de recherche de P1 à P2 ou B) à gauche ou à droite de la ligne dans le plan.
phkahler
2
Pour clarifier, à la deuxième partie de votre question, vous pouvez utiliser atan2 () au lieu de acos () pour calculer l'angle correct. Cependant, utiliser un produit croisé est la meilleure solution à cela, comme l'a souligné Eric Bainville.
dionyziz le
La plupart des solutions ci-dessous ne fonctionnent pas car elles donnent des réponses opposées si vous échangez les points a et b (les points que nous utilisons pour définir notre ligne). Je donne une solution dans Clojure qui trie les deux points lexicographiquement avant de les comparer au troisième point.
Purplejacket

Réponses:

202

Utilisez le signe du déterminant des vecteurs (AB,AM), où M(X,Y)est le point de requête:

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

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

Eric Bainville
la source
10
+1 gentil, avec une chose à savoir: l'erreur d'arrondi peut être un problème lorsque le point est très proche de la ligne. Ce n'est pas un problème pour la plupart des utilisations, mais cela mord les gens de temps en temps.
Stephen Canon
16
Si vous vous trouvez dans une situation où une erreur d'arrondi sur ce test vous pose des problèmes, vous voudrez consulter les «Prédicats robustes rapides pour la géométrie informatique» de Jon Shewchuk.
Stephen Canon
14
Pour clarifier, c'est le même que la composante Z du produit croisé entre la ligne (ba) et le vecteur au point de a (ma). Dans votre classe vectorielle préférée: position = sign ((ba) .cross (ma) [2])
larsmoa
3
échanger A et B ne garderait-il pas la même ligne, mais changerait le signe de positions?
Jayen
6
Oui. A, B définit l'orientation, comme dans "à votre gauche lorsque vous vous tenez à A et que vous regardez B".
Eric Bainville
224

Essayez ce code qui utilise un produit croisé :

public bool isLeft(Point a, Point b, Point c){
     return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0;
}

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

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

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

jethro
la source
6
Si la ligne est verticale alors?
Tofeeq Ahmad le
9
voulez-vous dire produit scalaire?
Baiyan Huang
13
@lzprgmr: Non, c'est un produit croisé, de manière équivalente le déterminant d'une matrice 2D. Considérons la matrice 2D définie par les lignes (a, b) et (c, d). Le déterminant est ad - bc. Le formulaire ci-dessus transforme une ligne représentée par 2 points en un vecteur unique, (a, b), puis définit un autre vecteur en utilisant PointA et PointC pour obtenir (c, d): (a, b) = (PointB.x - PointA.x, PointB.y - PointA.y) (c, d) = (PointC.x - PointA.x, PointC.y - PointA.y) Le déterminant est donc exactement comme il est indiqué dans le post.
AndyG
6
Je pense que la confusion quant à savoir s'il s'agit d'un produit croisé ou d'un produit scalaire est due au fait qu'il est en deux dimensions. Il est le produit croisé, en deux dimensions: mathworld.wolfram.com/CrossProduct.html
brianmearns
4
Pour ce que ça vaut, cela peut être légèrement simplifié return (b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x);, mais le compilateur optimise probablement cela de toute façon.
Nicu Stiurca
44

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 de l'autre (et nul pour les points sur la ligne elle-même).

AVB
la source
1
En développant cette réponse, au cas où les gens ne savent pas à quoi ressemble le produit croisé. La prochaine étape visuelle est ((x2-x1) * (y3-y1)) - ((y2 - y1) * (x3-x1))
Franky Rivera
10

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

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

Victor Nicollet
la source
5

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 à trier.

  • Si le point x> la ligne x, le point est à droite de la ligne.
  • Si le point x <la ligne x, le point est à gauche de la ligne.
  • Si le point x == la ligne x, le point est sur la ligne.
mbeckish
la source
C'est faux, car comme vous pouvez le voir d'après le commentaire d'Aaginor sur la première réponse, nous ne voulons pas savoir si le point est à gauche ou à droite de la ligne DIRECTED AB, c'est-à-dire si vous vous tenez sur A et que vous regardez vers B est-il à votre gauche ou à votre droite?
dionyziz le
1
@dionyziz - Hein? Ma réponse n'attribue pas de «direction» à la ligne passant par AB. Ma réponse suppose que "gauche" est la direction -x du système corrdinate. La réponse acceptée a choisi de définir un vecteur AB et de définir la gauche en utilisant le produit croisé. La question initiale ne précise pas ce que l'on entend par «gauche».
mbeckish le
3
REMARQUE: Si vous utilisez cette approche (plutôt que celle du produit croisé qui a été approuvée comme réponse), soyez conscient d'un piège lorsque la ligne s'approche de l'horizontale. Les erreurs mathématiques augmentent et atteignent l'infini si elles sont exactement horizontales. La solution consiste à utiliser l’axe qui a le plus grand delta entre les deux points. (Ou peut-être un delta plus petit ... c'est hors de ma tête.)
ToolmakerSteve
c'est totalement ce que je cherchais. Je ne veux pas savoir si A est au-dessus ou en dessous de B. Je veux juste savoir s'il est à gauche (direction x négative) de la ligne!
Jayen
5

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éer une équation de la droite en utilisant la forme de la pente du point: y - y1 = m*(x-x1) + y1. Par souci de mon explication, simplifier la forme pente à l' origine (pas nécessaire dans votre algorithme): y = mx+b.

Maintenant, branchez (x3, y3)pour xet y. Voici un pseudocode détaillant ce qui devrait se passer:

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
maksim
la source
3
Échec: calcul de la pente non valide pour les lignes verticales. Des trucs if / else sans fin. Je ne sais pas si c'est ce que l'OP entendait par gauche / droite - si tel était le cas, le regarder tourné de 90 degrés couperait ce code de moitié puisque "au-dessus" serait à droite ou à gauche.
phkahler
1
Cette réponse pose plusieurs problèmes. Les lignes verticales provoquent une division par zéro. Pire, il échoue car il ne se soucie pas de savoir si la pente de la droite est positive ou négative.
2
@phkahler, a corrigé le problème de la ligne verticale. Ce n'est certainement pas un échec pour avoir oublié un cas de test, mais merci pour les aimables paroles. «Infini si / sinon» est pour expliquer la théorie mathématique; rien dans la question d'OP ne mentionne la programmation. @woodchips, a corrigé le problème de la ligne verticale. La pente est la variable m; Je vérifie quand c'est positif ou négatif.
maksim
5

J'ai implémenté cela en java et exécuté un test unitaire (source ci-dessous). Aucune des solutions ci-dessus ne fonctionne. Ce code passe le test unitaire. Si quelqu'un trouve un test unitaire qui ne réussit pas, veuillez me le faire savoir.

Code: REMARQUE: nearlyEqual(double,double)renvoie vrai 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));
}
Al Globus
la source
2

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

(Bx - Axe) * (Cy - Ay) - (Par - Ay) * (Cx - Axe)

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 selon le côté. De quel côté il s'agit 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.

user2154342
la source
2

Je souhaitais proposer une solution inspirée de la physique.

Imaginez une force appliquée le long de la ligne et vous mesurez le couple de la force autour du point. Si le couple est positif (sens antihoraire), le point est à la «gauche» de la ligne, mais si le couple est négatif, le point est la «droite» de la ligne.

Donc si le vecteur de force est égal à l'étendue des deux points définissant la ligne

fx = x_2 - x_1
fy = y_2 - y_1

vous testez le côté d'un point en (px,py)fonction du signe du test suivant

var torque = fx*(py-y_1)-fy*(px-x_1)
if  torque>0  then
     "point on left side"
else if torque <0 then
     "point on right side"  
else
     "point on line"
end if
John Alexiou
la source
1

en gros, je pense qu'il existe une solution qui est beaucoup plus simple et directe, pour tout polygone donné, disons se composer de quatre sommets (p1, p2, p3, p4), trouver les deux sommets extrêmes opposés dans le polygone, dans un autre mots, trouvez par exemple le sommet le plus en haut à gauche (disons p1) et le sommet opposé qui est situé au plus en bas à droite (disons). Par conséquent, étant donné votre point de 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 <p2x AND cy <p2y ==> signifie que C est supérieur et à gauche de p4

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

Merci :)

Mohamed
la source
1
(1) Répond à une question différente de celle posée? Sonne comme un test de "boîte englobante", lorsqu'un rectangle est aligné avec les deux axes. (2) Plus en détail: fait des hypothèses sur les relations possibles entre 4 points. Par exemple, prenez un rectangle et faites-le pivoter de 45 degrés pour obtenir un losange. Il n'y a pas de "point en haut à gauche" dans ce diamant. Le point le plus à gauche n'est ni le plus haut ni le plus bas. Et bien sûr, 4 points peuvent former des formes encore plus étranges. Par exemple, 3 points peuvent être éloignés dans une direction et le 4e point dans une autre direction. Continue d'essayer!
ToolmakerSteve
1

@ Réponse d'AVB en rubis

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

Si detest positif, c'est au-dessus, si négatif, c'est en dessous. Si 0, c'est sur la ligne.

boulder_ruby
la source
1

Voici une version, toujours en utilisant la logique cross product, é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

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

REMARQUE: cette implémentation résout un problème qu'aucun des autres (jusqu'à présent) ne fait! L'ordre est important lorsque l'on attribue les points qui déterminent la ligne. C'est-à-dire que c'est une «ligne dirigée», dans un certain sens. Donc, avec le code ci-dessus, cet appel 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 de troisième résultat pour la colinéarité. Mais cela donnera un résultat qui a du sens, par exemple:

(is-left? [[1 1] [3 1]] [10 1])
false
Purplejacket
la source
0

Une autre façon de se faire une idée des solutions fournies par les filets est de comprendre quelques implications géométriques.

Soit pqr = [P, Q, R] des points qui forment un plan divisé en 2 côtés par la ligne [P, R] . Nous devons savoir si deux points du plan pqr , A, B, sont du même côté.

Tout point T sur le plan pqr peut être représenté avec 2 vecteurs: v = PQ et u = RQ, comme:

T '= TQ = i * v + j * u

Maintenant, les implications géométriques:

  1. i + j = 1: T sur la ligne pr
  2. i + j <1: T sur Sq
  3. i + j> 1: T sur Snq
  4. i + j = 0: T = Q
  5. i + j <0: T sur Sq et au-delà Q.

i+j: <0 0 <1 =1 >1 ---------Q------[PR]--------- <== this is PQR plane ^ pr line

En général,

  • i + j est une mesure de la distance entre T de Q ou de la ligne [P, R] , et
  • le signe de i + j-1 implique la sidération de T.

Les autres significations géométriques de i et j (non liées à cette solution) sont:

  • i , j sont les scalaires pour T dans un nouveau système de coordonnées où v, u sont les nouveaux axes et Q est la nouvelle origine;
  • i , j peut être considéré comme une force de traction pour P, R , respectivement. Plus i est grand , plus T est éloigné de R (plus grande traction de P ).

La valeur de i, j peut être obtenue en résolvant les équations:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

On nous donne donc 2 points, A, B sur le plan:

A = a1 * v + a2 * u B = b1 * v + b2 * u

Si A, B sont du même côté, ce sera vrai:

sign(a1+a2-1) = sign(b1+b2-1)

Notez que cela s'applique également à la question: A, B sont-ils du même côté du plan [P, Q, R] , dans lequel:

T = i * P + j * Q + k * R

et i + j + k = 1 implique que T est sur le plan [P, Q, R] et le signe de i + j + k-1 implique son côté. De cela, nous avons:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

et A, B sont du même côté du plan [P, Q, R] si

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)

s'exécute
la source