Поскольку вы не вставляете / удаляете и, по-видимому, у вас достаточно времени для предварительной обработки данных, вы можете использовать дополнительную память для ускорения вычислений. Основная идея для предварительной обработки:
- Возьмите все точки многоугольника и определите наименьший ограничивающий прямоугольник с осями, содержащий их все; в основном это мин и макс X и Y.
- Выберите коэффициент распределения dX и dY, который вы будете использовать для создания поисковой сетки. Выбор степеней двух для коэффициентов разделения может привести к несколько более быстрому вычислению позже.
- Переведите данные многоугольника так, чтобы их минимум ограничивающего прямоугольника совпадал с (0,0), и разверните прямоугольник так, чтобы он был кратным целому числу коэффициента разделения в каждом измерении.
- Рассмотрим каждый квадрат сетки и составьте список полигонов, которые пересекают квадрат. Сохраните этот список для каждого квадрата сетки. В зависимости от характера данных (сколько полигонов вы можете ожидать пересечения с квадратом), есть несколько способов оптимизировать это для пространства хранения или скорости.
Теперь, когда вы хотите найти регионы, содержащие точку:
- Переведите точку, используя начало, которое мы определили ранее, и определите квадрат сетки, содержащий точку (если вы использовали степень два, это операция сдвига; в противном случае это деление).
- Посмотрите на список для квадрата сетки. Если он пуст, то в нем нет содержащего многоугольника. Если нет, вы должны рассмотреть каждый из многоугольников в списке и найти пересечение.
Это хорошо работает для разбросанных и в основном непересекающихся многоугольников, особенно если вы можете выбрать достаточно точный размер сетки, чтобы на квадрат приходилось всего несколько многоугольников. Это будет медленно в тех случаях, когда вы попадаете на квадраты с множеством пересекающихся полигонов. Одна дополнительная оптимизация состоит в том, чтобы иметь флаг для каждого перечисленного многоугольника в квадрате, чтобы указать, что квадрат полностью содержится внутри многоугольника; это позволяет избежать теста на медленное сдерживание во многих случаях за счет одного бита на вход в полигон. Это особенно ценно, если ваш интервал сетки будет хорошим по сравнению с размерами многоугольника, так как большинство квадратов не будут находиться на пересечениях или краях.
Если вам нужна еще большая скорость, вы можете начать хранить информацию о ребрах в каждом квадрате с помощью ссылки на полигон. Вам нужно только проверить на ребра многоугольника, которые фактически пересекают площадь квадрата. Это может уменьшить усилия до нескольких тестов ребер на полигон.