内容转载自：
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; }
}
}
}
网友评论