Нахождение точки лежит внутри прямоугольника или нет
Я хочу выяснить, находится ли точка внутри прямоугольника или нет. Прямоугольник может быть ориентирован любым способом и не должен быть выровнен по оси.
Одним из способов, который я мог придумать, было вращение координат прямоугольника и точки, чтобы выровнять ось прямоугольника, а затем просто проверить координаты точки, лежат ли они в пределах координат прямоугольника или нет.
Вышеуказанный метод требует вращения и, следовательно, операций с плавающей запятой. Есть ли другой эффективный способ сделать это?
9 ответов
Как представлен прямоугольник? Три очка? Четыре очка? Точка, стороны и угол? Две точки и сторона? Что-то другое? Не зная этого, любые попытки ответить на ваш вопрос будут иметь чисто академическое значение.
В любом случае, для любого выпуклого многоугольника (включая прямоугольник) тест очень прост: проверьте каждый край многоугольника, предполагая, что каждый край ориентирован против часовой стрелки, и проверьте, находится ли точка слева от края (слева полуплан самолета). Если все ребра проходят тест - точка находится внутри. Если хотя бы один сбой - точка находится снаружи.
Для того, чтобы проверить, является ли точка (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 имеют одинаковую величину, но разные знаки для противоположных (то есть параллельных) краев, которые могут быть использованы для упрощения теста.
Предполагая, что прямоугольник представлен тремя точками 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), точка (AB,AB)=29, точка (BC,BC)=10.
Для точки запроса M(4,2) имеем AM=(-1,2), BM=(4,0), точка (AB,AM)=9, точка (BC,BM)=4. М внутри прямоугольника.
Для точки запроса P(6,1) имеем AP=(1,1), BP=(6,-1), точка (AB,AP)=-3, точка (BC,BP)=3. P не находится внутри прямоугольника, потому что его проекция на стороне AB не находится внутри отрезка AB.
Я позаимствовал у Эрика Бейнвилля ответ:
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)
Который в JavaScript выглядит так:
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var BC = vector(r.B, r.C);
var BM = vector(r.B, m);
var dotABAM = dot(AB, AM);
var dotABAB = dot(AB, AB);
var dotBCBM = dot(BC, BM);
var dotBCBC = dot(BC, BC);
return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC;
}
function vector(p1, p2) {
return {
x: (p2.x - p1.x),
y: (p2.y - p1.y)
};
}
function dot(u, v) {
return u.x * v.x + u.y * v.y;
}
например:
var r = {
A: {x: 50, y: 0},
B: {x: 0, y: 20},
C: {x: 10, y: 50},
D: {x: 60, y: 30}
};
var m = {x: 40, y: 20};
затем:
pointInRectangle(m, r); // returns true.
Вот кодекс, чтобы нарисовать вывод в виде визуального теста:) http://codepen.io/mattburns/pen/jrrprN
# 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
Я понимаю, что это старый поток, но для тех, кто заинтересован в том, чтобы взглянуть на это с чисто математической точки зрения, здесь есть отличная тема по обмену стека математики:
https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle
Изменить: Вдохновленный этим потоком, я собрал простой векторный метод для быстрого определения, где ваша точка лежит.
Предположим, у вас есть прямоугольник с точками в p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) и p4 = (x4, y4), идущий по часовой стрелке. Если точка p = (x, y) лежит внутри прямоугольника, то произведение точек (p - p1). (P2 - p1) будет лежать между 0 и |p2 - p1|^2, и (p - p1).(p4 - p1) будет лежать между 0 и |p4 - p1|^2. Это эквивалентно взятию проекции вектора p - p1 вдоль длины и ширины прямоугольника с началом координат p1.
Это может иметь больше смысла, если я покажу эквивалентный код:
p21 = (x2 - x1, y2 - y1)
p41 = (x4 - x1, y4 - y1)
p21magnitude_squared = p21[0]^2 + p21[1]^2
p41magnitude_squared = p41[0]^2 + p41[1]^2
for x, y in list_of_points_to_test:
p = (x - x1, y - y1)
if 0 <= p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared:
if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared:
return "Inside"
else:
return "Outside"
else:
return "Outside"
И это все. Это также будет работать для параллелограммов.
bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) {
Point AB = vect2d(A, B); float C1 = -1 * (AB.y*A.x + AB.x*A.y); float D1 = (AB.y*m.x + AB.x*m.y) + C1;
Point AD = vect2d(A, D); float C2 = -1 * (AD.y*A.x + AD.x*A.y); float D2 = (AD.y*m.x + AD.x*m.y) + C2;
Point BC = vect2d(B, C); float C3 = -1 * (BC.y*B.x + BC.x*B.y); float D3 = (BC.y*m.x + BC.x*m.y) + C3;
Point CD = vect2d(C, D); float C4 = -1 * (CD.y*C.x + CD.x*C.y); float D4 = (CD.y*m.x + CD.x*m.y) + C4;
return 0 >= D1 && 0 >= D4 && 0 <= D2 && 0 >= D3;}
Point vect2d(Point p1, Point p2) {
Point temp;
temp.x = (p2.x - p1.x);
temp.y = -1 * (p2.y - p1.y);
return temp;}
Я только что реализовал ответ AnT, используя C++. Я использовал этот код, чтобы проверить, находится ли координация пикселя (X,Y) внутри фигуры или нет.
Если вы не можете решить проблему с прямоугольником, попробуйте разделить проблему на более простые задачи. Разделите прямоугольник на 2 треугольника, чтобы проверить, находится ли точка внутри какого-либо из них, как они объясняют здесь
По сути, вы проходите через ребра на каждые две пары линий из точки. Затем используйте перекрестное произведение, чтобы проверить, находится ли точка между двумя линиями, используя перекрестное произведение. Если это проверено для всех 3 точек, то точка находится внутри треугольника. Хорошая вещь об этом методе - то, что он не создает никаких ошибок с плавающей точкой, которые происходят, если вы проверяете на углы.
Если точка находится внутри прямоугольника. На плоскости. Для координат математики или геодезии (GPS)
- Пусть прямоугольник задан вершинами A, B, C, D. Точка P. Координаты прямоугольные: x, y.
- Продлим стороны прямоугольника. Таким образом, мы имеем 4 прямые линии l AB, l BC, l CD, l DA или, для краткости, l 1, l 2, l 3, l 4.
Составьте уравнение для каждого l i. Уравнение вроде:
f i (P) = 0.
P это точка. Для точек, принадлежащих l i, уравнение верно.
- Нам нужны функции в левой части уравнений. Это f 1, f 2, f 3, f 4.
- Обратите внимание, что для каждой точки с одной стороны от l i функция f i больше 0, а для точек с другой стороны f i меньше 0.
- Таким образом, если мы проверяем, что P находится в прямоугольнике, нам нужно только, чтобы p было на правильных сторонах всех четырех линий. Итак, мы должны проверить четыре функции на их признаки.
- Но какая сторона линии является правильной, к которой принадлежит прямоугольник? Это сторона, где лежат вершины прямоугольника, которые не принадлежат линии. Для проверки мы можем выбрать любую из двух не принадлежащих вершин.
Итак, мы должны проверить это:
f AB (P) f AB (C)> = 0
f BC (P) f BC (D)> = 0
f CD (P) f CD (A)> = 0
f DA (P) f DA (B)> = 0
Уклонения не являются строгими, поскольку, если точка находится на границе, она также принадлежит прямоугольнику. Если вам не нужны точки на границе, вы можете поменять неравенства на строгие. Но пока вы работаете в операциях с плавающей запятой, выбор не имеет значения.
- Для точки, которая находится в прямоугольнике, все четыре неравенства верны. Обратите внимание, что это работает также для каждого выпуклого многоугольника, только количество линий / уравнений будет отличаться.
Осталось только получить уравнение для линии, проходящей через две точки. Это хорошо известное линейное уравнение. Запишем это для линии AB и точки P:
f AB (P) ≡ (x A -x B) (y P -y B) - (y A -y B) (x P -x B)
Проверка может быть упрощена - давайте пройдем по прямоугольнику по часовой стрелке - A, B, C, D, A. Тогда все правильные стороны будут справа от линий. Таким образом, нам не нужно сравнивать со стороной, где находится другая вершина. И нам нужно проверить набор более коротких неравенств:
f AB (P)> = 0
f BC (P)> = 0
f CD (P)> = 0
f DA (P)> = 0
Но это верно для нормального, математического (из школьной математики) набора координат, где X - справа, а Y - вверху. А для координат геодезии, которые используются в GPS, где X вверху, а Y вправо, мы должны повернуть неравенства:
f AB (P) <= 0
f BC (P) <= 0
f CD (P) <= 0
f DA (P) <= 0
Если вы не уверены в направлениях осей, будьте осторожны с этой упрощенной проверкой - проверьте одну точку с известным расположением, если вы выбрали правильные уравнения.
В продолжение мат ответить. нам нужно использовать решение https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle/190373, чтобы оно работало
Ниже не работает
0 <= точка (AB,AM) <= точка (AB,AB) && 0 <= точка (BC,BM) <= точка (BC,BC)
Ниже работает
0 <= точка (AB,AM) <= точка (AB,AB) && 0 <= точка (AM,AC) <= точка (AC, AC)
вы проверяете, вставив ниже в консоль javascript // Решение Javascript для того же
var screenWidth = 320;
var screenHeight = 568;
var appHeaderWidth = 320;
var AppHeaderHeight = 65;
var regionWidth = 200;
var regionHeight = 200;
this.topLeftBoundary = {
A: {x: 0, y: AppHeaderHeight},
B: {x: regionWidth, y: AppHeaderHeight},
C: {x: 0, y: regionHeight + AppHeaderHeight},
D: {x: regionWidth, y: regionHeight + AppHeaderHeight}
}
this.topRightBoundary = {
A: {x: screenWidth, y: AppHeaderHeight},
B: {x: screenWidth - regionWidth, y: AppHeaderHeight},
C: {x: screenWidth, y: regionHeight + AppHeaderHeight},
D: {x: screenWidth - regionWidth, y: regionHeight + AppHeaderHeight}
}
this.bottomRightBoundary = {
A: {x: screenWidth, y: screenHeight},
B: {x: screenWidth - regionWidth, y: screenHeight},
C: {x: screenWidth, y: screenHeight - regionHeight},
D: {x: screenWidth - regionWidth, y: screenHeight - regionHeight}
}
this.bottomLeftBoundary = {
A: {x: 0, y: screenHeight},
B: {x: regionWidth, y: screenHeight},
C: {x: 0, y: screenHeight - regionHeight},
D: {x: regionWidth, y: screenHeight - regionHeight}
}
console.log(this.topLeftBoundary);
console.log(this.topRightBoundary);
console.log(this.bottomRightBoundary);
console.log(this.bottomLeftBoundary);
checkIfTapFallsInBoundary = function (region, point) {
console.log("region " + JSON.stringify(region));
console.log("point" + JSON.stringify(point));
var r = region;
var m = point;
function vector(p1, p2) {
return {
x: (p2.x - p1.x),
y: (p2.y - p1.y)
};
}
function dot(u, v) {
console.log("DOT " + (u.x * v.x + u.y * v.y));
return u.x * v.x + u.y * v.y;
}
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var AC = vector(r.A, r.C);
var BC = vector(r.B, r.C);
var BM = vector(r.B, m);
console.log("AB " + JSON.stringify(AB));
console.log("AM " + JSON.stringify(AM));
console.log("AM " + JSON.stringify(AC));
console.log("BC " + JSON.stringify(BC));
console.log("BM " + JSON.stringify(BM));
var dotABAM = dot(AB, AM);
var dotABAB = dot(AB, AB);
var dotBCBM = dot(BC, BM);
var dotBCBC = dot(BC, BC);
var dotAMAC = dot(AM, AC);
var dotACAC = dot(AC, AC);
console.log("ABAM " + JSON.stringify(dotABAM));
console.log("ABAB " + JSON.stringify(dotABAB));
console.log("BCBM " + JSON.stringify(dotBCBM));
console.log("BCBC " + JSON.stringify(dotBCBC));
console.log("AMAC " + JSON.stringify(dotAMAC));
console.log("ACAC" + JSON.stringify(dotACAC));
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotBCBM && dotBCBM <= dotBCBC));
console.log(" first check" + check);
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotAMAC && dotAMAC <= dotACAC));
console.log("second check" + check);
return check;
}
return pointInRectangle(m, r);
}
//var point = {x: 136, y: 342};
checkIfTapFallsInBoundary(topLeftBoundary, {x: 136, y: 342});
checkIfTapFallsInBoundary(topRightBoundary, {x: 136, y: 274});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 141, y: 475});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 131, y: 272});
checkIfTapFallsInBoundary(bottomLeftBoundary, {x: 131, y: 272});
Самый простой способ, о котором я думал, это просто спроецировать точку на ось прямоугольника. Позволь мне объяснить:
Если вы можете получить вектор от центра прямоугольника к верхнему или нижнему краю и левому или правому краю. И у вас также есть вектор от центра прямоугольника до вашей точки, вы можете проецировать эту точку на ваши векторы ширины и высоты.
P = точечный вектор, H = вектор высоты, W = вектор ширины
Получить единичный вектор W', H' путем деления векторов на их величину
proj_P,H = P - (P.H')H' proj_P,W = P - (P.W')W'
Если я не ошибаюсь, что я не думаю, что я... (поправьте меня, если я ошибаюсь), но если величина проекции вашей точки на вектор высоты меньше, чем величина вектора высоты (который половину высоты прямоугольника) и величина проекции вашей точки на вектор ширины равна, тогда у вас есть точка внутри вашего прямоугольника.
Если у вас есть универсальная система координат, вам, возможно, придется вычислять векторы высоты / ширины / точки, используя векторное вычитание. Векторные проекции потрясающие! помни это.