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

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

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

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

Ответ 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

Однако этот тест, опять же, работает для любого выпуклого многоугольника, а это значит, что он может быть слишком общим для прямоугольника. Прямоугольник может позволить более простой тест... Например, в прямоугольнике (или в любом другом параллелограмме) значения A и B имеют одинаковую величину, но разные знаки для противоположных (то есть параллельных) ребер, которые можно использовать для упрощения тест.

Ответ 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), dot (AB, AB) = 29, точка (BC, BC) = 10.

Для точки запроса M (4,2) имеем AM = (- 1,2), BM = (4,0), dot (AB, AM) = 9, dot (BC, BM) = 4. M находится внутри прямоугольника.

Для точки запроса P (6,1) имеем AP = (1,1), BP = (6, -1), точка (AB, AP) = - 3, точка (BC, BP) = 3, P не находится внутри прямоугольника, так как его проекция на сторону AB не находится внутри сегмента AB.

Ответ 3

# 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

Ответ 4

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

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

Ответ 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"

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

Ответ 6

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

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

Ответ 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 Answer, используя c++. Я использовал этот код, чтобы проверить, находится ли координация пикселей (X, Y) внутри фигуры или нет.

Ответ 8

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

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

f _i (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

f _BC (P) <= 0

f _CD (P) <= 0

f _DA (P) <= 0

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

Ответ 9

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

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

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

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

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

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

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