Как проверить принадлежит ли точка области
Этот вопрос был самостоятельно удалён автором .
- Проверить, принадлежит ли какая-либо точка отрезка заданной (заданным) окружностям
- Проверить попадает ли точка в заданную область
- Как вычислить, принадлежат ли точки коориднат заданному графику?
- Вхождение точки в заштрихованную облость
- Вхождение в область
Если вы думаете, что здесь чего-то не хватает, свяжитесь с нами.
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Попадание точки в заданную область (Алгоритм)
Пусть необходимо определить попадает ли заданная точка с координатами (x,y) в заданную область:
В данном случае, очевидно, что точка (x,y) попадает на линию графика, если у=x. Точка попадает в закрашенную область, лежит выше линии графика, если y>x. Наконец, точка (x, y) лежит ниже линии графика, если y if y>x then writeln('Да, попадает') else writeln('Нет');
Аналогично, точка (x, y) попадает в закрашенную область,
Рассмотрим попадание точки в круг. Уравнение окружности: x2+y2=r2, в представленном на рисунке случае r=1.
Алгоритм определения попадания точки в контур на основе комплексного анализа
Привет всем Хабра людям. Хочу представить уважаемым читателям пример, когда сухая и далекая от жизни в нашем понимании высшая математика дала не плохой практический результат.
Сначала немного воспоминаний
Было это в бытность мою студентом одного из технических Вузов в 90-е, курсе наверно втором. Попал я как-то на олимпиаду по программированию. И вот на этой самой олимпиаде и было задача: задать координаты треугольника, тестовой точки на плоскости, и определить принадлежит ли эта точка области треугольника. В общем, плевая задачка, но тогда я ее так и не решил. Но после задумался – над более общей задачей – принадлежность полигону. Повторюсь – была середина 90 –х, интернета не было, книжек по компьютерной геометрии не было, а были лекции по вышке и лаборатория 286 –х с турбо паскалем. И вот так совпали звезды, что как раз в то время когда я размышлял над проблемой, на вышке нам читали теорию комплексного переменного. И одна формула (о ней ниже) упала на благодатную почву. Алгоритм был придуман и реализован на паскале (к сожалению мой полутора гиговый винт погиб и унес в небытие этот код и кучу других моих юношеских наработок). После института я попал работать в один НИИ. Там мне пришлось заниматься разработкой ГИС для нужд работников института и собственной одной из задачей было определение попадания объектов в контур. Алгоритм был переписан на С++ и отлично зарекомендовал себя в работе.
Задача для алгоритма
Определить:
принадлежит ли точка области D, ограниченной полигоном.
Вывод формул для последующего написания алгоритма ни в коем случае не претендует на математическую полноту и точность, а лишь демонстрирует инженерный (потребительский подход) к Царице полей наук.
Интегральная формула Коши
Пояснение с рабоче-крестьянской инженерной точки зрения:
— граница Г наш заданный контур,
— z0 -тестируемая точка
— f(z) — комплексная функция от комплексного аргумента нигде в контуре не обращается в бесконечность.
Те есть, чтобы установить принадлежность точки контуру, нам необходимо вычислить интеграл и сравнить его со значением функции в данной точки. Если они совпадают, то точка лежит в контуре. Замечание: интегральная теорема коши гласит, что если точка не лежит в контуре, те подынтегральное выражение нигде не обращается в бесконечность, то интеграл равен нулю. Это упрощает дело – нужно лишь вычислить интеграл и проверить его на равенство нулю: равен нулю точка не контура, отличен — лежит в контуре.
Займемся вычислением интеграла. За f(z) примем простую функцию 1. Не нарушая общности можно за z0 принять точку 0 (всегда можно сдвинуть координаты). 
Избавляемся от мнимой единицы в знаменателе подынтегральной части и расщепим интеграл на действительную и мнимую части:
Получилось два криволинейных интеграла II рода.
Вычислим первый 
Выполнятся условие не зависимости интеграла от пути, следовательно, первый интеграл равен нулю и его вычислять не нужно.
С мнимой частью такой фокус не проходит. Вспоминаем, что наша граница состоит из отрезков прямых, получаем: 
Где Гi- это отрезок (xi,yi)- (xi+1,y i+1)
Вычислим i-ый интеграл. Для этого запишем уравнение i-го отрезка в параметрическом виде 
Подставим в интеграл 
и после громоздких и нудных преобразований получим следующую прельстивую формулу: 
Окончательно получаем 
Алгоритм на C++:
template <class T>
bool pt_in_polygon(const T &test,const std::vector &polygon)
<
if (polygon.size()<3) return false;
double sum=0.0;
for(
std::vector::const_iterator iter=polygon.begin();
iter!=end;
++iter
)
<
T cur_pt=*iter;
cur_pt.x-=test.x;
cur_pt.y-=test.y;
double del= last_pt.x*cur_pt.y-cur_pt.x*last_pt.y;
double xy= cur_pt.x*last_pt.x+cur_pt.y*last_pt.y;
sum+=
(
atan((last_pt.x*last_pt.x+last_pt.y*last_pt.y — xy)/del)+
atan((cur_pt.x*cur_pt.x+cur_pt.y*cur_pt.y- xy )/del)
);
return fabs(sum)>eps;
T – тип точки, например:
struct PointD
<
double x,y;
>;
Пример
Пример работы алгоритма написан с применением самой на мой взгляд великой библиотеки 2D графики:Anti-Grain Geometry (AGG) .
Управление:
клик левой кнопкой – добавление новой точки контура
правой кнопкой — замыкание контура
левой с зажатым Shift-ом – перенос тестовой точки
Господа, кому интересно, привожу более быстрый алгоритм. Уже не мой.
Отдельное и огромное спасибо forgotten за статейку.
template bool pt_in_polygon2(const T &test,const std::vector &polygon)
<
Точка в области
Проверьте, принадлежит ли точка данной закрашенной области:
Если точка принадлежит области (область включает границы), выведите слово YES, иначе выведите слово NO.
Решение должно содержать функцию IsPointInArea(x, y), возвращающую True, если точка принадлежит области и False, если не принадлежит. Основная программа должна считать координаты точки, вызвать функцию IsPointInArea и в зависимости от возвращенного значения вывести на экран необходимое сообщение.