Вот есть народная карта, допустим я ее распарсил и получил точки вершин многоугольника каждого района. Таких многоугольников у меня дохуища. Как бы мне с минимальными затратами найти тот многоугольник, которому эта точка принадлежит?
 
Брать все многоугольники и для каждого проверять http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83 ?

Абырвалг, область видимости сократи для начала, а потом проверяй. Любой многоугольник можно вписать в прямоугольники, если данные находятся в базе то можно с участием индексов выбрать все прямоугольники в которых есть эта точка, а потом там хуйня останется..

с прямоугольниками - да, все просто, там тупо WHERE lat BETWEEN lat_from AND lat_to AND lng BETWEEN lng_from AND lng_to. Окей, спасибо

Абырвалг, в MS SQL есть уже готовые штуки для вычисления, не  знаю может в PostgreSQL уже тоже есть или в MySQL

читал?

учитывая то, что я несколькими сообщениями ранее ссылку на эту статью кинул - да) Костян разрулил вопрос, спасибо ему, тема собственно говоря исчерпала себя.

Я когда-то игрухи писАл ))) Если многоугольников много, надо на первом проходе отсеять заведомо неподходящие. Тебе надо знать мин/макс координаты точек для каждого из них, т.е. координаты "описывающего" прямоугольника. С ними сравниваешь точку.
Если грубый тест прошел - считаешь по алгоритму трассировки луча. А если заранее потрудиться и разбить многоугольники на множество ВЫПУКЛЫХ многоугольников, то считать можно вообще влет.

Абырвалг

учитывая то, что я несколькими сообщениями ранее ссылку на эту статью кинул - да)

ухахаах сори )))
Там просто в ссылке кракозябры я и щелкать на неё не стал ))

artoodetoo, да, об этом и написал kostyl

Абырвалг, да, только ВЫПУКЛОСТЬ, как заметил artoodetoo может повлиять, так что ты смотри

молодец костыль, чо )))

а я бы уже сделал блеядь :D

Вообще я слышал что то подобное на видео из какой-то PHP конфе толи 2006 толи 2007, там чуваки на постгри делали поиск ближайших ресторанов или типа того...