2018-10-24凸包算法

内容转载自：
https://blog.csdn.net/u010251278/article/details/50469594?utm_source=blogxgwz21
https://www.2cto.com/kf/201212/177098.html

代码实现，转自第二篇博客（添加了注释）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Drawing;

namespace pipelineSpatialAnalysis.Function.analysis
{

class ConvexAogrithm
{

    private List<PointF> nodes;

    private Stack<PointF> sortedNodes;

    public PointF[] sor_nodes;

    public ConvexAogrithm(List<PointF> points)
    {

        nodes = points;


    }

    //求两点之间的距离
    private double DistanceOfNodes(PointF p0, PointF p1)
    {

        if (p0.IsEmpty || p1.IsEmpty)

            return 0.0;

        return Math.Sqrt((p1.X - p0.X) * (p1.X - p0.X) + (p1.Y - p0.Y) * (p1.Y - p0.Y));

    }

    //获取凸包的点
    public void GetNodesByAngle(out PointF p0)
    {
        #region 先把夹角排序排出来
        LinkedList<PointF> list_node = new LinkedList<PointF>();

        p0 = GetMinYPoint();

        LinkedListNode<PointF> node = new LinkedListNode<PointF>(nodes[0]);

        list_node.AddFirst(node);

        for (int i = 1; i < nodes.Count; i++)
        {
            int direct = IsClockDirection(p0, node.Value, nodes[i]);
            if (direct == 1)
            {
                list_node.AddLast(nodes[i]);
                node = list_node.Last;              
            }
            else if (direct == -10)
            {
                list_node.Last.Value = nodes[i];
            }
            else if (direct == 10)
                continue;
            else if (direct == -1)
            {
                LinkedListNode<PointF> temp = node.Previous;
                while (temp != null && IsClockDirection(p0, temp.Value, nodes[i]) == -1)
                {
                    temp = temp.Previous;
                }
                if (temp == null)
                {
                    list_node.AddFirst(nodes[i]);
                    continue;
                }
                if (IsClockDirection(p0, temp.Value, nodes[i]) == -10)
                    temp.Value = nodes[i];
                else if (IsClockDirection(p0, temp.Value, nodes[i]) == 10)
                    continue;
                else
                    list_node.AddAfter(temp, nodes[i]);
            }

        }
        # endregion

        # region 用栈的形把点塞进去
        sor_nodes = list_node.ToArray();

        sortedNodes = new Stack<PointF>();

        sortedNodes.Push(p0);

        sortedNodes.Push(sor_nodes[0]);

        sortedNodes.Push(sor_nodes[1]);

        for (int i = 2; i < sor_nodes.Length; i++)
        {



            PointF p2 = sor_nodes[i];

            PointF p1 = sortedNodes.Pop();

            PointF p0_sec = sortedNodes.Pop();

            sortedNodes.Push(p0_sec);

            sortedNodes.Push(p1);



            if (IsClockDirection1(p0_sec, p1, p2) == 1)
            {

                sortedNodes.Push(p2);

                continue;

            }

            while (IsClockDirection1(p0_sec, p1, p2) != 1)
            {

                sortedNodes.Pop();

                p1 = sortedNodes.Pop();

                p0_sec = sortedNodes.Pop();

                sortedNodes.Push(p0_sec);

                sortedNodes.Push(p1);

            }

            sortedNodes.Push(p2);

        #endregion

        }

    }

    //是否是顺时针
    private int IsClockDirection1(PointF p0, PointF p1, PointF p2)
    {

        PointF p0_p1 = new PointF(p1.X - p0.X, p1.Y - p0.Y);

        PointF p0_p2 = new PointF(p2.X - p0.X, p2.Y - p0.Y);

        return (p0_p1.X * p0_p2.Y - p0_p2.X * p0_p1.Y) > 0 ? 1 : -1;

    }

    //获取最小的坐标Y的点
    private PointF GetMinYPoint()
    {

        PointF succNode;

        float miny = nodes.Min(r => r.Y);

        IEnumerable<PointF> pminYs = nodes.Where(r => r.Y == miny);

        PointF[] ps = pminYs.ToArray();

        if (pminYs.Count() > 1)
        {

            succNode = pminYs.Single(r => r.X == pminYs.Min(t => t.X));

            nodes.Remove(succNode);

            return succNode;

        }

        else
        {

            nodes.Remove(ps[0]);

            return ps[0];

        }



    }
    //是否是顺时针
    private int IsClockDirection(PointF p0, PointF p1, PointF p2)
    {

        PointF p0_p1 = new PointF(p1.X - p0.X, p1.Y - p0.Y);

        PointF p0_p2 = new PointF(p2.X - p0.X, p2.Y - p0.Y);

        if ((p0_p1.X * p0_p2.Y - p0_p2.X * p0_p1.Y) != 0)

            return (p0_p1.X * p0_p2.Y - p0_p2.X * p0_p1.Y) > 0 ? 1 : -1;

        else

            return DistanceOfNodes(p0, p1) > DistanceOfNodes(p0, p2) ? 10 : -10;



    }

    public Stack<PointF> SortedNodes
    {

        get { return sortedNodes; }

    }


}

}