caxapa.ru :: Поинтересуюсь: Кто как решает задачу определения вхождения точки с определенными координатами в полигон произвольной формы на карте? Например, имеется *.kml файл с несколькими десятками полигонов. Есть задача определить принадлежность точки

Гудвин, волшебник (22.04.2017 20:16, просмотров: 31495)

Поинтересуюсь: Кто как решает задачу определения вхождения точки с определенными координатами в полигон произвольной формы на карте? Например, имеется *.kml файл с несколькими десятками полигонов. Есть задача определить принадлежность точки какому-либо из них. Может есть какие-нибудь free онлайн сервисы для этого? Или (что лучше) свободные библиотеки? Дело для меня неизведанное. Ткните, плиз, носом... Я в принципе решил проблему. Правда нестандартно - через "задний проход". 40-50 строк скрипта на AutoIt. Пользую google maps, google my map и IE11 (mozilla, сцуко, шибко жручая для этой цели). Работает железно, но хочется узнать, как нужно/можно "правильно" ;)

Ответить

- Рапортую еще раз: Алгоритм классный - рекомендую. Прекрасно работает вот с таким объектами в количестве 505 штук. Принадлежность находит мгновенно. И даже вот так могЁт... (В "Tip" показывает имя объекта, расстояние до него от точки и направление Гудвин(2812 знак., 26.04.2017 20:45)
  - Если бы ты знал о методе contains класса Polygon из коллекции Java, то это сэкономило бы тебе немного трудозатрат - Petrovich(27.04.2017 10:56, )
    - Ога! И "Шестиум" вместо любимых Гудвиновских "mega328"? - Точка опоры(27.04.2017 15:15)
      - Примерно в 2.5 раза быстрее чем его реализация для 8-разрядника. Все дело в том, что не все итерации надо умножать... - Petrovich(27.04.2017 15:20, )
        
        Реализация не моя - спертая из тырнетов :) Скорость в PC более чем устраивает. Оно работает с реальными картографическими форматами в плавучке и этого за глаза... Взялся за это, прямо скажем, не свое дело, когда услышал, как эту задачу собираются Гудвин(526 знак., 27.04.2017 17:55)
        
        Вспылил... был неправ... Гудвин рассудит. - Точка опоры(27.04.2017 16:27)
  - Главное, чтобы после твоих рекомендаций снова где-нить Чернобыль не шарахнул. Или чтобы, очередной Фобос-в-Грунт не улетел. :) - Хаос(26.04.2017 21:22, )
    - Не. Эта фиговинка сугубо для внутреннего потребления :) - Гудвин(26.04.2017 21:30)
      - "Нам не дано предугадать, как наше слово отзовется.." - Хаос(26.04.2017 21:35, )
