Оптимизация поиска полигонов

Question

Я разделил мир на X случайных многоугольников.

Затем мне дают координату C1, например (-21.45, 7.10), и я хочу приписать правый многоугольник этой координате.

Первое решение - применить мой алгоритм 'point_in_polygon' (учитывая набор координат, определяющих многоугольник, и координату, определяющую точку, скажите, находится ли точка внутри или нет) на каждом многоугольникепока я не найду правильный.Но это очень дорого, если у меня есть много точек, чтобы вставить много полигонов.

Улучшение, основанное на следующей идее: Для оптимизации поиска я создаю grid (набор) с шагом n, k , где я уже приписываю каждую пару координат таким образом:

for i=-180 to 180 step n 
    for j = -90 to 90 step k
        grid.add(i,j)

Затем я создаю словарь, и для каждой пары вВ коллекции я нахожу соответствующий многоугольник

For each g in grid
    For each p in polygons
        If point_in_polygon(g,p) == True
            my_dict(g) = p

Затем, когда я получаю C1, я ищу ближайшую координату в моей сетке, скажем, g1.Благодаря my_dict я могу быстро получить p1 = my_dict(g1) Затем я вычисляю point_in_polygon(C1, p1), что, вероятно, будет правдой.Если это не так, я нахожу ближайший g, который назначен другому многоугольнику, и я повторяю тест.И т.д., пока я не нашел правильный многоугольник.

Теперь вопрос: Какое оптимальное n, k для создания сетки?

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

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

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

Любые отзывы приветствуются!

Answer 1

Укажите любую точку и нарисуйте линию прямо от этой точки.Первое ребро полигона, которое вы ударили, говорит вам, в каком полигоне находится точка.

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

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

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

Google 'трапециевидныйразложение ", чтобы найти много информации о похожих методах.

Answer 2

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

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

Если бы мне пришлось угадывать, я бы сказал, что ваши клетки должны быть квадратными и иметь площадь около 1% - 5% средней площади полигона.Кроме того, более компактные полигоны могут обрабатываться более эффективно, чем многие длинные и тонкие полигоны.