Javascript: point-in-polygon performance improvement

3
votes

I have an array of objects. Each object represents a point has an ID and an array with x y coordinates. , e.g.:

let points = [{id: 1, coords: [1,2]}, {id: 2, coords: [2,3]}]

I also have an array of arrays containing x y coordinates. This array represents a polygon, e.g.:

let polygon = [[0,0], [0,3], [1,4], [0,2]]

The polygon is closed, so the last point of the array is linked to the first.

I use the following algorithm to check if a point is inside a polygon:

pointInPolygon = function (point, polygon) {
  // from https://github.com/substack/point-in-polygon
  let x = point.coords[0]
  let y = point.coords[1]
  let inside = false

  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    let xi = polygon[i][0]
    let yi = polygon[i][1]
    let xj = polygon[j][0]
    let yj = polygon[j][1]
    let intersect = ((yi > y) !== (yj > y)) &&
                    (x < (xj - xi) * (y - yi) / (yj - yi) + xi)
    if (intersect) inside = !inside
  }

  return inside
}

The user draws the polygon with the mouse, which works like this: http://bl.ocks.org/bycoffe/5575904

Every time the mouse moves (gets new coordinates), we have to add the current mouse location to the polygon, and then we have to loop through all the points and call the pointInPolygon function on the point on every iteration. I have throttled the event already to improve performance:

handleCurrentMouseLocation = throttle(function (mouseLocation, points, polygon) {
    let pointIDsInPolygon = []
    polygon.push(mouseLocation)

    for (let point in points) {
        if (pointInPolygon(point, polygon) {
            pointIDsInPolygon.push(point.id)
        }
    }
    return pointIDsInPolygon
}, 100)

This works fine when the number of points is not that high (<200), but in my current project, we have over 4000 points. Iterating through all these points and calling the pointInPolygon function for each point every 100 ms makes the whole thing very laggy.

I am looking for a quicker way to accomplish this. For example: maybe, instead of triggering this function every 100 ms when the mouse is drawing the polygon, we could look up some of the closest points to the mouse location and store this in a closestPoints array. Then, when the mouse x/y gets higher/lower than a certain value, it would only loop through the points in closestPoints and the points already in the polygon. But I don't know what these closestPoints would be, or if this whole approach even makes sense. But I do feel like the solution is in decreasing the number of points we have to loop through every time.

To be clear, the over 4000 points in my project are fixed- they are not generated dynamically, but always have exactly the same coordinates. In fact, the points represent centroids of polygons, which represent boundaries of municipalities on a map. So it is, for example, possible to calculate the closestPoints for every point in advance (in this case we would calculate this for the points, not the mouse location like in the previous paragraph).

Any computational geometry expert who could help me with this?

2
javascriptpolygoncomputational-geometrypointpoint-in-polygon

2 Answers

4
votes

If I understand you correctly, a new point logged from the mouse will make the polygon one point larger. So if at a certain moment the polygon is defined by n points (0,1,...,n-1) and a new point p is logged, then the polygon becomes (0,1,...,n-1,p).

So this means that one edge is removed from the polygon and two are added to it instead.

For example, let's say we have 9 points on the polygon, numbered 0 to 8, where point 8 was the last point that was added to it:

enter image description here

The grey line is the edge that closes the polygon.

Now the mouse moves to point 9, which is added to the polygon:

enter image description here

The grey edge is removed from the polygon, and the two green ones are added to it. Now observe the following rule:

Points that are in the triangle formed by the grey and two green edges swap in/out of the polygon when compared to where they were before the change. All other points retain their previous in/out state.

So, if you would retain the status of each point in memory, then you only need to check for each point whether it is within the above mentioned triangle, and if so, you need to toggle the status of that point.

As the test for inclusion in a triangle will take less time than to test the same for a potentially complex polygon, this will lead to a more efficient algorithm.

You can further improve the efficiency, if you take the bounding rectangle of the triangle with corners at (x0, y0),(x1, y0),(x1, y1),(x0, y1). Then you can already skip over points that have an x or y coordinate that is out of range:

enter image description here

Any point outside of the blue box will not change state: if it was inside the polygon before the last point 9 was added, it still is now. Only for points within the box you'll need to do the pointInPolygon test, but on the triangle only, not the whole polygon. If that test returns true, then the state of the tested point must be toggled.

Group points in square boxes

To further speed up the process you could divide the plane with a grid into square boxes, where each point belongs to one box, but a box will typically have many points. For determining which points are in the triangle, you could first identify which boxes overlap with the triangle.

For that you don't have to test each box, but can derive the boxes from the coordinates that are on the triangle's edges.

Then only the points in the remaining boxes would need to be tested individually. You could play with the box size and see how it impacts performance.

Here is a working example, implementing those ideas. There are 10000 points, but I have no lagging on my PC:

canvas.width = document.body.clientWidth; 

const min = [0, 0], 
    max = [canvas.width, canvas.height],
    points = Array.from(Array(10000), i => {
        let x = Math.floor(Math.random() * (max[0]-min[0]) + min[0]);
        let y = Math.floor(Math.random() * (max[1]-min[1]) + min[1]);
        return [x, y];
    }),
    polygon = [],
    boxSize = Math.ceil((max[0] - min[0]) / 50),
    boxes = (function (xBoxes, yBoxes) {
        return Array.from(Array(yBoxes), _ => 
                Array.from(Array(xBoxes), _ => []));
    })(toBox(0, max[0])+1, toBox(1, max[1])+1),
    insidePoints = new Set,
    ctx = canvas.getContext('2d');

function drawPoint(p) {
    ctx.fillRect(p[0], p[1], 1, 1);
}

function drawPolygon(pol) {
    ctx.beginPath();
    ctx.moveTo(pol[0][0], pol[0][1]);
    for (const p of pol) {  
        ctx.lineTo(p[0], p[1]);
    }
    ctx.stroke();
}

function segmentMap(a, b, dim, coord) {
    // Find the coordinate where ab is intersected by a coaxial line at 
    // the given coord.
    // First some boundary conditions:
    const dim2 = 1 - dim;
    if (a[dim] === coord) {
        if (b[dim] === coord) return [a[dim2], b[dim2]];
        return [a[dim2]];
    }
    if (b[dim] === coord) return [b[dim2]];
    // See if there is no intersection:
    if ((coord > a[dim]) === (coord > b[dim])) return [];
    // There is an intersection point:
    const res = (coord - a[dim]) * (b[dim2] - a[dim2]) / (b[dim] - a[dim]) + a[dim2];
    return [res];
}

function isLeft(a, b, c) {
    // Return true if c lies at the left of ab:
    return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) > 0;
}

