Мне нужно вычислить площадь области перекрытия между двумя треугольниками в плоскости 2D. Как ни странно, я написалакод дляпроблема треугольникаи это работает довольно хорошо и надежно, но у меня есть проблема с треугольником-треугольником.

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

Решение, которое я ищу, является ответом на любой из этих вопросов:

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

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

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

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