6

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

введите сюда описание изображения

5
  • 3
    Это вопрос по геометрии, не по программированию. По сути вам нужна площадь произвольного выпуклого многоугольника.
    – VladD
    4 янв 2016 в 13:18
  • 1
    @VladD пересечение полигонов - это вполне программирование
    – user177221
    4 янв 2016 в 13:23
  • 1
    В метках и указано что вопрос относится к геометрии. 4 янв 2016 в 13:23
  • Чтобы решить задачу, для начала нужно найти все точки пересечения. Каждая сторона может пересекаться больше одного раза, как в таком случае сортировать полученные точки? 4 янв 2016 в 13:27
  • Ваш вопрос участвует в конкурсе: Новогодний алгоритм 2016
    – Nick Volynkin
    7 янв 2016 в 8:40

3 ответа 3

9

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

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

  2. Найти площадь полученного полигона. Например, по формуле из википедии:

введите сюда описание изображения

0
1

реализация решения, предложенного 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)
4
  • Неплохо бы с примером, похожим на картинку. 6 янв 2016 в 15:15
  • @Yuri Negometyanov, оба метода принимают на вход два списка вершин, можно больше трёх, но без самопересечений (в порядке обхода против часовой стрелки). метод clip вернёт список вершин обрезанного многоугольника, а метод calcArea подсчитает площадь полученного многоугольника. pastebin.com/NHxrf2nV 6 янв 2016 в 16:22
  • Хотелось бы увидеть на примере двух треугольников, что пара новых вершин выстроилась по часовой стрелке по отношению к остальным вершинам. 6 янв 2016 в 16:33
  • Боже мой, ну дак подберите сами, в чём проблема? Как - написал в прошлом коменте. К тому же не очень понимаю, чего вы хотите. 6 янв 2016 в 17:30
0

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.