Каков эффективный алгоритм для копирования пикселей, которые находятся внутри четырехугольника?

Question

У меня есть два растровых изображения, и я хочу копировать пиксели из A в B, только когда они находятся внутри области, определяемой четырьмя углами (четырехугольник). Растровые изображения A и B имеют одинаковый размер, а четырехугольник определяется как четыре {x, y} координаты в пиксельном пространстве изображения.

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

Answer 1

Если четырехугольник выпуклый, вы можете использовать этот алгоритм:

Короткая версия : для каждой линии сканирования (горизонтальная линия растрового изображения) найдите ребра, которые пересекают эту линию сканирования, и скопируйтепикселей между ними.

Длинная версия : переход от линии сканирования к строке сканирования.Начните с верхней вершины (минимум у) и следите за ребрами слева и справа.Для каждого значения y вычислите значение x двух ребер (либо с использованием прямого уравнения линии, либо с использованием алгоритма Брезенхема ).Затем скопируйте пиксели с (xLeft, y) на (xRight, y) во второе растровое изображение.

Когда вы достигнете вершины в конце ребра, переключитесь на другое ребро, соединенное с этой вершиной.Продолжайте до достижения нижней вершины.

Для вогнутых четырехугольников это сложнее.Вы можете использовать аналогичный алгоритм, но для некоторых линий сканирования будет четыре ребра, пересекающих линию сканирования.В этом случае вам нужно скопировать пиксели между краями # 1 - # 2 и # 3 - # 4 (с краями, упорядоченными по значению x).Другой вариант - разделить четырехугольник на два треугольника и использовать для них алгоритм, описанный выше.