Нахождение точки лежит внутри прямоугольника или нет

Question

Я хочу выяснить, находится ли точка внутри прямоугольника или нет.Прямоугольник можно ориентировать любым способом, и его не нужно выравнивать по оси.

Один из способов, о котором я мог подумать, - это повернуть прямоугольник и координаты точки, чтобы выровнять ось прямоугольника, а затем просто протестировать координатыуказать, лежат ли они в пределах прямоугольника или нет.

Приведенный выше метод требует вращения и, следовательно, операций с плавающей запятой.Есть ли другой эффективный способ сделать это?

Answer 1

Как представлен прямоугольник? Три очка? Четыре очка? Точка, стороны и угол? Две точки и сторона? Что-то другое? Не зная об этом, любые попытки ответить на ваш вопрос будут иметь чисто академическое значение.

В любом случае для любого выпуклого многоугольника (включая прямоугольник) тест очень прост: проверьте каждый край многоугольника, предполагая, что каждый край ориентирован против часовой стрелки, и проверьте, находится ли точка слева от края (в левой полуплоскости). Если все ребра проходят тест - точка находится внутри. Если хотя бы один сбой - точка находится вне.

Чтобы проверить, лежит ли точка (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 имеют одинаковую величину, но разные знаки для противоположных (то есть параллельных) ребер, которые могут использовать для упрощения теста.

Answer 2

Предполагая, что прямоугольник представлен тремя точками 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.

Answer 3

Я позаимствовал у Эрика Бейнвилля ответ:

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

Answer 4

# 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

Answer 5

Я понимаю, что это старая ветка, но для тех, кто заинтересован в том, чтобы взглянуть на это с чисто математической точки зрения, на бирже стека математики есть отличная тема:

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"

И это все. Это также будет работать для параллелограммов.

Answer 6

Если вы не можете решить проблему с прямоугольником, попробуйте разделить проблему на более простые задачи. Разделите прямоугольник на 2 треугольника, чтобы проверить, находится ли точка внутри какого-либо из них, как они объясняют в здесь

По сути, вы проходите через ребра на каждых двух парах линий от точки. Затем используйте перекрестное произведение, чтобы проверить, находится ли точка между двумя линиями, используя перекрестное произведение. Если это проверено для всех 3 точек, то точка находится внутри треугольника. Преимущество этого метода в том, что он не создает ошибок с плавающей запятой, которые возникают, если вы проверяете углы.

Answer 7

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) внутри фигуры или нет.

Answer 8

Если точка находится внутри прямоугольника. На плоскости. Для координат математики или геодезии (GPS)

• Пусть прямоугольник задан вершинами A, B, C, D. Точка P. Координаты прямоугольные: x, y.
• Позволяет удлинить стороны прямоугольника. Итак, у нас есть 4 прямые линии l _AB , l _BC , l _CD , l _DA или, для краткости, l ₁ , л ₂ , л ₃ , л ₄ .

• Составьте уравнение для каждого l _i . Уравнение рода:

  * 1 028 * F _я (P) = 0.

P - точка. Для точек, принадлежащих l _i , уравнение истинно.

• Нам нужны функции в левой части уравнений. Это f ₁ , f ₂ , f ₃ , f ₄ .
• Обратите внимание, что для каждой точки с одной стороны 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 </p>

f _BC (P) <= 0 </p>

f _CD (P) <= 0 </p>

f _DA (P) <= 0 </p>

Если вы не уверены в направлениях осей, будьте осторожны с этой упрощенной проверкой - проверьте одну точку с известным расположением, если вы выбрали правильные уравнения.

Answer 9

Самый простой способ, о котором я думал, это просто спроецировать точку на ось прямоугольника. Позвольте мне объяснить:

Если вы можете получить вектор от центра прямоугольника к верхнему или нижнему краю и левому или правому краю. И у вас также есть вектор от центра прямоугольника к вашей точке, вы можете проецировать эту точку на ваши векторы ширины и высоты.

P = точечный вектор, H = вектор высоты, W = вектор ширины

Получите единичный вектор W ', H', разделив векторы на их величину

proj_P, H = P - (P.H ') H' proj_P, W = P - (P.W ') W'

Если я не ошибаюсь, я не думаю, что я ... (поправьте меня, если я ошибаюсь), но если величина проекции вашей точки на вектор высоты меньше, чем величина вектора высоты (что составляет половину высоты прямоугольника) и величина проекции вашей точки на вектор ширины равна, тогда у вас есть точка внутри прямоугольника.

Если у вас есть универсальная система координат, вам, возможно, придется вычислять векторы высоты / ширины / точки, используя векторное вычитание. Векторные проекции потрясающие! помни это.