四叉树+哈希表应用之:连接直线，运行速度很快

highflybird

gzxl 发表于 2025-9-22 21:26
1742669 条直线直接干废了。

楼主的方法的确很好，我的还要进一步优化

gzxl

控制了下节点深度，明显速度提升了不少。 收工...

输入直线连接容差<0.001>:0.001
指定对角点: 找到 130537 个
曲线连接用时 266 毫秒
绘制多段线共 2838 条，用时 16 毫秒

输入直线连接容差<0.001>:0.001
指定对角点: 找到 1742669 个
曲线连接用时 11109 毫秒
绘制多段线共 10154 条，用时 156 毫秒

highflybird

优化了算法，不用四叉树，只是采用了哈希表。速度得到极大提升。




命令: LJ
选择对象: 指定对角点: 找到 130537 个
选择对象:
收集 用时: 0.032852 秒.  ---收集是指的采集线段的两个端点
连接 用时: 0.128950 秒.  ---连接是把相连的线段（包括曲线）连接起来。
找到了2509条相连的曲线。

和楼主同样的容差 ，最后合并的线条数更少。

容差设置为0.1的时候，合并的线条数我这边运行的结果是：2478

highflybird

我在这里把核心代码贴出来
此算法采用了hash_map和DFS

1. //方法二：采用hash_map
   
2. void QT::QuadTree::findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId> > & out)
   
3. {
   
4.   Acad::ErrorStatus es;
   
5.   AcDbExtents exts;
   
6.   std::vector<Point> points;
   
7.   if (objs.empty()) return;
   
8. 
   
9.   TimeCounter tt;
   
10.   for (int i = 0, k = 0; i < (int)objs.size(); ++i)
    
11.   {
    
12.     AcDbObjectId id = objs;
    
13.     AcDbObjectPointer<AcDbCurve> curve(id, AcDb::kForRead);
    
14.     es = curve.openStatus();
    
15.     if (es != Acad::eOk) continue;
    
16.     Point pt1, pt2;
    
17.     curve->getStartPoint(pt1);
    
18.     curve->getEndPoint(pt2);
    
19.     pt1.z = 0; //Z坐标归零
    
20.     pt2.z = 0; //Z坐标归零
    
21.     pt1.id = id;
    
22.     pt2.id = id;
    
23.     pt1.index = k++;
    
24.     pt2.index = k++;
    
25.     points.push_back(pt1);
    
26.     points.push_back(pt2);
    
27.     if (curve->isClosed() || pt1.distanceTo(pt2) < Point::pointTol)
    
28.     {
    
29.       points[k - 1].bClosed = true;
    
30.       points[k - 2].bClosed = true;
    
31.     }
    
32.   }
    
33.   tt.PrintTime(_T("收集"));
    
34. 
    
35.   std::vector<Point*> pp(points.size());
    
36.   for (size_t i =0; i<points.size();++i)
    
37.   {
    
38.     pp = & points;
    
39.   }
    
40. 
    
41.   for (size_t i =0; i<points.size();++i)
    
42.   {
    
43.     points.pNext = pp[i+1];
    
44.     points[i+1].pNext = pp;
    
45.     ++i;
    
46.   }
    
47. 
    
48.   //点按照先x后y从小到大排序，然后相同（相近）位置的分为一组
    
49.   std::sort(pp.begin(),pp.end(),Point_Comp());
    
50.   hash_map<int, std::vector<Point*> > hashPoints;
    
51.   std::set<int> allGroups;
    
52.   for (int i = 0, j = 0; i < (int)pp.size(); ++j)
    
53.   {
    
54.     Point* pt = pp;
    
55.     pt->iGroup = j;
    
56.     hashPoints[j].push_back(pt);
    
57.     allGroups.insert(j);
    
58.     i++;
    
59.     for(;i<pp.size();++i)
    
60.     {
    
61.       if (pp->distanceTo(*pp[i-1]) > 1e-1)
    
62.       {
    
63.         break;
    
64.       }
    
65.       pp->iGroup = j;
    
66.       hashPoints[j].push_back(pp);
    
67.     }
    
68.   }
    
69. 
    
70.   //DFS 算法得出相连的线段
    
71.   while (!allGroups.empty())
    
72.   {
    
73.     int i =  *allGroups.begin();
    
74.     Point* pt = *(hashPoints.begin());
    
75.     std::vector<AcDbObjectId> Ids;
    
76.     findConnected(pt, hashPoints, Ids, allGroups);
    
77.     out.push_back(Ids);
    
78.   }
    
79.   tt.PrintTime(_T("连接"));
    
80. }
    
81. 
    
82. //方法二的子程序
    
83. void QT::QuadTree::findConnected(Point* pt, hash_map<int, std::vector<Point*> > & hashPoints, std::vector<AcDbObjectId>& outIds, std::set<int> & allGroups)
    
84. {
    
85.   if (pt->bVisited) return;
    
86.   std::vector<Point*>& ptSame = hashPoints[pt->iGroup];
    
87.   allGroups.erase(pt->iGroup);
    
88.   for (size_t i = 0; i < ptSame.size(); ++i)
    
89.   {
    
90.     ptSame->bVisited = true;
    
91.     if (!ptSame->pNext->bVisited)
    
92.     {
    
93.       outIds.push_back(ptSame->id);
    
94.     }
    
95.   }
    
96. 
    
97.   for (size_t i = 0; i < ptSame.size(); ++i)
    
98.   {
    
99.     if (!ptSame->pNext->bVisited)
    
100.     {
     
101.       findConnected(ptSame->pNext, hashPoints, outIds, allGroups);
     
102.     }
     
103.   }
     
104. }

