Как определить, находится ли точка в правой или левой части строки - программирование
Подтвердить что ты не робот

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 2

Попробуйте использовать этот код, который использует 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;
}

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

Код: ПРИМЕЧАНИЕ: 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;
}

Здесь unit test:

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

Ответ 6

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

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

Ответ 7

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

if (x2-x1) == 0
  if x3 < x2
     it on the left
  if x3 > x2
     it on the right
  else
     it 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 on the left
  else if y3 < m*x3 + b
    it on the right
  else
    it on the line
else if m < 0
  if y3 < m*x3 + b
    it on the left
  if y3 > m*x3+b
    it on the right
  else
    it on the line
else
  horizontal line; up to you what you do

Ответ 8

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

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

C находится внутри прямоугольника.

Спасибо:)

Ответ 9

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

(Вх - Ах) * (Су - Ау) - (By - Ay) * (Cx - Ax)

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

Ответ 10

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

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

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

Ответ 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

Ответ 12

Альтернативный способ получить представление о решениях, предлагаемых сетями, состоит в том, чтобы понять небольшие геометрические последствия.

Пусть pqr= [P, Q, R] - это точки, которые образуют плоскость, которая разделена на 2 стороны линией [P, R]. Мы должны выяснить, находятся ли две точки на плоскости pqr, A, B, на одной стороне.

Любая точка T на плоскости pqr может быть представлена двумя векторами: v= PQ и u= RQ, как:

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

Теперь о значениях геометрии:

  1. я + j = 1: T на линии pr
  2. я + j <1: T на кв.
  3. я + j> 1: T на Snq
  4. я + j = 0: T = Q
  5. я + j <0: T на кв. и выше Q.

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

В общем,

  • i + j - это мера того, как далеко T от Q или линии [P, R], и
  • знак i + j-1 подразумевает боковую Т-образность.

Другие значения геометрии i и j (не связанные с этим решением):

  • i, j - скаляры для T в новой системе координат, где v, u - новые оси, а Q - новое начало координат;
  • i, j можно рассматривать как тяговое усилие для P, R соответственно. Чем больше я, тем дальше T от R (больше тяга от P).

Значение i, j можно получить, решив уравнения:

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

Итак, нам даны 2 балла A, B на плоскости:

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

Если A, B находятся на одной стороне, это будет верно:

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

Обратите внимание, что это относится и к вопросу: находятся ли A, B на одной стороне плоскости [P, Q, R], в которой:

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

и i + j + k = 1 означает, что T находится на плоскости [P, Q, R], а знак i + j + k-1 означает его боковость. Из этого мы имеем:

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

и A, B находятся на одной стороне плоскости [P, Q, R], если

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

Ответ 13

Я хотел предложить решение, основанное на физике.

Представьте себе силу, приложенную вдоль линии, и вы измеряете момент силы вокруг точки. Если крутящий момент положительный (против часовой стрелки), то точка находится "слева" от линии, но если крутящий момент отрицательный, точка находится "справа" от линии.

Таким образом, если вектор силы равен промежутку двух точек, определяющих линию

fx = x_2 - x_1
fy = y_2 - y_1

вы проверяете сторону точки (px,py) на основе знака следующего теста

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