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

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

где X₀,Y₀ = X_n+1,Y_n+1 (координаты последней точки совпадают с первой). Таким образом, реализация алгоритма вычисления площади многоугольника в C# может базироваться как на использовании «простых» типов данных, например, с использованием массивов, так и на использовании списков (List, LinkedList). Сегодня рассмотрим вариант реализации алгоритма определения площади многоугольника с использованием двусвязного списка.

Задача и условия

Многоугольник задан в виде замкнутой ломаной линии без самопересечений. Координаты вершин (X, Y) многоугольника заданы в порядке в порядке их обхода (по часовой или против часовой стрелки). Необходимо определить площадь многоугольника.

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

Используя навыки работы с двусвязными списками, алгоритм расчёта площади многоугольника можно представить следующим образом:

1. N-угольник задается списком из N+1 вершин где N+1 вершина совпадает с первой;
2. Используя формулу, представленную выше, в цикле рассчитываем площадь многоугольника;
3. Выводим результат расчёта

Реализация алгоритма вычисления площади многоугольника в C#

Вершину многоугольника можно описать в виде такого класса:

public class Vertex
{ 
   public double X { get; set; }
   public double Y { get; set; }
   public Vertex(double x, double y)
   {
      X = x;
      Y = y;
   }
}

или использовать готовый класс PointF из пространства имен System.Drawing.

Все вершины будем хранить в списке:

LinkedList<Vertex> vertices = new LinkedList<Vertex>();

Цикл в котором рассчитывается площадь:

using static System.Math;

LinkedListNode<Vertex> vertex = vertices.First; 
for (int i = 0; i < vertices.Count-1; i++)
{
    sum +=  0.5*Abs(vertex.Value.X + vertex.Next.Value.X) * (vertex.Value.Y - vertex.Next.Value.Y);
    vertex = vertex.Next;
}

Программа вычисления площади многоугольника в C#

Ниже представлен код программы, реализующей расчёт площади многоугольника в C#:

using System;
using System.Collections.Generic;
using static System.Math;


namespace Square
{
    public class Vertex
    { 
        public double X { get; set; }
        public double Y { get; set; }
        public Vertex(double x, double y)
        {
            X = x;
            Y = y;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<Vertex> vertices = new LinkedList<Vertex>();

            bool doRead = true;
            Console.ForegroundColor = ConsoleColor.Yellow;
            Console.WriteLine("Введите координаты очередной вершины многоугольника в формате X,Y и нажмите Enter. Для разделения целой и дробной части используйте точку");
            Console.WriteLine("Для завершения ввода наберите команды Calc и нажмите Enter");
            while (doRead)
            {
                Console.ForegroundColor = ConsoleColor.White;
                string str = Console.ReadLine();
                if (str.ToLower() == "calc")
                {
                    doRead = false;
                    continue;
                }
                    
                string[] coords = str.Split(new char[] { ',' });
                if ((coords.Length != 2) || !double.TryParse(coords[0], out double X)|| (!double.TryParse(coords[1], out double Y)))
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.WriteLine("Координата вершины заданы не верно");
                    continue;
                }
                vertices.AddLast(new Vertex(X, Y));
                Console.ForegroundColor = ConsoleColor.Blue;
                Console.WriteLine($"В список добавлено {vertices.Count} вершин");
            }


            if (vertices.Count < 3)
            {
                Console.ForegroundColor = ConsoleColor.Red;
                Console.WriteLine("Количество вершин многоугольника должно быть не менее трех");
            }
            else
            {
                double sum = 0;
                Vertex endVertex = vertices.First.Value;
                vertices.AddLast(endVertex);

                LinkedListNode<Vertex> vertex = vertices.First;
                for (int i = 0; i < vertices.Count - 1; i++)
                {
                    sum += 0.5 * Abs(vertex.Value.X + vertex.Next.Value.X) * (vertex.Value.Y - vertex.Next.Value.Y);
                    vertex = vertex.Next;
                }
                Console.WriteLine($"Площадь многоугольника {sum}");
            }
        }
    }
}

Помимо непосредственно расчёта площади, в программе также реализована проверка ввода пользователем координат — любой многоугольник должен состоять минимум из трех вершин. Последняя (замыкающая вершина с индексом N+1) добавляется программой автоматически после набора пользователем команды «Calc»:

Vertex endVertex = vertices.First.Value;
vertices.AddLast(endVertex);

Результаты работы программы

Ниже представлен скриншот работы программы по расчёту площади многоугольника в C#

Итого

Сегодня мы рассмотрели пример реализации алгоритма расчёта площади многоугольника заданного в виде упорядоченного набора координат его вершин. Для реализации алгоритма в C# использован двусвязный список.