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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Где = линия точка 1; b = строка 2; c = точка для проверки.

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

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

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. Ради моего объяснения, упростите его до формы перехвата (не обязательно в вашем алгоритме): y = mx+b.

Теперь подключите (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

в принципе, я думаю, что есть решение, которое гораздо проще и прямо вперед, для любого заданного многоугольника, позволяет сказать, что состоит из четырех вершин (p1, p2, p3 , p4), найдите две крайние противоположные вершины в многоугольнике, другими словами, найдите, например, самую верхнюю левую вершину (скажем, p1) и противоположную вершину, расположенную в самом нижнем правом углу (скажем). Следовательно, учитывая вашу контрольную точку C (x, y), теперь вы должны выполнить двойную проверку между C и p1 и C и p4:

, если cx> p1x AND cy> p1y ==> означает, что C ниже и справа от p1 следующего если се < p2x и Сайте < P2Y ==> означает, что с верхней и слева от p4

заключения C внутри прямоугольника.

Спасибо :)

Answer 8

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

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

/* 
* @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 9

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

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

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

Answer 10

@ ответ AVB в рубин

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

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

Answer 11

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

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

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

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

(sort line) 

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

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