Faster way to loop through array of points and find if within polygons

Question

I have a Node app which allows users to plot 'events' on dot plot graphs. An event is represented by an array of floats, e.g 1 event may look like this.

[ 242841.86914496083,
1090.0027001134586,
11711.344635666988,
142639.20305005432 ]

Users can plot the 1st element(242841.86914496083) against the 2nd element(1090.0027001134586) on a graph, and for example the 3rd(11711.344635666988) against the 4th(142639.20305005432), and all combinations in between.

In the following example, all values range from 0 to 262,144. So to plot on a 200x200 pixel graph I get the ratio and plot accordingly. A graph of 20 events will look something like this (this graph plots the first element of an event on the x axis against the 2nd element of the same event on the y axis):

My users can then do what they call a 'gate'. They can draw a polygon around certain events to isolate these events. For example here, I've draw a gate around these events, colored the events in the gate red, and I'm only showing these events on the graph:

You can see i have 'gated' 12 events. Now I'd like to see these gated events plotted with the 4th element on the x axis and the 3rd element on the y axis:

Now I'd like to draw another gate on this. This new gate will be a child of the previous gate i.e. an event considered in this gate is also in the first gate:

Now on my original graph (with the 1st element plotted on x axis and 2nd on y axis), I want to see all the events colored correctly. I.e non-gated events will be white, events that are in both gates will be green, and events in the first gate will be red. The result is this:

Its important to notice that the gates were made on different elements: the first gate was made on the 1st and 2nd elements of an event, and the 2nd on the 3rd and 4th.

The issue I'm having is that some users are uploading files with 800,000 events. My algorithms work well for anything below 200,000 but then everything becomes very slow. I have made a detailed plunker here.

My algorithm is based on getting an array of gate 'chains'. Each of these chains is an array. If an event is within the polygon defined in each gate element, then it gets the color of the furthest down child gate. If you look at the console on Plunkr for example here, you'll see what the gate chain array looks like:

So the problem I have is that when looping through the events, I then have to loop through each 'chain' and working out if the event is within all the polygons in the chain. This is really slow after about 200k. At 800k, it can take over a minute.

So I loop through the 800k events and then check for the color like this:

for (var i = 0; i < events.length; i++) {

    // draw graph 1
    x = events[i][0];
    y = events[i][1];

    pointX = getPointOnCanvas(x);
    pointY = getPointOnCanvas(y, 'y');

    color = getColorOfCell({
      gateChain: allGatesChain,
      events: events,
      i: i
    });

    color = color;

    drawDot(pointX, pointY, color, context1);
}

getColorOfCell() is:

function getColorOfCell(params){

    var allGatesChain = params.gateChain;
    var events = params.events;
    var i = params.i;

    var checked = false;
    var plotDot = true;
    var color = '#FFF';
    var nextGate;
    var isGated = false;

    allGatesChain.every(function(gateChain){

        if(isGated) {
            // break
            return false;
        } 
        else {
            gateChain.every(function(nextGate){

                    if (isInDotPlotGate({
                        x: events[i][nextGate.paramX],
                        y: events[i][nextGate.paramY],
                        gatingCoords: nextGate.gatingDetails.gatingCoords,
                        boundingBox: nextGate.gatingDetails.boundingBox
                    })){
                        color = gateChain[0].color;

                        isGated = true;
                        return true;
                    } else {
                        isGated = false;
                        color = '#FFF'
                        //break to next chain
                        return false;
                    }

            });

            return true;
        }

    });

    return  color;

}

isInDotPlotGate() is:

function isInDotPlotGate(params){

    if(params.x < params.boundingBox.minGateX || params.x > params.boundingBox.maxGateX || params.y < params.boundingBox.minGateY || params.y > params.boundingBox.maxGateY){
        return false
    }

    return inside([params.x, params.y], params.gatingCoords);

    return false;
}

And inside() is:

function inside(point, vs){
    // ray-casting algorithm based on
    // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

    var x = point[0], y = point[1];

    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 > y) != (yj > y))
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }

    return inside;

}   

To check if an event is actually in a polygon, I first check if it's within the bounding box (the rectangle made from getting the lowest and highest x and y points), then I use a small NPM package https://www.npmjs.com/package/point-in-polygon

All the code in on plunker.

I know this is complex but I've racked my grains and cant think of how to improve it. Is there a faster way?

Any help greatly appreciated.

