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

StackOverflow https://stackoverflow.com/questions/1560492

  •  21-09-2019
  •  | 
  •  

Question

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 tracer une ligne imaginaire entre eux. Maintenant, je veux avoir tous les points qui sont laissés de cette ligne dans un ensemble et ceux qui ont raison de cette ligne dans l'autre ensemble.

Comment puis-je dire à un moment donné z si elle est à gauche ou à droite fixés? J'ai essayé de calculer l'angle entre azb - angles inférieurs à 180 sont sur le côté droit, supérieur à 180 sur le côté gauche - mais à cause de la définition de ArcCos, les angles calculés sont toujours plus petits à 180 °. Y at-il une formule pour calculer des angles supérieurs à 180 ° (ou de toute autre formule de choisir le côté droit ou gauche)?

Était-ce utile?

La solution

Utilisez le signe du déterminant de (AB,AM) vecteurs, 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é.

Autres conseils

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 à zéro pour les points sur la ligne elle-même).

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

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

Je mis en place ce en Java et couru un test unitaire (source ci-dessous). Aucun des travaux de solutions ci-dessus. Ce code passe le test unitaire. Si quelqu'un trouve un test unitaire qui ne passe pas, s'il vous plaît laissez-moi savoir.

code: REMARQUE:. nearlyEqual(double,double) retourne vrai si les deux chiffres 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 les de la ligne ab , obtenir le coordonnée x sur la ligne à la même coordonnée y en tant que point à trier.

  • Si de point x> x de la ligne de, le point se trouve à droite de la ligne.
  • Si le point de x
  • Si le x de points == x de la ligne, 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, calculer 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 x et y. Voici quelques détails pseudocode ce qui devrait se produire: 

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 fait, je pense qu'il ya une solution qui est beaucoup plus facile et simple, pour tout polygone donné, permet de dire composé de quatre sommets (p1, p2, p3, p4), trouver les deux sommets extrêmes opposés dans le polygone , en d'autres mots, trouver par exemple le plus haut sommet gauche (disons p1) et le sommet opposé qui est situé au plus bas à droite (laisse dire). Par conséquent, compte tenu de votre point de test C (x, y), maintenant vous devez faire une double vérification entre C et p1 et C et p4:

si cx> p1x ET cy> P1Y ==> signifie que C est plus faible et à droite de p1 suivant si cx signifie que C est supérieure 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 - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

Ce sera égale à 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é. De quel côté cela est dépend de l'orientation de (x, y) les coordonnées, mais on peut brancher des valeurs de test pour A, B et C dans la formule suivante pour déterminer si les valeurs négatives sont à la gauche ou vers la droite.

@ réponse de AVB en rubis 

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

Si det est positif de son ci-dessus, si elle est négative son ci-dessous. Si 0, son sur la ligne.

Voici une version, en utilisant à nouveau la logique de produit croisé, écrit 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 revient à dire que le point (0, 10) est à la 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) fait! Questions d'ordre en donnant les points qui déterminent la ligne. À savoir, il 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 ce bout de code: 

(sort line)

Enfin, comme les autres solutions multiproduits, cette solution retourne un booléen, et ne donne pas un troisième résultat pour colinéarité. Mais il donnera un résultat qui est logique, par exemple:. 

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

Je voulais fournir une solution inspirée par la physique.

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

Donc, si le vecteur de force est égale à la durée des deux points définissant la ligne 

fx = x_2 - x_1
fy = y_2 - y_1

test pour le côté d'un point (px,py) basé sur le 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

Une autre façon de se faire une idée des solutions fournies par les fileyeurs est de comprendre un peu les implications de la géométrie.

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

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

T »= T-Q = i * v + j * u

Maintenant, les implications de la géométrie:

  1. i + j = 1: T sur la ligne de 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 T est la Q ou de la ligne [P, R] et
  • le signe i + j-1 implique la sideness T.

Les autres significations de la géométrie de i et j (non lié à 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 force de traction P, R , respectivement. Plus i , T est la plus loin R (plus grande traction dans 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

Alors nous donne 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 vaut également pour la question suivante: sont A, B dans le même côté du plan [P, Q, R] , dans laquelle:

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 sideness. De ce que nous avons:

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

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

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top