Алгоритм точки в многоугольнике для нескольких многоугольников

Question

У меня есть карты Google с кучей полигонов.

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

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

Answer 1

Я не знаю, что под ним, но применяя пространственный фильтр к слою, содержащему многоугольник, предварительно выбираю многоугольники для меня ... Например, void GRLayer::SetSpatialFilter ( OGRGeometry * poFilter) http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169. I Представляю, что во многих ГИС-средах есть похожая особенность.

Answer 2

Единственный способ улучшить алгоритм «для каждого многоугольника» - это создать набор метаданных, которые позволят вам пропустить некоторые многоугольники.Например, если для ваших тысяч полигонов у вас есть список или набор списков всех полигонов, которые перекрывают друг друга, то вы сможете быстро устранить множество сравнений точек-полигонов.Т.е. найдите первый многоугольник, который содержит точку, затем сравните только те многоугольники, которые пересекают / перекрывают этот исходный многоугольник, потому что любой многоугольник, содержащий точку, также должен перекрывать какой-то другой многоугольник, который ее содержит.Наихудшим случаем будет N сравнений, например, ваше для каждой реализации.

Вы также можете создавать логические / физические области многоугольников, такие как, например, квадранты, многоугольников в определенной области.В примере с квадрантом вы можете / должны иметь возможность удалить 3/4 полигонов для сравнения.Это все зависит от того, как устроены ваши полигоны.

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