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

Question

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

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

Answer 1

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

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

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

Спасибо :)

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

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 соответственно. Чем больше i , тем дальше 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 означает его sideness. Из этого имеем:

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)