Perhaps this question should be elsewhere but as its mainly a mathematical problem Im posting here.
I have a dataset of which looks like this:
[ [ 242841.86914496083, 1090.0027001134586, 11711.344635666988, 142639.20305005432 ], [ 212841.86914496083, 128007.0027001134586, 11711.344635666988, 142639.20305005432 ] ... ]
Each array is called an "event" and in this case have 4 "parameters". I want to plot these events on multiple scatter charts. For example, on the first scatter chart, i'll plot the first and second parameter of each event, so the (x, y) point for the first event is (242841.86914496083, 1090.0027001134586), for the 2nd event is (212841.86914496083, 128007.0027001134586) etc. On the second chart, i'll plot the second and third parameter of each event, so the (x, y) point for the first event is (11711.344635666988, 142639.20305005432), for the 2nd event is (11711.344635666988, 142639.20305005432) etc.
In the example Im giving the range is 0 to 262144;
The scatter charts are 200px x 200px but can be any pixel size up to 2000px. It's always square.
When plotting, I want to work out which points are within a polygon. Here is a sample polygon:
[ [ 200000, 100000 ], [ 230000, 180000 ], [ 200000, 200000 ], [ 200000, 230000 ], [ 110000, 220000 ], [ 100000, 180000 ], ]
The points within the polygon are to be plotted in a different color to the points outside it. The polygon is to be applied to scatter chart 1 and 2, but it's the first and second parameter of each event that is to be used to figure out if the event is within the polygon and what color it should be on both charts. E.g. say the point for event 2 (212841.86914496083, 128007.0027001134586) are within the polygon, this mean that event will appear in red in each chart.
I have a simple algorithm which runs through each point and checks if it's within the polygon. I use https://www.npmjs.com/package/point-in-polygon.
Keep in mind, there are often multiple polygons (n), and these can be applied to different combinations of parameters. So I need to work out if an event is in all n polygons, or if its in n-1 polygons etc.
To sum up, what I need to know is:
- percentage of total events within each polygon
- number of events within a polygon
- number of events within n, n-1 etc polygons
- x value mean of event with polygon
- y value mean of event with polygon
My algorithm performs well for up to 10,000 events. But then it hits issues. Some of my users have files that contain 1 millions events, and my algorithms take minutes.
How can I work out what I need more efficiently? Binning data is an option but then I lose accuracy in results. E.g. for a 200 by 200 pixel image I could create 200 bins for each axis. Problem is a then lose accuracy on the x and y mean values. Also, users can change to 201 x 201 pixel images, now I need to work out 201 bins etc.
After file upload, these files are on the server and can be pre-processed before graphs are generated. Is there anything that can be done mathematically to improve performance for large number of events?
EDIT: To be clear - figuring out if a point is in a polygon is not the most performance intensive. The most performance intensive part is looping through 1 million events in order to plot them on a, say, 400px by 400px image. The solution, probably lies somewhere in binning data - but if I make 400 bins, then the user - on the fly - changes the image size to 410px, I now need to make 410 bins from the ORIGINAL dataset. Is there some way around this?
EDIT So the data is known in advance. This sits on my server and can be manipulated in anyway. The size of the image and the polygons are now knows in advance - users draw the polygons and the image must change on the fly. With, say, 1 million events, this is not possible - the browser usually crashes...I can bin the data, but if I create 200 bins (standard image is 200 x 200), then the user makes the image bigger e.g. 210 x 210, now I have to cycle through 1 million events and create 210 bins, which is obviously a big performance issue