- Чтобы тред не превратился во флейм, рапортую о конкретике ;) Спасибо Генералу за ссылку. Там я благополучно пропустил все математические выкладки и почерпнул только одну важную штуку - имя функции для поиска в тырнетах "PtInPolygon" :) Ну и нашел Гудвин(1109 знак., 23.04.2017 19:53)
  - А чтой-то у тебя правый острый уголок после закраски заовалился? Не то что-то с границами - Petrovich(24.04.2017 16:38, )
    - Виноват: он был в полигоне до окраски не острый, но четкий. После заливки стал заметно плавным - Petrovich(24.04.2017 16:42, )
      - Сегодня тестю на реальной картографии. Есть карта в *.KML файле - 505 полигонов(объектов), максимальное количество точек в одном из них 317. Все вроде жужжит, как надо. Определение вхождения точки во все 505 полигонов занимает единицы Гудвин(15 знак., 24.04.2017 17:52)
        
        Проверьте, пожалуйста вхождение в квадрат 10,1 10,10 1,10 1,1 Олдфаг(166 знак., 24.04.2017 19:25, )
        
        У меня почему то не входит... может с паскаля не так перевел. - Олдфаг(24.04.2017 19:52, )
        
        Входит только точка 1.1. А что это меняет применительно к реальному полигону на карте? Гудвин(53 знак., 25.04.2017 16:42)
        
        Просто забей. Алгоритм говно, там деление на 0 не проверяется и делится как ни в чем не бывало :) - Petrovich(25.04.2017 10:20, )
        
        Аудитория у Ваших ног. Ждём хорошего алгоритма. - Крок(27.04.2017 17:00)
        
        В папке где находится java jdk есть архив src.zip - там есть все исходники. В нем есть каталог awt. В нем есть файл Polygon.java. В нем есть метод public boolean contains(double x, double y) - Petrovich(27.04.2017 17:36, )
        
        А смерть его находится в яйце... - Крок(27.04.2017 17:44)
        
        В левом или правом? :)) - MBedder(27.04.2017 18:02)
        
        Пошляк :) - Shatun_(28.04.2017 10:02)
        
        Нормальный алгоритм. Я туды конечно же вонзил проверку на ноль. Это же очевидно... Но на реальной картографии и без проверки тестил - ни разу в делителе нуль не появлялся. Тренирую "на кошках" - практических 505 полигонов (есть один аж с 371 Гудвин(189 знак., 25.04.2017 17:32)
        
        А где же окончательный вариант? Что делать если действительно знаменатель нуль? - Олдфаг(25.04.2017 19:10, )
        
        Заменить"исчезающе малым" значением Double... Повторюсь - этого ни разу не зарегистрировал. - Гудвин(25.04.2017 19:19)
        
        А в моем простеньком примере с вышеуказанным квадратом деление на нуль как назло проявилось - Олдфаг(25.04.2017 19:32, )
        
        Я тоже нарисовал такой квадрат после твоего поста. У меня все пучком. Гудвин(226 знак., 25.04.2017 20:36)
        
        Да не ~~бзди~~слушай скептиков, отличный алгоритм. И главное быстрый - 1111111(25.04.2017 18:18)
        
        Повторяю, медленный говноалгоритм. Проверил для AVR по его полигону для точки 400,250. Его реализация функции 14500 циклов, взятая из Джавы - 3500 циклов. Сразунах. Резюме: брать реализацию из ДжаваДок. Моя адаптация для 8-разрядников одинаковая и Petrovich(202 знак., 27.04.2017 15:45, )
        
        Ну дык! Поведай же в чем разница, в сути самой методы или тоже самое на каких то математических хитростях оптимизировали. Может там банально количество рассчетов в даблах разное вот и расхождение - 1111111(27.04.2017 22:17)
        
        Там целочисленная арифметика похоже. А "от латиноса" в даблах напрямую разруливает полигоны, ограниченные угловыми секундами. Вот она, эта круть: Гудвин(1763 знак., 27.04.2017 22:25)
        
        Точки то в интах заданы. Вот и весь вундерваффе. А смысл тогда задавать тестируюемую точку даблами? - 1111111(27.04.2017 23:01)
        
        Да не. Судя по приведенному коду, там все дело в continue-ловушках. Сравнение и новая итерация без математики. Меня смущает только вызов неведомой функции в начале кода. - Олдфаг(28.04.2017 08:17, )
        
        В общем суть такова что сравниваются конкретные реализации одного и того же быстрого алгоритма. При должном умении можно написать и вдесятеро медленее - 1111111(28.04.2017 09:07)
  - Все. Засасываю в дельфийную приблудку "*.KML" файл с картой объектов и координаты искомой точки. В выхлопе - имя объекта. Надо бы еще добавить "круг" или концентрическую спираль" с задаваемым диаметром, чтобы найти близлежащие объекты, ежели точка Гудвин(257 знак., 24.04.2017 04:51 - 04:56)
    - Я в принципе задачу решил до этого "черезжопным" способом с помощь тов. Брина :) Гудвин(2831 знак., 24.04.2017 05:01)
      - Абыдна только: Гугель берет пользовательсий '*.KML' c гуглодрайва по хэшу опубликованной карты в запросе, посылает его в браузер вместе с кучей JS, и JS "математика" работает у того же юзверя в браузере... Много лишних звеньев, трафика и жрачки Гудвин(121 знак., 24.04.2017 05:19 - 05:25)
  - Алгоритмически это подсчёт угла поворота в квадрантах - argus98(23.04.2017 20:05)
    - Вы юристом случайно не работали? Алгоритмически это подсчет количества пересечений - 1111111(23.04.2017 20:36)
    - ИМХО, считают четное или нечетное число раз приращение угла радиус-вектора меняет знак. USSR(255 знак., 23.04.2017 20:21, )
  - :) До Генерала эту ссылку давали здесь как минимум двое.. Гудвин - не читатель? :) - USSR(23.04.2017 20:01, )
    - Ну он произнес только одну команду ~~ФАС~~Хабр, я вынужден был исполнить :) - Гудвин(23.04.2017 20:06)
