Какая структура пространственных данных (алгоритм) лучше всего подходит для (поиска) набора регионов (пространственных данных)?

Поскольку вы не выполняете вставку/удаление и, по-видимому, у вас достаточно времени для предварительной обработки данных, вы можете использовать дополнительную память для ускорения вычислений. Основная идея предварительной обработки:

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

Теперь, когда вы хотите найти регионы, содержащие точку:

1. Переместите точку, используя начало координат, которое мы определили ранее, и определите квадрат сетки, содержащий точку (если вы использовали степень двойки, это операция сдвига; в противном случае это деление).
2. Посмотрите на список квадратов сетки. Если оно пустое, содержащего полигона нет. Если нет, то придется рассматривать каждый из полигонов в списке и искать пересечение.

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

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

Для этой задачи можно использовать структуру данных R-Tree.