Вот есть народная карта, допустим я ее распарсил и получил точки вершин многоугольника каждого района. Таких многоугольников у меня дохуища. Как бы мне с минимальными затратами найти тот многоугольник, которому эта точка принадлежит?
Брать все многоугольники и для каждого проверять 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 ?
новые сообщения
ответы на мои сообщения
избранное
скрытые темы
случайный топик
открыть всё в новых вкладках
Форум → Программирование → PHP для идиотов → Как быстро находить многоугольник, которому принадлежит точка?
Как быстро находить многоугольник, которому принадлежит точка?
-
Сообщения:
6480
Репутация:
N
Группа:
Джедаи
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 2:46, спустя 18 минут 5 секунд
Абырвалг, область видимости сократи для начала, а потом проверяй. Любой многоугольник можно вписать в прямоугольники, если данные находятся в базе то можно с участием индексов выбрать все прямоугольники в которых есть эта точка, а потом там хуйня останется.. -
Сообщения:
6480
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 2:56, спустя 10 минут 28 секунд
с прямоугольниками - да, все просто, там тупо WHERE lat BETWEEN lat_from AND lat_to AND lng BETWEEN lng_from AND lng_to. Окей, спасибо
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 2:59, спустя 3 минуты 8 секунд
Абырвалг, в MS SQL есть уже готовые штуки для вычисления, не знаю может в PostgreSQL уже тоже есть или в MySQL
-
Сообщения:
6067
Репутация:
N
Группа:
Джедаи
-
Сообщения:
6480
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 3:16, спустя 3 минуты
учитывая то, что я несколькими сообщениями ранее ссылку на эту статью кинул - да)Спустя 23 сек.Костян разрулил вопрос, спасибо ему, тема собственно говоря исчерпала себя.
-
Сообщения:
5147
Репутация:
N
Группа:
в ухо
26 декабря 2011 г. 3:19, спустя 3 минуты 3 секунды
Я когда-то игрухи писАл ))) Если многоугольников много, надо на первом проходе отсеять заведомо неподходящие. Тебе надо знать мин/макс координаты точек для каждого из них, т.е. координаты "описывающего" прямоугольника. С ними сравниваешь точку.
Если грубый тест прошел - считаешь по алгоритму трассировки луча.Спустя 93 сек.А если заранее потрудиться и разбить многоугольники на множество ВЫПУКЛЫХ многоугольников, то считать можно вообще влет.ιιlllιlllι унц-унц -
Сообщения:
6067
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 3:19, спустя 16 секунд
учитывая то, что я несколькими сообщениями ранее ссылку на эту статью кинул - да)
ухахаах сори )))
Там просто в ссылке кракозябры я и щелкать на неё не стал )) -
Сообщения:
6480
Репутация:
N
Группа:
Джедаи
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 3:31, спустя 9 минут 55 секунд
Абырвалг, да, только ВЫПУКЛОСТЬ, как заметил artoodetoo может повлиять, так что ты смотри
-
Сообщения:
5147
Репутация:
N
Группа:
в ухо
-
Сообщения:
26646
Репутация:
N
Группа:
в ухо
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
26 декабря 2011 г. 3:38, спустя 1 минуту 44 секунды
Вообще я слышал что то подобное на видео из какой-то PHP конфе толи 2006 толи 2007, там чуваки на постгри делали поиск ближайших ресторанов или типа того…
Пожалуйста, авторизуйтесь, чтобы написать комментарий!