Получить средний цвет треугольника, наложенного на битмап

Предположим, у меня есть изображение в формате RGB I. Я хочу получить средний цвет нескольких случайных треугольников с вершинами A, B и C. Вершины A, B и C гарантированно находятся внутри границ изображения I, но не гарантированно имеют целочисленные значения. Как эффективно получить средний цвет этой области?

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

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

Хотя я в первую очередь ищу «питонистские» ответы и библиотеки, которые могут иметь способы реализации этого, около 90% будет связано с нахождением правильного алгоритма, а 10% — с его реализацией.

ИЗМЕНЕНИЕ: Вот иллюстрация некоторых вырожденных случаев, связанных с маленькими треугольниками, очень близкими к ярким границам, чтобы продемонстрировать проблемы с простыми методами.

Для наглядности я создал изображение, которое использует только два цвета: маджента и синий, на поле высотой 6 пикселей и шириной 16 пикселей.

Если мы просто будем считать пиксели, чьи центры находятся в треугольнике, треугольник A имеет площадь 10 (8 маджентовых, 4 синих), треугольник B имеет площадь 2 (2 маджентовых), а треугольник C имеет площадь 4 (3 маджентовых, 1 синий). Это явно неверная оценка как общей площади каждого треугольника, так и соотношения маджентового цвета к синему цвету в каждом треугольнике. Если мы будем считать любую часть пикселя как “внутри” треугольника, треугольник A имеет площадь 19 (10 маджентовых пикселей и 9 синих пикселей), треугольник B имеет площадь 8 (4 маджентовых пикселя и 4 синих пикселя), а треугольник C также имеет площадь 8 (4 маджентовых пикселя и 4 синих пикселя). Несмотря на то, что треугольники B и C имеют одинаковую “площадь” при учете всех пикселей, частично обрезанных треугольником, пропорции их площадей заметно различаются и не должны иметь одинаковый средний цвет.

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

• x = a
• y = b
• y = cX + d

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

https://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/

# Утилита для вычисления площади 
# треугольника, образованного (x1, y1), 
# (x2, y2) и (x3, y3)

def area(x1, y1, x2, y2, x3, y3):

    return abs((x1 * (y2 - y3) + x2 * (y3 - y1) 
                + x3 * (y1 - y2)) / 2.0)

# Функция для проверки, находится ли точка P(x, y)
# внутри треугольника, образованного 
# A(x1, y1), B(x2, y2) и C(x3, y3) 
def isInside(x1, y1, x2, y2, x3, y3, x, y):

    # Вычислить площадь треугольника ABC
    A = area(x1, y1, x2, y2, x3, y3)

    # Вычислить площадь треугольника PBC 
    A1 = area(x, y, x2, y2, x3, y3)

    # Вычислить площадь треугольника PAC 
    A2 = area(x1, y1, x, y, x3, y3)

    # Вычислить площадь треугольника PAB 
    A3 = area(x1, y1, x2, y2, x, y)

    # Проверить, если сумма A1, A2 и A3 
    # равна A
    if(A == A1 + A2 + A3):
        return True
    else:
        return False

# Драйверная программа для проверки вышеуказанной функции
# Давайте проверим, находится ли точка P(10, 15)
# внутри треугольника, образованного 
# A(0, 0), B(20, 0) и C(10, 30)
if (isInside(0, 0, 20, 0, 10, 30, 10, 15)):
    print('Внутри')
else:
    print('Не внутри') 

# Этот код был предложен Данишем Разой

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