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

Question

Итак, у меня есть функция, которая получает N случайных 2D баллов.

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

Answer 1

Вы хотите вычислить площадь многоугольника ?

(взято по ссылке, преобразовано в C #)

class Point { double x, y; } 

double PolygonArea(Point[] polygon)
{
   int i,j;
   double area = 0; 

   for (i=0; i < polygon.Length; i++) {
      j = (i + 1) % polygon.Length;

      area += polygon[i].x * polygon[j].y;
      area -= polygon[i].y * polygon[j].x;
   }

   area /= 2;
   return (area < 0 ? -area : area);
}

Answer 2

Вы можете использовать алгоритм Тимоти Чана для поиска выпуклой оболочки в nlogh, где n - количество точек, h - количество вершин выпуклой оболочки. Если вам нужен простой алгоритм, отправляйтесь на сканирование Грэма.

Кроме того, если вы знаете, что ваши данные упорядочены как простая цепочка, где точки не пересекаются, вы можете использовать алгоритм Мелкмана для вычисления выпуклой оболочки в O (N).

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

Answer 3

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

Answer 4

Я нашел другую функцию, написанную на Java , поэтому я перенес ее на C #

public static double area(List<Double> lats,List<Double> lons)
{       
double sum=0;
double prevcolat=0;
double prevaz=0;
double colat0=0;
double az0=0;
for (int i=0;i<lats.Count;i++)
{
    double colat=2*Math.Atan2(Math.Sqrt(Math.Pow(Math.Sin(lats[i]*Math.PI/180/2), 2)+ Math.Cos(lats[i]*Math.PI/180)*Math.Pow(Math.Sin(lons[i]*Math.PI/180/2), 2)),
        Math.Sqrt(1-  Math.Pow(Math.Sin(lats[i]*Math.PI/180/2), 2)- Math.Cos(lats[i]*Math.PI/180)*Math.Pow(Math.Sin(lons[i]*Math.PI/180/2), 2)));
    double az=0;
    if (lats[i]>=90)
    {
        az=0;
    }
    else if (lats[i]<=-90)
    {
        az=Math.PI;
    }
    else
    {
        az=Math.Atan2(Math.Cos(lats[i]*Math.PI/180) * Math.Sin(lons[i]*Math.PI/180),Math.Sin(lats[i]*Math.PI/180))% (2*Math.PI);
    }
    if(i==0)
    {
         colat0=colat;
         az0=az;
    }           
    if(i>0 && i<lats.Count)
    {
        sum=sum+(1-Math.Cos(prevcolat  + (colat-prevcolat)/2))*Math.PI*((Math.Abs(az-prevaz)/Math.PI)-2*Math.Ceiling(((Math.Abs(az-prevaz)/Math.PI)-1)/2))* Math.Sign(az-prevaz);
    }
    prevcolat=colat;
    prevaz=az;
}
sum=sum+(1-Math.Cos(prevcolat  + (colat0-prevcolat)/2))*(az0-prevaz);
return 5.10072E14* Math.Min(Math.Abs(sum)/4/Math.PI,1-Math.Abs(sum)/4/Math.PI);
}

Answer 5

Ваша проблема не подразумевает наличие готового многоугольника (что подразумевается этим ответом ). Я бы порекомендовал триангуляцию, такую ​​как Триангуляция Делоне , а затем тривиально вычислить площадь каждого треугольника. OpenCV (я использовал его с большим количеством точек 2D, и это очень эффективно) и CGAL обеспечивают отличные реализации для определения триангуляции.