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

gzxl

四叉树+哈希表应用之:连接直线，甚至可以是多段线、圆弧等等。
指定对角点: 找到 130300 个
连接成功后的条数为:2831
曲线连接用时 328 毫秒




以下是核心代码部分(代码结构有些像深度优先搜索 DFS)

1. // 连接打散的线段(四叉树查找方式)
   
2. // segments : 线段对象数组
   
3. // polylines: 返回的点集数组
   
4. // tol : 连接容差
   
5. void CSegmentQtree::ConnectSegQ(vector<Segment>& segments, vector<GPolyline>& polylines, double tol)
   
6. {
   
7.     // 构建包围所有线段的矩形边界
   
8.     double minX = 1e9, minY = 1e9, maxX = -1e9, maxY = -1e9;
   
9. 
   
10.     for (size_t i = 0; i < segments.size(); ++i)
    
11.     {
    
12.         minX = min(minX, min(segments[i].ptStart.x, segments[i].ptEnd.x));
    
13.         minY = min(minY, min(segments[i].ptStart.y, segments[i].ptEnd.y));
    
14.         maxX = max(maxX, max(segments[i].ptStart.x, segments[i].ptEnd.x));
    
15.         maxY = max(maxY, max(segments[i].ptStart.y, segments[i].ptEnd.y));
    
16.     }
    
17. 
    
18.     double margin = 10.0;  // 扩展边界
    
19.     Rect world(minX - margin, minY - margin, maxX - minX + 2 * margin, maxY - minY + 2 * margin);
    
20. 
    
21.     // 构建四叉树
    
22.     CSegmentQtree quadtree(world);
    
23.     // 构建哈希表
    
24.     HashSegments mapSegments;
    
25. 
    
26.     int nSuccess = 0;
    
27.     for (size_t i = 0; i < segments.size(); ++i)
    
28.     {
    
29.         if (quadtree.Insert(&segments[i]))
    
30.         {
    
31.             // 哈希表加入该线段的索引值
    
32.             mapSegments[segments[i]] = i;
    
33.             nSuccess++;
    
34.         }
    
35.     }
    
36.     //acutPrintf(_T("成功参与构建四叉树的线段共: %d 条\n"), nSuccess);
    
37. 
    
38.     // 标记已处理的线段  true: 已访问
    
39.     vector<bool> used(segments.size(), false);
    
40. 
    
41.     for (size_t i = 0; i < segments.size(); ++i)
    
42.     {
    
43.         if (used[i])
    
44.             continue;
    
45. 
    
46.         GPolyline poly;
    
47.         poly.push_back(segments[i].ptStart);
    
48.         poly.push_back(segments[i].ptEnd);
    
49.         used[i] = true;
    
50.         
    
51.         // 从线段的终点开始搜索
    
52.         bool found = true;
    
53.         while (found)
    
54.         {
    
55.             found = false;
    
56. 
    
57.             // 获取当前折线最后一个点
    
58.             Point lastPt = poly.back();
    
59.             // 查询该点附近区域的线段（容差范围）
    
60.             Rect queryRect(lastPt.x - tol, lastPt.y - tol, tol * 2, tol * 2);
    
61.             vector<Segment*> nearbySegments;
    
62.             quadtree.Query(queryRect, nearbySegments);
    
63.             for (size_t j = 0; j < nearbySegments.size(); ++j)
    
64.             {
    
65.                 Segment* seg = nearbySegments[j];
    
66.                 // 找到该线段在 segments 中的索引
    
67.                 int idx = -1;
    
68.                
    
69.                 // 这线性遍历速度实在慢
    
70.                 /*for (size_t k = 0; k < segments.size(); ++k)
    
71.                 {
    
72.                     if (&segments[k] == seg)
    
73.                     {
    
74.                         idx = k;
    
75.                         break;
    
76.                     }
    
77.                 }*/
    
78.                
    
79.                 // 哈希表中查找该线段的索引值
    
80.                 idx = mapSegments[*seg];
    
81. 
    
82.                 if (idx != -1 && !used[idx])
    
83.                 {
    
84.                     if (AppendSegmentBack(poly, *seg, tol))
    
85.                     {
    
86.                         used[idx] = true;
    
87.                         found = true;
    
88.                         break;
    
89.                     }
    
90.                 }
    
91.             }
    
92.         }
    
93.         
    
94.         // 从线段的起点开始搜索
    
95.         if (!found)
    
96.         {
    
97.             bool found = true;
    
98.             while (found)
    
99.             {
    
100.                 found = false;
     
101. 
     
102.                 // 获取当前折线开始一个点
     
103.                 Point frontPt = poly.front();
     
104.                 // 查询该点附近区域的线段（容差范围）
     
105.                 Rect queryRect(frontPt.x - tol, frontPt.y - tol, tol * 2, tol * 2);
     
106.                 vector<Segment*> nearbySegments;
     
107.                 quadtree.Query(queryRect, nearbySegments);
     
108.                 for (size_t j = 0; j < nearbySegments.size(); ++j)
     
109.                 {
     
110.                     Segment* seg = nearbySegments[j];
     
111.                     
     
112.                     // 找到该线段在 segments 中的索引
     
113.                     int idx = -1;
     
114.                     
     
115.                     // 这线性遍历速度实在慢
     
116.                     /*for (size_t k = 0; k < segments.size(); ++k)
     
117.                     {
     
118.                         if (&segments[k] == seg)
     
119.                         {
     
120.                             idx = k;
     
121.                             break;
     
122.                         }
     
123.                     }
     
124.                     */
     
125.                     
     
126.                     idx = mapSegments[*seg];
     
127. 
     
128.                     if ((idx != -1) && !used[idx])
     
129.                     {
     
130.                         if (AppendSegmentFront(poly, *seg, tol))
     
131.                         {
     
132.                             used[idx] = true;
     
133.                             found = true;
     
134.                             break;
     
135.                         }
     
136.                     }
     
137.                 }
     
138.             }
     
139.         }
     
140. 
     
141.         if (!poly.empty())
     
142.         {
     
143.             polylines.push_back(poly);
     
144.         }
     
145.     }
     
146. }

