Поиск пересечения многоугольников

← →
kavlad (2003-10-10 14:57) [0]

Вопрос к любителям (и профессионалам :) векторной графики.
Представим бо-ольшой массив многоугольников (пусть 100 тыс.). Назовем его гордым словом "хранилище".
Каждый многоугольник описывается вектором точек (x, y).
И вот на вход системы подается еще один многоугольник. И необходимо выбрать из хранилища все многоугольники, пересекающиеся с поданным. Задача решена методами линейной алгебры. Но уж больно долго происходят вычисления. Пришла в голову бредовая мысль - описать многоугольники каким-либо хитрым образом и применить не менее хитрое преобразование (например, Фурье :), чтобы получить простой образ - например число однозначно описывающее положение многоугольника в пространстве. Тогда взаимное положение многоугольников можно определить просто сравнением (или другой элементарной операцией) этих чисел.
ПОДСКАЖИТЕ В КАКУЮ СТОРНУ КОПАТЬ!!! А то забыл я математику и физику :(

P.S. Эта бредовая идея пришла в голову не только мне. Оказываетяс на преобразовании Фурье основано ядро UniGraphix...

← →
Ketmar (2003-10-10 16:43) [1]

бредовых мыслей много. более точно очерти задачу.

← →
kavlad (2003-10-10 16:49) [2]

>Ketmar (10.10.03 16:43) [1]
Сказать "дайте мне готовый алгоритм" самомнение не позволяет.
Там было сказано: "описать многоугольники каким-либо хитрым образом". Вот и думаю каким. Но не знаю настолько теорию, чтобы сразу в голове что-то образовалось.

← →
WondeRu © (2003-10-10 17:02) [3]

Посмотри сайты по программированию игр . Там задача сформулирована как "проверка на столкновение"(елси чего-то не напутал). Спроси на фофруме "игры" здесь же!

← →
Ketmar (2003-10-10 17:22) [4]

>kavlad (10.10.03 16:49) [2]
ещё раз повторю: зависит от задачи. иногда есть "читсто программерские" методы, иногда нужна математика.

← →
kavlad (2003-10-10 17:40) [5]

>Ketmar (10.10.03 17:22)
В декартовой системе координат (многоугольник описывается массивом сових вершин) задача решается с большими вычислительными затратами. Поэтому хочется описать многоугольник в других координатах. И найти для такого описания многоугольника преобразование (это математика :), после которого положение объекта в пространстве однозначно описывалось бы простым набором параметров (в идеале одним параметром - числом). Тогда задача нахождения взаимного положения двух многоугольников свелась бы к тривиальной операции (сравнение, сложение, вычитание и т.п.). И за счет этого добиться более высокой скорости работы приложения.
Что конкретно не понятно?

← →
kavlad (2003-10-10 17:41) [6]

>WondeRu © (10.10.03 17:02)
На сайтах по программированию игр про такие вещи слыхом не слыхивали :( К сожалению.

← →
Mystic © (2003-10-10 17:45) [7]

Если ли какие-то предположения относительно расположения многоугольников? Напрашивающаяся оптимизация --- разделить участки на зоны. При помещении многоугольника в зону (или несколько зон) рассматривать только те прямоугольники, которые расположены в этих зонах... Те, которые в эти зоны не попадают, исключаются из рассмотрения...

← →
kavlad (2003-10-10 18:00) [8]

>Mystic © (10.10.03 17:45)
Это реализовано. Но встает вопрос оптимизации размера зоны.
Многоугольники в хранилище и на входе системы могут быть абсолютно произвольных размеров. Если объект на входе занимает несколько зон (частично) - то количество операций многократно возрастает. Если сделать зону большой - количество операция для маленьких объектов также СИЛЬНО возрастает.
Но это другой вопрос :) А вот с математикой, с представлением объекта в более удобном для вычислений виде у меня траблы :(

← →
kavlad (2003-10-10 18:07) [9]

>ystic © (10.10.03 17:45) [7]
Для пояснения - речь идет о работе с электронной картой.
Есть множество объектов, плохо обрабатываемых таким зональным методом. Напрмер многоугольники окружающие дороги - они занимают много зон, но площадь имеют маленькую, поэтому придется перебрать много объектов из хранилища и проверить их взаимное расположение с дорогой, хотя пересекаются с дорогой порядка 2% (к примеру).
Т.е. зональное разбиение по вычислительной сложности сильно привязано к размеру зоны.

← →
Ketmar (2003-10-10 18:40) [10]

а разбивать "многозональные" на куски? тогда, имхо, octree "канает" аж со свистом.

← →
Mystic © (2003-10-10 18:48) [11]

Основные идеи оптимизации мне видятся в слудующем:

1) Оптимизация порядка хранения прямоугольников таким образом, чтобы на самом раннем стадии отбросить большую часть объектов
2) Хранение дополнительной информации о прямоугольнике. Например прямоугольник, описывающий размеры исходного прямоугольника... т. е. сначала иет тест, могут ли пересекаться многоугольники в принципе, а потом уточнение деталей.
3) Разбиение сложных многоугольников на несколько более простых. Например, по границам зон. Это борьба с объектами занимающими малую площадь но большой объем (типа окружной).

