如何绘制路线上等距点位 优化地图路径渲染缩放性能

问题背景 #

开发地图两点间最短路径程序时，若路线过长、路径点位过多，程序运行速度会大幅下降，因此需要实现仅渲染部分点位、而非全量点位绘制的路线渲染方案。
初始实现逻辑为：

• 监听地图缩放交互，每次缩放级别变化时检测点位重叠情况
• 将所有不重叠的点位存入routeToDraw列表后执行绘制
  现有实现的点位重叠检测逻辑计算开销极高，虽然计算完成后确实减少了待绘制点位、提升了绘制阶段的速度，但每次缩放时的计算等待时间过长，整体性能收益很差。
  目标效果为实现类似谷歌地图的路线渲染：绘制一系列等距分布的点位，点位密度随缩放级别动态调整，视觉效果流畅自然。

原有问题代码 #

//route is a list of latitude and longitude points
LinkedList<Point.Double> route = MapPanel.this.getGlassPane().getRoute();
LinkedList<Point.Double> routeToDraw = new LinkedList<Point.Double>();
int ovalSize = 8;
boolean compareMorePoints;
for(int i = 0; i < route.size(); i++) {
     Point p1 = getScreenCoordinates(route.get(i).x, route.get(i).y);       
     compareMorePoints = true;
     int j = i + 1;
     while (j < route.size() && compareMorePoints == true) {
         Point p2 = getScreenCoordinates(route.get(j).x, route.get(j).y);
         
         if (Math.sqrt(Math.pow(p1.x  - p2.x, 2) + Math.pow(p1.y - p2.y, 2)) > ovalSize ) {
             routeToDraw.add(route.get(i));
             compareMorePoints = false;
         }
         j++;
     }
}
MapPanel.this.getGlassPane().setRouteToDraw(routeToDraw);

原有代码性能瓶颈：最坏时间复杂度为O(n²)，点位量较大时嵌套循环计算量会指数级上涨；同时循环内反复调用经纬度转屏幕坐标的方法，重复计算开销极高。

优化方案 #

核心逻辑 #

放弃逐点两两比较的重叠检测逻辑，改用屏幕等距步长沿路径采样，时间复杂度直接降至O(n)，哪怕是十万级点位的长路径，计算耗时也能控制在毫秒级，完全不会产生卡顿：

• 设定固定的屏幕像素最小间距（即步长，可随缩放级别动态调整），保证任意两个待绘制点的屏幕距离不小于该值，从根源避免点位重叠
• 单次遍历全量路径点，累计当前点与上一个入选绘制点的屏幕距离，累计值达到步长就将当前点加入绘制列表，重置累计距离
• 路径起点、终点强制加入绘制列表，避免路线首尾缺失

优化后实现代码 #

LinkedList<Point.Double> route = MapPanel.this.getGlassPane().getRoute();
LinkedList<Point.Double> routeToDraw = new LinkedList<Point.Double>();
// 屏幕点位最小间距，可根据缩放级别动态调整：地图放大时减小、缩小时增大
int minPixelGap = 8;
if (route.isEmpty()) {
    MapPanel.this.getGlassPane().setRouteToDraw(routeToDraw);
    return;
}
// 强制加入路径起点
routeToDraw.add(route.get(0));
Point lastDrawnScreenPoint = getScreenCoordinates(route.get(0).x, route.get(0).y);
double accumulatedDist = 0;

for (int i = 1; i < route.size(); i++) {
    Point.Double currentGeoPoint = route.get(i);
    Point currentScreenPoint = getScreenCoordinates(currentGeoPoint.x, currentGeoPoint.y);
    // 计算与上一个绘制点的屏幕距离
    double dx = currentScreenPoint.x - lastDrawnScreenPoint.x;
    double dy = currentScreenPoint.y - lastDrawnScreenPoint.y;
    double pointDist = Math.sqrt(dx*dx + dy*dy);
    accumulatedDist += pointDist;

    if (accumulatedDist >= minPixelGap) {
        routeToDraw.add(currentGeoPoint);
        lastDrawnScreenPoint = currentScreenPoint;
        accumulatedDist = 0;
    }
}
// 强制加入路径终点，避免最后一段距离不足步长导致终点丢失
Point.Double endPoint = route.getLast();
if (!routeToDraw.getLast().equals(endPoint)) {
    routeToDraw.add(endPoint);
}
MapPanel.this.getGlassPane().setRouteToDraw(routeToDraw);

额外性能&效果优化点 #

• 计算优化：如果不需要严格等距，可以去掉Math.sqrt开方运算，直接比较距离平方与步长平方，进一步降低计算开销
• 缩放适配：将minPixelGap与缩放级别绑定，缩放级别每升高1级（地图放大1倍）将minPixelGap减半，缩放级别降低时对应增大步长，即可实现缩放时点位密度自动适配，和谷歌地图的渲染效果完全一致
• 防抖处理：缩放操作触发的事件频率极高（每秒可触发数十次），给计算逻辑加16ms防抖（对应60帧屏幕刷新率），等缩放操作停顿后再执行计算，避免大量无效重复计算
• 坐标缓存：给经纬度转屏幕坐标的方法加简单缓存，key为「经度+纬度+缩放级别」，value为转换后的屏幕坐标，避免同一点位在同一缩放级别下被重复转换

内容的提问来源于stack exchange，提问作者sushiwithoutsushi