最近在把一套基于地图标注的 Flutter 应用往鸿蒙平板设备上迁移其中一个核心功能是“点击/触摸任意位置在 10 万个点位里找出命中目标”。Android 版之前用暴力遍历点位几千个时没问题换到鸿蒙上第一次真机压测十万级点位下单次点击平均要 80 到 120 毫秒才能拿到结果主界面直接卡到掉帧。同事说要不把点位砍到五千个我当时就知道问题的本质不是设备变弱了而是我手里缺一棵能让二维空间查询从线性变成对数的索引树。于是我把目光放到了 rbush 上——这是我做 WebGIS 时就一直在用的 R-Tree 工业级实现纯 Dart 包在 Flutter 生态里也有。这篇东西就是我把它适配到鸿蒙并最终把十万点碰撞检测压进几个毫秒的完整记录包括选型、代码、调参和踩坑链路。1. 为什么在鸿蒙上需要 R-Tree暴力遍历的尽头就是卡顿1.1 十万点位实时触摸检测一个能打爆性能的典型场景很多人在鸿蒙上做 2D 交互时点数量级还停留在几百上千这时候暴力遍历完全没问题。但一旦进入工业级场景——地图标注、IoT 设备分布、游戏单位选择、CAD 图纸上的图元拾取点位动辄十万、百万情况就完全不同了。我当时的原始实现很朴素每次触摸遍历全部点位数组计算当前触摸点与每个点的距离筛选出小于阈值的点。十万个点就要执行十万次距离运算就算不做开根号只比较平方距离也要做几十万次乘法和加法。在鸿蒙平板真机上release 模式单次遍历大约 30 到 60 毫秒如果触摸按下、移动、抬起都触发主线程大量时间被消耗跟滚动、缩放手势叠加在一起视觉上就是持续性掉帧。更麻烦的是这种遍历没法随着设备升级自动变快它是 O(n) 的。数据量翻倍耗时也跟着翻倍属于典型的“加需求就崩”。1.2 R-Tree 的核心思想把“每个点都问一遍”变成“整块整块地排除”R-Tree 做的事情本质上就是把二维空间划分成一层一层的矩形包围盒。你可以把它想成查地图你要找一条街不会从全国所有街道里逐个排查而是先定位到省再进入省里的市再从市里的区域中找街道。R-Tree 的叶子节点存的是具体点位每个内部节点存的是子节点的最小包围盒。查询时从根节点开始把查询框和节点的包围盒做相交判断。不相交整个分支直接剪掉相交才继续向下展开。这样大部分点连被读取的机会都没有单次查询的复杂度可以降到 O(log n)而且节点越紧凑、剪枝效果越强性能越好。这个思路放到碰撞检测里尤其重要。碰撞检测的第一诉求从来不是“把所有碰撞精确算出来”而是“先把不可能碰撞的候选排除掉”。R-Tree 快速返回一小簇候选点之后无论你要做精确距离计算还是更复杂的图形相交检测计算量都小到可以忽略。1.3 为什么选中 rbush 而不是自己写树或换四叉树R-Tree 实现并不算简单核心难点在节点分裂策略、删除后的节点收缩、批量加载时的打包质量。自己写一套能稳定生产用的树至少需要一两周而且边界情况极多。rbush 是 Web 开源生态里公认的 R-Tree 实现作者是 Vladimir AgafonkinLeaflet 的作者它被广泛用在 GIS、图形编辑器里。它最大的特点是有三个内存非常紧凑。它没有用“每个节点一个对象”的稀疏结构而是把所有节点放在数组中通过索引维护父子关系。这带来的好处是 CPU 缓存友好在大数组节点上遍历非常快这一点在鸿蒙的 Flutter engine 上同样成立。提供 load 批量构建。大量点位一次性灌入时load 比逐条 insert 快得多树的整体质量也更高。API 精简。核心就是 insert、search、collides、remove、load、all、toJSON/fromJSON半天就能上手不需要理解内部细节就能用。还有一点对鸿蒙适配至关重要rbush 的 Dart 版是纯 Dart 实现完全不依赖原生平台通道不依赖dart:io之外的能力。这对跨平台尤其友好因为 Flutter 鸿蒙分支的环境跟标准 Android/iOS 有些差异能少碰一层原生就少一层风险。2. 鸿蒙上的三条适配路线别急着抄别人的方案“鸿蒙化适配”这个词听起来像是要改 rbush 源码实际上真正问题是怎么把 R-Tree 能力放进鸿蒙应用体系里。我调研时发现有三条路线每条都有自己的代价。2.1 路线 AFlutter 容器里直接用 pub 依赖的 Dart 版 rbush如果你的业务依然用 Flutter 开发鸿蒙界面那这是最自然的一条路。把rbush加进 pubspec在 Dart 侧构建索引查询结果直接喂给 Flutter 的渲染层整条链路都不需要跨语言桥接。数据模型可以定义成普通类rbush 只管读取minX/minY/maxX/maxY这四个参数。这个方案的优点是工程改动最小几乎是一行依赖就解决而且完全保留 Flutter 的热重载、状态管理、Canvas 绘制能力。缺点是它要求你的鸿蒙构建环境里已经接好 Flutter SDK 的鸿蒙分支如果项目主体是纯 ArkTS为了一个索引库去拖一个 Flutter 运行时进来有点杀鸡用牛刀。2.2 路线 BArkTS 侧用 Worker 自建 R-Tree如果你的应用主体是 ArkTS、ArkUI你会在网上看到不少人建议“自己用 ArkTS 写个二维索引”。这个方向理论上可行但你要重新面对 R-Tree 最棘手的几个点节点分裂时怎么选切割轴、最小包围盒怎么更新、删除后树怎么收缩不失衡、批量加载怎么减少重叠。我不建议你在业务项目里用两周时间重造一个容易出边界 bug 的轮子。除非点位规模很小或者你的查询模式极其固定比如只查固定半径的近邻否则自研树的维护成本会高到让你后悔。如果真要走这条路可以考虑移植思路而不是从零设计算法。2.3 路线 CJS 版 rbush JSBridge还有一种诱惑rbush 的 JS 原版功能更全npm 安装一行命令于是有人想在 ArkTS 应用里通过 JS 引擎调用或者在 Web 组件里跑 JS再用 bridge 把结果传回 ArkTS/Flutter。这条路对低频管理后台也许够用但对高频碰撞检测是毒药——每一次 search 都要跨桥传递查询框、序列化结果光通信开销就比树的查询时间大一个数量级越用越卡还牺牲了可调试性。2.4 我的选型结论与对比我最终选了路线 A。为什么因为我的目标是“大规模点位碰撞检测引擎”它最核心的指标是单次查询延迟而纯 Dart 在同一个 Flutter isolate 里执行不需要任何桥接延迟最低。对比表如下方案接入成本单次查询延迟维护复杂度适用场景路线 ADart rbush 直用低改依赖最低低纯 DartFlutter 鸿蒙业务路线 BArkTS 自建树高需重写中等高算法坑多纯 ArkUI 且余量充足路线 CJS 版 bridge低装 npm 包高跨桥开销中双端协调低频工具型页面如果你的应用是纯 ArkTS 且数据量不大我反而建议先用最朴素的数组过滤别上树。树的优势只有在数据量上到五万以上时才凸显出来几千个点遍历一次连 1 毫秒都不到没必要为了“工业级”三个字给自己增加复杂度。3. 实操在 Flutter 鸿蒙工程里集成 rbush跑通第一次碰撞检测3.1 依赖接入与 pub 环境处理在 Flutter 工程的 pubspec.yaml 里加上dependencies: rbush: ^0.0.4然后执行flutter pub get。这里有个实际操作中很容易卡住的点鸿蒙开发环境如果在国内pub 默认源有时候下载非常慢甚至失败。我的做法是配置 PUB_HOSTED_URL 使用镜像源或者提前在有网络的环境把包拉进 pub 缓存再到离线环境开发。不要把时间浪费在反复 pub get 上。拿到包之后先别急着写业务先看一眼库的构造参数。不同版本的 rbush Dart 包构造方式可能略有差别有的是命名参数RBush(maxEntries: 16)有的直接传位置参数。后面所有代码都按“maxEntries 一定能调”的大前提写具体以你拉到的版本为准。3.2 定义点模型与批量写入十万点位rbush 不认识你业务里的“点位”是什么它只认四个字段minX、minY、maxX、maxY。所以自定义点类的时候必须把这些 getter 暴露出来。import package:rbush/rbush.dart; class PointItem { PointItem(this.x, this.y, {this.id, this.payload}); final double x; final double y; final int? id; final Object? payload; double get minX x; double get minY y; double get maxX x; double get maxY y; }这里有个细节点没有宽高所以 minX 和 maxX 都是同一个 x。后面我会专门说到工业级实现里如何给点加一个微小半径避免浮点边界问题。接下来创建索引并灌入数据关键是用 load不要用 for 循环逐条 insert。final tree RBushPointItem(maxEntries: 16); final points ListPointItem.generate(100000, (i) { return PointItem( Random().nextDouble() * 10000, Random().nextDouble() * 10000, id: i, ); }); final stopwatch Stopwatch()..start(); tree.load(points); stopwatch.stop(); print(load 100k points: ${stopwatch.elapsedMilliseconds}ms);在鸿蒙平板上我实测 load 十万个点大约是 40 到 70 毫秒这个耗时只在启动时发生一次完全可以接受。相比之下如果我用 insert 逐条写入往往要到 150 毫秒以上而且树质量更差。3.3 触摸点碰撞检测的完整调用碰撞检测的核心就一句话用触摸点附近的小方块去树里搜候选再对候选做精确判断。void onPointerMove(PointerEvent e) { final dx e.localPosition.dx; final dy e.localPosition.dy; final hitRadius 20.0; final Listdynamic rawHits tree.search([ dx - hitRadius, dy - hitRadius, dx hitRadius, dy hitRadius, ]); final ListPointItem hits rawHits.castPointItem(); // search 返回的是“包围盒相交”的候选不是真正碰撞 // 这里再做一次精确圆心距离过滤 final precise hits.where((p) { final ox p.x - dx; final oy p.y - dy; return ox * ox oy * oy hitRadius * hitRadius; }).toList(); // precise 就是最终命中的点 }如果你现在还是暴力遍历把这套 search 替换进去十万个点下的查询会从几十毫秒降到几个毫秒。我工作流里的标准做法是触摸事件来了直接 search再对结果做真实命中判断所有绘制只在拿到候选之后进行。3.4 search 的 BBox 语义和边界误差rbush 的 search 参数是“最小包围盒”四个数字分别是 minX、minY、maxX、maxY。不少新手会犯同一个错误把触摸点坐标当作中心忘了先减后加半径结果搜出来的区域是一个偏移了的位置明明点就在手边却永远查不到。另一个很容易踩的坑是“退化包围盒”。当你用触摸点本身做查询时可能出现[x, y, x, y]这种宽高为零的矩形。在浮点计算中这种退化矩形的相交判断很容易因为精度问题得到 false。我在做点选命中时永远给搜索框至少加一个像素的边界不让它是零宽度。4. 性能底座maxEntries、load、坐标类型每一项都影响最后十倍差距4.1 maxEntries 到底调多少才合适maxEntries 是每个节点最多能容纳的子项数量它直接决定树的深度和节点包围盒的紧凑程度。值太小比如 4树会更高搜索时要访问的节点更多缓存命中率下降。值太大比如 64每个节点的包围盒会很大剪枝效率变差很容易把大量不相干区域一起捞进来。rbush 的默认值是 9但我不建议你在十万级数据下直接默认。实测中16 到 32 之间的表现通常最好。你可以在代码里留一个可配项跑一次自己的数据分布观察“构建耗时 单次查询耗时”的综合曲线。我自己的案例里16 比 9 快了大概 15%而 32 和 16 相差不大。如果你手头数据分布极度聚团比如都集中在一个城区那么适度调大 maxEntries 反而能减少树的高度对查询更有利。4.2 为什么批量加载必须用 load()逐条 insert 到底差在哪这个其实网上说得不多但实际影响非常大。load 方式会先把数据排序再按矩形打包策略建立一层层节点尽量让兄弟节点在空间上彼此靠近重叠面积小。逐条 insert 是从空树开始一条条插每次插入都可能触发节点分裂分裂质量取决于当前已有的空间分布很容易制造出互相重叠严重的节点。重叠严重的 R-Tree 是“看起来是树、查起来像遍历”的头号原因。所以我的建议非常明确启动阶段如果有一批静态数据要进树一律 load后续动态增加的单条数据才用 insert。如果你想更新一批数据宁可先 clear 再整体 load也不要在一棵已经有十万节点的树上逐条 insert 几万条。4.3 坐标转整数的收益与风险如果业务允许把浮点坐标统一放大后转成整数再进树会让比较运算更快也能规避浮点边界问题。比如地图坐标(x, y)乘上 1000 再 round仍能保留毫米级精度。但这个做法的风险是一旦坐标范围超过整数安全上限会出现溢出导致包围盒错乱。另外如果你负责的是地图经纬度数据直接转整数可能会丢掉小数点精度。我的建议是在碰撞检测这种“人对屏幕像素交互”的场景里直接用逻辑像素的浮点坐标即可不必强行转整数但如果数据本身来自网格或逻辑地图转整数是稳赚不赔的。4.4 一组我在鸿蒙设备上的实测数据测试环境鸿蒙平板release 模式100 万个随机点查询半径 20 像素。数据如下方案构建耗时单次查询平均耗时暴力遍历无约 280msRBush maxEntries9约 400ms约 6~9msRBush maxEntries16约 420ms约 4~6msRBush maxEntries32约 460ms约 4~5ms你可以看到R-Tree 带来的提升是几十倍的而 maxEntries 的调优只影响最后一两倍。先把树用起来再慢慢调参数顺序一定不能反。很多团队一开始就陷入“参数洁癖”其实连树都还没建对。5. 鸿蒙化过程中实际踩过的四个坑附带完整排查链路5.1 现象一search 永远返回空但 tree.all() 明明有十万个点第一次跑通时我的 search 一直返回空怀疑是 rbush 在鸿蒙的 Flutter 引擎上初始化出了问题。我当时的排查链路是这样的先打印tree.all().length确认树里确实有 10 万个数据排除 load 失败。再打印 search 传入的四个值发现触摸点坐标是逻辑像素而点位数据是用物理像素生成的。鸿蒙设备的 devicePixelRatio 常见的是 1.5、2、3触摸点拿到的 localPosition 和 Canvas 里点的坐标不在同一个坐标系里。问题出在我自己身上跟 rbush 没关系。解法是统一坐标系所有点位在进入树之前先做归一化触摸事件也统一除以 devicePixelRatio。这个坑特别隐蔽因为在模拟器上 DPR 正好为 1不会有问题真机上立刻现形。5.2 现象二debug 模式正常release 模式少数边缘点位查不到debug 下一切正常release 下一小部分点就是查不到。排查的时候我是这么想的先怀疑编译器优化对浮点运算产生误差于是打印了具体查不到的那个点坐标发现它刚好位于搜索框边界上。R-Tree 判断相交用的是浮点比较点本身没有宽高minX/maxX 相等跟查询框边界比较时可能出现“看似相交、实际不等”的情况。解法很简单让点携带一个极小的包围盒而不是退化成一个点。我在点模型里改成double get minX x - 0.5; double get minY y - 0.5; double get maxX x 0.5; double get maxY y 0.5;这样每个点都变成一个边长 1 单位的小矩形查询时不会再因为退化和精度漏边缘。这个改动在纯内存计算里几乎感受不到性能损耗但能彻底解决边界问题。5.3 现象三想把 R-Tree 放到后台 isolate结果数据传不过去为了不阻塞 UI我想用 Flutter 的 isolate/compute 来做碰撞检测结果发现 rbush 实例根本没法直接传进 isolate。原因很直接Dart isolate 之间传递数据本质是拷贝快照rbush 内部是大量嵌套数组和节点对象拷贝成本极高甚至可能出现不可序列化的问题。我最后的方案是主线程一次性构建索引碰撞检测也留在主线程因为一次 search 只要几毫秒完全不至于卡 UI。如果数据规模大到百万级且每帧要查询数次那就换一种思路网格分片 每片独立的小树把查询分发给多个 isolate而不是试图传一整棵大树。这个经验通用性很强在 Flutter 鸿蒙环境里不要为了“看起来高性能”而强行拆 isolate。先把主线程的单次查询压到 5 毫秒以内比引入 isolate 通信开销实用得多。5.4 现象四热重载之后点击位置全乱开发期我用热重载改界面样式改完后触摸命中区域全部偏移。一开始以为是坐标系又被 DPR 影响了实际排查后发现是 Flutter 鸿蒙分支的热重载对状态恢复不完整RenderObject 状态出现了错位。处理方式很简单遇到热重载后交互异常先hot restart不要用hot reload。这不是 rbush 的问题也不是业务代码的问题而是引擎分支在开发工具链上的一个限制。省得你在错误的方向上排查几个小时。6. 从“能跑”到“工业级”动态更新、持久化和工程化收尾6.1 动态增删维护remove 的代价比很多人想象的大地图标注场景不可能只读不写。用户会不断新增点、删除点。rbush 支持 insert 和 remove但 remove 需要能够判定“要删的是哪个对象”。如果你的业务数据里有重复坐标比如多个点叠在一起就必须提供一个相等性对比函数否则 remove 可能删错对象。动态操作多了之后树的包围盒会越来越大删除后节点又不会自动收缩查询性能会慢慢劣化。我的经验法则是如果一次性删除比例超过 30%或者你观察到查询耗时比刚构建时慢了两倍以上就触发一次clear load重建。重建的成本是几百毫秒但换来的是之后连续几十分钟的稳定高性能非常值得。6.2 与手势事件、Canvas 坐标系的整合碰撞检测要在真实项目里站住脚必须把坐标变换做对。我见过很多团队把屏幕坐标直接拿去搜索忽略了 Canvas 的平移缩放变换。正确做法是先把屏幕上的触摸 bbox 转换到世界坐标系再用世界坐标 bbox 去 search。如果你反过来先在世界坐标里全量搜再用屏幕坐标过滤等于剪枝全部失效又变回 O(n)。具体实现时我给手势回调做了一层坐标转换封装统一从“屏幕坐标到世界坐标”的映射所有 localPosition 都必须经过这层转换才能进 rbush。这套机制也方便适配未来鸿蒙不同尺寸设备只需要改映射矩阵。6.3 序列化树应该存还是点应该存rbush 提供了 toJSON/fromJSON可以把整棵树序列化成 JSON 再恢复。但工业级项目里我建议反过来永久存储只存业务点数据不存索引结构。因为索引里包含的内部节点布局对 R-Tree 版本非常敏感rbush 升级后可能出现序列化不兼容。更好的做法是存一份轻量的点位列表启动时 load 重建几百毫秒换一个可靠的持久化边界太划算了。如果点量实在太大几百万个点每次都重新 load 不可接受可以存 rbush 的 JSON 快照并附带版本号加载后做一次完整性校验这样能兼顾启动速度和兼容性。6.4 往这个引擎上继续扩展的思路如果你已经在鸿蒙上把 rbush 跑起来了后续可以顺着这几个方向继续做百万级点位不直接塞一棵树而是按网格分片每片单独一棵树查询时先定位到片再进树。这样可以极大降低单树的体积和维护压力。与 Canvas 渲染联动只在search返回的候选里绘制点位未命中的一律跳过绘制耗时会稳定下降。把碰撞检测从“点选命中”扩展到“矩形框选”“多边形拾取”核心还是先用树的 bbox 粗筛再对候选做几何精算。这套思路不仅适用于鸿蒙也适用于任何想在地图、编辑器、游戏里做大空间查询的场景。最后再分享一个我个人的习惯每接到一类空间查询需求我都会先用纯遍历算出基准线再上 R-Tree 对比而不是一上来就优化参数。因为只有拿到“暴力法到底多慢”的底线你才知道树的优化空间有没有榨干。实际踩过几次坑之后我现在在鸿蒙上做空间索引基本形成了肌肉记忆先保证数据在进入 rbush 前坐标系唯一再保证点对象带最小包围盒最后再谈 maxEntries 和 isolate 方案。顺序反过来很容易被各种玄学问题带偏。