- Как уже заметили ниже, критерий нахождения точки внутри полигона = поворот угла радиус-вектора на 2pi argus98(768 знак., 23.04.2017 17:32 - 17:54)
  - Чтобы избежать тригонометрии нужно использовать алгоритм с лучем - 1111111(23.04.2017 17:37)
    - На, держи полигон и красную точку. Попробуй свой волшебный луч. PS Только не забывай, что между точками границы полигона есть (в общем случае) пропуски. Значительные. argus98(23.04.2017 18:00 - 18:04)
      - "Между точками границы полигона есть (в общем случае) пропуски" это как? Ведем луч ну хотя бы вправо - 4 пересечения = точка снаружи. Ведем влево - 2 = снаружи. Вверх - 4 = снаружи. Вниз - 2 = снаружи. - 1111111(23.04.2017 18:16)
        
        Как определить пересечения, если луч проходит МЕЖДУ точками. Напоминаю - по условиям задачи есть только точки границы полигона, а не граница сплошняком. Причём (если уж решать, то решать в общем виде) соседство точек в массиве совсем не означает argus98(121 знак., 23.04.2017 19:47)
        
        Полигон образован вешинами (точками из условия) и ребрами (отрезками между этими точками). Обисни мне тупому где там пропуски? В условии - полигон. А эта ерунда с индексами в массиве это не полигон а месиво точек - 1111111(23.04.2017 20:07)
        
        А что будет, если луч пройдет по касательной к границе полигона? - USSR(23.04.2017 18:30, )
        
        "Я тебе студент на зачете?" (с). В описании алгоритма есть условия которые нужно проверить - 1111111(23.04.2017 18:49)
