площадь пересечения двух треугольников, или набор полуплоскостей, или область множества выпуклой точки

Question

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

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

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

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

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

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

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

Answer 1

Вопрос 1: почему точки в случайном порядке?Если они есть, вы должны упорядочить их так, чтобы соединение последовательных точек с прямыми линиями давало выпуклый многоугольник.Как их заказать - например, запустив алгоритм выпуклой оболочки (хотя, возможно, существуют и более простые методы).После того, как вы их заказали, вычислите площадь, как описано здесь .

-

Вопрос 2 проще.Полуплоскость определяется одной линией, имеющей неявное уравнение a*x+b*y+c=0;все точки (x, y), для которых a*x+b*y+c <= 0 (обратите внимание на неравенство) находятся "за" полуплоскостью.Теперь вам нужно как минимум три плоскости, чтобы пересечение их отрицательных полупространств было замкнуто (это необходимое, но не достаточное условие).Если пересечение замкнуто, это будет выпуклый многоугольник.

Я предлагаю вам поддерживать связанный список вершин.Алгоритм инициализируется тремя строками.Вычислить три точки (в общем случае), где линии пересекаются;это начальные вершины вашего региона (треугольника).Вы также должны проверить, что каждая вершина находится «позади» полуплоскости, определенной линией, проходящей через две другие вершины;это гарантирует, что пересечение фактически является замкнутой областью.

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

Новые вершины пересечения определяют линию, которая разделяет текущую область на две области.Опять же, используйте ориентацию новой полуплоскости, чтобы решить, какую из двух новых областей назначить новой «текущей области», а какую отбросить.

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

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