Нахождение, находится ли точка в прямоугольнике или нет
Я хочу найти, находится ли точка в прямоугольнике или нет. Прямоугольник может быть ориентирован всегда и не должен быть выровненной осью.
Один метод, о котором я мог думать, должен был повернуть прямоугольник и координаты точки для создания прямоугольной оси выровненной и затем путем простого тестирования координат точки, находятся ли они в том из прямоугольника или нет.
Вышеупомянутый метод требует вращения и следовательно операций с плавающей точкой. Там какой-либо другой эффективный путь состоит в том, чтобы сделать это?
4 ответа
Каким образом представлен прямоугольник? Три очка? Четыре очка? Точка, стороны и угол? Два очка и сторона? Что-то другое? Не зная этого, любые попытки ответить на ваш вопрос будут иметь чисто академическое значение.
В любом случае, для любого выпуклого многоугольника (включая прямоугольник) проверка очень проста: проверьте каждое ребро многоугольника, предполагая, что каждое ребро ориентировано против часовой стрелки, и проверьте, лежит ли точка слева от края (в левой полуплоскости). Если все ребра проходят проверку - точка внутри. Если хоть один выйдет из строя - дело во внешнем.
Чтобы проверить, лежит ли точка (xp, yp) слева от ребра (x1, y1) - (x2, y2) , вы просто нужно вычислить
D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)
Если D> 0 , точка находится слева. Если D <0 , точка находится справа. Если D = 0 , точка находится на прямой.
Предыдущая версия этого ответа описывала, казалось бы, другую версию левого теста (см. Ниже). Но легко показать, что он вычисляет то же значение.
... Чтобы проверить, лежит ли точка (xp, yp) слева от ребра (x1, y1) - (x2, y2) , вам нужно построить линейное уравнение для линии, содержащей ребро. Уравнение выглядит следующим образом
A * x + B * y + C = 0
где
A = -(y2 - y1)
B = x2 - x1
C = -(A * x1 + B * y1)
Теперь все, что вам нужно сделать, это вычислить
D = A * xp + B * yp + C
Если D> 0 , точка находится слева. Если D <0 , точка находится справа. Если D = 0 , точка находится на прямой.
Однако этот тест, опять же, работает для любого выпуклого многоугольника, а это означает, что он может быть слишком общим для прямоугольника. Прямоугольник может позволить более простой тест ... Например, в прямоугольнике (или в любом другом параллелограмме) значения A и B имеют одинаковую величину, но разные знаки для противоположных (т.е. параллельные) кромки, которые можно использовать для упрощения теста.
Если вы не можете решить проблему для прямоугольника, попробуйте разделить проблему на более простые. Разделите прямоугольник на 2 треугольника и проверьте, находится ли точка внутри любого из них, как описано в ] здесь
По сути, вы циклически перебираете ребра на каждых двух парах линий от точки. Затем используйте кросс-произведение, чтобы проверить, находится ли точка между двумя линиями, используя кросс-произведение. Если это проверено для всех трех точек, то точка находится внутри треугольника. Преимущество этого метода в том, что он не создает ошибок с плавающей запятой, которые возникают, если вы проверяете углы.
# Pseudo code
# Corners in ax,ay,bx,by,dx,dy
# Point in x, y
bax = bx - ax
bay = by - ay
dax = dx - ax
day = dy - ay
if ((x - ax) * bax + (y - ay) * bay < 0.0) return false
if ((x - bx) * bax + (y - by) * bay > 0.0) return false
if ((x - ax) * dax + (y - ay) * day < 0.0) return false
if ((x - dx) * dax + (y - dy) * day > 0.0) return false
return true
Предполагая, что прямоугольник представлен тремя точками A,B,C, а AB и BC перпендикулярны, достаточно проверить проекции точки запроса M на AB и BC:
0 <= dot(AB,AM) <= dot(AB,AB) &&
0 <= dot(BC,BM) <= dot(BC,BC)
AB - вектор AB с координатами (Bx-Ax,By-Ay), а dot(U,V) - точечное произведение векторов U и V: Ux*Vx+Uy*Vy.
Обновление. Рассмотрим пример, иллюстрирующий это: A(5,0) B(0,2) C(1,5) и D(6,3). Из координат точек получаем AB=(-5,2), BC=(1,3), dot(AB,AB)=29, dot(BC,BC)=10.
Для точки запроса M(4,2) имеем AM=(-1,2), BM=(4,0), точка(AB,AM)=9, точка(BC,BM)=4. M находится внутри прямоугольника.
Для точки запроса P(6,1) имеем AP=(1,1), BP=(6,-1), точка(AB,AP)=-3, точка(BC,BP)=3. Точка P не находится внутри прямоугольника, так как ее проекция на сторону AB не находится внутри отрезка AB.