Алгоритм для вычисления площади замкнутой кривой с отверстиями

Question

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

Количество, положение, ориентацию, диаметр и развертки/угол сегментов дуг и отрезков прямых является переменным.

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

Answer 1

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

   Проблема теперь заключается в вычислении области «обобщенного многоугольника»: псевдополигона, ребра которого являются либо прямыми сегментами, либо дугами.

2. Обычный Shoelace formula даст вам место для поиска любых обычных polygon. Но поскольку мы имеем дело с «обобщенным многоугольником», формула не сразу применима из-за ребер дуги.

   Однако основную идею формулы Шеллэйса можно также адаптировать к этой ситуации.

   Shoelace формула в основном вычисляет сумму подписанных площадей треугольников OAB, построенных из точки O(0,0) и указывает A и B каждого ребра AB многоугольника в вопросе. Подпись области в этом случае означает, что площадь должна быть положительной, если OAB - это треугольник против часовой стрелки, а отрицательный - в противном случае. См. here для иллюстрации того, как он работает для расчета площади полигона.

   Для того, чтобы адаптировать эту формулу к вашей ситуации, вы должны найти способ, чтобы вычислить подписанную площадь «обобщенного треугольника»: псевдо-треугольник OAB, в котором OA и OB являются прямыми сегментами, в то время как AB может быть дуга , Это значительно более простая проблема, которая вполне разрешима.

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

Answer 2

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

Answer 3

Похоже, вам нужно найти область полигона, круга, эллипса и дуг. Приближенная дуга с многоугольниками. Кроме дугового остатка прямо. Если вы используете графический путь в GDI +, один из них - это выбор точек полигона. Ищите полигоновую аппроксимацию кривых. http://keisan.casio.com/ Возможно использовать GraphicsPath.PathPoints http://msdn.microsoft.com/en-us/library/system.drawing.drawing2d.graphicspath.pathpoints(v=vs.110).aspx

Answer 4

Я думаю, что у вас есть несколько вариантов:

1. интегрирует каждый сегмент (кроме прямых вертикальных сегментов), чтобы найти площадь под каждый сегмент. Интегралы должны быть легкими, потому что у вас есть только прямые и дуги окружности. Причина, по которой этот метод может быть слишком сложным или даже невозможным, состоит в том, что интегралы дают вам область экструзии дуги к оси x. Однако ваша окончательная форма не является объединением всех вертикальных экструзий каждой дуги. Это скорее больше, чем выпуклый корпус самых внешних дуг минус выпуклые оболочки внутренних дуг (которые делают отверстия в вашей форме).
2. Вы можете изменить вашу модель данных. Вместо дуг и прямых линий рассматривайте их как сектора и прямоугольники. Найти область каждого объекта легко - сложная часть затем учитывает совпадение, чтобы получить общую площадь.
3. Поскольку ваше приложение уже знает, как нарисовать конечную фигуру и узнать, какие части сплошны и какие дыры, используйте это, чтобы реализовать какой-то алгоритм подсчета пикселей/заливки флуда для вычисления площади.