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

← →
AlexanderMS © (2007-08-10 05:48) [0]

Известны координаты вершин прямоугольника (на плоскости), угол его поворота (относительно центра), и координаты точки. Как программно узнать, принадлежит ли точка прямоугольнику, или нет?

Нашёл в общем случае для полигона (можно обходить все вершины с суммированием углов между векторами "точка-вершина" (если +-360, то принадлежит)), но здесь как-то проще можно сделать.

← →
MBo © (2007-08-10 07:10) [1]

посчитать знаки векторных произведений векторов сторон и вершина-точка, т.е. определить, лежит ли точка слева от каждой стороны при обходе против часовой стрелки

← →
@!!ex © (2007-08-10 11:05) [2]

Аналитическая геометрия рулит.
Любая прямая(в прямоугольник - это четыер прямых) делят плоскость на две части + и -.
Если подставить координаты точки в уравнение прямой то получиться расстояние от точки до прямой, со знаком обозначающим принадлежность к одной из частей.
Соответственно будет примерно так:
+
-----------
| - |
| |
+|- -|+
| |
| - |
-----------
+
Тупо проверяешь, что результат подствановки всегда меньше или равен 0, значит точка в прямоугольнике.

P.S.
Знак зависит от направления направляющего вектора задающего прямую, это надо учитывать.

← →
Думкин © (2007-08-10 13:42) [3]

> @!!ex © (10.08.07 11:05) [2]

И чем это заруливает предложенное в [1]. Те же яйца, только сбоку.

← →
Pa5ha © (2007-08-10 13:43) [4]

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

Или ещё можно как было указано в [2] сделать. Ищем высоту от точки до прямой. Если все высоты положительные или отрицательные, то значит внутри (если направление обхода одно и то же). Для того чтоб найти высоту можно построить два прямоугольных треугольника и из них вывести формулу общего катета, который и будет высотой.

← →
grouzd)ev © (2007-08-10 14:32) [5]

http://algolist.manual.ru/maths/geom/belong/poly2d.php

---
... we are walking on a thin line and you better avoid the risk ...

← →
MBo © (2007-08-10 15:11) [6]

хм... прочитал subj неверно и отвечал в [1] о принадлежности к треугольнику ;)

Для прямоугольника не нужно все четыре стороны обсчитывать. Достаточно разложить вектор первая вершина - точка по векторам двух смежных сторон, и проверить, что обе параметрические координаты находятся в пределах 0..1. Делений даже не понадобится, если сравнивать не с единицей, а с дискриминантом (учтя его знак)

← →
@!!ex © (2007-08-10 15:26) [7]

> И чем это заруливает предложенное в [1]. Те же яйца, только
> сбоку.

Развернутые яйца. :))
А алгоритм тот же самый, если я правильно понимаю.

← →
Jkot © (2007-08-11 04:53) [8]

Есть такой самый простой но и самый медленнй алгоритм прямоугольник это 2 треугольника -> находим плошадь прямоугольника потом берём точку и от неё строим 4 треуголька (точка вершина и сторона треугольника совпадает с одной из сторон прямоугольника) складываем плошади этих 4 треугольников и сравниваем с погрешностью с плошадью прямоугольника всё...

← →
AlexanderMS © (2007-08-11 15:59) [9]

Большое спасибо.

← →
Pa5ha © (2007-08-13 00:46) [10]

Хз накодил там автор чего или нет ) Показую свой код )function tElement.CheckLinesUnderCur(x, y, w: Single): Boolean; var i: integer; a,b,c,l: Single; flag:Boolean; begin Result:=False; for i:=0 to Length(lines)-1 do begin // x = (sqr(b)+sqr(c)-sqr(a))/(2*c); // h = sqrt(sqr(b)-sqr(x)); a:= sqrt( sqr((lines[i].line[0].x)-x)+ sqr((lines[i].line[0].y)-y)); b:= sqrt( sqr((lines[i].line[1].x)-x)+ sqr((lines[i].line[1].y)-y)); c:= sqrt( sqr( (lines[i].line[0].x)- (lines[i].line[1].x) )+ sqr( (lines[i].line[0].y)- (lines[i].line[1].y) )); flag:=false; if c>0 then begin l:= ( sqr(b)+ sqr(c)- sqr(a) )/ (2*c); if (sqr(b)>=(sqr(l)))and ( sqr(a) <=( sqr(c)+sqr(w) ) )and (sqr(b)<=(sqr(c)+sqr(w))) then begin if sqrt(sqr(b)-sqr(l))<=w then begin flag:=true; end; end; end; if flag then begin // рядом с линией, в пределах w. // h (тут, наверно, l) - расстояние от точки до прямой. end; end; end;
Короче если ещё подумать, то можно сделать то что надо )

← →
Darkwingg (2007-08-27 10:02) [11]

> Если подставить координаты точки в уравнение прямой то
> получиться расстояние от точки до прямой,

Мне интересно, как вы в этом случае определите уравнение для вертикальной прямой )))

← →
@!!ex © (2007-08-27 10:35) [12]

> [11] Darkwingg (27.08.07 10:02)

