How to get all points contained within an SVG path string without checking every point on canvas?

Question

Is there an efficient way to find the [x, y] coordinates of every point in a inside a path without manually checking every point on the entire canvas using context.isPointInPath()?

Sample path from a geojson

<path d="
  M 588, 173,
  L 588, 176,  L 585, 216,  L 585, 216,  L 584, 223,
  L 580, 274,  L 565, 273,  L 565, 273,  L 549, 271,
  L 539, 270,  L 535, 269,  L 513, 267,  L 503, 266,
  L 486, 264,  L 477, 262,  L 468, 261,  L 464, 260,
  L 455, 259,  L 449, 258,  L 451, 249,  L 452, 244,
  L 453, 233,  L 456, 218,  L 456, 215,  L 460, 192,
  L 460, 191,  L 462, 180,  L 463, 174,  L 463, 171,
  L 464, 167,  L 464, 161,  L 465, 158,  L 470, 159,
  L 471, 159,  L 477, 160,  L 477, 160,  L 480, 161,
  L 482, 161,  L 487, 161,  L 499, 163,  L 500, 163,
  L 514, 165,  L 534, 168,  L 535, 168,  L 544, 169,
  L 555, 170,  L 557, 170,  L 565, 171,  L 581, 173,
  Z"  
fill="transparent" stroke-width="1" stroke="black"></path>

For example, this is what I'm doing now with a geojson file:

  const points = [];
  const pointWidth = 2;

  for (let x = 0; x < canvasWidth; x += pointWidth) {
    for (let y = 0; y < canvasHeight; y += pointWidth) {

      for (const feature of countyGeoJson.features) {
        const d = pathGenerator(feature);
        const countyShape = new Path2D(d);

        if (context.isPointInPath(countyShape, x, y)) {
          points.push({ coords: [x, y], data: feature.properties });
          break;
        }
      }
    }
  }

Basically, I'm looping through every point in the canvas grid (there are over one million), and nesting another loop that looks through every feature to determine if the point is in the feature's projected path string. That is terribly inefficient and my browser cannot handle it.

Is there a way to use the path string itself to generate the points?

Answer 1

Here is a full implementation from what we discussed on the comments

var image = `
    <svg xmlns="http://www.w3.org/2000/svg" width="800" height="400" version="1.1">
        <path d="
            M 588, 173,
            L588,176,  L585,216,  L585,216,  L584,223,  L580,274,  L565,273,  L565,273,  L549,271,
            L539,270,  L535,269,  L513,267,  L503,266,  L486,264,  L477,262,  L468,261,  L464,260,
            L455,259,  L449,258,  L451,249,  L452,244,  L453,233,  L456,218,  L456,215,  L460,192,
            L460,191,  L462,180,  L463,174,  L463,171,  L464,167,  L464,161,  L465,158,  L470,159,
            L471,159,  L477,160,  L477,160,  L480,161,  L482,161,  L487,161,  L499,163,  L500,163,
            L514,165,  L534,168,  L535,168,  L544,169,  L555,170,  L557,170,  L565,171,  L581,173,
            Z" fill="transparent" stroke-width="1" stroke="black">
        </path>
    </svg>`;

function inside(p, vs) {
    var inside = false;
    for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
        var xi = vs[i][0], yi = vs[i][1];
        var xj = vs[j][0], yj = vs[j][1];
        var intersect = ((yi > p[1]) != (yj > p[1])) && (p[0] < (xj - xi) * (p[1] - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }
    return inside;
}

function draw() {
    ctx.drawImage(img, 0, 0);

    const matches = image.matchAll(/L(...),(...),/g)
    const poly = Array.from(matches, m => [Number(m[1]), Number(m[2])])

    let xs = poly.map(p => p[0]);
    let ys = poly.map(p => p[1]);
    let [xmin, xmax] = [Math.min(...xs), Math.max(...xs)];
    let [ymin, ymax] = [Math.min(...ys), Math.max(...ys)];

    ctx.globalAlpha = 0.5
    const pointWidth = 4
    for (let x = xmin; x <= xmax; x += pointWidth) {
        for (let y = ymin; y <= ymax; y += pointWidth) {
            if (inside([x, y], poly)) {
                ctx.beginPath();
                ctx.fillStyle = Math.random()<0.5? "blue" : "red"
                ctx.arc(x, y, 1.5, 0, 2 * Math.PI);
                ctx.fill();               
            }
        }
    }
}

var canvas = document.querySelector('canvas');
var ctx = canvas.getContext('2d');


var img = new Image();
img.onload = draw
img.src = 'data:image/svg+xml;charset=utf-8,' + encodeURIComponent(image);

<canvas id=canvas width=800 height=400></canvas>

• function inside is the algorithm I mentioned:
  https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

• function draw is where all the action is, we collect all the matches from the svg path, then we build a polygon, then get the bounding box and loop over that to find what is inside and I'm drawing something if we are inside.

The only thing I left out is the correct regex pattern to find the matches:
image.matchAll(/L(...),(...),/g) That works on my simplified example, you need to look for a proper one for your examples.

You might not need to do regex, it all depends on the structure in that countyGeoJson you might be able to extract the polygon directly from that.

Answer 2

I think your algorithm is perfectly fine, you will hardly find more performant one in terms of big-O complexity. Still, there are some improvements you can do in your code:

1) It is important to know how big is the canvas in comparison to all the features together. If the canvas is way bigger, then it might be beneficial to find bounding rectangle of all the features (one bounding rectangle for all of them together), and then do your search withing that rectangle, instead of the whole canvas. If the canvas is just a bit bigger, than probably this will not do any improvements.

2) You are doing some work (like calling pathGenerator) that is inside the innermost loop, although it doesn't depend on the variables of the outer loops. If this work is expensive, it is better to precalculate beforehand.

3) From your code, because of your break;, I can assume that if you find that the point belongs to one feature, then it doesn't belong to any other. If that is really true, then some ordering of the features might be beneficial if you are able to order them in smart way to break from the loop sooner. Without knowing any info about your features, I will make a simple assumption here: if a point belongs to some feature, then it is very likely that the neighbor point belongs to the same feature.

According to my points 2) and 3), this is the update to your code I am suggesting:

// precalculate shapes outside the innermost loop (point 2. above)
// features with shapes (fws):
const fws = countyGeoJson.features.map(feature => {
  feature,
  shape: new Path2D(pathGenerator(feature))
});

const points = [];
const pointWidth = 2;

for (let x = 0; x < canvasWidth; x += pointWidth) {
  let lastIdx = 0;
  for (let y = 0; y < canvasHeight; y += pointWidth) {
    for (let i = 0; i < fws.length; i++) {
      // start with the last found feature (point 3. above):
      let j = (lastIdx + i) % fws.length;
      if (context.isPointInPath(fws[j].shape, x, y)) {
        points.push({ coords: [x, y], data: fws[j].feature.properties });
        lastIdx = j;  // remember this feature index for the next (x,y) point
        break;
      }
    }
  }
}