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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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