Как определить, находится ли точка справа или слева от линии
У меня есть набор очков. Я хочу разделить их на 2 разных набора. Для этого я выбираю две точки (a и b) и рисую воображаемую линию между ними. Теперь я хочу, чтобы все точки, которые остались от этой линии в одном наборе, и те, которые были справа от этой линии в другом наборе.
Как я могу определить для любой заданной точки z, находится ли она слева или справа? Я пытался вычислить угол между azb - углы, меньшие 180, находятся справа, больше 180 слева - но из-за определения ArcCos вычисленные углы всегда меньше 180°. Существует ли формула для расчета углов больше 180° (или любая другая формула для выбора правой или левой стороны)?
16 ответов
Используйте знак определителя векторов (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; b = точка 2 линии; с = точка для проверки.
Если формула равна 0, точки коллинеарны.
Если линия горизонтальная, то возвращается значение true, если точка находится над линией.
Вы смотрите на знак определителя
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
Он будет положительным для точек с одной стороны и отрицательным с другой (и нулем для точек на самой линии).
Вектор (y1 - y2, x2 - x1) перпендикулярно линии и всегда направлен вправо (или всегда направлен влево, если ваша плоскостная ориентация отличается от моей).
Затем вы можете вычислить скалярное произведение этого вектора и (x3 - x1, y3 - y1) определить, находится ли точка на той же стороне линии, что и перпендикулярный вектор (точка произведения> 0) или нет.
Используя уравнение линии ab, получите координату x на линии с той же координатой y, что и для сортируемой точки.
- Если точка x > линии x, точка находится справа от линии.
- Если точка х <линии х, точка находится слева от линии.
- Если точка х == линии х, точка находится на линии.
Я реализовал это в 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));
}
Я хотел предложить решение, основанное на физике.
Представьте себе силу, приложенную вдоль линии, и вы измеряете момент силы вокруг точки. Если крутящий момент положительный (против часовой стрелки), то точка находится "слева" от линии, но если крутящий момент отрицательный, точка находится "справа" от линии.
Таким образом, если вектор силы равен промежутку двух точек, определяющих линию
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
Сначала проверьте, если у вас есть вертикальная линия:
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
Предполагая, что точки (Ax, Ay) (Bx, By) и (Cx, Cy), вам необходимо вычислить:
(Bx - Axe) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
Это будет равно нулю, если точка C находится на линии, образованной точками A и B, и будет иметь другой знак в зависимости от стороны. То, с какой стороны это происходит, зависит от ориентации ваших (x, y) координат, но вы можете вставить тестовые значения для A, B и C в эту формулу, чтобы определить, являются ли отрицательные значения слева или справа.
Вот версия, снова использующая логику кросс-продукта, написанную на 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
@AVB ответ в рубине
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
Если det положительно выше, если отрицательно ниже. Если 0, это на линии.
В основном, я думаю, что есть решение, которое намного проще и понятнее, для любого данного многоугольника, скажем, состоящего из четырех вершин (p1,p2,p3,p4), найдите две крайние противоположные вершины в многоугольнике, в другом словами, найдите, например, самую верхнюю левую вершину (скажем, p1) и противоположную вершину, которая находится в самом нижнем правом углу (скажем, так). Следовательно, учитывая вашу контрольную точку C(x,y), теперь вы должны выполнить двойную проверку между C и p1 и C и p4:
если cx > p1x AND cy > p1y ==> означает, что C ниже и справа от p1 далее, если cx
Вывод, C находится внутри прямоугольника.
Спасибо:)
Проблемы с существующим решением:
Хотя я нашел ответ Эрика Бейнвилля правильным, я нашел его совершенно неадекватным для понимания:
- Как два вектора могут иметь определитель? Я думал, что относится к матрицам?
- Что
sign? - Как преобразовать два вектора в матрицу?
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
- Что
Bx? - Что ? Разве это не
Yдолжен быть вектором, а не скаляром? - Почему решение правильное - что за ним стоит?
Более того, в моем варианте использования использовались сложные кривые , а не простая линия, поэтому требуется небольшая переделка:
Восстановленный ответ
Point a = new Point3d(ax, ay, az); // point on line
Point b = new Point3d(bx, by, bz); // point on line
Если вы хотите увидеть, находятся ли ваши точки выше/ниже кривой , вам нужно будет получить первую производную конкретной интересующей вас кривой, также известную как касательная к точке на кривой. Если вы можете это сделать, то вы можете выделить интересующие вас моменты. Конечно, если ваша кривая представляет собой линию, вам просто нужна точка интереса без касательной. Тангенс - это линия.
Vector3d lineVector = curve.GetFirstDerivative(a); // where "a" is a point on the curve. You may derive point b with a simple displacement calculation:
Point3d b = new Point3d(a.X, a.Y, a.Z).TransformBy(
Matrix3d.Displacement(curve.GetFirstDerivative(a))
);
Point m = new Point3d(mx, my, mz) // the point you are interested in.
Решение:
return (b.X - a.X) * (m.Y - a.Y) - (b.Y - a.Y) * (m.X - a.X) < 0; // the answer
Работает для меня! Смотрите доказательство на фото выше. Зеленые кирпичи удовлетворяют условию, но кирпичи снаружи были отфильтрованы! В моем случае использования - мне нужны только кирпичи, которые касаются круга.
Теория ответа
Я вернусь, чтобы объяснить это. Когда-нибудь. Как-то...
A(x1,y1) B(x2,y2) отрезок длины L=sqrt( (y2-y1)^2 + (x2-x1)^2 )
и точка M(x,y)
выполнение преобразования координат, чтобы точка A стала новым началом, а B - точкой новой оси X.
у нас есть новые координаты точки M
которые являются новымиX = ((x-x1)(x2-x1)+(y-y1)(y2-y1)) / L
из (x-x1)*cos(t)+(y-y1)*sin(t ), где cos(t)=(x2-x1)/L, sin(t)=(y2-y1)/L
newY = ((y-y1)(x2-x1)-(x-x1)(y2-y1)) / L
из (y-y1)*cos(t)-(x-x1)*sin(t)
поскольку «левая» сторона оси X, где Y положительна, если newY (которое представляет собой расстояние M от AB) положительна, то она находится на левой стороне AB (новая ось X). Вы можете опустить деление на L (всегда положительное), если вам нужен только знак
Альтернативный способ получить представление о решениях, предлагаемых сетями, состоит в том, чтобы понять небольшие геометрические последствия.
Пусть pqr= [P,Q,R] - это точки, которые образуют плоскость, которая разделена на 2 стороны линией [P,R]. Мы должны выяснить, находятся ли две точки на плоскости pqr, A,B, на одной стороне.
Любая точка T на плоскости pqr может быть представлена двумя векторами: v = PQ и u = RQ, как:
T '= TQ = i * v + j * u
Теперь о значениях геометрии:
- i + j = 1: T на линии pr
- i+j <1: T на кв.
- i+j >1: T на Snq
- i + j = 0: T = Q
- i + j <0: T на Sq и выше 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)
Уравнение линии y-y1 = m(x-x1)
здесь m y2-y1 / x2-x1
теперь поместите m в уравнение и поставьте условие на y например.for i in rows:
for j in cols:
if j>m(i-a)+b:
image[i][j]=0