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

← →
Lexa11_2002 (2006-03-22 21:52) [0]

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

← →
Джо © (2006-03-22 21:58) [1]

PtInRect? Ей-богу, самому проще написать ;)

← →
Lexa11_2002 (2006-03-22 22:03) [2]

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

← →
Джо © (2006-03-22 22:13) [3]

Прямоугольник задан прямоугольными координатами двух противоположных вершин?

← →
Sergey Masloff (2006-03-22 22:18) [4]

Джо © (22.03.06 22:13) [3]
Ну как двумя? Стороны м.б. не параллельны осям...
Но все равно алгоритм нехитрый.

← →
Джо © (2006-03-22 22:20) [5]

> [4] Sergey Masloff (22.03.06 22:18)
> Джо © (22.03.06 22:13) [3]
> Ну как двумя? Стороны м.б. не параллельны осям...

Я поэтому и спросил. Иногда задается структурой TRect, двумя вершинами, стороны параллельны осям.

← →
имя (2006-03-22 23:06) [6]

Удалено модератором

← →
Просто Лёха (2006-03-23 10:56) [7]

Удалено модератором
Примечание: Оффтоп...

← →
isasa © (2006-03-23 12:03) [8]

Обходишь прямоуголиник по кажной стороне (x1,y1,x2,y2), по часовой или против часовой(в одну сторону!).
Сторона - прямая, заданая вершинами(уравнение прямой, проходящей через две точки).
Если заданная точка лежит "с одной и той же стороны" прямых (в данном случае четыре), то она внутри четырехугольника.

← →
isasa © (2006-03-23 12:11) [9]

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

← →
grisme © (2006-03-23 17:37) [10]

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

← →
имя (2006-03-23 17:50) [11]

Удалено модератором

← →
Jeer © (2006-03-23 19:14) [12]

А не использовать ли тут общую теорию относительности ?
Самое место.

← →
Cash © (2006-03-23 22:14) [13]

Удалено модератором
Примечание: Модераторы, они, знаете-ли тоже люди :)

← →
Cash © (2006-03-23 22:50) [14]

Lexa11_2002 (22.03.06 21:52):
Гы! :)
Придумал!
Заведи себе для помощи запись из 4-х точек (TPoint).
А потом определяй, стоит ли требуемая точка между левой, правой, верхней
и нижней ограничивающими прямыми.

Функция ограничивающей прямой:
Function f(x: integer; P1,P2: TPoint): integer; var pr: single; begin if (P2.Y-P1.Y) <> 0 then pr:=(p2.X-P1.X)/(P2.Y-P1.Y) else pr:=0; Result:=Trunc((p1.Y-pr)+(pr*x)); end;

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

← →
Defunct © (2006-03-24 02:58) [15]

> isasa © (23.03.06 12:11) [9]
е-мае.. У прямоугольника углы прямые! Проще всего повернуть оси так, чтобы прямоугольник представить в виде TRect и сместить точку относительно прямоугольника, ну а дальше просто:

function PtInRect(Pt: Point; R: Rect):boolean;
begin
Result := (Pt.X >= R.Left ) and
(Pt.X <= R.Right) and
(Pt.Y >=R.Top) and
(Pt.Y <= R.Bottom)
end;

← →
isasa © (2006-03-24 12:11) [16]

Defunct © (24.03.06 02:58) [15]
Безусловно.
А теперь - функцию пересчета координат вершин прямоугольника(TRect)?
X(x1,y1...) -> TRect(...) ?

← →
Джо © (2006-03-24 14:01) [17]

Ага, тут с этими афинными преобразованиями функция выйдет совсем монструозной :) Ей-богу, быстрее будет [10] grisme.

← →
Defunct © (2006-03-24 15:54) [18]

> А теперь - функцию пересчета координат вершин прямоугольника(TRect)?

Хм.. ну собсно там формула простейшая (один cos и 1 sin):
поворот относительно точки (x1, y1) для точки (x4, y4) и для точки принадлежность которой требуется к прямоугольнику требуется найти.

Находим вектор поворота для точки (x4, y4) - складываем его с точкой (x4, y4) - TRect готов, дальше домножаем этот вектор на вектор образуемый точками (x4, y4) и искомой точкой, складываем полученный вектор с координатами точки.

← →
isasa © (2006-03-24 16:06) [19]

Defunct © (24.03.06 15:54) [18]
А координаты самой точки не надо пересчитывать?

Джо © (24.03.06 14:01) [17]
Ей-богу, быстрее будет [10] grisme.
Очень изящно. Запомнил. Но действительно для тех фигур где легко посчитать площадь, а [8] для всех "полностью выпуклых".
:)
Универсального способа не знаю

Defunct © (24.03.06 15:54) [18]
... и для точки принадлежность которой требуется к прямоугольнику требуется найти.

Сорри, недочитал. Тогда "выгоднее" поместить начало координат в одну из вершин ....

> Джо © (24.03.06 14:01) [17]
> Ага, тут с этими афинными преобразованиями функция выйдет
> совсем монструозной :) Ей-

Если сделать из него регион, то функция выйдет совсем простой
PtInRegion.

--
Regards, LVT.

isasa © (24.03.06 16:09) [20]

сории, да там одно слово "требуется" лишнее ;>
осталось там при редактировании так что это моя вина, что вы не заметили все сразу..

> Тогда "выгоднее" поместить начало координат в одну из вершин ....
Я бы сказал не "выгоднее", а нагляднее... Еще нагляднее поместить начало координат в точку (x1, y1). Хотя вычислительная сложность при этом незначительно [u]увеличится[/u].

А интересно, как "игроки" решают проблему :)

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

> [21] Leonid Troyanovsky © (24.03.06 16:25)

Да, только если координаты floating point, то привести к целым (простым умножением), ну, и вычесть минимальную координату, для подстраховки, ибо: "Region coordinates are represented as 27-bit signed integers". Сам так делал, для различных полигонов.

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

> (пересечение с вершиной считать за "адын")

извинияюсь, просчет... такую ситуацию нужно рассматривать отдельно...

Что касается "игороков", то можно сложить углы между векторами проведенными из заданной точки к вершинам прямоугольника (многоугольника). Если сумма всех углов равно 360 градусов - точка в прямоугольнике (многоугольнике).

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