-
- Рапортую еще раз: Алгоритм классный - рекомендую. Прекрасно работает вот с таким объектами в количестве 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)
- Примерно в 2.5 раза быстрее чем его реализация для 8-разрядника. Все дело в том, что не все итерации надо умножать... - Petrovich(27.04.2017 15:20, )
- Ога! И "Шестиум" вместо любимых Гудвиновских "mega328"? - Точка опоры(27.04.2017 15:15)
- Главное, чтобы после твоих рекомендаций снова где-нить Чернобыль не шарахнул. Или чтобы, очередной Фобос-в-Грунт не улетел. :) - Хаос(26.04.2017 21:22, )
- Не. Эта фиговинка сугубо для внутреннего потребления :) - Гудвин(26.04.2017 21:30)
- "Нам не дано предугадать, как наше слово отзовется.." - Хаос(26.04.2017 21:35, )
- Не. Эта фиговинка сугубо для внутреннего потребления :) - Гудвин(26.04.2017 21:30)
- Если бы ты знал о методе contains класса Polygon из коллекции Java, то это сэкономило бы тебе немного трудозатрат - Petrovich(27.04.2017 10:56, )
- Чтобы тред не превратился во флейм, рапортую о конкретике ;) Спасибо Генералу за ссылку. Там я благополучно пропустил все математические выкладки и почерпнул только одну важную штуку - имя функции для поиска в тырнетах "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)
- В левом или правом? :)) - MBedder(27.04.2017 18:02)
- А смерть его находится в яйце... - Крок(27.04.2017 17:44)
- В папке где находится java jdk есть архив src.zip - там есть все исходники. В нем есть каталог awt. В нем есть файл Polygon.java. В нем есть метод public boolean contains(double x, double y) - Petrovich(27.04.2017 17:36, )
- Нормальный алгоритм. Я туды конечно же вонзил проверку на ноль. Это же очевидно... Но на реальной картографии и без проверки тестил - ни разу в делителе нуль не появлялся. Тренирую "на кошках" - практических 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)
- А в моем простеньком примере с вышеуказанным квадратом деление на нуль как назло проявилось - Олдфаг(25.04.2017 19:32, )
- Заменить"исчезающе малым" значением Double... Повторюсь - этого ни разу не зарегистрировал. - Гудвин(25.04.2017 19:19)
- Да не
бздислушай скептиков, отличный алгоритм. И главное быстрый - 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)
- Там целочисленная арифметика похоже. А "от латиноса" в даблах напрямую разруливает полигоны, ограниченные угловыми секундами. Вот она, эта круть: Гудвин(1763 знак., 27.04.2017 22:25)
- Ну дык! Поведай же в чем разница, в сути самой методы или тоже самое на каких то математических хитростях оптимизировали. Может там банально количество рассчетов в даблах разное вот и расхождение - 1111111(27.04.2017 22:17)
- Повторяю, медленный говноалгоритм. Проверил для AVR по его полигону для точки 400,250. Его реализация функции 14500 циклов, взятая из Джавы - 3500 циклов. Сразунах. Резюме: брать реализацию из ДжаваДок. Моя адаптация для 8-разрядников одинаковая и Petrovich(202 знак., 27.04.2017 15:45, )
- А где же окончательный вариант? Что делать если действительно знаменатель нуль? - Олдфаг(25.04.2017 19:10, )
- Аудитория у Ваших ног. Ждём хорошего алгоритма. - Крок(27.04.2017 17:00)
- У меня почему то не входит... может с паскаля не так перевел. - Олдфаг(24.04.2017 19:52, )
- Проверьте, пожалуйста вхождение в квадрат 10,1 10,10 1,10 1,1 Олдфаг(166 знак., 24.04.2017 19:25, )
- Сегодня тестю на реальной картографии. Есть карта в *.KML файле - 505 полигонов(объектов), максимальное количество точек в одном из них 317. Все вроде жужжит, как надо. Определение вхождения точки во все 505 полигонов занимает единицы Гудвин(15 знак., 24.04.2017 17:52)
- Виноват: он был в полигоне до окраски не острый, но четкий. После заливки стал заметно плавным - Petrovich(24.04.2017 16:42, )
- Все. Засасываю в дельфийную приблудку "*.KML" файл с картой объектов и координаты искомой точки. В выхлопе - имя объекта. Надо бы еще добавить "круг" или концентрическую спираль" с задаваемым диаметром, чтобы найти близлежащие объекты, ежели точка Гудвин(257 знак., 24.04.2017 04:51 - 04:56)
- Я в принципе задачу решил до этого "черезжопным" способом с помощь тов. Брина :) Гудвин(2831 знак., 24.04.2017 05:01)
- Алгоритмически это подсчёт угла поворота в квадрантах - 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)
- Ну он произнес только одну команду
- А чтой-то у тебя правый острый уголок после закраски заовалился? Не то что-то с границами - Petrovich(24.04.2017 16:38, )
- Как уже заметили ниже, критерий нахождения точки внутри полигона = поворот угла радиус-вектора на 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)
- А что будет, если луч пройдет по касательной к границе полигона? - USSR(23.04.2017 18:30, )
- "Я тебе студент на зачете?" (с). В описании алгоритма есть условия которые нужно проверить - 1111111(23.04.2017 18:49)
- "Между точками границы полигона есть (в общем случае) пропуски" это как? Ведем луч ну хотя бы вправо - 4 пересечения = точка снаружи. Ведем влево - 2 = снаружи. Вверх - 4 = снаружи. Вниз - 2 = снаружи. - 1111111(23.04.2017 18:16)
- На, держи полигон и красную точку. Попробуй свой волшебный луч. PS Только не забывай, что между точками границы полигона есть (в общем случае) пропуски. Значительные. argus98(23.04.2017 18:00 - 18:04)
- Чтобы избежать тригонометрии нужно использовать алгоритм с лучем - 1111111(23.04.2017 17:37)
- Может проще преобразовать полигон в растр? Если считать, что точность 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, )
- Ошибся.. Площадь знак не меняет.. :( - USSR(23.04.2017 10:49, )
- Хабр - General(23.04.2017 09:04, ссылка)
- Проведите через точку прямую и посчитайте количество пересечений этой прямой с границами полигона, если четное - точка вне полигона, нечетное - внутри. ANV(103 знак., 23.04.2017 00:14)
- Ну если точка на границе полигона и луч пошел через его тело и пересек другую границу, то сколько пересечееий покажет и какое решение будет принято? - Олдфаг(23.04.2017 00:25, )
- В границу надо суметь ещё попасть, даже в целых числах. И в этом случае нужно спрашивать скорее «а как должна разрешаться такая неопределённость» с точки зрения реальных потребностей. - Николай Коровин(23.04.2017 00:33)
- Разве не покажет пересечения с этой гранью в этом случае? Думаю покажет. - ANV(23.04.2017 00:31)
- Так сколько покажет пересечений, если полигон квадрат, точка в середине правой стороны, луч от точки пошел горизонтально влево? - Олдфаг(23.04.2017 00:35, )
- Когда мы решим системы уравнений прямых, мы найдём точку пересечения. Когда мы будем оставлять от прямой луч, мы посмотрим, лежит точка пересечения по нужную сторону от проверяемой точки или по ненужную. И увидим, что они равны, не > и не <. Николай Коровин(212 знак., 23.04.2017 01:47)
- А контуры полигона содержат 100500 точек, полученных с GPS трекера. Задобаешься интерполировать эти прямые, потому, как там все кривое ;) - Гудвин(23.04.2017 01:57)
- Это уже не полигон, а прямо какой-то контур О_О По-моему, тут только интегрировать. - Николай Коровин(23.04.2017 08:38)
- А контуры полигона содержат 100500 точек, полученных с GPS трекера. Задобаешься интерполировать эти прямые, потому, как там все кривое ;) - Гудвин(23.04.2017 01:57)
- Эта ситуация легко проверяема и является граничным условием, которые всегда надо проверять и определять поведение логики программы в таких ситуациях. Алгоритм от этого хуже не становится. - ANV(23.04.2017 00:41)
- Когда мы решим системы уравнений прямых, мы найдём точку пересечения. Когда мы будем оставлять от прямой луч, мы посмотрим, лежит точка пересечения по нужную сторону от проверяемой точки или по ненужную. И увидим, что они равны, не > и не <. Николай Коровин(212 знак., 23.04.2017 01:47)
- Так сколько покажет пересечений, если полигон квадрат, точка в середине правой стороны, луч от точки пошел горизонтально влево? - Олдфаг(23.04.2017 00:35, )
- Говорильни на тему пересечений в тырнетах много. А реального примера работающей функции, на входе которой массив координат точек замкнутого полигона и координаты искомой точки с результатом True/False, увы, нигде нет... - Гудвин(23.04.2017 00:24)
- Вопрос был как считают, написал как делают в геймдеве :) - ANV(23.04.2017 00:27)
- Поправка - не прямую а луч - 1111111(23.04.2017 00:19)
- Вариант. Наверняка даже побыстрее нормалей будет. Найти пересечения прямой со всеми прямыми сторон (система из двух уравнений), отбросить те, что лежат «не с той стороны» от точки (чтобы получить луч), отбросить те, что на прямых лежат вне Николай Коровин(102 знак., 23.04.2017 00:25)
- Когда то из всех попавшихся алгоритмов выбрал именно его. Самый бесхитростный и с простой арифметикой - 1111111(23.04.2017 02:27)
- Да, представил одно, а написал чуть другое) В общем, от исходной точки провести луч "куда-нибудь" точно вне полигона и считать пересечения. - ANV(23.04.2017 00:24)
- Вариант. Наверняка даже побыстрее нормалей будет. Найти пересечения прямой со всеми прямыми сторон (система из двух уравнений), отбросить те, что лежат «не с той стороны» от точки (чтобы получить луч), отбросить те, что на прямых лежат вне Николай Коровин(102 знак., 23.04.2017 00:25)
- Ну если точка на границе полигона и луч пошел через его тело и пересек другую границу, то сколько пересечееий покажет и какое решение будет принято? - Олдфаг(23.04.2017 00:25, )
- Вот, кстати, быстрый способ для выпуклого полигона. Отрезки перебираются последовательно. Если знак не меняется, точка внутри. - 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, )
- 128X128 - фигня. А если задача определить принадлежность координат полигону с разрешением 2 метра на реальной земной карте? Да и полигонов таких может быть сотня в процедуре определения координат... - Гудвин(22.04.2017 23:24)
- Ну, вот смотря какое зерно у карты.... по экрану 128х128 пикселов fill делал без проблем подобным образом - Олдфаг(22.04.2017 23:05, )
- Была подобная идея с "Монте-карло". "В лоб" Но это жеж какие надо ресурсы... - Гудвин(22.04.2017 23:01)
- Ну вот ниасилил я фсю эту гэомэтрию :) Полигоны могут быть всяческие ("серпообразные загогулинины" и пр.), масштабы и расположение могут быть "где и как угодно". БоблиОтек не нарыл - все видать куркуют, а наш Евгений вообще наращивает Гудвин(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)
- Бить на треугольники и работать с каждым отдельно. Возможно оптимизации типа проверки попадания в объемлющий прямоугольник, окружность и т.п. А про интегралы -- по второй ссылке (я ниасилил): fk0(33 знак., 22.04.2017 20:51, ссылка)
- ЕМНИП, в теории обходят полигон по контуру и интегрируют угол между отрезком, соединяющим точку на контуре полигона с "точкой с определенными координатами" принадлежность которой нужно определить и любой из декартовых осей координатной плоскости USSR(252 знак., 22.04.2017 20:38, )
- Только есть одно условие. Линии, соединяющие вершины полигона, не должны пересекаться. Типа полигон из 4-х точек в форме песочных часов. Т.е. произвольный набор вершин нужноверифировать и разбивать на непересекающиеся полигоны - ig_z(22.04.2017 23:24)
- похоже на правильное решение - General(22.04.2017 23:10)
- Рапортую еще раз: Алгоритм классный - рекомендую. Прекрасно работает вот с таким объектами в количестве 505 штук. Принадлежность находит мгновенно. И даже вот так могЁт... (В "Tip" показывает имя объекта, расстояние до него от точки и направление Гудвин(2812 знак., 26.04.2017 20:45)