Подскажите, пожалуйста, алгоритм нахождения полигона которому принадлежит заданная точка.
Суть такова:
Есть полигоны(выпуклые и не выпуклые без самопересечений)
Нужно определить вхождение точки в полигон.
Пробовал перебирать все полигоны проверяя на вхождение точки(методом луча, подсчёт углов, триангуляция) предварительно выбрав полигоны которые могут попасть под условия отбора(т.е. плюс минус X Y), но быстродействие никакое.
Может кто то сталкивался с данной задачей.

Бенедикт,

Таблица ~3 млн строк(id,lat, lon), от 8 секунд, экспериментирую пока.

полигоны имеют от 400 до 23000 точек

Бенедикт,

Могут иметь общие точки.
Пока на плоскости считаю.
Хочется вообще отказаться от таблицы(в бинарном виде как то хочу всё это описать, пока объёмы большие получаются).
Поиск многоугольников-кандидатов, при использовании таблицы на сервере сейчас самая не трудозатратная операция.

AndreTM,

Полигоны задаются точками которые описывают полигон по часовой стрелке(первая точка <> последней).
В среднем 2-3 кандидата отбираются.

Бенедикт,
Да, треугольники самое оптимальное, но память!

Бенедикт,

Пока неприемлемо вообще по времени.
Смысл примерно в следующем (в идеале), переместил курсор и получил номер страны, федерального округа, района, улуса.

Konst_One,

Пробовал - при большом количестве точек неприемлемо.
Хотя пробовал так «на посмотреть» надо ещё разок попробовать.

Я возьму тайм-аут, что бы не пудрить Вам мозг.
У меня смешалось всё(в коде, голове). Надо всё переосмыслить и опробовать ещё раз.
Спасибо за ответы!