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

[alibek]

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

[Mikle]

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

[alibek]

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

[Mikle]

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

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

[Хакер]

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

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

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

Кстати, есть пара соображний:

• Сразу посоветую стремится не к строгой проверки пересечений, а к проверки пересечений с неким допуском (tolerance). Допуск, на практике, должен равняться сумме погрешности GPS-трекера и погрешности картографии. Это сразу облегчит обработку ситуаций «линия трекера проходит по касательной к объекту» или «линия трекера не пересекает объект, но пересекается с его вершиной».
• Реализовывать всё это дело, как мне видится, лучше на C/C++, и может быть даже с привлечением SSE для убыстрения обработки путём параллелизации математики проверок.

[alibek]

Да, набор фигур изменяется редко и его можно считать постоянным.

[alibek]

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

[Хакер]

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

Тебе придётся перебирать их все. Если у тебя 1000 фигур и путь из 20 отрезков, придётся делать 20000 проверок. А с квадро-деревом количество провок, которые придётся сделать, уменьшается на порядки. По сути это обычное дерево поиска, как бинарные деревья поиска в случае с обычными скалярными данными, и эффект в виде упрощения (в плане снижения «вычислительной» сложности) от его применения такой же.

[alibek]

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

[Хакер]

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

Каких точек?

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

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

Когда я сказал «сталкивать», я имел в виду проверять отрезок пути на пересечение с полигоном карты.

[alibek]

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

[Хакер]

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

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

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

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

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

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

Поэтому без применения деревьев поиска — никуда.