Как определить, находится ли точка справа или слева от линии

Question

У меня есть набор очков. Я хочу разделить их на 2 разных набора. Для этого я выбираю две точки ( a и b ) и рисую воображаемую линию между ними. Теперь я хочу, чтобы все точки, которые остались от этой линии в одном наборе, и те, которые были справа от этой линии в другом наборе.

Как я могу определить для любой заданной точки z , находится ли она в левом или в правом наборе? Я пытался вычислить угол между a-z-b & ndash; углы меньше 180 с правой стороны, больше 180 с левой стороны - ndash; но из-за определения ArcCos рассчитанные углы всегда меньше 180 °. Существует ли формула для расчета углов больше 180 ° (или любая другая формула для выбора правой или левой стороны)?

Answer 1

Попробуйте этот код, который использует перекрестное произведение :

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 = точка 1 линии; b = точка 2; c = точка для проверки.

Если формула равна 0, точки коллинеарны.

Если линия горизонтальная, то возвращается значение true, если точка находится над линией.

Answer 2

Используйте знак определителя векторов (AB,AM), где M(X,Y) - точка запроса:

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

Это 0 на линии, +1 на одной стороне, -1 на другой стороне.

Answer 3

Вы смотрите на знак определителя

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

Он будет положительным для точек с одной стороны и отрицательным с другой (и нулем для точек на самой линии).

Answer 4

Вектор (y1 - y2, x2 - x1) перпендикулярен линии и всегда направлен вправо (или всегда направлен влево, если ваша плоскостная ориентация отличается от моей).

Затем можно вычислить скалярное произведение этого вектора и (x3 - x1, y3 - y1), чтобы определить, находится ли точка на той же стороне линии, что и перпендикулярный вектор (скалярное произведение> 0), или нет.

Answer 5

Я реализовал это в Java и запустил модульный тест (источник ниже). Ни одно из вышеперечисленных решений не работает. Этот код проходит модульный тест. Если кто-то обнаружит, что юнит-тест не прошел, пожалуйста, дайте мне знать.

Код: ПРИМЕЧАНИЕ: nearlyEqual(double,double) возвращает истину, если два числа очень близки.

/*
 * @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;
}

Вот модульный тест:

@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));
}

Answer 6

Сначала проверьте, есть ли у вас вертикальная линия:

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

Затем рассчитайте наклон: m = (y2-y1)/(x2-x1)

Затем создайте уравнение линии, используя форму наклона точки: y - y1 = m*(x-x1) + y1. Ради моего объяснения, упростите его до формы перехвата с уклоном (не обязательно в вашем алгоритме):

Теперь подключите (x3, y3) для x и y. Вот некоторый псевдокод, детализирующий, что должно произойти:

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

Answer 7

Используя уравнение для линии ab , получите x-координату на линии в той же y-координате, что и точка для сортировки.

• Если точка x> линии x, точка находится справа от линии.
• Если точка x <строка x, точка находится слева от линии. </li>
• Если точка х == линии х, точка находится на линии.

Answer 8

Вот версия, снова использующая логику кросс-продукта, написанную на 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)))))

Пример использования:

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

То есть точка (0, 10) находится слева от линии, определяемой (-3, -1) и (3, 1).

ПРИМЕЧАНИЕ. Эта реализация решает проблему, которую никто из остальных (пока) не делает! Порядок имеет значение при указании точек, определяющих линию. То есть, это в некотором смысле «направленная линия». Таким образом, в приведенном выше коде этот вызов также приводит к результату true:

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

Это из-за этого фрагмента кода:

(sort line)

Наконец, как и в случае других решений, основанных на нескольких продуктах, это решение возвращает логическое значение и не дает третьего результата для коллинеарности. Но это даст результат, который имеет смысл, например ::

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

Answer 9

@ АВБ ответ в рубине

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

Если det положительно, то выше, если отрицательно, ниже. Если 0, это на линии.

Answer 10

Предполагая, что точки (Ax, Ay) (Bx, By) и (Cx, Cy), вам необходимо вычислить:

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

Это будет равно нулю, если точка C находится на линии, образованной точками A и B, и будет иметь различный знак в зависимости от стороны. С какой стороны это зависит, зависит от ориентации ваших (x, y) координат, но вы можете вставить тестовые значения для A, B и C в эту формулу, чтобы определить, являются ли отрицательные значения слева или справа.