using System;

using System.Collections.Generic;

using System.Drawing;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        string input = "-7.550922_4.1042356_0.6384368_5.4494743;-1.7815869_3.484396_-7.300193_2.5778723;2.1230996_-3.5886428_-0.5217197_-4.023099;-7.300193_2.5778723_-7.5509224_4.1042356;-0.5217197_-4.0230985_-0.6676799_-3.1345446;-0.8337523_-2.285698_-1.7815874_3.4843962;0.6384367_5.449475_2.1230998_-3.588643;";

        var aa = BTCMep.Helpers.AreaHelper.PolygonArea(input);

        Console.WriteLine(aa);

    }

}

​

namespace BTCMep.Helpers

{

    public class AreaHelper

    {

        /// <summary>

        /// Refer: https://www.geeksforgeeks.org/area-of-a-polygon-with-given-n-ordered-vertices/?fbclid=IwAR3hW_gWB0T6H1SkNbfgBKewtgWke9yuPFhjV4JyGr_Kn28DBiENUxSPGsQ

        /// </summary>

        /// <param name="input">A list of vertical, separated by ";" character, with format: {x1,y1,x2,y2}</param>

        /// <returns></returns>

        public static double PolygonArea(string input)

        {

            var originalLines = input.Split(';').Where(s => !string.IsNullOrEmpty(s)).Select(a => a.Split('_').Select(b => Convert.ToDouble(b)).ToArray()).ToList();

​

            if (originalLines.Any(s => s.Length != 4))

            {

                // Can't perform.

                return -1;

            }

​

            // Round data first.

            var convertedLines = originalLines.Select(s => new Line(Math.Round(s.ElementAt(0), 2),

                                                                    Math.Round(s.ElementAt(1), 2),

                                                                    Math.Round(s.ElementAt(2), 2),

                                                                    Math.Round(s.ElementAt(3), 2))).ToList();

​

            // Many groups, ex: group 1, group 2, group 3,... 

            // https://dotnetfiddle.net/lEsMkn?fbclid=IwAR2Qp97v3J4nGV3jwv8_wEAp4xcAGDdoq59ns8dwYy3UGk742-EQwPFUbY4

            var groups = DetectGroups(convertedLines);

​

            // Try to connect groups into 1 group to prevent the missing path.

            groups = ConnectGroups(groups);

​

            var groupedLines = groups.First().Select(s => new Line(s.ElementAt(0),

                                                                     s.ElementAt(1),

                                                                     s.ElementAt(2),

                                                                     s.ElementAt(3))).ToList();

​

            var distincedPoints = GetPoints(groupedLines);

​

            // Initialize area

            var X = distincedPoints.Select(s => s.X).ToList();

            var Y = distincedPoints.Select(s => s.Y).ToList();

​

            var n = X.Count;

            int j = n - 1;

            double area = 0.0;

​

            for (int i = 0; i < n; i++)

            {

                area += (X[j] + X[i]) * (Y[j] - Y[i]);

​

                // j is previous vertex to i

                j = i;

            }

​

            // Return absolute value

            return Math.Round(Math.Abs(area / 2.0), 2);

        }

​

        private static List<List<double[]>> ConnectGroups(List<List<double[]>> groups)

