Узнайте, как залить заливку полигона наименьшим количеством векторных линий

Question

Скажем, у меня есть векторный многоугольник с отверстиями.Мне нужно залить заливку, рисуя связанные сегменты.Конечно, поскольку дыры есть, я не могу заполнить их, используя одну непрерывную ломаную линию: мне иногда нужно прерывать мой путь, затем переходить к области, которая была пропущена, и запускать там другую ломаную линию.

Моя цель - найти набор полилиний, необходимых для заполнения всего многоугольника.Лучше, если я найду набор наименьший (то есть способ, которым я могу заполнить многоугольник с минимальным количеством прерываний).

Бонусный вопрос: как могЯ делаю это для частичной заливки?Скажем, я не хочу заполнять при 100% плотности, но я хочу 50% (для этого потребуется, чтобы линии заливки, предполагая, что они параллельны друг другу и имеют ширину в одну единицу, размещены на расстоянии двух единиц).

Я не смог найти подобный вопрос здесь, хотя есть много связанных с алгоритмами заливки.

Есть идеи или указатели?

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

Answer 1

Я предполагаю, что расстояние между линиями составляет 1 единицу.Грубая реализация, без гарантии нахождения минимального количества ломаных линий:

1. Начните с пустого набора полилиний.
2. Определите minx и maxx многоугольника.
3. Цикл x от xmin до xmax с шагом 1. Линия L - вертикальная линия в точке x.
   • Пересечь вертикальную линию L с вашим многоугольником (быстрый алгоритм, легко найти).Это даст вам набор сегментов: {(x, y1) - (x, y2)}.
   • Для всех полилиний и всех сегментов объедините сегмент + конец полилиний (см. Примечание 1 ниже).Когда вы объединяете сегмент и полилинию, добавьте небольшое растяжение в конце полилинии (чтобы соединить его с сегментом) и сам сегмент.Для всех сегментов, которые нельзя объединить с помощью этого, добавьте новую полилинию в глобальный набор.
4. В конце, попробуйте снова объединить полилинии, если это возможно (концы близко друг к другу).

Оптимальный алгоритм для объединения новых сегментов с существующими полилиниями должен быть легко найден (хэширование по y), или алгоритма грубой силы может быть достаточно:

1. количество новых сегментовСканирование на строку не должно быть слишком высоким, если у ваших полигонов нет миллиардов дырок,
2. число глобальных полилиний на каждом шаге не должно быть слишком большим,
3. вы сравниваете только с конечным сегментомкаждой полилинии, а не всей.

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