4

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

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

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

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

UPD:

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

9
  • 1
    Можно проверить каждый пиксел внутри круга, и узнать, находится ли там точка. Этот алгоритм быстрее проверки каждой точки только тогда, когда количество точек вне круга больше количество пикселов внутри круга. 12 окт 2015 в 7:16
  • Тут ещё важно понимать что за область (Как задана? Выпуклая или нет?) 12 окт 2015 в 7:20
  • @PeterOlson, да да, думал об этом. Тут компьютеру будет важна детализация, а человеку она не так важна (в пределах детализации сетчатки, а детализация сетчатки довольно большая). То есть скорость вычисления будет зависеть от детализации и от размера области. Тоже не подходит.
    – iRumba
    12 окт 2015 в 7:33
  • 1
    @iRumba , конечно здорово видеть всю картину в целом, практически мгновенно отмечая примерное местоположение точек и их примерное кол-во, однако в том-то и дело, что ключевым словом здесь является именно "примерное". Попробуйте ответить самому себе после быстрого рассмотрения картинки, по какому индексу (координатам) находится любая из обнаруженных Вами точек.
    – user177227
    12 окт 2015 в 7:49
  • 1
    @iRumba , такое ощущение, что речь идёт о дереве квадратов, только вместо, собственно, квадратов должен браться круг.
    – user177227
    12 окт 2015 в 10:35

5 ответов 5

4

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

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

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

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

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


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

5
  • Мне в конечном счете пришла в голову эта же мысль. Однако в моем случае (в области применения) у меня есть сфера. А вот как отсортировать точки по широте и долготе я не представляю. И округление не легче получится. Ведь на экваторе отклонение угла будет большим фактическим значением, чем отклонение у полюсов. В итоге на экваторе я получу детализацию ниже. Во всяком случае по долготе. А на отклонениях на 90 градусов от нулевого меридиана и по широте. Короче задал вопрос, а потом понял, что его решение применить скорее всего не смогу. :(
    – iRumba
    28 окт 2015 в 11:14
  • Think global, act local : ) Ведь область интереса каждый раз маленькая, относительно глобуса, так что ближайшее окружение можно считать плоским? Сделать раздутый индекс отдельных перекрывающихся областей, где все точки спроецированы на плоскость, с двумерными координатами. А ещё посмотрите, как это сделано в ElasticSearch напр. – там геоточки как раз кластеризуются на сетку каждый раз при отображении в Kibana. При увеличении масштаба просмотра сетка перестраивается. Но всегда точки группируются по ортогональной сетке.
    – Sergiks
    28 окт 2015 в 11:23
  • Так если я разверну сферу, то я потеряю возможность пройти ее по кругу, а смогу только по прямой от начального Х до конечного. Ну или как то так.
    – iRumba
    28 окт 2015 в 11:40
  • Опишите область применения, а то я то плоскую бумажку представлял, то традиционные задачи на поверхности Земли : )
    – Sergiks
    28 окт 2015 в 11:43
  • 1
    В общем то мне всего то нужно рассчитать кратчайший путь из аэропорта А в аэропорт Б с учетом максимальной дальности полета. Учебная задачка. В учебном варианте я бы просто обошел граф. Но очень хочется придумать универсальное решение не только для 1000 аэропортов по миру, но и для 100000 аэропортов в будущем (представьте, сколько будет ребер уже), или для хреновой тучи планет в совсем далеком будущем. Чтобы эту задачку в итоге использовать в дипломе )
    – iRumba
    28 окт 2015 в 11:56
3

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

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

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

введите сюда описание изображения

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

введите сюда описание изображения

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

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

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

7
  • Добавлю только, что обычно применяют достаточно большие «пикселы», и называют это кластеризацией.
    – VladD
    12 окт 2015 в 9:06
  • Тут будет либо большая погрешность либо медленный поиск. Если человеку дать задачу посчитать все точки на стене, то он, конечно, провозится долго. Однако если начертить на стене кружок, в котором будет 1-10 точек, то он справится быстрее, а вот компьютер будет пересчитывать всю стену. Я же хочу научить компьютер отбрасывать ненужные точки. Точнее вообще их не видеть, как это делает человек.
    – iRumba
    12 окт 2015 в 9:12
  • если начертить на стене кружок, в котором будет 1-10 точек, то он справится быстрее, а вот компьютер будет пересчитывать всю стену - почему? Человек и компьютер оба могут искать только в кружке. 12 окт 2015 в 9:15
  • Конечно. Только человек скажет либо точнее либо быстрее )) Попробуйте увеличить детализацию кружка и количество точек в нем для проверки компьютером резко увеличится. Исключение - когда две точки будут находиться почти друг на друге. Тогда человек их не различит и примет за одну. Но если их развести по одной координате, но сохранить другую, то человек разберется, быстро, а вот компьютеру с таким уровнем детализации придется повозиться
    – iRumba
    12 окт 2015 в 10:05
  • ну представьте, что координата точки задана с точностью до 1 знака после запятой. Тогда компьютеру придется проверять все с точностью до 1 знака, а это в 10 раз больше, чем в случае с целыми числами. А если у нас точность 8 знаков после запятой?
    – iRumba
    12 окт 2015 в 10:10
1

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

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

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

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

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

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

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

2
  • Я ведь написал в вопросе, что определить, находится ли точка в области - не проблема. Проблема в том, что если в базе находится большое количество точек, то такую задачу компьютер будет решать очень долго.
    – iRumba
    12 окт 2015 в 8:03
  • @iRumba, а, черт, не заметил
    – DreamChild
    12 окт 2015 в 8:06
1

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

Графическое представление

2
  • Полезная информация. Однако я имел ввиду кое что другое. Представьте, что есть огромная стена с точками. На ней (на переднем плане) располагается окошко, которое можно перемещать. Так вот вы можете взять и посчитать все точки, которые вам видны через это окно, ДАЖЕ НЕ ЗНАЯ О СУЩЕСТВОВАНИИ ОСТАЛЬНЫХ. Вы можете даже сказать их цвет. Компьютеру же для этого придется перебирать все точки и сравнивать их координаты с областью. Вопрос, в чем тут подвох? Мне эта мысль не дает покоя :)
    – iRumba
    28 окт 2015 в 8:58
  • обновил ответ.. 28 окт 2015 в 10:36
-1

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.