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

Question

Я вижу, что есть хороший вопрос для общих полигонов here. Существуют ли более простые или более эффективные алгоритмы, характерные для quadrilaterals?

Answer 1

Для (выпуклого) четырехугольника часто бывает просто разделить квадрант на два треугольника и вычислить площадь двух треугольников.

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

---

Редактировать от Комментарии:

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

Answer 2

Nope. Я бы использовал формулу в сообщении, которое вы упомянули.

редактирует:

подробно остановиться на том, что много, метод, представленный в посте вы упоминаете (так называемый подход Closed Polygon в ответ Reed Copsey) не имеет в конечном итоге разорвать список точек на треугольники и вычисление их площадей с использованием перекрестных продуктов. Он уходит, не триангулируя ничего, пользуясь как положительными, так и отрицательными областями, в соответствии с упорядочением (обмоткой) точек, описывающих многоугольник. Поскольку он использует как положительные, так и отрицательные области, этот подход не требует каких-либо вычислений для линий, составляющих каждый треугольник в четырехугольниках, и не имеет значения, является ли четырехугольник выпуклым или нет.

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

В сущности, эти два алгоритма одинаковы. Нет разницы в производительности; предположим, что квад определяется х0, y0, x1, y1, x2, y2, x3 и y3. Тогда замкнутый многоугольник подход имеет следующие операции:

area = 0.5 * abs(x0 * y1 - x1 * y0 + x1 * y2 - x2 * y1 + 
    x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3) 

Что может быть упрощена:

area = 0.5 * abs(x0 * (y1 - y3) + x1 * (y2 - y0) + x2 * (y3 + y1) + 
    x3 * (y0 - y2)) 

Который работает, чтобы (подсчитать * s и + 's) 12 операций в целом. Другой подход, находя каждый отдельный треугольник и принимая декартово произведение работает следующим образом:

x2_line = x2 - x0 
y2_line = y2 - y0 
area = 0.5 * abs((x1 - x0) * y2_line + (y1 - y0) * x2_line + 
    x2_line * (y3 - y0) + y2_line * (x3 - x0)) 

Что может быть снова упрощается до:

x2_line = x2 - x0 
y2_line = y2 - y0 
area = 0.5 * abs(y2_line * (x1 - x0 + x3 - x0) + x2_line * (y1 - y0 + y3 - y0)) 

Который также работает из 12 операций. Точное количество операций.

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

В заключение, да, формула в сообщении, о котором вы упоминаете, является наиболее эффективной, которую вы получили, и в то же время является самым простым алгоритмом, когда он представлен по-разному.

Answer 3

На странице mathworld перечислены несколько формул.

Answer 4

Разделите четырехугольник на два треугольника и вычислите площадь обоих.

Как только у вас есть два треугольника, Heron's Formula хорошо работает в компьютерной программе.

Для треугольника со сторонами а, Ь, с, площадь

double area = Math.Sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)/16); 

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