RouteBuilder.cs

using System.Collections.Generic;
using System.Drawing;

namespace Clusterization_algorithms
{
    public class RouteBuilder
    {
        private Point _startPoint = new Point(0, 0);
        private List<Point> _all_points = new List<Point> { }; // start point position
        private List<Point> _routeList = new List<Point> { }; // finish point position
        private List<Point> _convex_hull = new List<Point> { };
        private List<Point> _inside_points = new List<Point> { };

        private double _length;

        public List<Point> Convex_hull { get => _convex_hull; }
        public List<Point> RouteList { get => _routeList; set => _routeList = value; }

        public RouteBuilder() { }

        public void SetPoints(List<Point> points)
        {
            _all_points.Clear();
            _all_points.AddRange(points);
        }

        public List<Point> CalculateRouteByConvexHullInsertion()
        {
            JarvisMarch();
            ConvexHullInsertion();

            List<Point> unsort_route = new List<Point> { };
            unsort_route.AddRange(_routeList);
            _routeList.Clear();

            SortInsidePoints();
            ConvexHullInsertion();

            double unsorted_route_length = Calculator.CalcRouteLength(unsort_route);
            double sorted_route_length = Calculator.CalcRouteLength(_routeList);

            if (unsorted_route_length < sorted_route_length)
            {
                _routeList.Clear();
                _routeList.AddRange(unsort_route);
            }

            return _routeList;
        }

        private List<Point> ConvexHullInsertion()
        {
            _routeList.AddRange(_convex_hull);

            for (int i = 0; i < _inside_points.Count; i++)
            {
                double minCos = Calculator.GetCOS(_routeList[0], _inside_points[i], _routeList[1]); // variables value when j = 0 in loop
                int pos = 0; // first selected position in route

                for (int j = 1; j < _routeList.Count - 1; j++)
                {
                    double cos = Calculator.GetCOS(_routeList[j], _inside_points[i], _routeList[j + 1]);

                    if (cos >= minCos)
                    {
                        minCos = cos;
                        pos = j;
                    }
                }

                AddToRouteAtPos(pos + 1, _inside_points[i]);
            }
            return _routeList;
        }

        /// <summary>
        /// Add point at the selected position in route
        /// </summary>
        private void AddToRouteAtPos(int position, Point point)
        {

            List<Point> newRoute = new List<Point> { };

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

                if (i == position)
                    newRoute.Add(point);

                newRoute.Add(_routeList[i]);
            }
            _routeList.Clear();
            _routeList.AddRange(newRoute);
        }

        /// <summary>
        /// Jarvis march algorithm, also known as gift wrappening algorithm.
        /// If not stop it on a start point when wrappening is finished, will create a spiral route
        /// </summary>
        public void JarvisMarch(bool getSpiralRoute = false)
        {
            _routeList.Clear();
            _convex_hull.Clear();
            _inside_points.Clear();

            List<Point> points = new List<Point> { };
            points.AddRange(_all_points);

            Point falsePoint = new Point(_startPoint.X - 1, _startPoint.Y); // line(vector) point where wrappening starts (counterclockwise)
            
            // axes directions -> ↓(Y) →(X)
            _convex_hull.Add(_startPoint);
            _convex_hull.Add(falsePoint);

            Point point = points[0];
            
            if(!getSpiralRoute)
                points.Add(_startPoint); // if we want to wrap points

            int ki = 0;

            do
            {
                double max_cos = -1; // cos(0°...90°...180°) = 1...0...-1 
                Point nextPoint = _startPoint;

                for (int i = 0; i < points.Count; i++)
                { // where cos is min that point is next
                    double cos = Calculator.GetCOS(_convex_hull[ki], _convex_hull[ki + 1], points[i]); // шукаємо косинус кута між векторами
                                                                                                    //Console.WriteLine("cos = " + 
                    if (cos > max_cos) // the less cos the larger angle between vectors
                    {
                        max_cos = cos;
                        nextPoint = points[i];
                    }
                }

                point = nextPoint;
                ki++;
                points.Remove(nextPoint);
                _convex_hull.Add(nextPoint);
            }
            while (point != _startPoint);

            _convex_hull.Remove(falsePoint);
            _inside_points.AddRange(points);

            if (getSpiralRoute)
            {
                _routeList = _convex_hull;
            } 
        }

