ФорумПрограммированиеPHP для идиотов → Как быстро находить многоугольник, которому принадлежит точка?

Как быстро находить многоугольник, которому принадлежит точка?

  • Абырвалг

    Сообщения: 6480 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 14:28

    Вот есть народная карта, допустим я ее распарсил и получил точки вершин многоугольника каждого района. Таких многоугольников у меня дохуища. Как бы мне с минимальными затратами найти тот многоугольник, которому эта точка принадлежит?

    Брать все многоугольники и для каждого проверять 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 ?
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 14:46, спустя 18 минут 5 секунд

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

    Сообщения: 6480 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 14:56, спустя 10 минут 28 секунд

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

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 14:59, спустя 3 минуты 8 секунд

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

    Сообщения: 6067 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:13, спустя 13 минут 30 секунд

  • Абырвалг

    Сообщения: 6480 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:16, спустя 3 минуты

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

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 26 декабря 2011 г. 15:19, спустя 3 минуты 3 секунды

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

    Сообщения: 6067 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:19, спустя 16 секунд

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

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

    Сообщения: 6480 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:21, спустя 1 минуту 43 секунды

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

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:31, спустя 9 минут 55 секунд

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

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 26 декабря 2011 г. 15:32, спустя 1 минуту 6 секунд

    молодец костыль, чо )))
    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 26 декабря 2011 г. 15:36, спустя 4 минуты 20 секунд

    а я бы уже сделал блеядь :D
    Сапожник без сапог
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 26 декабря 2011 г. 15:38, спустя 1 минуту 44 секунды

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

Пожалуйста, авторизуйтесь, чтобы написать комментарий!