一个c#写的葛立恒凸包算法....网上还有安德鲁算法,分治法....
我竟然收了半天没看到可以直接拿来用的..还是小轩轩给我的....
还可以去这个博客看cpp的代码: https://www.cnblogs.com/VividBinGo/p/11637684.html
葛立恒凸包算法:
db.Action(tr => 的委托见:https://www.cnblogs.com/JJBox/p/12196287.html
#if !HC2020
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System.Collections.Generic;
using System.Linq;
#else
using GrxCAD.DatabaseServices;
using GrxCAD.EditorInput;
using GrxCAD.Geometry;
using GrxCAD.ApplicationServices;
using GrxCAD.Runtime;
using GrxCAD.Colors;
using GrxCAD.GraphicsInterface;
using Viewport = GrxCAD.DatabaseServices.Viewport;
#endif
namespace JoinBox.src.数学操作
{
public class Graham
{
/*
视频参考: https://www.bilibili.com/video/BV1v741197YM
相关学习: https://www.cnblogs.com/VividBinGo/p/11637684.html
① 找到所有点中最左下角的点_p0(按 x 升序排列，如果 x 相同，则按 y 升序排列)
② 以_p0为基准求所有点的极角,并按照极角排序(按极角升序排列,若极角相同,则按距离升序排列),设这些点为p1,p2,……,pn-1
③ 建立一个栈,_p0,p1进栈，对于P[2..n-1]的每个点,利用叉积判断,
若栈顶的两个点与它不构成"向左转(逆时针)"的关系,则将栈顶的点出栈,直至没有点需要出栈以后,将当前点进栈
④ 所有点处理完之后栈中保存的点就是凸包了。
*/
/// <summary>
/// 最靠近x轴的点(必然是凸包边界的点)
/// </summary>
private Point2d _p0;
/// <summary>
/// 角度p0和pn的角度
/// </summary>
/// <param name="pn"></param>
/// <returns></returns>
private double Cosine(Point2d pn)
{
double d = _p0.GetDistanceTo(pn);
//距离是相同返回1.0表示true:那么求角度(高/斜)==sin(角度)
return d == 0.0 ? 1.0 : (pn.Y - _p0.Y) / d;
}
/// <summary>
/// 叉乘,顺时针方向为真,表示要剔除
/// </summary>
/// <param name="n"></param>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private bool Clockwise(Point2d n, Point2d a, Point2d b)
{
return ((a.X - b.X) * (a.Y - n.Y) - (a.X - n.X) * (a.Y - b.Y)) > -1e-6;
}
/// <summary>
/// 葛立恒求凸包
/// </summary>
/// <param name="pts"></param>
/// <returns></returns>
private Point2d[] ConvexHull(List<Point2d> pts)
{
//靠近x轴的点
_p0 = pts.OrderBy(p => p.X).ThenBy(p => p.Y).Last();
//按角度及距离排序
pts = pts.OrderByDescending(p => Cosine(p)).ThenBy(p => _p0.GetDistanceTo(p)).ToList();
var stack = new Stack<Point2d>();
stack.Push(_p0);//顶部加入对象
stack.Push(pts[1]);
bool tf = true;
//遍历所有的点,因为已经角度顺序,所有是有序遍历.从第三个点开始
for (int i = 2; i < pts.Count; i++)
{
Point2d qn = pts[i]; //第一次为p2,相当于pn
Point2d q1 = stack.Pop(); //第一次为p1,相当于前一个点,删除顶部对象(相当于点回退)
Point2d q0 = stack.Peek();//第一次为_p0,相当于后面一个点,查询顶部对象
while (tf && Clockwise(qn, q1, q0))//顺时针方向为真,表示要剔除
{
if (stack.Count > 1)//保护栈中_p0不剔除
{
stack.Pop();//删除顶部对象(相当于删除前一个点进行回退)
//前后点交换,用于while循环,
//可参考 https://www.bilibili.com/video/BV1v741197YM 04:15
//栈顶就是回滚之后的,再次和qn进行向量叉乘,看看是不是顺时针,是就继续回滚..
//否则结束循环后加入栈中.
q1 = q0;
q0 = stack.Peek();
}
else
{
tf = false;
}
}
stack.Push(q1);
stack.Push(qn);
tf = true;
}
return stack.ToArray();
}
/// <summary>
/// 葛立恒求法
/// </summary>
[CommandMethod("Test_Gra")]
public void Test_Gra()
{
Document doc = Application.DocumentManager.MdiActiveDocument;
Editor ed = doc.Editor;
Database db = doc.Database;//当前的数据库
ed.WriteMessage("\n****{惊惊盒子}葛立恒求凸包,选择曲线:");
//定义选择集选项
var pso = new PromptSelectionOptions
{
RejectObjectsOnLockedLayers = true, //不选择锁定图层对象
AllowDuplicates = true, //不允许重复选择
};
var ssPsr = ed.GetSelection(pso);//手选 这里输入al会变成all,无法删除ssget的all关键字
if (ssPsr.Status != PromptStatus.OK)
{
return;
}
db.Action(tr =>
{
var pts = new List<Point2d>();
foreach (ObjectId id in ssPsr.Value.GetObjectIds())
{
var ent = id.ToEntity(tr);
if (ent is Curve curve)
{
var cs = new CurveSample<Point2d>(curve, 300);
pts.AddRange(cs.GetSamplePoints);
}
else if (ent is DBPoint dbPt)
{
pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
}
}
Point2d[] npts = ConvexHull(pts);
var bv = new List<BulgeVertex>();
for (int i = 0; i < npts.Length; i++)
{
bv.Add(new BulgeVertex(npts[i], 0));
}
Entity pl = EntityAdd.AddPolyLineToEntity(0, bv);
tr.AddEntityToMsPs(db, pl);
});
}
}
}
View Code
cad曲线采样:
namespace JoinBox.src.数学操作
{
public class CurveSplit<TPoint> where TPoint : struct, IFormattable
{
Curve _curve { get; set; }
double _fixedValue { get; set; }
/// <summary>
/// 求间隔点
/// </summary>
/// <param name="curve">曲线</param>
/// <param name="fixedValue">定值分割</param>
public CurveSplit(Curve curve, double fixedValue)
{
_curve = curve;
_fixedValue = fixedValue;
}
/// <summary>
/// 获取定值分割的曲线集合
/// </summary>
/// <returns></returns>
public List<Curve> GetSplitCurves
{
get
{
var lstCurves = new List<Curve>();
//算曲线长度
double totalLength = _curve.GetLength();
//若少于定值,则直接返回这长度
if (totalLength < _fixedValue)
{
lstCurves.Add(_curve);
return lstCurves;
}
double addLength = 0;
var pt3dCol = new Point3dCollection();
//这段代码通过定值采集点
while (addLength < totalLength)
{
//求起点到长度的点
pt3dCol.Add(_curve.GetPointAtDist(addLength));
addLength += _fixedValue;
}
if (addLength != totalLength)
{
pt3dCol.Add(_curve.GetPointAtDist(totalLength));
}
//通过点集,分割曲线,可能有精度问题......
var splits = _curve.GetSplitCurves(pt3dCol);
foreach (var item in splits)
{
lstCurves.Add((Curve)item);
}
splits.Dispose();//释放
return lstCurves;
}
}
}
public class CurveSample<TPoint> where TPoint : struct, IFormattable
{
Curve _curve { get; set; }
int _numSample { get; set; } = 1;
/// <summary>
/// 求采样
/// </summary>
/// <param name="curve">曲线</param>
/// <param name="numSample">采样份数</param>
public CurveSample(Curve curve, int numSample)
{
_curve = curve;
_numSample = numSample;
}
/// <summary>
/// 曲线采样
/// </summary>
/// <returns></returns>
public List<TPoint> GetSamplePoints
{
get
{
if (_numSample == 0)
{
throw new System.Exception("NumSample参数不能为0");
}
// https://www.cnblogs.com/luludongxu/p/5669729.html
// 泛型构造传参
// 泛型是point2d时候参数是XY,我传入的obj数组有3个值,竟然能自动忽略到末尾的z
Type T = typeof(TPoint);
var length = _curve.GetLength();
var fixedValue = length / _numSample;
var cs = new CurveSplit<TPoint>(_curve, fixedValue);
var spls = cs.GetSplitCurves;
var pts = new List<TPoint>();
pts.Add((TPoint)Activator.CreateInstance(T, spls[0].StartPoint.ToArray()));//起点
foreach (var item in spls)
{
pts.Add((TPoint)Activator.CreateInstance(T, item.EndPoint.ToArray()));//间隔点,尾点
}
return pts;
}
}
}
}
View Code
它可以用来求最小包围盒....下次再写