In case you missed it (its a long question!) the plunker is here.

EDIT

@juvian Suggested it might be quicker to create a canvas, draw a gate on it, fill it, and then check the pixel color, rather than checking if a point is inside the point of a polygon. I did this with data of over 800k and the results were very similar: 18 seconds for current method and 18.5 seconds using the pixel color way. So it doesnt improve the efficiency of the algorithm but was a nice suggestion!

EDIT I've created another plunker with data more like my own. This plunker has 873,620 events and each event as 11 elements.

I've also separated out the getting of the colors from actually drawing the canvas because as @juvian pointed out on Chrome its the drawing part that takes the longest. On Node, the drawings isn't the issue, it does that very quickly.

So now I can see that on chrome it takes just 1.2 seconds to loop through the entire array and figure out the color, but it takes 16 seconds to do the same job on Node! Puzzling, i'll keep investigating.

New Plunker is here https://plnkr.co/edit/1k1Y0HzkNClSf7hSoPFZ?p=preview

EDIT This seems to be a deeper problem than I had thought. I'm doing all these calculations within a http request. So a user clicks draw, i make a post request and retrieve the canvas. It takes 16 seconds to work out the colors when i do it that way. However when I just run the code on node through the command line, it takes less than a second. Not sure if there's anyway around this now....

Answer 1

I don't do JS so I can't claim I understand fully what it is you do. However I gather that you are having performance problems with determining which points are in the gate polygon.

If I understood correctly you are checking each point against the polygon which gives you \$O(np)\$ run time where \$n\$ is the number of points and \$p\$ is the number of corners on the polygon.

One idea to make this scale you can make a bitmap of the same resolution as the user is drawing the polygon in and in each pixel store the ID of the event that was rendered on that pixel (or a list of events if you have collisions). Then simply raster the polygon and find all events inside the polygon. However as you still need to go through all the points of the data set and then raster the polygon the run time is now \$O(n + A)\$ where \$A\$ is the area of the polygon.

This is already a big improvement. However we can do better.

Lets arrange the points in the data set into a quadtree in a pre-processing step when the user uploads, this is \$O(n\log(n))\$ work.

Then when the user draws a gate, compute the bounding box of the polygon and then construct a quadtree for the polygon where each node is either "inside" or "outside" going down to pixel level.

Then start at the root of the point quadtree, test each child if it intersects the bounding box of the gate, if not you can skip that child. Next you test the child against the gate quadtree. Is the child contained in a node that is "outside"? Skip the child and it's children. Is the child contained in a node that is "inside" mark all the children as being in the gate and continue without recursing. If the child isn't contained in either an outside or inside node in the gate quadtree, recurse into the children of the child and repeat until you reach a leaf node in the point quadtree. If the leaf is still not strictly contained in an "inside" or "outside" of node in the gate quadtree, test each of the \$k\$ points against the gate quadtree.

Computing the run time is a bit hard but lets try... assume that along each pixel of the circumference of the gate, you have to test all of the \$k\$ points in the leaf that covers that bit of the periphery. This bit is \$O(kc)\$ where \$c\$ is the circumference of the gate (note \$c<A\$ typically). To get down to each of the leafs we need to traverse \$O(log(n))\$ nodes in the point quadtree and each of those needs to be tested against \$O(log(A))\$ nodes of the gate quadtree.

Which gives a total run time of \$O(\log(n)\log(A)kc)\$.

This way of doing it allows your users to scale their datasets massively as the only dependence on \$n\$ is in \$log(n)\$ which grows very slowly. You can consider \$k\$ as a design parameter that is constant so you can remove it from the above expression if you want. Then the circumference of the gate is what dominates the run time (note, not the area but the circumference).

Answer 2

I would start by running a profiling tool to see what is really happening.

The one thing that stands out to me is that the number of vectors in each polygon looks like it is in the hundreds. That is your innermost loop so if you can reduce that you will probably get the greatest benefit. You can probably improve your performance by reducing that somehow. You could either taking them arbitrarily (skip 4 out of 5 say) or use an algorithm which skips points that are almost in a straight line.

I would also use some or find instead of every in getColorOfCell both of these can be made to stop on the first match which would save you the funny if/else logic.

What happens if your user draws the second gate so that it is partially outside of the first gate? By your description they should be white (because they are not in the first gate) but your code would make them green (because the second gate is tested first)