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

Question

[E6APB]

Как найти, в каком полигоне находится точка?
У меня в таблице polygons хранятся полигоны районов РФ. Их 8 штук, планируется большое увеличение их количества. Структура:

region_id (int), lat (decimal, 8, 6), lng (decimal, 9, 6).

region_id - ID района
lat - широта точки
lng - долгота точки

Как найти, к какому полигону принадлежит точка? Как оптимизировать запрос под нагрузки? Мне нужно узнать лишь region_id полигона

Гугл дает только инфу как проверить что точка в регионе

Answer 1

[longclaps]

тыц

Comments

[E6APB]

спасибо, а есть решение без Polygon от mysql? А то ларавел со своими миграциями не позволяет)

[longclaps]

E6APB: Хотите поработать руками? Это можно ).
1. Подготовьте данные: побейте каждый полигон на треугольники. Для невыпуклых полигонов надо быть аккуратным.
2. Напишите код для проверки, относится ли точка к треугольнику - это несложно.
3. Создайте вспомогательную стуктуру - кэш по квадратной сетке, в каждой клетке - треугольники, которые на неё попадают.
4. Теперь всё будет летать.