复制代码

highflybird

我以前也写过类似的函数。也是用到了四叉树。

1. //寻找首尾相连的曲线的子函数
   
2.     static void findConnected(Point& pt, std::vector<AcDbObjectId>& outIds, std::set<AcDbObjectId> & visitedIds, std::set<Point> & points, QuadTree &qt, double tol = 1e-2)
   
3.     {
   
4.       visitedIds.insert(pt.id);
   
5.       outIds.push_back(pt.id);
   
6.       Rectangle recQuery;
   
7.       recQuery.x = pt.x - tol;
   
8.       recQuery.y = pt.y - tol;
   
9.       recQuery.width = tol + tol;
   
10.       recQuery.height = recQuery.width;
    
11.       std::vector<Point> res;
    
12.       qt.query(recQuery, res);
    
13.       points.erase(pt);
    
14.       Point ptOther(pt.ptOther.x, pt.ptOther.y, pt.id);
    
15.       ptOther.ptOther = pt;
    
16.       points.erase(ptOther);
    
17.       if (!pt.bVisited)
    
18.       {
    
19.         recQuery.x = pt.ptOther.x - tol;
    
20.         recQuery.y = pt.ptOther.y - tol;
    
21.         qt.query(recQuery, res);
    
22.       }
    
23.       qt.remove(pt);
    
24.       qt.remove(ptOther);
    
25. 
    
26.       for (size_t i = 0; i < res.size(); ++i)
    
27.       {
    
28.         if (res.id == pt.id) continue;
    
29.         std::set<AcDbObjectId>::iterator it = visitedIds.find(res.id);
    
30.         if (it == visitedIds.end())
    
31.         {
    
32.           Point ptNew(res.ptOther.x, res.ptOther.y, res.id);
    
33.           ptNew.ptOther = res;
    
34.           ptNew.bVisited = true;
    
35.           findConnected(ptNew, outIds, visitedIds, points, qt, tol);
    
36.         }
    
37.       }
    
38.     }
    
