پوش محدب

 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GrahamScan
{
    class GrahamScan
    {
        const int TURN_LEFT = 1;
        const int TURN_RIGHT = -1;
        const int TURN_NONE = 0;
        public int turn(Point p, Point q, Point r)
        {
            return ((q.getX() - p.getX()) * (r.getY() - p.getY())
 - (r.getX() - p.getX()) * (q.getY() - p.getY())).CompareTo(0);
        }

        public void keepLeft(List<Point> hull, Point r)
        {
            while (hull.Count> 1 &&
 turn(hull[hull.Count - 2], hull[hull.Count - 1], r) != TURN_LEFT)
            {
                //Removing Point ({0}, {1}) because turning right
                hull.RemoveAt(hull.Count - 1);
            }
            if (hull.Count == 0 || hull[hull.Count - 1] != r)
            {
                //Adding Point ({0}, {1})
                hull.Add(r);
            }    
        }

        public double getAngle(Point p1, Point p2)
        {
            float xDiff = p2.getX() - p1.getX();
            float yDiff = p2.getY() - p1.getY();
            return Math.Atan2(yDiff, xDiff) * 180.0 / Math.PI;
        }

        public List<Point> MergeSort(Point p0, List<Point> arrPoint)
        {
            if (arrPoint.Count == 1)
            {
                return arrPoint;
            }
            List<Point> arrSortedInt = new List<Point>();
            int middle = (int)arrPoint.Count / 2;
            List<Point> leftArray = arrPoint.GetRange(0, middle);
            List<Point> rightArray = arrPoint.GetRange(middle, arrPoint.Count - middle);
            leftArray = MergeSort(p0, leftArray);
            rightArray = MergeSort(p0, rightArray);
            int leftptr = 0;
            int rightptr = 0;
            for (int i = 0; i <leftArray.Count + rightArray.Count; i++)
            {
                if (leftptr == leftArray.Count)
                {
                    arrSortedInt.Add(rightArray[rightptr]);
                    rightptr++;
                }
                else if (rightptr == rightArray.Count)
                {
                    arrSortedInt.Add(leftArray[leftptr]);
                    leftptr++;
                }
                else if (getAngle(p0, leftArray[leftptr]) <getAngle(p0, rightArray[rightptr]))
                {
                    arrSortedInt.Add(leftArray[leftptr]);
                    leftptr++;
                }
                else
                {
                    arrSortedInt.Add(rightArray[rightptr]);
                    rightptr++;
                }
            }
            return arrSortedInt;
        }

        public List<Point> convexHull(List<Point> points)
        {
            //let p[0] be the point in Q with the minimum y-coordinate
        
            Point p0 = null;
            foreach (Point value in points)
            {
                if (p0 == null)
                    p0 = value;
                else
                {
                    if (p0.getY()> value.getY())
                        p0 = value;
                }
            }

            //the left most such point in case of a tie
            List<Point> order = new List<Point>();
            order.Add(p0);
            foreach (Point value in points)
            {
                if (p0 != value)
                    order.Add(value);
            }
            //sorted by polar angle in counterclockwise order around p[0]
            //if more than one point has the same angle, remove it
            order = MergeSort(p0, order);           
            //add first 3  point
            List<Point> result = new List<Point>();
            result.Add(p0);
            result.Add(order[0]);
            result.Add(order[1]);
            //remove 2 element form order list
            order.RemoveAt(0);
            order.RemoveAt(0);
            //Current Convex Hull           
            foreach (Point value in order)
            {
                keepLeft(result, value);
            }

            return result;
        }

       
    }
}