Разметка графика для определения точки

Question

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

Теперь у меня есть координата точки, какой лучший алгоритм сказать мне, в каком состоянии указать точку?

Конечно, я могу подобрать суб-область по суб-области, но это глупо, потому что я должен искать половину из них в среднем праве?

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

Answer 1

Я бы начал с устранения всех областей, которые не могут иметь точку внутри них.

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

Затем вы можете отсортировать площади по их наименьшей и наибольшей координатам x и y (всего 4 способа сортировки). Вы можете устранить все области, которые имеют их наименьшее x координат больше, чем x координаты вашей точки и т.д.

После этого, вы можете проверить оставшиеся полигоны с простым ray-casting algorithm, и вы должны быть хорошо.

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