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) { 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; //node.Value = nodes[i]; } else if (direct == -10) { list_node.Last.Value = nodes[i]; //node = list_node.Last //node.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]); } } 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); } } 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; } 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; } } } public partial class Form1 : Form { private List<PointF> nodes; private Graphics g; private Pen pen; public Form1() { InitializeComponent(); g=this.panel1.CreateGraphics(); g.TranslateTransform(0f,this.panel1.Height); g.ScaleTransform(1f,-1f); pen = new Pen(Color.Blue); } private void button2_Click(object sender, EventArgs e) { g.Clear(panel1.BackColor); nodes = new List<PointF>(); nodes.Clear(); Random rand = new Random(); Point p = new Point(); ; for (int i = 0; i < 1000; i++) { p.X = rand.Next(10, panel1.Width - 9); p.Y = rand.Next(10, panel1.Height - 9); nodes.Add(p); DrawCircle(p); } } private void DrawCircle(Point p) { g.DrawEllipse(pen, p.X - 4, p.Y - 4, 8, 8); g.FillEllipse(Brushes.Blue, p.X - 4, p.Y - 4, 8, 8); } private void button1_Click(object sender, EventArgs e) { ConvexAogrithm ca = new ConvexAogrithm(nodes); PointF p; ca.GetNodesByAngle(out p); //PointF[] ps = ca.sor_nodes; //float[] psangle=new float[ps.Length]; //for (int i = 0; i < psangle.Length; i++) // psangle[i] = CalcAngle(p, ps[i]); g.DrawEllipse(pen, p.X - 8, p.Y - 8, 16,16); g.FillEllipse(Brushes.Blue, p.X - 8, p.Y - 8, 16, 16); Stack<PointF> p_nodes = ca.SortedNodes; pen = new Pen(Color.Black, 2.0f); g.SmoothingMode = SmoothingMode.HighQuality; pen.LineJoin = LineJoin.Round; g.DrawPolygon(pen, p_nodes.ToArray()); } private float CalcAngle(PointF p1,PointF p2) { float angle = (float)(Math.Atan(Math.Abs(p2.Y - p1.Y + 0.0) / Math.Abs(p2.X - p1.X + 0.0)) * 180 / Math.PI); if ((p2.Y - p1.Y + 0.0) / (p2.X - p1.X + 0.0) < 0) angle = 180 - angle; return angle; } }
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
