У меня есть несколько выпуклых многоугольников, которые пересекаются. Я хочу найти области, где многие из них пересекаются. В изображении можно думать о нем как о «пике». Я ищу местные пики.Множество пересекающихся многоугольников.
У меня есть программное обеспечение для пересечения двух полигонов. Теперь я думаю о том, как вычислить пики, не вычисляя все возможные пересечения (экспоненциальное время!).
Есть ли у кого-нибудь намек?
Данные k выпуклых многоугольников. Предположим, что мы имеем границу всех многоугольников, заданных в виде n отрезков. Каждый сегмент линии имеет ссылку на многоугольник, к которому он принадлежит, и его внутреннюю сторону. Сортируем вершины отрезков линии по их координате x. Теперь мы начинаем линию развертки слева направо.
Во время развертки не более O (k) раз начинается и заканчивается многоугольник, так как все полигоны являются выпуклыми. В таком стартовом событии мы просматриваем состояние линии развертки и определяем, сколько окружающих нас полигонов. Который берет O (n) время.
Для n сегментов линия развертки дает вам все пересечения в O (n log n + k^2), добавляя обработку начальных событий, которые мы получаем O (n log n + k^2 + kn). Используя ссылки отрезков линии, можно присвоить каждой области (сегменту линии) количество покрывающих в настоящее время полигонов.
Благодарим за быстрый ответ! – yar
Если я правильно понимаю вас, то следующий пример не будет работать: два многоугольника в форме ромба пересекаются посередине, но их левая и правая части не пересекаются. Строка развертки идет слева направо, так что в каждом начале многоугольника мы подсчитываем 1 многоугольник, а в конце подсчитываем 0 многоугольников. Таким образом, мы пропустим перекресток, не так ли? – yar
@yar Основным преимуществом подхода sweepline является то, что мы находим эти пересечения. Поскольку мы уже знаем, сколько полигонов вложены перед таким пересечением, нам нужно только увеличить или уменьшить число, присвоенное соответствующим сегментам, в зависимости от типа пересечения. Поскольку мы знаем, где лежит относительная внутренность сегментов, мы можем локально решить, что делать. – gue