function inTriangle(a, b, c, p) {
    // First do a bounding box check:
    if (p[0] < Math.min(a[0], b[0], c[0]) ||
            p[0] > Math.max(a[0], b[0], c[0]) ||
            p[1] < Math.min(a[1], b[1], c[1]) ||
            p[1] > Math.max(a[1], b[1], c[1])) return false;
    // Then check that the point is on the same side of each of the 
    // three edges:
    const x = isLeft(a, b, p),
        y = isLeft(b, c, p),
        z = isLeft(c, a, p);
    return x ? y && z : !y && !z;
}

function toBox(dim, coord) {
    return Math.floor((coord - min[dim]) / boxSize);
}
function toWorld(dim, box) {
    return box * boxSize + min[dim];
}

function drawBox(boxX, boxY) {
    let x = toWorld(0, boxX);
    let y = toWorld(1, boxY);
    drawPolygon([[x, y], [x + boxSize, y], [x + boxSize, y + boxSize], [x, y + boxSize], [x, y]]);
}

function triangleTest(a, b, c, points, insidePoints) {
    const markedBoxes = new Set(), // collection of boxes that overlap with triangle
        box = [];
    for (let dim = 0; dim < 2; dim++) {
        const dim2 = 1-dim,
            // Order triangle points by coordinate
            [d, e, f] = [a, b, c].sort( (p, q) => p[dim] - q[dim] ),
            lastBox = toBox(dim, f[dim]);
        for (box[dim] = toBox(dim, d[dim]); box[dim] <= lastBox; box[dim]++) {
            // Calculate intersections of the triangle edges with the row/column of boxes
            const coord = toWorld(dim, box[dim]),
                intersections = 
                        [...new Set([...segmentMap(a, b, dim, coord),
                                     ...segmentMap(b, c, dim, coord), 
                                     ...segmentMap(a, c, dim, coord)])];
            if (!intersections.length) continue;
            intersections.sort( (a,b) => a - b );
            const lastBox2 = toBox(dim2, intersections.slice(-1)[0]);
            // Mark all boxes between the two intersection points
            for (box[dim2] = toBox(dim2, intersections[0]); box[dim2] <= lastBox2; box[dim2]++) {
                markedBoxes.add(boxes[box[1]][box[0]]);
                if (box[dim]) {
                    markedBoxes.add(boxes[box[1]-dim][box[0]-(dim2)]);
                }
            }
        }
    }
    // Perform the triangle test for each individual point in the marked boxes
    for (const box of markedBoxes) {
        for (const p of box) {
            if (inTriangle(a, b, c, p)) {
                // Toggle in/out state of this point
                if (insidePoints.delete(p)) {
                    ctx.fillStyle = '#000000';
                } else {
                    ctx.fillStyle = '#e0e0e0';
                    insidePoints.add(p);
                }
                drawPoint(p);
            }
        }
    }
}

// Draw points
points.forEach(drawPoint);

// Distribute points into boxes
for (const p of points) {
    let hor = Math.floor((p[0] - min[0]) / boxSize);
    let ver = Math.floor((p[1] - min[1]) / boxSize);
    boxes[ver][hor].push(p);
}

canvas.addEventListener('mousemove', (e) => {
    if (e.buttons !== 1) return;
    polygon.push([Math.max(e.offsetX,0), Math.max(e.offsetY,0)]);
    ctx.strokeStyle = '#000000';
    drawPolygon(polygon);
    const len = polygon.length;
    if (len > 2) {
        triangleTest(polygon[0], polygon[len-2+len%2], polygon[len-1-len%2], points, insidePoints);
    }
});

canvas.addEventListener('mousedown', (e) => {
    // Start a new polygon
    polygon.length = 0;
});
Drag mouse to draw a shape:
<canvas id="canvas"></canvas>
0
votes

Keep a background image where you perform polygon filling every time you update the polygon.

Then testing any point for interiorness will take constant time independently of the polygon complexity.