//方法二：采用hash_map<br /> void QT::QuadTree::findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId> > & out)<br /> {<br />   Acad::ErrorStatus es;<br />   AcDbExtents exts;<br />   std::vector<Point> points;<br />   if (objs.empty()) return;<br /> <br />   TimeCounter tt;<br />   for (int i = 0, k = 0; i < (int)objs.size(); ++i)<br />   {<br />     AcDbObjectId id = objs<i>;<br />     AcDbObjectPointer<AcDbCurve> curve(id, AcDb::kForRead);<br />     es = curve.openStatus();<br />     if (es != Acad::eOk) continue;<br />     Point pt1, pt2;<br />     curve->getStartPoint(pt1);<br />     curve->getEndPoint(pt2);<br />     pt1.z = 0; //Z坐标归零<br />     pt2.z = 0; //Z坐标归零<br />     pt1.id = id;<br />     pt2.id = id;<br />     pt1.index = k++;<br />     pt2.index = k++;<br />     points.push_back(pt1);<br />     points.push_back(pt2);<br />     if (curve->isClosed() || pt1.distanceTo(pt2) < Point::pointTol)<br />     {<br />       points[k - 1].bClosed = true;<br />       points[k - 2].bClosed = true;<br />     }<br />   }<br />   tt.PrintTime(_T("收集"));<br /> <br />   std::vector<Point*> pp(points.size());<br />   for (size_t i =0; i<points.size();++i)<br />   {<br />     pp<i> = & points<i>;<br />   }<br /> <br />   for (size_t i =0; i<points.size();++i)<br />   {<br />     points<i>.pNext = pp[i+1];<br />     points[i+1].pNext = pp<i>;<br />     ++i;<br />   }<br /> <br />   //点按照先x后y从小到大排序，然后相同（相近）位置的分为一组<br />   std::sort(pp.begin(),pp.end(),Point_Comp());<br />   hash_map<int, std::vector<Point*> > hashPoints;<br />   std::set<int> allGroups;<br />   for (int i = 0, j = 0; i < (int)pp.size(); ++j)<br />   {<br />     Point* pt = pp<i>;<br />     pt->iGroup = j;<br />     hashPoints[j].push_back(pt);<br />     allGroups.insert(j);<br />     i++;<br />     for(;i<pp.size();++i)<br />     {<br />       if (pp<i>->distanceTo(*pp[i-1]) > 1e-1)<br />       {<br />         break;<br />       }<br />       pp<i>->iGroup = j;<br />       hashPoints[j].push_back(pp<i>);<br />     }<br />   }<br /> <br />   //DFS 算法得出相连的线段<br />   while (!allGroups.empty())<br />   {<br />     int i =  *allGroups.begin();<br />     Point* pt = *(hashPoints<i>.begin());<br />     std::vector<AcDbObjectId> Ids;<br />     findConnected(pt, hashPoints, Ids, allGroups);<br />     out.push_back(Ids);<br />   }<br />   tt.PrintTime(_T("连接"));<br /> }<br /> <br /> //方法二的子程序<br /> void QT::QuadTree::findConnected(Point* pt, hash_map<int, std::vector<Point*> > & hashPoints, std::vector<AcDbObjectId>& outIds, std::set<int> & allGroups)<br /> {<br />   if (pt->bVisited) return;<br />   std::vector<Point*>& ptSame = hashPoints[pt->iGroup]; <br />   allGroups.erase(pt->iGroup);<br />   for (size_t i = 0; i < ptSame.size(); ++i)<br />   {<br />     ptSame<i>->bVisited = true;<br />     if (!ptSame<i>->pNext->bVisited)<br />     {<br />       outIds.push_back(ptSame<i>->id);<br />     }<br />   }<br /> <br />   for (size_t i = 0; i < ptSame.size(); ++i)<br />   {<br />     if (!ptSame<i>->pNext->bVisited)<br />     {<br />       findConnected(ptSame<i>->pNext, hashPoints, outIds, allGroups);<br />     }<br />   }<br /> }

highflybird

再次改善了以前的用四叉树的算法，没用到哈希表，也得到不错的速度，


命令: LJ
选择对象: 指定对角点: 找到 130537 个
选择对象:
收集 用时: 0.040853 秒.
连接 用时: 0.583467 秒.
找到了2377条相连的曲线。


四叉树似乎更准确 ，在0.1的误差（或者间隙）范围内，可以相连在一起的，是2377条。
对于楼主这个图，0.1这个数值比较合理。

两种方法比较：哈希表+DFS,速度更快，四叉树+DFS准确度更高。
我再想办法提高哈希表的准确度。

gzxl

highflybird 发表于 2025-9-24 13:11
再次改善了以前的用四叉树的算法，没用到哈希表，也得到不错的速度，

0.1 允许容差，不知道我哪里代码出 bug了，整出了 11957 条

输入直线连接容差<0.001>:0.1
请框选需要连接的直线
指定对角点: 找到 130537 个
直线连接用时 312 毫秒
绘制多段线共 11957 条，用时 125 毫秒（应该是绘制越少，越证明连接成功）

highflybird

这个是0.1间隙下的可连接线段图，用各种不同颜色以使得能看清楚哪些线段是连在一起的。
连接到一起的部分我没处理了，但是那部分程序我已经做了。那部分处理的时间较短。

gzxl

HashTable+DFS 确实比四叉树快了一半以上时间，特别是在大容量数据。

highflybird

gzxl 发表于 2025-9-26 13:03
HashTable+DFS 确实比四叉树快了一半以上时间，特别是在大容量数据。

嗯，现在只要是CAD内存支持，估计千万级别的也能跑下来，可惜，不能跑并行。不然会更快

gzxl