        {

            while (groups.Count > 1)

            {

                #region Process to find the connection and merge to group.

​

                var mergedGroup = groups.SelectMany(s => s.Select(a => new Line(a.ElementAt(0),

                                                                                a.ElementAt(1),

                                                                                a.ElementAt(2),

                                                                                a.ElementAt(3)))).ToList();

​

                // Connect group into 1 by finding the shortest path between the alone point of current group to another group.

                var processedGroups = new List<List<double[]>>();

​

                for (int i = 0; i < groups.Count; i++)

                {

                    processedGroups.Add(groups[i]);

​

                    // Find the alone points.

                    // Alone Points are the records that has only 1.

                    var currentPoints = new List<double[]>();

                    foreach (var item in groups[i])

                    {

                        var point1 = new double[] { item.ElementAt(0), item.ElementAt(1) };

                        var point2 = new double[] { item.ElementAt(2), item.ElementAt(3) };

                        currentPoints.Add(point1);

                        currentPoints.Add(point2);

                    }

​

                    var alonePoint = new double[] { processedGroups[i].Last().ElementAt(2), processedGroups[i].Last().ElementAt(3) };

​

                    // Generate the list of point for comparation.

                    var listPointForComparation = new List<double[]>();

                    var remainingGroups = groups.Except(processedGroups).SelectMany(s => s).ToList();

                    foreach (var item in remainingGroups)

                    {

                        var point1 = new double[] { item.ElementAt(0), item.ElementAt(1) };

                        var point2 = new double[] { item.ElementAt(2), item.ElementAt(3) };

                        if (!listPointForComparation.Contains(point1))

                        {

                            listPointForComparation.Add(point1);

                        }

                        if (!listPointForComparation.Contains(point2))

                        {

                            listPointForComparation.Add(point2);

                        }

                    }

​

                    if (!listPointForComparation.Any())

                    {

                        continue;

                    }

​

                    // Initialize the minimum distance and closest point

                    var minDistance = double.PositiveInfinity;

                    var closestPoint = new double[0];

​

                    // Find the shortest distance and Point.

                    foreach (var p in listPointForComparation.Distinct())

                    {

                        // Calculate the distance between the current point and the given point

                        var distance = Math.Sqrt(p.Zip(alonePoint, (a, b) => Math.Pow(a - b, 2)).Sum());

                        // Update the closest point if the distance is smaller than the current minimum distance

                        if (distance < minDistance)

                        {

                            minDistance = distance;

                            closestPoint = p;

                        }

                    }

​

                    // Prevent to process if closestPoint is not found.

                    if (closestPoint.Length == 0)

                    {

                        continue;

                    }

​

                    // Prevent the dupplicated item to be inserted.

                    var newLine = new Line(alonePoint.ElementAt(0), alonePoint.ElementAt(1), closestPoint.ElementAt(0), closestPoint.ElementAt(1));

                    if (mergedGroup.All(s => (s.x1 == newLine.x1 && s.y1 == newLine.y1) || (s.x1 == newLine.x2 && s.y1 == newLine.y2)))

                    {

                        continue;

                    }

​

                    mergedGroup.Add(newLine);

                }

​

                #endregion

​

                groups = DetectGroups(mergedGroup);

            }

​

            return groups;

        }

​

        #region Line Group Detector

​

        private static List<List<double[]>> DetectGroups(List<Line> lines)

        {

            var groups = new List<List<double[]>>();

​

            var graph = BuildGraph(lines);

            if (!graph.Any())

            {

                return groups;

            }

​

            var visited = new HashSet<Line>();

            foreach (var line in lines)

            {

                // Move next if dupplicated.

                if (visited.Contains(line))

                {

                    continue;

                }

​

                var group = new List<Line>();

                TraverseGroup(line, graph, visited, group);

​

                // Convert back into this format to use for calculating later.

                groups.Add(group.Select(s => new double[] { s.x1, s.y1, s.x2, s.y2 }).ToList());

            }

​

            return groups;

        }

​

        private static Dictionary<Line, List<Line>> BuildGraph(List<Line> lines)

        {

            var graph = new Dictionary<Line, List<Line>>();

​

            foreach (var line1 in lines)

            {

                foreach (var line2 in lines)

                {

                    if (line1 != line2 && line1.ConnectsTo(line2))

                    {

                        if (!graph.ContainsKey(line1))

                        {

                            graph[line1] = new List<Line>();

                        }

                        if (!graph.ContainsKey(line2))

                        {

                            graph[line2] = new List<Line>();

                        }

​

                        graph[line1].Add(line2);

                        graph[line2].Add(line1);

                    }

                }

            }

​

            return graph;

        }

​

        private static void TraverseGroup(Line line, Dictionary<Line, List<Line>> graph, HashSet<Line> visited, List<Line> group)

