gzxl 发表于 2025-9-22 21:26
1742669 条直线直接干废了。
楼主的方法的确很好，我的还要进一步优化
控制了下节点深度，明显速度提升了不少。 收工...
输入直线连接容差<0.001>:0.001
指定对角点: 找到 130537 个
曲线连接用时 266 毫秒
绘制多段线共 2838 条，用时 16 毫秒
输入直线连接容差<0.001>:0.001
指定对角点: 找到 1742669 个
曲线连接用时 11109 毫秒
绘制多段线共 10154 条，用时 156 毫秒
本帖最后由 highflybird 于 2025-9-23 23:08 编辑
优化了算法，不用四叉树，只是采用了哈希表。速度得到极大提升。
命令: LJ
选择对象: 指定对角点: 找到 130537 个
选择对象:
收集 用时: 0.032852 秒.---收集是指的采集线段的两个端点
连接 用时: 0.128950 秒.---连接是把相连的线段（包括曲线）连接起来。
找到了2509条相连的曲线。
和楼主同样的容差 ，最后合并的线条数更少。
容差设置为0.1的时候，合并的线条数我这边运行的结果是：2478
我在这里把核心代码贴出来
此算法采用了hash_map和DFS
//方法二：采用hash_map
void QT::QuadTree::findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId> > & out)
{
Acad::ErrorStatus es;
AcDbExtents exts;
std::vector<Point> points;
if (objs.empty()) return;
TimeCounter tt;
for (int i = 0, k = 0; i < (int)objs.size(); ++i)
{
AcDbObjectId id = objs;
AcDbObjectPointer<AcDbCurve> curve(id, AcDb::kForRead);
es = curve.openStatus();
if (es != Acad::eOk) continue;
Point pt1, pt2;
curve->getStartPoint(pt1);
curve->getEndPoint(pt2);
pt1.z = 0; //Z坐标归零
pt2.z = 0; //Z坐标归零
pt1.id = id;
pt2.id = id;
pt1.index = k++;
pt2.index = k++;
points.push_back(pt1);
points.push_back(pt2);
if (curve->isClosed() || pt1.distanceTo(pt2) < Point::pointTol)
{
points.bClosed = true;
points.bClosed = true;
}
}
tt.PrintTime(_T("收集"));
std::vector<Point*> pp(points.size());
for (size_t i =0; i<points.size();++i)
{
pp = & points;
}
for (size_t i =0; i<points.size();++i)
{
points.pNext = pp;
points.pNext = pp;
++i;
}
//点按照先x后y从小到大排序，然后相同（相近）位置的分为一组
std::sort(pp.begin(),pp.end(),Point_Comp());
hash_map<int, std::vector<Point*> > hashPoints;
std::set<int> allGroups;
for (int i = 0, j = 0; i < (int)pp.size(); ++j)
{
Point* pt = pp;
pt->iGroup = j;
hashPoints.push_back(pt);
allGroups.insert(j);
i++;
for(;i<pp.size();++i)
{
if (pp->distanceTo(*pp) > 1e-1)
{
break;
}
pp->iGroup = j;
hashPoints.push_back(pp);
}
}
//DFS 算法得出相连的线段
while (!allGroups.empty())
{
int i =*allGroups.begin();
Point* pt = *(hashPoints.begin());
std::vector<AcDbObjectId> Ids;
findConnected(pt, hashPoints, Ids, allGroups);
out.push_back(Ids);
}
tt.PrintTime(_T("连接"));
}
//方法二的子程序
void QT::QuadTree::findConnected(Point* pt, hash_map<int, std::vector<Point*> > & hashPoints, std::vector<AcDbObjectId>& outIds, std::set<int> & allGroups)
{
if (pt->bVisited) return;
std::vector<Point*>& ptSame = hashPoints;
allGroups.erase(pt->iGroup);
for (size_t i = 0; i < ptSame.size(); ++i)
{
ptSame->bVisited = true;
if (!ptSame->pNext->bVisited)
{
outIds.push_back(ptSame->id);
}
}
for (size_t i = 0; i < ptSame.size(); ++i)
{
if (!ptSame->pNext->bVisited)
{
findConnected(ptSame->pNext, hashPoints, outIds, allGroups);
}
}
}
再次改善了以前的用四叉树的算法，没用到哈希表，也得到不错的速度，
命令: LJ
选择对象: 指定对角点: 找到 130537 个
选择对象:
收集 用时: 0.040853 秒.
连接 用时: 0.583467 秒.
找到了2377条相连的曲线。
四叉树似乎更准确 ，在0.1的误差（或者间隙）范围内，可以相连在一起的，是2377条。
对于楼主这个图，0.1这个数值比较合理。
两种方法比较：哈希表+DFS,速度更快，四叉树+DFS准确度更高。
我再想办法提高哈希表的准确度。
本帖最后由 gzxl 于 2025-9-24 13:42 编辑
highflybird 发表于 2025-9-24 13:11
再次改善了以前的用四叉树的算法，没用到哈希表，也得到不错的速度，
0.1 允许容差，不知道我哪里代码出 bug了，整出了 11957 条
输入直线连接容差<0.001>:0.1
请框选需要连接的直线
指定对角点: 找到 130537 个
直线连接用时 312 毫秒
绘制多段线共 11957 条，用时 125 毫秒（应该是绘制越少，越证明连接成功）
这个是0.1间隙下的可连接线段图，用各种不同颜色以使得能看清楚哪些线段是连在一起的。
连接到一起的部分我没处理了，但是那部分程序我已经做了。那部分处理的时间较短。
HashTable+DFS 确实比四叉树快了一半以上时间，特别是在大容量数据。
gzxl 发表于 2025-9-26 13:03
HashTable+DFS 确实比四叉树快了一半以上时间，特别是在大容量数据。
嗯，现在只要是CAD内存支持，估计千万级别的也能跑下来，可惜，不能跑并行。不然会更快