四叉树+哈希表应用之:连接直线，运行速度很快
本帖最后由 gzxl 于 2025-9-22 21:24 编辑四叉树+哈希表应用之:连接直线，甚至可以是多段线、圆弧等等。
指定对角点: 找到 130300 个
连接成功后的条数为:2831
曲线连接用时 328 毫秒
以下是核心代码部分(代码结构有些像深度优先搜索 DFS)
// 连接打散的线段(四叉树查找方式)
// segments : 线段对象数组
// polylines: 返回的点集数组
// tol : 连接容差
void CSegmentQtree::ConnectSegQ(vector<Segment>& segments, vector<GPolyline>& polylines, double tol)
{
// 构建包围所有线段的矩形边界
double minX = 1e9, minY = 1e9, maxX = -1e9, maxY = -1e9;
for (size_t i = 0; i < segments.size(); ++i)
{
minX = min(minX, min(segments.ptStart.x, segments.ptEnd.x));
minY = min(minY, min(segments.ptStart.y, segments.ptEnd.y));
maxX = max(maxX, max(segments.ptStart.x, segments.ptEnd.x));
maxY = max(maxY, max(segments.ptStart.y, segments.ptEnd.y));
}
double margin = 10.0;// 扩展边界
Rect world(minX - margin, minY - margin, maxX - minX + 2 * margin, maxY - minY + 2 * margin);
// 构建四叉树
CSegmentQtree quadtree(world);
// 构建哈希表
HashSegments mapSegments;
int nSuccess = 0;
for (size_t i = 0; i < segments.size(); ++i)
{
if (quadtree.Insert(&segments))
{
// 哈希表加入该线段的索引值
mapSegments] = i;
nSuccess++;
}
}
//acutPrintf(_T("成功参与构建四叉树的线段共: %d 条\n"), nSuccess);
// 标记已处理的线段true: 已访问
vector<bool> used(segments.size(), false);
for (size_t i = 0; i < segments.size(); ++i)
{
if (used)
continue;
GPolyline poly;
poly.push_back(segments.ptStart);
poly.push_back(segments.ptEnd);
used = true;
// 从线段的终点开始搜索
bool found = true;
while (found)
{
found = false;
// 获取当前折线最后一个点
Point lastPt = poly.back();
// 查询该点附近区域的线段（容差范围）
Rect queryRect(lastPt.x - tol, lastPt.y - tol, tol * 2, tol * 2);
vector<Segment*> nearbySegments;
quadtree.Query(queryRect, nearbySegments);
for (size_t j = 0; j < nearbySegments.size(); ++j)
{
Segment* seg = nearbySegments;
// 找到该线段在 segments 中的索引
int idx = -1;
// 这线性遍历速度实在慢
/*for (size_t k = 0; k < segments.size(); ++k)
{
if (&segments == seg)
{
idx = k;
break;
}
}*/
// 哈希表中查找该线段的索引值
idx = mapSegments[*seg];
if (idx != -1 && !used)
{
if (AppendSegmentBack(poly, *seg, tol))
{
used = true;
found = true;
break;
}
}
}
}
// 从线段的起点开始搜索
if (!found)
{
bool found = true;
while (found)
{
found = false;
// 获取当前折线开始一个点
Point frontPt = poly.front();
// 查询该点附近区域的线段（容差范围）
Rect queryRect(frontPt.x - tol, frontPt.y - tol, tol * 2, tol * 2);
vector<Segment*> nearbySegments;
quadtree.Query(queryRect, nearbySegments);
for (size_t j = 0; j < nearbySegments.size(); ++j)
{
Segment* seg = nearbySegments;
// 找到该线段在 segments 中的索引
int idx = -1;
// 这线性遍历速度实在慢
/*for (size_t k = 0; k < segments.size(); ++k)
{
if (&segments == seg)
{
idx = k;
break;
}
}
*/
idx = mapSegments[*seg];
if ((idx != -1) && !used)
{
if (AppendSegmentFront(poly, *seg, tol))
{
used = true;
found = true;
break;
}
}
}
}
}
if (!poly.empty())
{
polylines.push_back(poly);
}
}
}
我以前也写过类似的函数。也是用到了四叉树。
//寻找首尾相连的曲线的子函数
static void findConnected(Point& pt, std::vector<AcDbObjectId>& outIds, std::set<AcDbObjectId> & visitedIds, std::set<Point> & points, QuadTree &qt, double tol = 1e-2)
{
visitedIds.insert(pt.id);
outIds.push_back(pt.id);
Rectangle recQuery;
recQuery.x = pt.x - tol;
recQuery.y = pt.y - tol;
recQuery.width = tol + tol;
recQuery.height = recQuery.width;
std::vector<Point> res;
qt.query(recQuery, res);
points.erase(pt);
Point ptOther(pt.ptOther.x, pt.ptOther.y, pt.id);
ptOther.ptOther = pt;
points.erase(ptOther);
if (!pt.bVisited)
{
recQuery.x = pt.ptOther.x - tol;
recQuery.y = pt.ptOther.y - tol;
qt.query(recQuery, res);
}
qt.remove(pt);
qt.remove(ptOther);
for (size_t i = 0; i < res.size(); ++i)
{
if (res.id == pt.id) continue;
std::set<AcDbObjectId>::iterator it = visitedIds.find(res.id);
if (it == visitedIds.end())
{
Point ptNew(res.ptOther.x, res.ptOther.y, res.id);
ptNew.ptOther = res;
ptNew.bVisited = true;
findConnected(ptNew, outIds, visitedIds, points, qt, tol);
}
}
}
//寻找首尾相连的曲线
static void findConnected(const std::vector<AcDbObjectId>& objs, std::vector<std::vector<AcDbObjectId>>& out, std::vector<AcDbObjectId> & closedIds)
{
Acad::ErrorStatus es;
AcDbExtents exts;
std::vector<Point> points;
for (size_t i = 0; i < objs.size(); ++i)
{
AcDbObjectId id = objs;
AcDbObjectPointer<AcDbCurve> curve(id, AcDb::kForRead);
es = curve.openStatus();
if (es != Acad::eOk) continue;
AcGePoint3d pt1, pt2;
curve->getStartPoint(pt1);
curve->getEndPoint(pt2);
pt1.z = 0; //除掉Z坐标
pt2.z = 0; //除掉Z坐标
if (curve->isClosed() || pt1.distanceTo(pt2) <= 1e-3)
{
closedIds.push_back(id);
}
else
{
AcDbExtents ext;
curve->getGeomExtents(ext);
exts.addExt(ext);
points.push_back(Point(pt1.x, pt1.y, id));
points.push_back(Point(pt2.x, pt2.y, id));
points.ptOther = pt1;
points.ptOther = pt2;
}
}
Rectangle rec;
AcGePoint3d ptMin = exts.minPoint();
AcGePoint3d ptMax = exts.maxPoint();
double width = ptMax.x - ptMin.x;
double height = ptMax.y - ptMin.y;
rec.x = ptMin.x - 10;
rec.y = ptMin.y - 10;
rec.width = width + 20;
rec.height = height + 20;
QuadTree qt(rec);
for (size_t i = 0; i < points.size(); i++)
{
qt.insert(points);
}
std::set<Point> setPoints;
for (size_t i = 0; i < points.size(); ++i)
{
setPoints.insert(points);
}
std::set<AcDbObjectId> visitedIds;
while (!setPoints.empty())
{
Point pt = *setPoints.begin();
std::vector<AcDbObjectId> ids;
findConnected(pt, ids, visitedIds, setPoints, qt);
out.push_back(ids);
}
}
我在这里把核心代码贴出来
此算法采用了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);
}
}
}
本帖最后由 highflybird 于 2025-9-23 23:08 编辑
优化了算法，不用四叉树，只是采用了哈希表。速度得到极大提升。
命令: LJ
选择对象: 指定对角点: 找到 130537 个
选择对象:
收集 用时: 0.032852 秒.---收集是指的采集线段的两个端点
连接 用时: 0.128950 秒.---连接是把相连的线段（包括曲线）连接起来。
找到了2509条相连的曲线。
和楼主同样的容差 ，最后合并的线条数更少。
容差设置为0.1的时候，合并的线条数我这边运行的结果是：2478
感谢大佬无私分享 感谢大佬无私奉献
感谢大佬无私奉献 大佬一出手就是神器 感谢大佬无私分享 楼主不妨发一个测试图，我验证一下我的代码的效率。 感谢大佬分享
1742669 条直线直接干废了。
输入曲线连接容差<0.001>:
请框选直线、圆弧、多段线:指定对角点: 找到 1742669 个
请框选直线、圆弧、多段线:
曲线连接用时 95172 毫秒
绘制连接线共: 13442 条，用时 250 毫秒