        {

            visited.Add(line);

            group.Add(line);

​

            if (graph.ContainsKey(line))

            {

                foreach (var neighbor in graph[line])

                {

                    if (!visited.Contains(neighbor))

                    {

                        TraverseGroup(neighbor, graph, visited, group);

                    }

                }

            }

        }

​

        private static List<List<PointF>> FindPolygons(List<PointF> points)

        {

            List<List<PointF>> polygons = new List<List<PointF>>();

​

            while (points.Count > 0)

            {

                // Initialize a new polygon

                List<PointF> polygon = new List<PointF>();

​

                // Add the first point to the polygon

                polygon.Add(points[0]);

​

                // Remove the first point from the list of points

                points.RemoveAt(0);

​

                // Initialize a variable to keep track of the last point in the polygon

                PointF lastPoint = polygon[0];

​

                while (true)

                {

                    // Find the nearest point to the last point in the polygon

                    PointF nearestPoint = FindNearestPoint(lastPoint, points);

​

                    // If no point is found, the polygon is complete

                    if (nearestPoint == PointF.Empty)

                    {

                        break;

                    }

​

                    // Add the nearest point to the polygon

                    polygon.Add(nearestPoint);

​

                    // Remove the nearest point from the list of points

                    points.Remove(nearestPoint);

​

                    // Set the last point to the nearest point

                    lastPoint = nearestPoint;

                }

​

                // Add the polygon to the list of polygons

                polygons.Add(polygon);

            }

​

            return polygons;

        }

​

        private static PointF FindNearestPoint(PointF point, List<PointF> points)

        {

            PointF nearestPoint = PointF.Empty;

            double minDistance = double.MaxValue;

​

            foreach (PointF p in points)

            {

                double distance = Math.Sqrt(Math.Pow(point.X - p.X, 2) + Math.Pow(point.Y - p.Y, 2));

​

                if (distance < minDistance)

                {

                    minDistance = distance;

                    nearestPoint = p;

                }

            }

​

            return nearestPoint;

        }

​

        private static List<PointF> GetPoints(List<Line> lines, PointF? findx = null)

        {

            // Assume "lines" is a list of Line objects in the order of the graph

            List<PointF> points = new List<PointF>();

​

            // Iterate through the lines and add the unique points in order to the "points" list

            foreach (Line line in lines)

            {

                if (!findx.HasValue || findx.Value == PointF.Empty)

                {

                    var remainingLines = lines.Where(s => s != line).ToList();

                    points.Add(line.Point1);

                    points.AddRange(GetPoints(remainingLines));

                    break;

                }

                else if (findx == line.Point1)

                {

                    var remainingLines = lines.Where(s => s != line).ToList();

                    points.Add(line.Point2);

                    points.AddRange(GetPoints(remainingLines));

                    break;

                }

                else if (findx == line.Point2)

                {

                    var remainingLines = lines.Where(s => s != line).ToList();

                    points.Add(line.Point1);

                    points.AddRange(GetPoints(remainingLines));

                    break;

                }

            }

            // The "points" list now contains all the unique points in order of the graph

            return points;

        }

​

        #endregion

    }

​

    class Line

    {

        public double x1, y1, x2, y2;

​

        public PointF Point1 { get { return new PointF { X = (float)x1, Y = (float)y1 }; } }

​

        public PointF Point2 { get { return new PointF { X = (float)x2, Y = (float)y2 }; } }

​

        public Line(double x1, double y1, double x2, double y2)

        {

            this.x1 = x1;

            this.y1 = y1;

            this.x2 = x2;

            this.y2 = y2;

        }

​

        public bool ConnectsTo(Line other)

        {

            return x1 == other.x2 && y1 == other.y2 || x2 == other.x1 && y2 == other.y1;

        }

    }

​

    class ArrayComparer : IEqualityComparer<double[]>

    {

        public bool Equals(double[] x, double[] y)

        {

            return x.SequenceEqual(y);

        }

​

        public int GetHashCode(double[] obj)

        {

            return string.Join(",", obj).GetHashCode();

        }

    }

}

​