| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм определения попадания точки в контур |
| Автор: Dementor 27.11.2014, 11:03 |
| Всем привет! Как всегда за помощью прихожу сюда. Итак, что имеется: в свое время, когда мне нужен был алгоритм определения попадания точки в контур, я отыскал подходящий http://habrahabr.ru/post/125356/. Представленный там алгоритм (самый конец статьи) работает достаточно быстро когда речь идет о достаточно небольшом объеме данных (например, отлично справляется с ситуацией, когда несколько сотен тысяч точек (даже миллион) и множество (до нескольких сотен) мелких контуров, состоящих из 4-5 вершин). Но сейчас я столкнулся с ситуацией, когда необходимо обработать несколько сотен миллионов точек при этом контуры, вхождения в которые я проверяю, могут состоять из десятков тысяч вершин. И вот тут возникает проблема - быстродействие просто ужасное. Понятно, что пути два (ну или я вижу только два): либо вводить потоки и кучу точек делить на количество ядер и далее каждое ядро будет проверять свою кучу, либо подыскать алгоритм, который сам по себе будет давать гораздо более адекватное быстродействие. Очень прошу подсказать существуют ли какой-то сверхбыстрый алгоритм для решения подобных задач? Дополнительно: в принципе т.к. важна именно скорость, то можно пожертвовать памятью - алгоритм может отжирать сколько ему угодно, лишь бы работал быстро. Заранее всем откликнувшимся огромное спасибо! |
| Автор: baldina 27.11.2014, 12:03 | ||
| насколько сложные формы контуров образует этот миллион точек? какова вероятность (на реальных данных), что тестовая точка находится внутри? можно сначала применять быстрый тест, например проверять на принадлежность описывающему прямоугольнику или окружности Добавлено @ 12:08
если контуры содержат небольшое число точек, быстрый тест не поможет. если число тестов велико, можно предварительно обработать полигоны, https://ru.wikipedia.org/wiki/K-%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE, и сначала определять в какую область попадает точка, а затем проводить тест только для полигонов, попадающих в эту область. |
| Автор: Dementor 27.11.2014, 12:15 |
| baldina, вероятность попадания точки мала. Такова сама задача (т.е. если рассматривать именно частную задачу) - если взять вообще все проверяемые точки, то в требуемые контуры попадет не более 5-10%. Я еще думал над расчетом выпуклой оболочки контура для каждого контура - заведомо количество вершин в ней будет на порядок меньше, а ее расчет достаточно прост и быстр. Т.е. фактически это тоже, что предлагаете и Вы (если я правильно Вас понял) - для начала посмотреть будет ли точка лежать внутри этой оболочки, а потом уже смотреть, а будет ли она лежать внутри самого контура. Это конечно некий костыль, но в общем-то производительность точно повысится. |
| Автор: baldina 27.11.2014, 12:51 | ||
да Добавлено через 5 минут и 46 секунд если области небольшие и примерно одинаковые по габаритам, можно поступить наоборот: проверить, какие точки контуров попадают в окружность c центром в тестируемой точке и радиусом равным среднему габариту, а дальше смотреть полигоны, которым принадлежат эти точки. еще можно построить триангуляцию всего множества точек, присвоив каждому треугольнику атрибут, указывающий какому полигону он принадлежит. поиск треугольника, в который попадает точка, очень быстрая процедура. |
| Автор: Dementor 27.11.2014, 13:13 |
| baldina, Попробовал с помощью выпуклых оболочек, которые создаются для каждого контура - прирост есть. Плюс дописал еще специфические костыли под саму задачу - тоже чуть подускорилось. Сами контуры разнятся как небо и земля - есть контуры, площадь которых не больше пары-тройки десятков метров, а есть такие, площадь которых уходит за десяток квадратных километров. Вот с триангуляцией я как-то не продумал. Да, если каждый контур выразить множеством треугольников, то нужно будет перебрать эту кучу до первого попадания и все... Надо будет проверить это - сам просто с триангуляцией не сталкивался (ну не с самой триангуляцией, а ее реализацией в коде). |
