Определить, принадлежит ли точка области
Определить, принадлежит ли точка области
Ввести координаты точки M(x,y). Определить, принадлежит ли точка области, ограниченной осью.
Определить, принадлежит ли точка области
как проверить лежит ли точка в областях 3 или 1? с 4 и 2 все понятно
Определить, принадлежит ли точка закрашенной области
Доброго времени суток! У меня появилась сложность в написании консольной программы. Задача: Для.
Определить, принадлежит ли точка заштрихованной области
По введённым с клавиатуры координатам точки (x;y) определить, принадлежит ли точка заштрихованной.
Попадание точки в заданную область (Алгоритм)
Пусть необходимо определить попадает ли заданная точка с координатами (x,y) в заданную область:
В данном случае, очевидно, что точка (x,y) попадает на линию графика, если у=x. Точка попадает в закрашенную область, лежит выше линии графика, если y>x. Наконец, точка (x, y) лежит ниже линии графика, если y if y>x then writeln('Да, попадает') else writeln('Нет');
Аналогично, точка (x, y) попадает в закрашенную область,
Рассмотрим попадание точки в круг. Уравнение окружности: x2+y2=r2, в представленном на рисунке случае r=1.
Определить, находится ли точка в области
Есть ряд точек на плоскости и есть область (например круг). Нужно определить, какие точки входят в область.
Решение есть. Но оно подразумевает проверку каждой точки на вхождение в область. Натыкал я по рандому в редакторе 100000 точек. Нарисовал кружок. И вот я точно вижу, какие точки входят в область. Я даже не знаю про существование остальных, потому что область рисования огромна. А компьютер же будет перебирать все 100000 точек. А если их миллион? А миллиард? В итоге время вычисления прямо пропорционально количеству точек, тогда как человек с его тормознутостью даст ответ сразу. 🙂
Вот и подумалось мне, а как бы облегчить задачу программе? На ИИ я не претендую, но разобравшись в вопросе, можно топорно научить компьютер решать такую задачу. Нужно только понять, как это делает человек. На что обращает внимание. Какими величинами оперирует. Уж точно не координатами 🙂
Еще пример. Я выбираю точку и мне нужно найти ближайшую к ней. Не хочется перебирать все множество точек для этого.
Есть вариант разбить всю область на подобласти с заданной детализацией. Каждую область хранить в памяти как отдельный объект и добавляя точки в основную область, добавлять их так же в подобласти (квадрат А2). Далее вычислять, какие подобласти пересекаются с поверяемой областью и проверять на вхождение в проверяемую область уже не всех точек, а лишь тех, которые содержатся в подобластях. В этом случае скорость поиска будет быстрее лишь в тех случаях, когда количество точек значительно выше количества областей. Количество областей зависит от детализации. Детализация будет зависеть от конкретной задачи (было бы не очень хорошо, если бы размер подобласти приближался к размеру проверяемой области).
Несколько (не)очевидных моментов:
- на картинке – все точки уже отсортированы самим своим расположением. Когда двигается «окно», осуществляется выборка узкого диапазона значений. В базе данных – длинный список безликих координат.
- на картинке точки имеют ненулевую площадь, т.е. можно говорить об округлении их координат до какой-то области.
Т.о. для быстрого решения, сравнимого со зрением нужно:
- отсортировать координаты и построить индексы по X и Y, а может, и деревья для каждой точки — расстояния до соседних, или только список ближайших. На бумаге это делается в момент расстановки точек.
- округлять, или, вернее, «оквадрачивать» : ) – значения координат точек квантизировать до довольно крупной сетки. Форму окна — тоже — до угловатого подобия окружности, проходящего всегда между узлами координатной сетки.
Тогда задача приблизится по условиям к «естественному» зрению и станет заметно быстрее.
Если дельше приближаться к зрению, которое, в какой-то степени, нечёткое, для ч/б картинки задачу можно решить графически, не заморачиваясь распознаванием объектов. Допустим, белый фон и чёрные точки. Считаем, что примерно известны средняя площадь каждой черной точки и площадь окна. Размыть полностью картинку (Blur-Average в Photoshop). Получится оттенок серого. Из пропорции серый : черный = N_точек : (площадь фигуры : площадь точки) получаем примерное число точек.
Есть ряд точек на плоскости и есть область (например круг). Нужно определить, какие точки входят в область.
Как я сказал в комментарии, можно проверить каждый пиксел внутри области, и узнать, находится ли там точка. Временная сложность этого алгоритма — O(n) , где n означает количество пикселов внутри области.
Человек не может считать быстрее. Может быть, нам кажется, например в следующей картинке, что можем очень быстро определить, что там 4 точки внутри круга.
Но представьте, что у нас полная стена точек, а не маленькая область:
Теперь видно, что сложность задания для человека тоже зависит от размера области. То есть, и для компьютера и для человека, временная сложность — O(n) . И я уверен, что компьютер может посмотреть всюду намного быстрее. Значит, наш алгоритм не быстрее, так что зачем понять как это делает человек?
Еще пример. Я выбираю точку и мне нужно найти ближайшую к ней. Не хочется перебирать все множество точек для этого.
Можно проверить пикселы вокруг точки, пока самая ближайщая точка не найдена. Скорость этой алгоритм зависит от расстояния от самой ближайщей точки. Если d — расстояние, то временная сложность этого алгоритма — O(d^2) .
Перебор точек — это действительно очень плохая идея. Даже перебор точек только внутри области.
Если речь идет об области в виде круга, то тут все просто, достаточно элементарной геометрии. Уравнение окружности с центром в точке (x0, y0) и радиусом R, как известно, выглядит так:
соответственно, чтобы точка находилась внутри этой окружности, необходимо, чтобы выполнялось такое условие:
В случае с многоугольниками есть распространенный метод подсчета пересечений. Смысл его вот в чем: проводите из вашей точки луч в любом направлении и считаете, сколько раз этот луч пересек ребра многоугольника. Для этого можно перебрать все ребра в цикле и проверить для каждого, пересекает ли его ваш луч. Если число пересечений нечетно, то точка лежит внутри многоугольника, если четно — снаружи. У этого алгоритма вполне приемлемая сложность по сравнению с полным перебором, пропорциональная количеству перебираемых ребер.
Впрочем, для выпуклых многоугольников есть еще более эффективный способ. О нем можно почитать тут
Допустим есть область N, она может быть любой, Даже неправильным многоугольником, и есть набор точек An, естественно проверять все точки на вхождение в область это очень долгий процесс, за исключением если эта область не прямоугольник, стороны которого параллельны осям X и Y. Вот тут и находим оптимизацию алгоритма.
Возьмем область N’ равную минимальному прямоугольнику, в который мы можем заключить область N, и отсеиваем все точки, которые в эту область не входят. Таких, видимо, будет предостаточно.
Теперь оставшиеся точки проверим на вхождение в сложную область N. Естественно мы должны проверить все точки, но алгоритм для сложных областей существенно повысит скорость.
PS: для проверки вхождения в область N’ не обязательно сразу проверять сразу все 4 условия вхождения в прямоугольник, лучше это сделать по очередности, и каждую следующую проверку делать при условии выполнения предыдущей, это уменьшит количество проверок в алгоритме как минимум в двое.
PS2: Если область N настолько неправильная, что заполняет 10% или даже менее области N’, то лучше сделать дополнительный упор на поиск нескольких областей N» для области N для наилучшего заполнения.
PS3: Если размеры всего поля точек заранее (до ввода точек) известны, то во время распределение точек кидать их также в стек массивов секторов S[x,y], который представляет заранее известные прямоугольные области. И выкидывать из проверки области не пересекающиеся с N’ (или N» при мультиоблостях). Тогда мы даже не будем рассматривать большую часть точек. Чем более раздроблена S, тем менее проверок точек необходимо будет сделать. Остается определиться с количеством областей Sxy, это можно сделать только экспериментальными или статистическими методами.
PS4: Если размеры заранее не известны, можно циклически-абстрактно повторять области Sxy в разные стороны, заранее задав размеры всей области S.
Алгоритм определения попадания точки в контур на основе комплексного анализа
Привет всем Хабра людям. Хочу представить уважаемым читателям пример, когда сухая и далекая от жизни в нашем понимании высшая математика дала не плохой практический результат.
Сначала немного воспоминаний
Было это в бытность мою студентом одного из технических Вузов в 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)
<