39. 
    
40.     //寻找首尾相连的曲线
    
41.     static void findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId>>& out, std::vector<AcDbObjectId> & closedIds)
    
42.     {
    
43.       Acad::ErrorStatus es;
    
44.       AcDbExtents exts;
    
45.       std::vector<Point> points;
    
46.       for (size_t i = 0; i < objs.size(); ++i)
    
47.       {
    
48.         AcDbObjectId id = objs;
    
49.         AcDbObjectPointer<AcDbCurve> curve(id, AcDb::kForRead);
    
50.         es = curve.openStatus();
    
51.         if (es != Acad::eOk) continue;
    
52.         AcGePoint3d pt1, pt2;
    
53.         curve->getStartPoint(pt1);
    
54.         curve->getEndPoint(pt2);
    
55.         pt1.z = 0; //除掉Z坐标
    
56.         pt2.z = 0; //除掉Z坐标
    
57.         if (curve->isClosed() || pt1.distanceTo(pt2) <= 1e-3)
    
58.         {
    
59.           closedIds.push_back(id);
    
60.         }
    
61.         else
    
62.         {
    
63.           AcDbExtents ext;
    
64.           curve->getGeomExtents(ext);
    
65.           exts.addExt(ext);
    
66.           points.push_back(Point(pt1.x, pt1.y, id));
    
67.           points.push_back(Point(pt2.x, pt2.y, id));
    
68.           points[points.size() - 1].ptOther = pt1;
    
69.           points[points.size() - 2].ptOther = pt2;
    
70.         }
    
71.       }
    
72. 
    
73.       Rectangle rec;
    
74.       AcGePoint3d ptMin = exts.minPoint();
    
75.       AcGePoint3d ptMax = exts.maxPoint();
    
76.       double width = ptMax.x - ptMin.x;
    
77.       double height = ptMax.y - ptMin.y;
    
78.       rec.x = ptMin.x - 10;
    
79.       rec.y = ptMin.y - 10;
    
80.       rec.width = width + 20;
    
81.       rec.height = height + 20;
    
82. 
    
83.       QuadTree qt(rec);
    
84.       for (size_t i = 0; i < points.size(); i++)
    
85.       {
    
86.         qt.insert(points);
    
87.       }
    
88. 
    
89.       std::set<Point> setPoints;
    
90.       for (size_t i = 0; i < points.size(); ++i)
    
91.       {
    
92.         setPoints.insert(points);
    
93.       }
    
94. 
    
95.       std::set<AcDbObjectId> visitedIds;
    
96.       while (!setPoints.empty())
    
97.       {
    
98.         Point pt = *setPoints.begin();
    
99.         std::vector<AcDbObjectId> ids;
    
100.         findConnected(pt, ids, visitedIds, setPoints, qt);
     
101.         out.push_back(ids);
     
102.       }
     
103.     }

