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

MrSTEP · 11.11.2010, 11:08

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

Vladimir_S · 11.11.2010, 11:22

Цитата:

Сообщение от MrSTEP

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

Есть. Аналогичная задача была недавно на нашем форуме, и даже не для прямоугольника, а для произвольного многоугольника. Алгоритм таков: если многоугольник выпуклый (а для прямоугольника это справедливо всегда), то следует, соединив нашу точку со всеми вершинами многоугольника, сосчитать сумму углов между всеми соседними соединяющими линиями (углов с вершинами в данной точке). Если точка лежит внутри, то эта сумма составит 360°.

MrSTEP · 11.11.2010, 11:51

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

Vladimir_S · 11.11.2010, 11:58

Цитата:

Сообщение от MrSTEP

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

Не между точками - между лучами.
А тут самый простой путь - вооружиться любым учебником аналитической геометрии или математическим справочником (напр. Бронштейна и Семендяева) и выяснить:
1. Уравнение прямой, проведенной через две точки с заданными координатами (на плоскости).
2. Угол между двумя прямыми, заданными аналитически (опять же на плоскости).

MrSTEP · 11.11.2010, 13:58

Хм.. спасибо за совет, попробую

11.11.2010, 11:08	#1 (permalink)
MrSTEP 一步一步地会到目的 Регистрация: 09.05.2009 Адрес: Черноземье Сообщений: 10,939 Записей в дневнике: 10 Сказал(а) спасибо: 140 Поблагодарили 80 раз(а) в 33 сообщениях Репутация: 28362	Попадание точки в прямоугольник Здравствуйте. Была задана следующая задача: пользователь задает координаты вершин прямоугольника, затем координаты точки. Необходимо определить, попадает ли эта точка в прямоугольник. Понятно, что если прямоугольник расположен параллельно оси Х, то найти ответ можно путем сравнения координат точки и двух противоположных углов прямоугольника. Но как быть, если фигура лежит под углом, мы не сообразили. Подскажите, есть ли какие-то идеи по решению задачи?

11.11.2010, 11:51	#3 (permalink)
MrSTEP 一步一步地会到目的 Регистрация: 09.05.2009 Адрес: Черноземье Сообщений: 10,939 Записей в дневнике: 10 Сказал(а) спасибо: 140 Поблагодарили 80 раз(а) в 33 сообщениях Репутация: 28362	Все гениальное просто. Все простое гениально. Но что-то мы тремя головами не можем сообразить, как найти углы между точками?

11.11.2010, 13:58	#5 (permalink)
MrSTEP 一步一步地会到目的 Регистрация: 09.05.2009 Адрес: Черноземье Сообщений: 10,939 Записей в дневнике: 10 Сказал(а) спасибо: 140 Поблагодарили 80 раз(а) в 33 сообщениях Репутация: 28362	Хм.. спасибо за совет, попробую

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070