Алгоритм наличия пересечения пары полигонов.

[lell3]

Добрый день.
Я сейчас работаю над алгоритмом, который определяет пересекаются ли пара полигонов.
Кто-нибудь сталкивался с такой задачей? Можете посоветовать наиболее быстрые алгоритмы?

[gamm]

Можете посоветовать наиболее быстрые алгоритмы?

алгоритм заметания (читаем Препарату и Шеймоса, "Вычислительная геометрия: введение")

[SergeyRyzhkov]

Добрый день.
Я сейчас работаю над алгоритмом, который определяет пересекаются ли пара полигонов.
Кто-нибудь сталкивался с такой задачей? Можете посоветовать наиболее быстрые алгоритмы?

Не совсем,конечно, по теме вопроса, но посмотрите также для общего образования DE-9IM (просто наберите в поиске, станет понятно).
А что будет результатом Вашего алгоритма?
Я имею ввиду - наилучшая производительность (по сравнению с существующими алгоритма), просто реализация в виде кода (программного) и т.д.?
Просто у меня лично есть определенный интерес к результату

[bim2010]

http://www.boost.org/doc/libs/1_53_0/li ... ction.html
http://www.boost.org/doc/libs/1_51_0/li ... /index.htm
http://www.gdal.org/classOGRLayer.html# ... ec99e0f48a

[lell3]

Спасибо, всем кто откликнулся. Сейчас буду смотреть то, что посоветовали)

Есть набор космических снимков спутников WV-1, WV-2, QB.
Каждый снимок представляет из себя:
-набор тайлов исходного пространственного разрешения снимка. Проще говоря, снимок порублен на равномерные фрагменты. Таких фрагментов около 300
-Шейп файл, содержащий сетку, по которой и формировались тайлы
-Шейп файл, содержащий контур снимка.

Ссылка на изображение: http://hostingkartinok.com/show-image.p ... e7d9042ae8

В среднем снимок весить 30Гб, набор снимков занимает около 20 Тб. Объем колосальный.

Пишу программу, на вход которой подается Шейп файл: точка, линия или полигон. Программа ищет тайлы, которые попали в указанные координаты из всего набора снимков и далее названия тайлов записывает в текстовый файл.

Здесь и возникает задача максимального быстрого определения пересечения пары полигонов.

[trir]

R-tree
было

[SergeyRyzhkov]

Пишу программу, на вход которой подается Шейп файл: точка, линия или полигон. Программа ищет тайлы, которые попали в указанные координаты из всего набора снимков и далее названия тайлов записывает в текстовый файл.
Здесь и возникает задача максимального быстрого определения пересечения пары полигонов.

Понятно, все банально проще... Я думал Вы новый алгоритм разрабатываете. Было бы интересно.
Скажите на чем пишете и дадим Вам код , зачем Вам алгоритм какой-то супер-быстрый для Вашей простой задачи?

[lell3]

Понятно, все банально проще... Я думал Вы новый алгоритм разрабатываете. Было бы интересно.Скажите на чем пишете и дадим Вам код , зачем Вам алгоритм какой-то супер-быстрый для Вашей простой задачи?

Пишу на С++ с использованием библеотек Toolkit Erdas Imagine, но не откажусь от кода на любом языке)