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

#алгоритм #геометрия

Координаты вершин двух треугольников на плоскости заданы в порядке обхода против
часов стрелки. Нужно найти и вывести площадь их пересечения.


    

Ответы

Ответ 1

Задача легко разбивается на подзадачи, для которых есть готовые решения:


Найти пересечение - обрезать (clip) один треугольник вторым. Например, с помощью
алгоритма Sutherland–Hodgman. Результатом пересечения будет выпуклый полигон.
Найти площадь полученного полигона. Например, по формуле из википедии:


Ответ 2

реализация решения, предложенного PashaPash♦

# Sutherland-Hodgman algorithm for clipping
def clip(subjectPolygon, clipPolygon):
    def inside(p):
        return (cp2[0] - cp1[0]) * (p[1] - cp1[1]) > (cp2[1] - cp1[1]) * (p[0] - cp1[0])

    def computeIntersection():
        dc = [cp1[0] - cp2[0], cp1[1] - cp2[1]]
        dp = [s[0] - e[0], s[1] - e[1]]
        n1 = cp1[0] * cp2[1] - cp1[1] * cp2[0]
        n2 = s[0] * e[1] - s[1] * e[0]
        n3 = 1.0 / (dc[0] * dp[1] - dc[1] * dp[0])
        return [(n1 * dp[0] - n2 * dc[0]) * n3, (n1 * dp[1] - n2 * dc[1]) * n3]

    outputList = subjectPolygon
    cp1 = clipPolygon[-1]

    for clipVertex in clipPolygon:
        cp2 = clipVertex
        inputList = outputList
        outputList = []
        s = inputList[-1]

        for subjectVertex in inputList:
            e = subjectVertex
            if inside(e):
                if not inside(s):
                    outputList.append(computeIntersection())
                outputList.append(e)
            elif inside(s):
                outputList.append(computeIntersection())
            s = e
        cp1 = cp2
    return outputList

def calcArea( subjectPolygon ):
    if subjectPolygon == []:
        return 0
    subjectPolygon = subjectPolygon + [subjectPolygon[0]]
    xSum = 0
    for i in range(len(subjectPolygon)-1):
        xSum += subjectPolygon[i][0]*subjectPolygon[i+1][1]
    ySum = 0
    for i in range(len(subjectPolygon)-1):
        ySum += subjectPolygon[i][1]*subjectPolygon[i+1][0]
    return 0.5 * abs(xSum - ySum)


Ответ 3

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


Записываем уравнение стороны оранжевого треугольника по двум вершинам и вычисляем
знак S его третьей вершины при подстановке в это уравнение.  
Подставляем каждую вершину синего полигона в уравнение стороны оранжевого треугольника
и умножаем результат на S. Если произведение меньше нуля, то заменяем одну вершину на две.
При замене вершин следует убедиться, что все остальные вершины полигона окажутся
по одну сторону от новых сторон. Если это не так - следует поменять новые вершины местами.