Performance becomes an issue with polylines with more than 100 points

[jaybo]

mapbox-gl-draw-geodesic has problems with polylines larger than around 100 points.

Here's a codepen: https://codepen.io/jaybonomad/pen/dyZbPJv?editors=1111

Buttons at the top let you create polylines of varying lengths.
When attempting to edit large polylines, the performance suffers. At 1000 points, things grind to a halt.
Just commenting out:

// modes = MapboxDrawGeodesic.enable(modes); 

Pretty much makes everything usable up to 10000 points.

I haven't looked into the source of the problem yet, but I'm wondering if just somehow internally disabling draw-geodesic on short segments might be a quick fix.

[jaybo]

Now that I've had a day to ponder this, I can imagine the overhead to decide whether each segment of each polyline met some criteria to enable the addition of geodesic approximating points might be onerous.

So I'm just throwing out another idea of adding a property to the GeoJson which could be manually set by the client application which indicates "draw-geodesic, don't bother with this polyline".

[jaybo]

I tried a crude, brute-force approach of determining whether the segment was larger than (say) 2 degrees and limiting the number of intermediate arc points, but didn't get a significant performance improvement for reasons unknown.

// create_geodesic_line.js

function createGeodesicLine(coordinates, steps = 32) {
  const segments = coordinatePairs(coordinates);

  const geodesicSegments = segments.map(segment => {
    let x0 = segment[0][0],
      y0 = segment[0][1],
      x1 = segment[1][0],
      y1 = segment[1][1],
      dx = x1 - x0,
      dy = y1 - y0;

    let pythagorean =  Math.sqrt(dx * dx  + dy * dy);
    const minAngularDistanceInDegrees = 2;
    // if smaller than 
    let newSteps = (pythagorean < minAngularDistanceInDegrees) ? 2 : steps;
    
    const greatCircle = new arc.GreatCircle(
      { x: x0, y: y0 },
      { x: x1, y: y1 }
    );
    return greatCircle.Arc(newSteps, { offset: 90 }).json();
  });

[jaybo]

Ok, now that I've spent some quality time with the code, it looks like the main performance bottleneck isn't actually in the geodesic calculations but rather with processMidpoint() and feature.toGeoJSON(). For a long polyline, both functions are called pairwise for every midpoint. Time to try adding some geoJSON cache? Or try to eliminate the need to convert to geoJSON?

[zakjan]

Hi, thanks for the detailed investigation! Currently midpoints are created for every line segment. For long polylines with many line segments, either a user is zoomed out to see the entire polyline, but then line points (and midpoints) are too close to each other that the line can't be edited well. Such line can be edited only after zooming in.

It seems that performance could be improved by 1) generating midpoints only in the visible viewport, and 2) generating midpoints only when projected line point positions are at least some number of pixels apart. Would this work for you?

[jaybo]

One possible complication with this alternative is that I'm using midpoints to display lengths and bearing for each segment. I don't think there would be a problem if the number of midpoints no longer corresponds to the number of segments, but I'm famous for unexpected consequences.

[jaybo]

I've tried eliminating the feature.toGeojson() call in createGeodesicGeojson, and just using the passed in geojson instead. Most tests pass until I get to:

function getCoordinate(coordinates, path) {
  const ids = path.split('.').map(x => parseInt(x, 10));
  const coordinate = ids.reduce((coordinates, id) => coordinates[id], coordinates);
  return JSON.parse(JSON.stringify(coordinate));
}

where I'm confounded by the meaning of ids when the path is "0.0" on returns a polygon midpoint.

[jaybo]

  it('returns a polygon midpoint', () => {
    const feature = mode.newFeature(createGeojson(Constants.geojsonTypes.POLYGON, [COORDINATES]));
    mode.addFeature(feature);
    const internalGeojson = createMidpoint(
      feature.id,
      createVertex(feature.id, feature.getCoordinate('0.0'), '0.0', false),
      createVertex(feature.id, feature.getCoordinate('0.1'), '0.1', false),
      map
    );

    const expectedResult = [createGeojsonMatch(Constants.geojsonTypes.POINT)];
    const result = createGeodesicGeojson(internalGeojson, { ctx: mode._ctx, steps: STEPS });

internalGeojson is just a point, and then it's used to create a new createGeodesicGeojson(internalGeojson???

[zakjan]

See createMidpoint imported from mapbox-gl-draw, it returns an internal GeoJSON representation of a single midpoint with linearly interpolated coordinates. Unfortunately, it's missing the original neighbour points, which we need to calculate the geodesic midpoint coordinates.

featureGeojson.geometry.coordinates contains all feature point coordinates. If you replace it with geojson.geometry.coordinates, it contains just the midpoint coordinates.

feature.toGeoJSON() could be removed if there is a simpler way to get the neighbour points, but I couldn't find it anywhere else.

[zakjan]

Hi @jaybo, I tried to improve performance by limiting feature.toGeoJSON calls only when it's necessary for circles.

The original reason why I used feature.toGeoJSON for all features is that it avoids the other issue with feature.getCoordinate, which fails for the last polygon vertex. I wrapped it with try/catch.

Could you test #14 if it improves the performance in your use case?

[jaybo]

YES! This works great!!!
I had tried the same basic idea of removing the toGeoJSON() calls for the non-circle path, and it hadn't made any performance difference so the true culprit must be in getCoordinate(), probably JSON.parse(JSON.stringify(coordinate));?

[zakjan]

Yeah, those excessive JSON.parse(JSON.stringify(...)) were suspicious. I'm glad it helped you. Released as 2.1.3.