Как определить, находится ли точка справа или слева от линии
https://stackoverflow.com/questions/1560492
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть набор баллов.Я хочу разделить их на 2 отдельных набора.Для этого я выбираю две точки(а и б) и проведите между ними воображаемую линию.Теперь я хочу, чтобы все точки, находящиеся слева от этой линии, были в одном наборе, а те, которые находятся справа от этой линии, в другом наборе.
Как я могу сказать для любой заданной точки я находится ли он в левом или правом наборе?Я попытался вычислить угол между а-я-б – углы меньше 180 находятся справа, больше 180 – слева – но из-за определения ArcCos рассчитанные углы всегда меньше 180°.Существует ли формула для расчета углов, превышающих 180° (или любая другая формула для выбора правой или левой стороны)?
Решение
Используйте знак определителя векторов (AB,AM), где M(X,Y) это точка запроса:
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
Это 0 на линии, и +1 на одной стороне, -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;
}
Где а = точка линии 1; б = точка линии 2; с = точка для проверки.
Если формула равна 0, точки лежат на одной прямой.
Если линия горизонтальна, это возвращает true, если точка находится над линией.
Посмотрите на знак определителя
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
Оно будет положительным для точек с одной стороны и отрицательным с другой (и нулевым для точек на самой линии).
Вектор (y1 - y2, x2 - x1) перпендикулярен линии и всегда указывает вправо (или всегда указывает влево, если ориентация вашей плоскости отличается от моей).
Затем вы можете вычислить скалярное произведение этого вектора и (x3 - x1, y3 - y1) чтобы определить, лежит ли точка на той же стороне линии, что и перпендикулярный вектор (скалярное произведение > 0) или нет.
Я реализовал это в 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));
}
Используя уравнение линии аб, получите координату X на линии с той же координатой Y, что и точка, подлежащая сортировке.
- Если x точки > x линии, точка находится справа от линии.
- Если X <Line's x x, точка слева от линии.
- Если x точки == x линии, точка находится на прямой.
Сначала проверьте, есть ли у вас вертикальная линия:
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
в принципе, я думаю, что есть решение, которое намного проще и понятнее: для любого заданного многоугольника, скажем, состоящего из четырех вершин (p1, p2, p3, p4), найдите две крайние противоположные вершины в многоугольнике, в другом Другими словами, найдите, например, самую верхнюю левую вершину (скажем, p1) и противоположную вершину, которая расположена максимально внизу справа (скажем, ).Следовательно, учитывая вашу тестовую точку C(x,y), теперь вам нужно сделать двойную проверку между C и p1 и C и p4:
Если cx> p1x и cy> p1y ==> означает, что C ниже и справа от P1 затем, если cx <p2x и cy <p2y ==> означает, что C является верхним и слева от P4
Вывод: C находится внутри прямоугольника.
Спасибо :)
Предполагая, что точки равны (Ax,Ay) (Bx,By) и (Cx,Cy), вам необходимо вычислить:
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
Оно будет равно нулю, если точка С находится на прямой, образованной точками А и В, и будет иметь разный знак в зависимости от стороны.Какая это сторона, зависит от ориентации ваших координат (x,y), но вы можете подставить в эту формулу тестовые значения для A, B и C, чтобы определить, находятся ли отрицательные значения слева или справа.
Ответ @AVB в рубине
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
Если det положительное значение — вверху, отрицательное — внизу.Если 0, то это на линии.
Вот версия, снова использующая логику перекрестного произведения, написанная на 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
Я хотел предложить решение, вдохновленное физикой.
Представьте себе силу, приложенную вдоль линии, и вы измеряете крутящий момент силы относительно этой точки.Если крутящий момент положительный (против часовой стрелки), то точка находится «слева» от линии, но если крутящий момент отрицательный, точка находится «справа» от линии.
Итак, если вектор силы равен пролету двух точек, определяющих линию
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
Альтернативный способ получить представление о решениях, предоставляемых сетками, — это понять некоторые последствия геометрии.
Позволять пкр=[P,Q,R] — точки, образующие плоскость, разделенную линией на 2 стороны. [П, Р].Нам предстоит выяснить, совпадают ли две точки пкр плоскости A,B находятся на одной стороне.
Любая точка Т на плоскости pqr можно представить двумя векторами: в = P-Q и ты = RQ, как:
Т' = Т-Q = я *в+ дж * ты
Теперь последствия геометрии:
- я+j =1:Т на линии пр
- я+j <1:Т на кв.
- я+j >1:Т на Snq
- я+j =0:Т = К
- я+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], и
- знак я+j-1 подразумевает боковость Т.
Другие геометрические значения я и дж (не относящиеся к этому решению):
- я,дж являются скалярами для T в новой системе координат, где в, ты это новые оси и вопрос это новое начало;
- я, дж можно рассматривать как тяговая сила для П, Р, соответственно.Чем больше я, чем дальше T от р (большая тяга от п).
Значение я, Джей можно получить, решив уравнения:
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], в котором:
Т = я * П + дж * Вопрос + к * Р
и я+j+k=1 подразумевает, что T находится в плоскости [P,Q,R] и знак я+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)
