-
Известны координаты вершин прямоугольника (на плоскости), угол его поворота (относительно центра), и координаты точки. Как программно узнать, принадлежит ли точка прямоугольнику, или нет?
Нашёл в общем случае для полигона (можно обходить все вершины с суммированием углов между векторами "точка-вершина" (если +-360, то принадлежит)), но здесь как-то проще можно сделать.
-
посчитать знаки векторных произведений векторов сторон и вершина-точка, т.е. определить, лежит ли точка слева от каждой стороны при обходе против часовой стрелки
-
Аналитическая геометрия рулит.
Любая прямая(в прямоугольник - это четыер прямых) делят плоскость на две части + и -.
Если подставить координаты точки в уравнение прямой то получиться расстояние от точки до прямой, со знаком обозначающим принадлежность к одной из частей.
Соответственно будет примерно так:
+
-----------
| - |
| |
+|- -|+
| |
| - |
-----------
+
Тупо проверяешь, что результат подствановки всегда меньше или равен 0, значит точка в прямоугольнике.
P.S.
Знак зависит от направления направляющего вектора задающего прямую, это надо учитывать.
-
> @!!ex © (10.08.07 11:05) [2]
И чем это заруливает предложенное в [1]. Те же яйца, только сбоку.
-
тупо по формуле поворота поворачиваются все точки прямоугольника для того чтоб сделать прямоугольник горизонтальным, а дальше проверяеца как обычно.
Или ещё можно как было указано в [2] сделать. Ищем высоту от точки до прямой. Если все высоты положительные или отрицательные, то значит внутри (если направление обхода одно и то же). Для того чтоб найти высоту можно построить два прямоугольных треугольника и из них вывести формулу общего катета, который и будет высотой.
-
-
хм... прочитал subj неверно и отвечал в [1] о принадлежности к треугольнику ;)
Для прямоугольника не нужно все четыре стороны обсчитывать. Достаточно разложить вектор первая вершина - точка по векторам двух смежных сторон, и проверить, что обе параметрические координаты находятся в пределах 0..1. Делений даже не понадобится, если сравнивать не с единицей, а с дискриминантом (учтя его знак)
-
> И чем это заруливает предложенное в [1]. Те же яйца, только
> сбоку.
Развернутые яйца. :))
А алгоритм тот же самый, если я правильно понимаю.
-
Есть такой самый простой но и самый медленнй алгоритм прямоугольник это 2 треугольника -> находим плошадь прямоугольника потом берём точку и от неё строим 4 треуголька (точка вершина и сторона треугольника совпадает с одной из сторон прямоугольника) складываем плошади этих 4 треугольников и сравниваем с погрешностью с плошадью прямоугольника всё...
-
Большое спасибо.
-
Хз накодил там автор чего или нет ) Показую свой код ) 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
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
end;
end;
end;
Короче если ещё подумать, то можно сделать то что надо )
-
> Если подставить координаты точки в уравнение прямой то
> получиться расстояние от точки до прямой,
Мне интересно, как вы в этом случае определите уравнение для вертикальной прямой )))
-
> [11] Darkwingg (27.08.07 10:02)
А есть какие то проблемы? :))
-
имхо самое правльное пересчитать координаты точки в систему координат, построенную на любой вершине и двух перпендикулярных сторонах прямоугольника, а затем сравнить координаты с длинами сторон. (суть процесса уже описана выше, привожу формулы)
выберем в качестве точки отсчета новой системы координат левую нижнюю точку прямоугольника.
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, то точка лежит внутри прямоугольника.
правда получится не совсем гуд, если длины сторон прямоугольника не известны, а известны только координаты вершин))) придется считать еще и их, на это нужно еще несколько операций.
-
> А есть какие то проблемы? :))
хм)), ну напишите тогда уравнение прямой проходящей через точки
x1=1, y1=0, x2=1, y2=3.
-
> [14] Darkwingg (27.08.07 10:59)
Вам в ВУЗе не преподавали свойства прямой? :)
Первое свойство:
Через любые две несовпадающие точки можно провести единственную прямую.
В данно мслучае уравнение прямой будет:
x = x1
и расстояние от прямой до точки будет находиться как разность x1 и x координаты точки.
-
хм...хм) да через любые 2 несовпадающие точки можно провести прямую, однако не каждую прямую можно описать уравнением y=f(x), то есть как раз в случае вертикальной прямой потребуется дополнительное условие, проверяющее вертикальна ли она.
У вас сказано, что просто достаточно подставить координаты в уравнение прямой, в таком случае, напишите это уравнение для всех прямых включая вертикальные)))
-
> [16] Darkwingg (27.08.07 12:00)
Вот не надо придираться к таким мелочам.
И идиоту известно, что вертикальная прямая не являеться обычной прямой, хотя бы потому, что не являеться графиком.
Соответственно и порверять ее нужно отдельно.
ИМХо проще проверить, чем воспользоваться вашим методом.
Да и работать будет быстрее.
-
> Вот не надо придираться к таким мелочам.
А это не совсем мелочи.... вот например что вы будете делать с прямой близкой к вертикальной?
подозреваю что ваша формула выглядит так y=x(y2-y1)/(x2-x1) + b, в таком случае при малом но не нулевом (x2-x1), что как раз имеет прямая, близкая к вертикальной, вы получите большую погрешность и можете промахнуться с положением точки, а кроме того может возникнуть деление на ноль.
канеш это всё зависит, от того с какой глубиной подходить к решению задачи. Для автора, я думаю, сойдет любой из вариантов.
-
>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] описан более экономичный способ.
-
> @!!ex ©
угу согласен)) я тож щас понял, что пора бы заново пролистать кой-какие книжки...
только вот к этому виду уравнение тоже надо еще привести, здается мне что в этом методе от деления на ноль всерно никуда не деться. Прямая, проходящая через две точки, если не ошибаюсь, описывается такой формулой:
(x-x1)/(y-y1) = (x-x2)/(y-y2)
путем бубна и ктулху его можно привести к виду ax + by + c = 0, где всерно будет (x1 - x2) в знаменателе.
-
> [24] Darkwingg (27.08.07 15:28)
Честно говоря я уже сейчас не помню, но нам объясняли как избегать случая, когда компонента направляющего вектора равно 0, вроде там както просто, но это было давно и я не помню.
-
в том то и дело что с синусами, косинусами, углами и векторами не дожно возникать никаких проблем. там вообще нет никакого деления. что собсно и отражено в моем методе))). все заканчиваю флудить....последний пост в этой теме.
-
> однако для построения уравнений придется делать вычисления
> для всех сторон, что излишне.
>
> в [5] описан более экономичный способ.
Зачем? парами считать, направляющие векторы то у парарельных прямых одинаквые.
А если это прямоугольник, то достаточно найти один, а второй будет под 90 градусов.
> [26] Darkwingg (27.08.07 15:41)
Нееет. Все таки я туплю конкретно.
Нет там деления на ноль. Даже при вертикальной прямой.
Это же тупо компоненты вектора, ну равна одна из них нулю, там же умножение, а не деление!
-
> однако для построения уравнений придется делать вычисления
> для всех сторон, что излишне.
>
> в [5] описан более экономичный способ.
Зачем? парами считать, направляющие векторы то у парарельных прямых одинаквые.
А если это прямоугольник, то достаточно найти один, а второй будет под 90 градусов.
> [26] Darkwingg (27.08.07 15:41)
Нееет. Все таки я туплю конкретно.
Нет там деления на ноль. Даже при вертикальной прямой.
Это же тупо компоненты вектора, ну равна одна из них нулю, там же умножение, а не деление!
|
Есть новые 
Нет новых [134431 +10][b:0][p:0.002]