Пересечение линии с фигурами

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Пересечение линии с фигурами

Сообщение alibek » 11.10.2016 (Вт) 8:44

Есть траектория произвольной формы (с GPS-треккера).
На карте есть некоторое количество (до тысячи) произвольных фигур: треугольники и круги.
Нужно определить фигуры, которые пересекаются траекторией.
Тут возможен только перебор точек/сегментов траектории или можно сделать какую-то оптимизацию?
Lasciate ogni speranza, voi ch'entrate.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3712
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Пересечение линии с фигурами

Сообщение Mikle » 11.10.2016 (Вт) 10:55

Траектория, это ломаная, состоящая из прямых отрезков?
Я бы выбрал QTree. Поле делится на большие квадраты, каждый квадрат ещё на 4 квадрата, далее рекурсивно до размера квадрата, примерно равного отрезку ломаной.
Можно сразу работать только с нижним уровнем маленьких квадратов (точнее верхним, это же дерево), при большом количестве и примерно равном размере проверяемых объектов это может быть оптимальнее.
в каждом квадрате регистрируются элементы карты (фигуры), хотя бы частично в нём лежащие, в цикле проходим по отрезкам ломаной, вычисляем квадраты, куда они попадают, и проверяем коллизии с зарегистрированными там элементами карты.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Пересечение линии с фигурами

Сообщение alibek » 11.10.2016 (Вт) 12:20

Да. Но отрезки могут быть произвольной длины, вплоть до нулевой (если GPS-трекер не двигался).
Так что видимо следовало бы предварительно оптимизировать исходную траекторию — сгладить заменить одинаковые точки одной.
Lasciate ogni speranza, voi ch'entrate.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3712
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Пересечение линии с фигурами

Сообщение Mikle » 11.10.2016 (Вт) 15:10

alibek писал(а):Так что видимо следовало бы предварительно оптимизировать исходную траекторию — сгладить заменить одинаковые точки одной.

Длинные порезать по границам ячеек.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16004
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Пересечение линии с фигурами

Сообщение Хакер » 11.10.2016 (Вт) 23:39

Причём, как я понимаю, набор кругов и треугольников все время одинаковый или не меняется каждый раз на серию проверок траекторий, потому что представляет собой какую-то городскую инфраструктуру (карту покрытия базовых станций?).

В таком случае, разбивку на квадратные кластеры и сопоставление постоянных объектов с кластерами надо сделать 1 раз и заранее — что-то вроде построения индекса в БД, который не перестраивается при каждой выборке, а модифицируется только при изменении набора, по которому часто производится выборка.

Кстати, во многих СУБД (даже в MySQL) есть географически-пространственные типы данных и географически-пространственные индексы на таблицах, которые как раз позволяет хранить какой-то набор геометрических примитивов и делать по нему выборки. Может воспользоваться этим?

Кстати, есть пара соображний:
  • Сразу посоветую стремится не к строгой проверки пересечений, а к проверки пересечений с неким допуском (tolerance). Допуск, на практике, должен равняться сумме погрешности GPS-трекера и погрешности картографии. Это сразу облегчит обработку ситуаций «линия трекера проходит по касательной к объекту» или «линия трекера не пересекает объект, но пересекается с его вершиной».
  • Реализовывать всё это дело, как мне видится, лучше на C/C++, и может быть даже с привлечением SSE для убыстрения обработки путём параллелизации математики проверок.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Пересечение линии с фигурами

Сообщение alibek » 12.10.2016 (Ср) 0:06

Да, набор фигур изменяется редко и его можно считать постоянным.
Lasciate ogni speranza, voi ch'entrate.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Пересечение линии с фигурами

Сообщение alibek » 12.10.2016 (Ср) 9:06

Смысла в кластеризации я особого не вижу — для грубого приближения можно просто использовать описанные вокруг фигур прямоугольники.
А вот про гео-координаты в БД я забыл, это действительно можно использовать.
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16004
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Пересечение линии с фигурами

Сообщение Хакер » 12.10.2016 (Ср) 9:09

alibek писал(а):Смысла в кластеризации я особого не вижу — для грубого приближения можно просто использовать описанные вокруг фигур прямоугольники.

Тебе придётся перебирать их все. Если у тебя 1000 фигур и путь из 20 отрезков, придётся делать 20000 проверок. А с квадро-деревом количество провок, которые придётся сделать, уменьшается на порядки. По сути это обычное дерево поиска, как бинарные деревья поиска в случае с обычными скалярными данными, и эффект в виде упрощения (в плане снижения «вычислительной» сложности) от его применения такой же.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Пересечение линии с фигурами

Сообщение alibek » 12.10.2016 (Ср) 10:22

Точек наверняка будет намного больше, тысячи и десятки тысяч.
Их можно оптимизировать, но отрезков в любом случае будет достаточно много, порядка нескольких сотен.
И поскольку траектория может проходить через всю карту, то скорее всего в любом случае придется проверять большую часть фигур.
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16004
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Пересечение линии с фигурами

Сообщение Хакер » 12.10.2016 (Ср) 10:24

alibek писал(а):Точек наверняка будет намного больше, тысячи и десятки тысяч.

Каких точек?

alibek писал(а):И поскольку траектория может проходить через всю карту, то скорее всего в любом случае придется проверять большую часть фигур.

Это не важно. Важно, что отдельно взятый сегмент пути будет пересекаться только с одним кластером, и его придётся «сталкивать» не с тысячей полигонов, а с десятком, который отфильруется из общей тысячи благодаря обходу дерева.

Когда я сказал «сталкивать», я имел в виду проверять отрезок пути на пересечение с полигоном карты.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14069
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Пересечение линии с фигурами

Сообщение alibek » 12.10.2016 (Ср) 22:07

Точки — это координаты GPS-трекера, который их периодически фиксирует.
Траектория это последовательность отрезков, соединяющих эти точки.
В принципе, после того, как какой-то отрезок коснулся фигуры, эту фигуру можно исключить из дальнейших проверок, что ускорит проверку оставшихся точек траектории. Думаю, это немало ускорит процесс.
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16004
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Пересечение линии с фигурами

Сообщение Хакер » 13.10.2016 (Чт) 4:15

alibek писал(а):В принципе, после того, как какой-то отрезок коснулся фигуры, эту фигуру можно исключить из дальнейших проверок, что ускорит проверку оставшихся точек траектории. Думаю, это немало ускорит процесс.

Особо не ускорит.

Приведу пример с использованием набора из 65536 объектов, среди которых нужно найти 100 нужных.
Если использовать простой перебор, придётся сделать 100*65536 провок = 6553600 проверок.
Если использовать просто перебор с отсечением уже найденных, придётся сделать 65536 + 65535 + ... + 65437 проверок = 6548650.

Разница на 0.07 процента.

Если использовать бинарное дерево поиска, обход дерева сводится к 16 шагам в худшем случае. Нужно сделать 16*100 = 1600 проверок.

Разница в 4000 раз.

Поэтому без применения деревьев поиска — никуда.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList