Определить, находится ли точка в области

#алгоритм #геометрия

Есть ряд точек на плоскости и есть область (например круг). Нужно определить, какие
точки входят в область.

Решение есть. Но оно подразумевает проверку каждой точки на вхождение в область. 
Натыкал я по рандому в редакторе 100000 точек. Нарисовал кружок. И вот я точно вижу,
какие точки входят в область. Я даже не знаю про существование остальных, потому что
область рисования огромна. А компьютер же будет перебирать все 100000 точек. А если
их миллион? А миллиард? В итоге время вычисления прямо пропорционально количеству точек,
тогда как человек с его тормознутостью даст ответ сразу. :)

Вот и подумалось мне, а как бы облегчить задачу программе? На ИИ я не претендую,
но разобравшись в вопросе, можно топорно научить компьютер решать такую задачу. Нужно
только понять, как это делает человек. На что обращает внимание. Какими величинами
оперирует. Уж точно не координатами :)

Еще пример. Я выбираю точку и мне нужно найти ближайшую к ней. Не хочется перебирать
все множество точек для этого.

UPD:

Есть вариант разбить всю область на подобласти с заданной детализацией. Каждую область
хранить в памяти как отдельный объект и добавляя точки в основную область, добавлять
их так же в подобласти (квадрат А2). Далее вычислять, какие подобласти пересекаются
с поверяемой областью и проверять на вхождение в проверяемую область уже не всех точек,
а лишь тех, которые содержатся в подобластях. В этом случае скорость поиска будет быстрее
лишь в тех случаях, когда количество точек значительно выше количества областей. Количество
областей зависит от детализации. Детализация будет зависеть от конкретной задачи (было
бы не очень хорошо, если бы размер подобласти приближался к размеру проверяемой области).
    

Ответы

Ответ 1

Несколько (не)очевидных моментов:


на картинке – все точки уже отсортированы самим своим расположением. Когда двигается
«окно», осуществляется выборка узкого диапазона значений. В базе данных – длинный список
безликих координат.
на картинке точки имеют ненулевую площадь, т.е. можно говорить об округлении их координат
до какой-то области.


Т.о. для быстрого решения, сравнимого со зрением нужно:


отсортировать координаты и построить индексы по X и Y, а может, и деревья для каждой
точки - расстояния до соседних, или только список ближайших. На бумаге это делается
в момент расстановки точек.
округлять, или, вернее, «оквадрачивать» : ) – значения координат точек квантизировать
до довольно крупной сетки. Форму окна - тоже - до угловатого подобия окружности, проходящего
всегда между узлами координатной сетки.


Тогда задача приблизится по условиям к «естественному» зрению и станет заметно быстрее.



Если дельше приближаться к зрению, которое, в какой-то степени, нечёткое, для ч/б
картинки задачу можно решить графически, не заморачиваясь распознаванием объектов.
Допустим, белый фон и чёрные точки. Считаем, что примерно известны средняя площадь
каждой черной точки и площадь окна. Размыть полностью картинку (Blur-Average в Photoshop).
Получится оттенок серого. Из пропорции серый : черный = N_точек : (площадь фигуры :
площадь точки) получаем примерное число точек.


Ответ 2

Есть ряд точек на плоскости и есть область (например круг). Нужно определить, какие
точки входят в область.


Как я сказал в комментарии, можно проверить каждый пиксел внутри области, и узнать,
находится ли там точка. Временная сложность этого алгоритма - O(n), где n означает
количество пикселов внутри области.

Человек не может считать быстрее. Может быть, нам кажется, например в следующей картинке,
что можем очень быстро определить, что там 4 точки внутри круга.



Но представьте, что у нас полная стена точек, а не маленькая область:



Теперь видно, что сложность задания для человека тоже зависит от размера области.
То есть, и для компьютера и для человека, временная сложность - O(n). И я уверен, что
компьютер может посмотреть всюду намного быстрее. Значит, наш алгоритм не быстрее,
так что зачем понять как это делает человек?


  Еще пример.  Я выбираю точку и мне нужно найти ближайшую к ней. Не хочется перебирать
все множество точек для этого.


Можно проверить пикселы вокруг точки, пока самая ближайщая точка не найдена. Скорость
этой алгоритм зависит от расстояния от самой ближайщей точки. Если d - расстояние,
то временная сложность этого алгоритма - O(d^2).


Ответ 3

Перебор точек - это действительно очень плохая идея. Даже перебор точек только внутри
области. 

Если речь идет об области в виде круга, то тут все просто, достаточно элементарной
геометрии. 
Уравнение окружности с центром в точке (x0, y0) и радиусом R, как известно, выглядит
так: 

(x - x0)^2 + (y - y0)^2 = R^2


соответственно, чтобы точка находилась внутри этой окружности, необходимо, чтобы
выполнялось такое условие: 

(x-x0)^2 + (y-y0)^2 <= R^2


В случае с многоугольниками есть распространенный метод подсчета пересечений. Смысл
его вот в чем: проводите из вашей точки луч в любом направлении и считаете, сколько
раз этот луч пересек ребра многоугольника. Для этого можно перебрать все ребра в цикле
и проверить для каждого, пересекает ли его ваш луч. Если число пересечений нечетно,
то точка лежит внутри многоугольника, если четно - снаружи. 
У этого алгоритма вполне приемлемая сложность по сравнению с полным перебором, пропорциональная
количеству перебираемых ребер. 

Впрочем, для выпуклых многоугольников есть еще более эффективный способ. О нем можно
почитать тут


Ответ 4

Допустим есть область 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.


Ответ 5

Если множество исходных точек хранится в БД, то для окошка правильной формы нетрудно
написать соответствующий запрос.
Если окошко имеет неправильные границы, то точки описанного прямоугольника (или другой
фигуры правильной формы) можно отобрать запросом в массив, а дополнительные проверки
провести внутри массива.