Привет всем!

Есть сеть точек и некий полигон, граница которого обозначена ломаной линией (см. Example.png), нужно получить те точки, которые попали в полигон. 
Какое решение будет оптимальным?
Количество точек может быть 1000000, при этом полигон может охватывать ~30%




Это сообщение отредактировал(а) W4FhLF - 11.12.2011, 19:14

Присоединённый файл ( Кол-во скачиваний: 26 )
 Example.png 46,67 Kb

Вертикальная декомпозиция?

Рассмотрим все иксы, в которых имеются вершины полигона, и отсортируем их: пусть это x[1] ... x[n]. Тогда внутри каждой вертикальной полосы x[i]..x[i+1] нет вершин полигона. Т.е., зафиксировав некоторую полосу x[i]...x[i+1], мы получим, что все стороны полигона либо пересекают всю эту полосу, либо совсем не пересекают (граничные касания в точке x[i] или x[i+1] нас не интересуют). Мы можем построить список таких сторон в порядке их следования снизу вверх, а также построить список точек, попавших в эту полосу x[i]...x[i+1]. Просматривая полосу снизу вверх, у нас будут события двух видов: "встретили сторону" (что значит, что мы зашли внутрь полигона, или, наоборот, вышли из него - если были внутри), и "встретили точку" - тогда ответом для этой точки будет просто текущее значение флага "внутри_полигона".

Асимптотика решения - O(n^2 log n + m log m), где n - количество вершин в полигоне, m - количество точек. Если у вас n тоже большое, то не прокатит. (Впрочем, если полигон не имеет очень сложной конфигурации, то n^2 почти наверняка превратится в что-то порядка n - особенно если повернуть всю картинку на случайный угол.)

По асимптотике более надёжным выглядит такой вариант: сканировать всю картину слева направо вертикальной прямой: эта прямая движется с x=-INF до x=+INF, и, пока она движется, она встречает события трёх типов:
1) вертикальная прямая начинает пересекать какую-то сторону полигона;
2) вертикальная прямая заканчивает пересекать какую-то сторону полигона;
3) на вертикальную прямую попадает точка-запрос.

Если мы будем поддерживать текущий список пересекаемых нами сторон в порядке их следования по игреку (в виде сбалансированного дерева (например, set<> в C++)), то обрабатывать события типа 3) становится тоже понятно как: мы просто находим сторону, ближайшую к нам снизу, и смотрим, какую чётность имеет эта сторона в списке (нечётная - значит, точка-запрос лежит внутри полигона, чётная - вне).

Это решение уже гарантирует нормальную асимптотику O ((n + m) log n), но аккуратно написать его - не самая простая задача.

maxdiver, последний вариант звучит хорошо.  "Точка-запрос" в вашем описании это что? Любая точка на вертикальной линии, которая принадлежит сети?

PS Количество вершин небольшое (< 100)

Точки-запросы - это те самые 1000000 точек, которые надо проверить на принадлежность полигону.

Во втором алгоритме мы "сканируем" всё вертикальной прямой слева направо, останавливаясь на иксах, равных иксам вершин полигона либо иксам точек-запросов.

Если количество вершин всего 100, то я бы всё же советовал первый вариант - он весьма просто пишется, и достаточно эффективен (самое узкое место в нём - это отсортировать точки по их игреку, а всё остальное работает за линейное время - ну т.е. за 1000000 + 100^2). (Наверное, я в том посте невнятно написал про асимптотику - чтобы понятнее, в вашем случае асимптотика превратится в O (100^2 * log(100) + 1000000 * log (1000000)), что не так и много - примерно как обычная сортировка).

Это сообщение отредактировал(а) maxdiver - 12.12.2011, 00:57

Я бы реализовал это методом суммирования углов. Сложность как O(n*m) (т.е. 1000000*100), легко пишется, легко параллелится, легко ускоряется (векторизуется).

Для прикола еще такой метод:

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

Можно еще и сэкономить на проверке что с чем граничит. Для этого при заливке заменяем на желтый не только белый фон, но и сами черные точки. Потом проверяем по координатам точек. Если в данных координатах пиксель пожелтел - значит точка была внутри полигона. Жаль только, что сами точки при этом трагически гибнут  

И еще. Если понятия "внутри полигона" и "на линии полигона" различать не надо, заливку надо проводить красным, т.е. цветом самого полигона.

Метод описанный на той же страничке с количеством пересечений ребёр с произвольным лучом имеют такую сложность и легко параллелится. Чем метод суммирования углов лучше?

Но вообще сложность алгоритма предложенного maxdiver'ом всё равно меньше получается. 


_Y_, исходная задача никакого отношения к изображениям не имеет  

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

Интересно, что, кажется, второй алгоритм можно превратить в онлайновый алгоритм (т.е. написать алгоритм таким образом, чтобы он отвечал на запрос для одной указанной точки, за время O (log n)).
В самом деле, второй алгоритм основывается на хранении списка сторон полигона, и поддержании этого списка при движении слева направо. Тупо сохранять все варианты этого списка после каждого изменения - не хочется (потому что получится O (n^2) памяти), но без этого никуда, если мы хотим отвечать на запросы в онлайне.
Выход - персистентные деревья. В самом деле, любая вставка/удаление в красно-чёрном дереве приводит к изменении O(log n) вершин красно-чёрного дерева. И если мы будем не менять значения в вершинах, а создавать новые экземпляры изменяемых вершин, то мы тем самым и старое дерево не изменим, и в то же время получим новое дерево. Таким образом, при каждой вставке/удалении в красно-чёрном дереве будет дополнительно выделяться O (log n) памяти, но зато мы в итоге получим компактное представление всей истории изменения списков.

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

P.S. При ручной реализации, конечно, стоит использовать не красно-чёрные, а декартовы деревья: они пишутся гораздо проще, а асимптотику имеют ту же.

А я и не настаиваю  

Кстати, если степень дискретизации шкал не очень большая, т.е. если поле можно представить растром не астрономических размеров, то для динамической задачи алгоритм будет самым быстрым:

1. Заранее стриоим растр с залитым полигоном.
2. Каждую вновьприбывшую точку просто проверяем на предмет попадания в поле нужного цвета.

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

Но это весьма частный случай, конечно.

Реализовал в итоге простейший алгоритм с подсчётом пересечений, думал как первый черновой вариант пойдёт, оказалось, что работает быстро, глазом моргнуть не успеваешь, а это главный критерий.  

Сетка регулярная значит алгоритм не отличается от алгоритма рисования закрашенного многоугольника.
Можно подсмотреть в любой графической бибилиотеке.

Второй способ.
Задача решается при помощи подвижного контура.
Берётся точка с заведомо известным координатами внутри полигона.
Такую точку легко найти из координат заданного многоугольника.
Вокруг точки строиться подвижный контур. Который будет разрастаться. 
Разрастаться он будет по контуру перемещаясь либо до ближаших точек к соседним либо если при разрастания произошло пересечение с заданным контуром, то помечаем сегмент пренадлежашей этому контуру.