//寻找首尾相连的曲线的子函数<br />     static void findConnected(Point& pt, std::vector<AcDbObjectId>& outIds, std::set<AcDbObjectId> & visitedIds, std::set<Point> & points, QuadTree &qt, double tol = 1e-2)<br />     {<br />       visitedIds.insert(pt.id);<br />       outIds.push_back(pt.id);<br />       Rectangle recQuery;<br />       recQuery.x = pt.x - tol;<br />       recQuery.y = pt.y - tol;<br />       recQuery.width = tol + tol;<br />       recQuery.height = recQuery.width;<br />       std::vector<Point> res;<br />       qt.query(recQuery, res);<br />       points.erase(pt);<br />       Point ptOther(pt.ptOther.x, pt.ptOther.y, pt.id);<br />       ptOther.ptOther = pt;<br />       points.erase(ptOther);<br />       if (!pt.bVisited)<br />       {<br />         recQuery.x = pt.ptOther.x - tol;<br />         recQuery.y = pt.ptOther.y - tol;<br />         qt.query(recQuery, res);<br />       }<br />       qt.remove(pt);<br />       qt.remove(ptOther);<br /> <br />       for (size_t i = 0; i < res.size(); ++i)<br />       {<br />         if (res<i>.id == pt.id) continue;<br />         std::set<AcDbObjectId>::iterator it = visitedIds.find(res<i>.id);<br />         if (it == visitedIds.end())<br />         {<br />           Point ptNew(res<i>.ptOther.x, res<i>.ptOther.y, res<i>.id);<br />           ptNew.ptOther = res<i>;<br />           ptNew.bVisited = true;<br />           findConnected(ptNew, outIds, visitedIds, points, qt, tol);<br />         }<br />       }<br />     }<br /> <br />     //寻找首尾相连的曲线<br />     static void findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId>>& out, std::vector<AcDbObjectId> & closedIds)<br />     {<br />       Acad::ErrorStatus es;<br />       AcDbExtents exts;<br />       std::vector<Point> points;<br />       for (size_t i = 0; i < 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 />         AcGePoint3d pt1, pt2;<br />         curve->getStartPoint(pt1);<br />         curve->getEndPoint(pt2);<br />         pt1.z = 0; //除掉Z坐标<br />         pt2.z = 0; //除掉Z坐标<br />         if (curve->isClosed() || pt1.distanceTo(pt2) <= 1e-3)<br />         {<br />           closedIds.push_back(id);<br />         }<br />         else<br />         {<br />           AcDbExtents ext;<br />           curve->getGeomExtents(ext);<br />           exts.addExt(ext);<br />           points.push_back(Point(pt1.x, pt1.y, id));<br />           points.push_back(Point(pt2.x, pt2.y, id));<br />           points[points.size() - 1].ptOther = pt1;<br />           points[points.size() - 2].ptOther = pt2;<br />         }<br />       }<br /> <br />       Rectangle rec;<br />       AcGePoint3d ptMin = exts.minPoint();<br />       AcGePoint3d ptMax = exts.maxPoint();<br />       double width = ptMax.x - ptMin.x;<br />       double height = ptMax.y - ptMin.y;<br />       rec.x = ptMin.x - 10;<br />       rec.y = ptMin.y - 10;<br />       rec.width = width + 20;<br />       rec.height = height + 20;<br /> <br />       QuadTree qt(rec);<br />       for (size_t i = 0; i < points.size(); i++)<br />       {<br />         qt.insert(points<i>);<br />       }<br /> <br />       std::set<Point> setPoints;<br />       for (size_t i = 0; i < points.size(); ++i)<br />       {<br />         setPoints.insert(points<i>);<br />       }<br /> <br />       std::set<AcDbObjectId> visitedIds;<br />       while (!setPoints.empty())<br />       {<br />         Point pt = *setPoints.begin();<br />         std::vector<AcDbObjectId> ids;<br />         findConnected(pt, ids, visitedIds, setPoints, qt);<br />         out.push_back(ids);<br />       }<br />     }

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.032852 秒.  ---收集是指的采集线段的两个端点
连接 用时: 0.128950 秒.  ---连接是把相连的线段（包括曲线）连接起来。
找到了2509条相连的曲线。

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

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

tigcat

感谢大佬无私分享

zhoupeng220

感谢大佬无私奉献

不一样地设计

感谢大佬无私奉献

lxl217114

大佬一出手就是神器

a2765852587

感谢大佬无私分享

highflybird

楼主不妨发一个测试图，我验证一下我的代码的效率。

yonjay

感谢大佬分享

gzxl

1742669 条直线直接干废了。


输入曲线连接容差<0.001>:
请框选直线、圆弧、多段线:指定对角点: 找到 1742669 个
请框选直线、圆弧、多段线:
曲线连接用时 95172 毫秒
绘制连接线共: 13442 条，用时 250 毫秒