- Может проще преобразовать полигон в растр? Если считать, что точность gps не лучше 10 метров, то точка растра соответствует квадрату площадью 1ар. На поле 100га надо 10Кточек. Накинуть еще запас +200% на кривую границу. ucMike(46 знак., 23.04.2017 17:11)
- Тут пугают "интегрирование угла", на самом деле это просто. Считаем вектора от точки до вершин. Суммируем разницы аргументов двух соседних векторов. Если результат равен 360, то внутри. Правда IBAH(78 знак., 23.04.2017 13:29)
- Да не, думаю, для «100500 точек» ничего лучше самого первого решения нет %) Обойти их все, интегрировать угол. Хотя вектора тоже соблазнительные — они в fixed-point считаются хорошо, это может перевесить. - Николай Коровин(23.04.2017 10:33)
- Еще вариант, через векторное произведение векторов. USSR(826 знак., 23.04.2017 10:05, )
  - Ошибся.. Площадь знак не меняет.. :( - USSR(23.04.2017 10:49, )
    - Короче, вот этот код до 10^6 точек вроде бы считает, если больше, то возникает переполнение: USSR(3133 знак., 23.04.2017 11:26, )
- Хабр - General(23.04.2017 09:04, ссылка)
- Проведите через точку прямую и посчитайте количество пересечений этой прямой с границами полигона, если четное - точка вне полигона, нечетное - внутри. ANV(103 знак., 23.04.2017 00:14)
- Вот, кстати, быстрый способ для выпуклого полигона. Отрезки перебираются последовательно. Если знак не меняется, точка внутри. - she(22.04.2017 23:56, ссылка)
- в книжках по программированияю игрушек (у мну была на си под досом еше, точно помню там было) - RED_DRAGON(22.04.2017 23:39)
- Возьмите прямые, образованные сторонами полигона. Опустите из точки на них нормали. Отбросьте те, которые пересекаются с прямыми вне пределов отрезка, являющегося стороной полигона. Выберите самую короткую нормаль. Николай Коровин(669 знак., 22.04.2017 23:28)
- если удастся сконвертировать в обычные координаты, вот этот алгоритм быстрый: ferrum(503 знак., 22.04.2017 23:22, ссылка)
- а сканирование не подходит? Тоесть просканировать все просранство по горизонтали и вертикали и составить альманах крайних точек север юг и запад востог для каждого полигона. Этим отсекутся все полигоны, которе не пересекаются с координатами Олдфаг(181 знак., 22.04.2017 22:56, )
  - Была подобная идея с "Монте-карло". "В лоб" Но это жеж какие надо ресурсы... - Гудвин(22.04.2017 23:01)
    - Ну, вот смотря какое зерно у карты.... по экрану 128х128 пикселов fill делал без проблем подобным образом - Олдфаг(22.04.2017 23:05, )
      - 128X128 - фигня. А если задача определить принадлежность координат полигону с разрешением 2 метра на реальной земной карте? Да и полигонов таких может быть сотня в процедуре определения координат... - Гудвин(22.04.2017 23:24)
        
        Тогда может хабр наведет на мыслю, если уже не предлагали Олдфаг(111 знак., 23.04.2017 07:25, )
- Ну вот ниасилил я фсю эту гэомэтрию :) Полигоны могут быть всяческие ("серпообразные загогулинины" и пр.), масштабы и расположение могут быть "где и как угодно". БоблиОтек не нарыл - все видать куркуют, а наш Евгений вообще наращивает Гудвин(290 знак., 22.04.2017 22:37)
  - Может на другие ГИСы посмотреть? - she(22.04.2017 23:24, ссылка)
- Полигон задан координатами вершин? тады так: IBAH(185 знак., 22.04.2017 22:26)
  - Это для выпуклого полигона. Впуклый придется бить на части. - she(22.04.2017 22:52)
    - Согласен. только ничего не надо бить на части. Тут пугают "интегрирование угла", на самом деле это просто. Считаем вектора от точки до вершин. Суммируем разницы аргументов двух соседних векторов. Если результат равен 360, то внутри. правда IBAH(76 знак., 23.04.2017 13:28)
- Бить на треугольники и работать с каждым отдельно. Возможно оптимизации типа проверки попадания в объемлющий прямоугольник, окружность и т.п. А про интегралы -- по второй ссылке (я ниасилил): fk0(33 знак., 22.04.2017 20:51, ссылка)
- ЕМНИП, в теории обходят полигон по контуру и интегрируют угол между отрезком, соединяющим точку на контуре полигона с "точкой с определенными координатами" принадлежность которой нужно определить и любой из декартовых осей координатной плоскости USSR(252 знак., 22.04.2017 20:38, )
  - Только есть одно условие. Линии, соединяющие вершины полигона, не должны пересекаться. Типа полигон из 4-х точек в форме песочных часов. Т.е. произвольный набор вершин нужноверифировать и разбивать на непересекающиеся полигоны - ig_z(22.04.2017 23:24)
    - Нет . Нежно чтоб полигон был оъявлен по-честному, то есть замкнутая не самопересекающая ломаная. И дальше все получится. Это же олимпиадная задача из нашего детства - Крок(24.04.2017 09:19)
  - похоже на правильное решение - General(22.04.2017 23:10)

Средства и методы разработки