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

Question

J'ai un ensemble de points. Je veux les séparer en 2 ensembles distincts. Pour ce faire, je choisis deux points ( a y b ) et tracez 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 que pour un point donné z si c'est dans l'ensemble gauche ou droit ? J'ai essayé de calculer l'angle entre a-z-b - les angles inférieurs à 180 sont à droite, les supérieurs à 180 à gauche - mais en raison de la définition d'ArcCos, les angles calculés sont toujours inférieurs à 180°. Existe-t-il une formule permettant de calculer les angles supérieurs à 180° (ou toute autre formule permettant de choisir le côté droit ou gauche) ?

Answer 1

Essayez ce code qui fait usage d'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;
}

Où a \= ligne point 1 ; b \= point de la 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.

Answer 2

Utiliser 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é.

Answer 3

Vous regardez le signe du déterminant de

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

Elle sera positive pour les points situés d'un côté, et négative de l'autre (et nulle pour les points situés sur la ligne elle-même).

Answer 4

Le vecteur (y1 - y2, x2 - x1) est perpendiculaire à la ligne, et pointe toujours vers la droite (ou 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 ) ou non.

Answer 5

J'ai implémenté ceci en java et j'ai fait 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 passe pas, merci de me le faire savoir.

Code : NOTE : 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));
}