← →
Ketmar (2003-10-10 19:06) [12]

угу. octrees + bounding boxes + subdivision.

← →
kavlad (2003-10-11 15:59) [13]

>Ketmar (10.10.03 18:40) [10]
Представляешь, сколько всего придется хранить в хранилище. В смысле дополнительной информации. Ее и так много хранится. Хранилище кешируестя в памяти сервера. После загрузки вот именно этих многоугольников (пресловутые 100 тыс.) сервер одним махом отъедает почти полгига оперативки. А таких хранилищ уже сейчас шестнадцать. И будут новые появляться. Видимо ошибка проектирования :)

>Mystic © (10.10.03 18:48) [11]
Первый пункт я сейчас пытаюсь реализовать.
Второй пункт реализован. Это было первое, что пришло в голову.
Третий пункт недопустим по идеологическим соображения. Хотя надо подумать :)
Спасибо за советы.

Не заметил, чтобы пробегала мысль, но скажу, что первое пришло в голову: хранить вместе с многоугольниками описанные вокруг каждого из них прямоугольник - определить непересекаемость прямоугольников проще, чем многоугольников.
Ну, а в плане оптимизации с точки зрения программирования - напрашивается многопоточность, но вряд ли этим я подал новую мысль :)

← →
CyberStorm (2003-10-11 23:35) [15]

Наиболее подходящее решение - "отбросить" многоугольники заведомо не могущие иметь пересечения с заданным. Для этого можно использовать R-tree для определения расположенных рядом многоугольников. Оптимальней никто ничего не придумал и не придумает.

← →
Ketmar (2003-10-12 10:14) [16]

>kavlad (11.10.03 15:59) [13]
а зачем хранить в пямяти ВСЁ? тот же самый octree даст возможность подгружать только те хоны, которые необходимы, и с неолбходимым уровнем детализации.

>Nikolay M. © (11.10.03 18:00) [14]
я сказал. bounding box. и Мистик тож, кажись.

> Ketmar (12.10.03 10:14) [16]

Да, действительно... Не могла такая очевидная вещь остаться невысказанной :)

← →
kavlad (2003-10-12 14:05) [18]

>Ketmar (10.10.03 19:06) [12]
Тогда уж quadtrees :)

>Третий пункт недопустим по идеологическим соображения. Хотя надо подумать :)

Не вижу никакой недопустимости... Особенно, если реализация будет прозрачной для тех модулей, кому знать об этом необязательно. Т. е. некоторые процедуры могут оставаться в неведении относительно того, что многоугольник состоит из более мелких частей.

Поиск пересечения многоугольников Найти похожие ветки