А есть какие то проблемы? :))

← →
Darkwingg (2007-08-27 10:56) [13]

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

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

pх, py - координаты точки в старой системе координат
newpx, newpy - координаты точки в новой системе координат
ax, ay - координаты левой нижней точки прямоугольника (естессно в ст. системе координат.)
la, lb - длины сторон прямоугольника

G - угол поворота прямоугольника по часовой стрелке, относительно его левой нижней точки.

1. newpx = (px - ax)*cos(G) - (py - ay)*sin(G)
2. newpy = (px - ax)*sin(G) + (py - ay)*cos(G)

если newpx <= la и newpy <= lb, то точка лежит внутри прямоугольника.

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

← →
Darkwingg (2007-08-27 10:59) [14]

> А есть какие то проблемы? :))

хм)), ну напишите тогда уравнение прямой проходящей через точки

x1=1, y1=0, x2=1, y2=3.

← →
@!!ex © (2007-08-27 11:34) [15]

> [14] Darkwingg (27.08.07 10:59)

Вам в ВУЗе не преподавали свойства прямой? :)

Первое свойство:
Через любые две несовпадающие точки можно провести единственную прямую.

В данно мслучае уравнение прямой будет:
x = x1
и расстояние от прямой до точки будет находиться как разность x1 и x координаты точки.

← →
Darkwingg (2007-08-27 12:00) [16]

хм...хм) да через любые 2 несовпадающие точки можно провести прямую, однако не каждую прямую можно описать уравнением y=f(x), то есть как раз в случае вертикальной прямой потребуется дополнительное условие, проверяющее вертикальна ли она.

У вас сказано, что просто достаточно подставить координаты в уравнение прямой, в таком случае, напишите это уравнение для всех прямых включая вертикальные)))

← →
@!!ex © (2007-08-27 12:18) [17]

> [16] Darkwingg (27.08.07 12:00)

Вот не надо придираться к таким мелочам.
И идиоту известно, что вертикальная прямая не являеться обычной прямой, хотя бы потому, что не являеться графиком.
Соответственно и порверять ее нужно отдельно.
ИМХо проще проверить, чем воспользоваться вашим методом.
Да и работать будет быстрее.

← →
Darkwingg (2007-08-27 13:03) [18]

> Вот не надо придираться к таким мелочам.

А это не совсем мелочи.... вот например что вы будете делать с прямой близкой к вертикальной?

подозреваю что ваша формула выглядит так y=x(y2-y1)/(x2-x1) + b, в таком случае при малом но не нулевом (x2-x1), что как раз имеет прямая, близкая к вертикальной, вы получите большую погрешность и можете промахнуться с положением точки, а кроме того может возникнуть деление на ноль.

канеш это всё зависит, от того с какой глубиной подходить к решению задачи. Для автора, я думаю, сойдет любой из вариантов.

← →
MBo © (2007-08-27 13:37) [19]

>Darkwingg
любую прямую можно описать,например, уравнением ax + by + c = 0

> [19] MBo © (27.08.07 13:37)

В данном случае нет смысла от такого описания, хоть оно и универсальное.. :(

> [18] Darkwingg (27.08.07 13:03)

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

>В данном случае нет смысла от такого описания
Если речь идет о том, с какой стороны от прямой находится точка, то это описание отлично подходит.

> [21] MBo © (27.08.07 15:01)

А! Точно. Протупил нафиг.
Ведь как раз именно это уравнение дает расстояние от прямой до точки и к тому же универсальное.

Блиин. Во я тупой стал... Вообще уже в математику не втыкаю, надо порешать задач....

Darkwingg, вот оно - то самое уравнение.

>@!!ex
однако для построения уравнений придется делать вычисления для всех сторон, что излишне.

в [5] описан более экономичный способ.

← →
Darkwingg (2007-08-27 15:28) [24]

> @!!ex ©

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

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

(x-x1)/(y-y1) = (x-x2)/(y-y2)

путем бубна и ктулху его можно привести к виду ax + by + c = 0, где всерно будет (x1 - x2) в знаменателе.

> [24] Darkwingg (27.08.07 15:28)

Честно говоря я уже сейчас не помню, но нам объясняли как избегать случая, когда компонента направляющего вектора равно 0, вроде там както просто, но это было давно и я не помню.

← →
Darkwingg (2007-08-27 15:41) [26]

в том то и дело что с синусами, косинусами, углами и векторами не дожно возникать никаких проблем. там вообще нет никакого деления. что собсно и отражено в моем методе))). все заканчиваю флудить....последний пост в этой теме.

> однако для построения уравнений придется делать вычисления
> для всех сторон, что излишне.
>
> в [5] описан более экономичный способ.

Зачем? парами считать, направляющие векторы то у парарельных прямых одинаквые.
А если это прямоугольник, то достаточно найти один, а второй будет под 90 градусов.

> [26] Darkwingg (27.08.07 15:41)

Нееет. Все таки я туплю конкретно.
Нет там деления на ноль. Даже при вертикальной прямой.
Это же тупо компоненты вектора, ну равна одна из них нулю, там же умножение, а не деление!

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