查找相同的种子集-四叉树示例
本帖最后由 wang2006zhi 于 2025-2-14 12:01 编辑public static void BlockSame()
{
using var tr = new DBTrans();
if (!Env.Editor.GetSelRect(out Rect selRec))
return;
//过滤块实体
var fil = OpFilter.Build(e => e.Dxf(0) != "INSERT");
if (!Env.Editor.SelIds(out List<ObjectId> ids, selRec.GetPointCollection(), fil))
return;
//选取种子集
if (!Env.Editor.GetEnts(out List<Entity> entsTemp, msg: "请选择要基准集:", fil: fil))
return;
//种子集四叉树数据
var oneGrop = new List<CadEntity>();
for (int i = entsTemp.Count - 1; i >= 0; i--)
{
var ent = entsTemp;
var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect());
oneGrop.Add(cadEnt);
}
// 种子集外包
var rectStart = oneGrop.GetCesRect();
// 参考种子
var ceSeed = oneGrop;
// 种子集相同的类似集
var oneSameGrop = new List<List<CadEntity>> { oneGrop };
//创建一个CAD进度条
using var pm = new ProgressMeter();
//添加提示语言
pm.Start($"正在构建{ids.Count}条四叉树数据...");
//设置总进度
pm.SetLimit(ids.Count);
//构造四叉树数据
var treeRoot = new QuadTree<CadEntity>(AppX.InfoRect);
//参考种子集
var cesSeed = new List<CadEntity>();
for (int i = ids.Count - 1; i >= 0; i--)
{
pm.MeterProgress();
var id = ids;
var ent = id.GetObject<Entity>();
if (ent==null)
continue;
var cadEnt = new CadEntity(id, ent.GetRect())
{
IsUsed = false,
IsSeed = false
};
if (ceSeed.IsSameEnt(cadEnt))
{
cadEnt.IsSeed = true;
cesSeed.Add(cadEnt);
}
treeRoot.Insert(cadEnt);
}
pm.Stop();
// #region 原始方案
// //查找相同种子集
// treeRoot.ForEach(nodes =>
// {
// foreach (var ceTemp in nodes.Contents)
// {
// if (!ceTemp.IsGetRect(out Rect recTemp,ceSeed,rectStart))
// continue;
// // 用相对外包搜索实体
// var oneGropTemp = treeRoot.Query(recTemp.Expand(10), QuadTreeSelectMode.Contains);
// if (!oneGropTemp.Any())
// continue;
// //过滤掉与种子集不同的实体
// var cesSearchTemp = new List<CadEntity>();
// foreach (var ceOld in oneGrop)
// {
// foreach (var ceNew in oneGropTemp)
// {
// if (!ceNew.IsUsed && ceNew.IsSameEnt(ceOld))
// cesSearchTemp.Add(ceNew);
// }
// }
//
// // 与种子集数目相同时看为一组
// if (cesSearchTemp.Count != oneGrop.Count)
// continue;
// var oneSame = new List<CadEntity>();
// foreach (var ce in cesSearchTemp)
// {
// oneSame.Add(ce);
// ce.IsUsed = true;
// }
// oneSameGrop.Add(oneSame);
// }
// return
// false;
// });
// #endregion
#region 新方案
//添加提示语言
pm.Start($"正在查找{cesSeed.Count}条可能相同的数据...");
//设置总进度
pm.SetLimit(cesSeed.Count);
//根据种子ceSeed查找相同种子集
for (int i = cesSeed.Count - 1; i >= 0; i--)
{
pm.MeterProgress();
var ceTemp = cesSeed;
if (!ceTemp.IsGetRect(out Rect recTemp, ceSeed, rectStart))
continue;
// 用相对外包搜索实体
var oneGropTemp = treeRoot.Query(recTemp.Expand(10), QuadTreeSelectMode.Contains);
if (!oneGropTemp.Any())
continue;
//过滤掉与种子集不同的实体
//与种子集可能相同的集
var cesSearchTemp = new List<CadEntity>();
for (int j = oneGrop.Count - 1; j >= 0; j--)
{
var ceOld = oneGrop;
for (int k = oneGropTemp.Count - 1; k >= 0; k--)
{
var ceNew = oneGropTemp;
if (!ceNew.IsUsed && ceNew.IsSameEnt(ceOld))
cesSearchTemp.Add(ceNew);
}
}
// 与种子集数目相同时看为一组
if (cesSearchTemp.Count != oneGrop.Count)
continue;
var oneSame = new List<CadEntity>();
foreach (var ce in cesSearchTemp)
{
oneSame.Add(ce);
ce.IsUsed = true;
}
oneSameGrop.Add(oneSame);
}
pm.Stop();
#endregion
//种子集块
var blkName = "HesiBlk_" + DateTime.Now.ToString("yyyyMMdd_HHmmss");
var btrId = entsTemp.MakeBlock(blkName);
//插入块并删除相似集
//添加提示语言
pm.Start($"正在插入{oneSameGrop.Count}个图块...");
//设置总进度
pm.SetLimit(oneSameGrop.Count);
oneSameGrop.ForEach(oneSameEs =>
{
pm.MeterProgress();
var pt = GetCesRect(oneSameEs).CenterPoint.Point3d();
var bId = tr.CurrentSpace.InsertBlock(pt.Ucs2Wcs(), btrId);
if (bId.GetObject<Entity>() is not BlockReference brf)
return;
brf.Layer = "0";
brf.Draw();
oneSameEs.ForEach(x => x.ObjectId.GetObject<Entity>()?.ForWrite(e => e.Erase(true)));
});
pm.Stop();
Env.Editor.WriteMessage($"\n共插入{oneSameGrop.Count}个图块！");
}
private class CadEntity(ObjectId objectId, Rect box) : QuadEntity(box)
{
/// <summary>
/// ObjectId
/// </summary>
public readonly ObjectId ObjectId = objectId;
/// <summary>
/// 是否已经用过
/// </summary>
public bool IsUsed;
/// <summary>
/// 是否种子
/// </summary>
public bool IsSeed;
/// <summary>
/// 大小比对
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
public int CompareTo(CadEntity? other)
{
if (other == null)
return -1;
return GetHashCode() ^ other.GetHashCode();
}
public override int GetHashCode()
{
return (base.GetHashCode(), objectId.GetHashCode()).GetHashCode();
}
/// <summary>
/// 判断外包大小是否相等
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
private bool IsSameSize(CadEntity other)
{
if (ObjectId.Equals(other.ObjectId))
return false;
if (Width.IsEqual(other.Width) && Height.IsEqual(other.Height))
return true;
return false;
}
/// <summary>
/// 判断两实体是否相同
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
public bool IsSameEnt(CadEntity other)
{
if (!IsSameSize(other))
return false;
var entL = ObjectId.GetObject<Entity>();
var entR = other.ObjectId.GetObject<Entity>();
if (entR != null && entL != null && entL.IsSameEnt(entR))
return true;
return false;
}
}
/// <summary>
/// 获取集合的边界
/// </summary>
/// <param name="ces">四叉树数据集</param>
/// <returns></returns>
private static Rect GetCesRect(this List<CadEntity> ces)
{
var xMin = ces.Min(x => x.X);
var yMin = ces.Min(x => x.Y);
var tMax = ces.Max(x => x.Top);
var rMax = ces.Max(x => x.Right);
return new Rect(xMin, yMin, rMax, tMax);
}
/// <summary>
/// 根据nRect中的某一个种子nCe是否成功获取到新的相对Rect
/// </summary>
/// <param name="nCe">种子</param>
/// <param name="nRect">新得的Rect</param>
/// <param name="oCe">原始种子</param>
/// <param name="oRect">原始Rect</param>
/// <returns></returns>
private static bool IsGetRect(this CadEntity nCe, out Rect nRect, CadEntity oCe, Rect oRect)
{
nRect = oRect;
if (!nCe.IsSeed)
return false;
if (nCe.IsUsed)
return false;
var vec = nCe.CenterPoint - oCe.CenterPoint;
nRect = new Rect(oRect.MinPoint + vec, oRect.MaxPoint + vec);
return true;
}
采用线程查找计算相同样本集合，，与插块（费时较多）
public static void BlockSame()
{
using var tr = new DBTrans();
if (!Env.Editor.GetSelRect(out Rect selRec))
return;
//过滤块实体
var fil = OpFilter.Build(e => e.Dxf(0) != "INSERT");
if (!Env.Editor.SelEnts(out List<Entity> ents, selRec.GetPointCollection(), fil))
return;
//选取种子集
if (!Env.Editor.GetEnts(out List<Entity> entsTemp, msg: "请选择要基准集:", fil: fil))
return;
// 种子
var ceSeed = new CadEntity(entsTemp.ObjectId, entsTemp.GetRect());
// 样本集
var oneGrop = new List<CadEntity>();
foreach (var ent in entsTemp)
{
var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect());
cadEnt.IsUsed = true;
oneGrop.Add(cadEnt);
}
//构造种子集
var cesSeed = new List<CadEntity>();
//构造四叉树
var treeRoot = new QuadTree<CadEntity>(AppX.InfoRect);
//获取四叉树数据及种子集
for (int i = ents.Count - 1; i >= 0; i--)
{
var ent = ents;
var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect())
{
IsUsed = false,
};
if (cadEnt.IsSameEnt(ceSeed))
cesSeed.Add(cadEnt);
treeRoot.Insert(cadEnt);
}
//线程任务查找相同种子集合
Task<List<List<CadEntity>>> runTask = Task.Run(() => cesSeed.FindGroup(ceSeed,treeRoot,oneGrop));
var result = runTask.Result;
InsertBlocks(result);
Env.Editor.WriteMessage($"\n 已完成{result.Count}个块添加");
void InsertBlocks(List<List<CadEntity>> list)
{
// 样本集块
var btrId = entsTemp.MakeBlock("HesiBlk_" + DateTime.Now.ToString("yyyyMMdd_HHmmss"));
var max = list.Count;
//创建一个CAD进度条
var pm = new ProgressMeter();
//添加提示语言
pm.Start($"正在插入{max}图块...");
//设置总进度
pm.SetLimit(max);
for (int i = max - 1; i >= 0; i--)
{
pm.MeterProgress();
var oneSameEs = list;
if (oneSameEs == null || !oneSameEs.Any())
return;
var pt = GetCesRect(oneSameEs).CenterPoint.Point3d();
var bId = DBTrans.GetTop(btrId.Database).CurrentSpace.InsertBlock(pt, btrId);
if (bId.GetObject<BlockReference>() is not { } brf)
return;
brf.Layer = "0";
brf.Draw();
oneSameEs.ForEach(x => x.ObjectId.GetObject<Entity>()?.ForWrite(e => e.Erase(true)));
}
pm.Stop();
}
}
/// <summary>
/// 查找相同样本
/// </summary>
/// <param name="cesTemp">种子集</param>
/// <param name="ceSeed">参考种子</param>
/// <param name="treeRoot">四叉树数据</param>
/// <param name="oneGrop">样本集</param>
/// <returns></returns>
static List<List<CadEntity>> FindGroup(this List<CadEntity> cesTemp,
CadEntity ceSeed,
QuadTree<CadEntity> treeRoot,
List<CadEntity> oneGrop)
{
//样本集一起外包。。相比与每个实体两点构造两个外包搜索快
var oRect = oneGrop.GetCesRect();
// 样本集相同的集
var oneSameGropTemp = new List<List<CadEntity>>(){oneGrop};
//遍历所有种子集合，不可避免的多重循环，小循环写在最外层相比与内部节约时间
for (int i = cesTemp.Count - 1; i >= 0; i--)
{
//临时种子与种子相对关系
var vec = cesTemp.CenterPoint - ceSeed.CenterPoint;
var nRect = new Rect(oRect.MinPoint + vec, oRect.MaxPoint + vec);
// 用相对外包搜索实体
var cesSearchTemp = treeRoot.Query(nRect.Expand(2), QuadTreeSelectMode.Contains);
if (!cesSearchTemp.Any())
continue;
//临时样本集
var oneGropTemp = new List<CadEntity>();
//过滤掉与样本集不同的实体
//遍历样本集
for (int k = oneGrop.Count - 1; k >= 0; k--)
{
var ceK = oneGrop;
//遍历搜索集中的可能实体
for (int j = cesSearchTemp.Count - 1; j >= 0; j--)
{
var ceJ = cesSearchTemp;
if (!ceJ.IsUsed && ceJ.IsSameEnt(ceK))
{
oneGropTemp.Add(ceJ);
ceJ.IsUsed = true;
}
}
}
// 与种子集数目相同时看为一组
if (oneGropTemp.Count != oneGrop.Count)
continue;
oneSameGropTemp.Add(oneGropTemp);
}
return oneSameGropTemp;
}
/// <summary>
/// 获取集合的边界
/// </summary>
/// <param name="ces">四叉树数据集</param>
/// <returns></returns>
private static Rect GetCesRect(this List<CadEntity> ces)
{
var xMin = ces.Min(x => x.X);
var yMin = ces.Min(x => x.Y);
var tMax = ces.Max(x => x.Top);
var rMax = ces.Max(x => x.Right);
return new Rect(xMin, yMin, rMax, tMax);
} dcl1214 发表于 2024-8-20 10:18
Lisp没法多线程，但是，lisp可以借助其他语言多线程，lisp将整个dwg上传上去，服务器端启动多线程，比如说1 ...
多线程要注意很多东西的,
基本需要推翻原本的单线程方案的众多想法,
着重注意锁粒度/cache miss/偷懒线程等等,
如果是发送文件这种多线程还在IO密集,
而图形学上面的处理才是CPU密集计算,
可谓是性能的两道线,
还是换到c#/c++干吧,不然还是缺少适当的训练.
别的不说,难道处理十万图元不想跑到毫秒级吗? 本帖最后由 dcl1214 于 2024-8-20 10:23 编辑
Lisp没法多线程，但是，lisp可以借助其他语言多线程，lisp将整个dwg上传上去，服务器端启动多线程，比如说100个人同时上传dwg，服务器端每个dwg启动10个线程，瞬间就是200个线程跑，负责将100个用户的dwg分析并返回给lisp，我们经常做类似的开发，我们客户都是集团的，下属很多分公司同时请求服务器，lisp只是负责发送dxf或者是数据，或者是dwg，都可以，具体看如何开发了
软件的注册授权，也顺带就做好了，非法用户，不返回数据给lisp
本帖最后由 dcl1214 于 2024-8-19 13:02 编辑
直线端点在相同点上，根据这个直接分组即可
几年前随手写的代码 相同项分组 - AutoLISP/Visual LISP 编程技术 - AutoCAD论坛 - 明经CAD社区 - Powered by Discuz! (mjtd.com)
如果直线端点处有误差，构建数据的时候加容差即可，这个代码是随便写的，应该还能提速300%甚至更高
能不能改改 代码的背景色，这是编译器，弄个深色背景啥都看不清楚 本帖最后由 wang2006zhi 于 2024-8-19 21:01 编辑
dcl1214 发表于 2024-8-19 12:59
直线端点在相同点上，根据这个直接分组即可
几年前随手写的代码 相同项分组 - AutoLISP/Visual LISP 编 ...
种子集随意。。不一定线相连，可以任意实体 没看到速度有什么差异啊,怎么不去想并行化呢? 你有种再说一遍 发表于 2024-8-19 19:41
没看到速度有什么差异啊,怎么不去想并行化呢?
不知道并行是否你口中的多线程，还不会，最好来一段Demo wang2006zhi 发表于 2024-8-19 21:02
不知道并行是否你口中的多线程，还不会，最好来一段Demo
并行必然多线程...去搜搜吧 你有种再说一遍 发表于 2024-8-20 18:12
多线程要注意很多东西的,
基本需要推翻原本的单线程方案的众多想法,
着重注意锁粒度/cache miss/偷懒线 ...
我们用go语言很多年了
页:
[1]
2