Растрирование 2D-полигона

Question

Мне нужно создать двоичное растровое изображение из замкнутого 2D-многоугольника, представленного в виде списка точек. Не могли бы вы указать мне эффективные и достаточно простые алгоритмы для этого или, что еще лучше, некоторый код C ++?

Большое спасибо!

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

Answer 1

Волшебная фраза Google, которую вы хотите, это либо «ненулевое правило намотки», либо «четная нечетная заливка полигона».

Смотрите записи в Википедии для:

• Правило ненулевой обмотки
• четная нечетная заливка полигона

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

Answer 2

Вы можете проверить процедуру заполнения полигонов в Pygame. Посмотрите на функцию draw_fillpoly.

Алгоритм довольно прост. Он находит все позиции, которые каждый сегмент пересекает вдоль оси Y. Эти пересечения сортируются, а затем по горизонтали заполняют каждую пару пересечений.

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

Answer 3

• Триангулируйте ваш многоугольник
• Растрирование каждого из треугольников (если вы используете графический процессор, тогда он может сделать это вместо вас, это примитивная работа графических процессоров)
  • Если треугольник не имеет сегмента, параллельного оси x, разбейте его на два треугольника с линией, параллельной оси x и проходящей через его точку с медианой-y
  • Теперь оставшаяся задача - нарисовать треугольник с отрезком, параллельным оси x. Такой треугольник имеет сегмент левой стороны и сегмент правой стороны
  • Перебор линий сканирования треугольника (от мин-у до макс-у). Для каждого y вычислите точки левого и правого сегментов на этих линиях сканирования. Заполните сегмент развертки этими двумя точками (простой набор записей).

Сложность O (Площадь в пикселях)

Answer 4

Для надежного выполнения "четно-нечетного правила"

См. Эффективное заполнение полигона Дарелом Рексом Финли или версия Blender .

Это нечетный / четный метод заполнения, который поддерживает самопересекающиеся линии, не требуя сложного кода для обнаружения таких ситуаций, и не зависит от намотки (многоугольник можно перевернуть и дать те же результаты) .

---

Обновление, я сделал оптимизированную версию метода Дарела Рекса, который позволяет избежать зацикливания по всем координатам для каждого y-пикселя.

Автономные реализации:

• C99 .
• Ржавчина (с тестами).

Хотя ускорение, скорее всего, будет экспоненциальным, из быстрого теста оно примерно в 7,5 раз быстрее (в 11 раз при удалении вызова round) с использованием произвольной рисованной каракулей в области 2540x1600, YMMV.