        /// <summary>
        /// Sort points inside convex hull by they mass center
        /// </summary>
        private void SortInsidePoints() // TODO: I definitely wanted to improve something here.
        { 
            Point center = Calculator.FindCentroid(_all_points);
            Dictionary<Point, double> dict = new Dictionary<Point, double> { };

            for (int i = 0; i < _inside_points.Count; i++)
            {
                double dist = Calculator.CalcDistance(center, _inside_points[i]);
                dict.Add(_inside_points[i], dist);
            }

            dict = Calculator.SortDictionaryByValue(dict);

            _inside_points.Clear();
            _inside_points.AddRange(Calculator.DictionaryToList(dict));
        }

        public List<Point> CalculateRouteBruteForce(List<Point> pointList)
        {
            if (pointList.Count < 10)
            {
                List<Point> points = new List<Point> { };
                points.Add(_startPoint);
                points.AddRange(pointList);
                points.Add(_startPoint);

                _length = double.MaxValue;
                RecursivePermutation(1, points);
            }

            return _routeList;
        }

        private void RecursivePermutation(int startPos, List<Point> points) // first and last points are fixed
        {
            int size = points.Count;

            if (startPos == size - 1)
            {
                double newLength = Calculator.CalcRouteLength(points);
                if (newLength < _length)
                {
                    _length = newLength;
                    _routeList.Clear();
                    _routeList.AddRange(points);
                }
            }
            else
            {
                for (int j = startPos; j < size - 1; ++j)
                {
                    Swap(startPos, j, points);
                    startPos++;
                    RecursivePermutation(startPos, points);
                    startPos--;
                    Swap(startPos, j, points);
                }
            }
        }

        private void Swap(int pos_1, int pos_2, List<Point> points)
        {
            Point point = points[pos_1];
            points[pos_1] = points[pos_2];
            points[pos_2] = point;
        }

        public List<Point> CalculateRouteByNearestNeighbour(List<Point> pointList)
        {
            List<Point> points = new List<Point> { };
            points.AddRange(pointList);
            List<bool> pointIsUsed = new List<bool> {};

            foreach (Point point in points)
            {
                pointIsUsed.Add(false);
            } 

            List<Point> route = new List<Point> { _startPoint };
            Point current_point = _startPoint;

            for (int j = 0; j < points.Count; j++)
            {
                int min_point_index = 0;
                double min_distance = double.MaxValue;

                for (int i = 0; i < points.Count; i++)
                {
                    if (!pointIsUsed[i])
                    {
                        double distance = Calculator.CalcDistance(current_point, points[i]);

                        if (distance < min_distance)
                        {
                            min_distance = distance;
                            min_point_index = i;
                        }
                    }
                }

                current_point = points[min_point_index];
                pointIsUsed[min_point_index] = true;
                route.Add(current_point);
            }

            route.Add(_startPoint);
            _routeList = route;
            return route;
        }

        public List<Point> CalculateRouteByFPPWR(List<Point> pointList, int x_count, int y_count, double width, double heigth)
        {
            List<Point> points = new List<Point> { };
            points.AddRange(pointList);
            List<Point> route = new List<Point> { _startPoint };

            // cell sides size
            double x_side = width / x_count;
            double y_side = heigth / y_count;

            for (int iy = 0; iy < y_count; iy++)
            {
                double y_up = y_side * iy;
                double y_down = y_side * (iy + 1);

                if (iy % 2 == 0)
                {
                    for (int ix = 0; ix < x_count; ix++)
                    {
                        double x_left = x_side * ix;
                        double x_right = x_side * (ix + 1);
                        
                        List<Point> cell = GetCellPointList(points, x_left, x_right, y_up, y_down, route);
                        cell = Calculator.SortPointListByX(cell);

                        route.AddRange(cell);
                    }
                }
                else {
                    for (int ix = x_count; ix > 0; ix--)
                    {
                        double x_right = x_side * ix;
                        double x_left = x_side * (ix - 1);

                        List<Point> cell = GetCellPointList(points, x_left, x_right, y_up, y_down, route);
                        cell = Calculator.SortPointListByX(cell);
                        cell.Reverse();
                        route.AddRange(cell);
                    }
                }
            }

            route.Add(_startPoint);
            _routeList = route;
            return route;
        }

        private List<Point> GetCellPointList(List<Point> points, double x_left, double x_rigth, double y_up, double y_down, List<Point> route)
        {
            List<Point> cell = new List<Point> { };

            foreach (Point point in points)
            {
                if ((point.X >= x_left) && (point.X) <= x_rigth)
                {
                    if ((point.Y >= y_up) && (point.Y) <= y_down)
                    {
                        if (!route.Contains(point))
                        {
                            cell.Add(point);
                        }
                    }
                }
            }
            return cell;
        }
    }
}