Find points that lie within plotted drawn boundaries.

Question

Hi,

We are using Bing Maps to plot a large number of drawn shapes, covering almost the entire USA. The coordinates are stored in string format. We have requirement to find given a latitude/longitude point, we need to determine which shape it falls within. When there are fewer shapes, the lookup is fast, but as the number increases, the process becomes significantly slower. Is there a more efficient method to improve performance.

Thanks!

Answer 1

You will always hit a performance bottleneck if you try and do this type of calculation in the browser. This calculation is pretty compute intensive. The more shapes and complexity of the shapes (number of coordinates) will directly impact performance and you will eventually hit a point where it is slow.

Doing this in the browser, there are a couple of optimizations that could be done as mentioned in another thread with you: https://learn.microsoft.com/en-us/answers/questions/2151765/along-the-route-performance-issues

That said, if you plan to do this calculation more than once, then one optimization you could do is implement a spatial index. Creating the spatial index does have a performance cost to create, but once created, can really speed up the initial filtering. For example: https://github.com/mourner/flatbush and https://github.com/mourner/rbushNote that these generally require you to first calculate the bounding box of all your shapes first.

On the off chance you know that all shapes will be visible on the map when you need to do this calculation, and you ok with a margin of error near edges, you could leverage the maps click event and programmatically trigger a click event at the coordinate. This would be very fast. The reason why the map is so fast at this is that when the map has stopped moving, it renders two canvases. One that you see, and another that is all that data overlaid but colored using a unique color and used as an index. When a click event happens, the pixel color in this reference canvas is used to determine which shape is clicked. This is basically an index, but with a limited resolution.

Assuming the shapes won't always be visible in the map, or you need high accuracy, the best option for this scenario is to hand this off to a backend server and process the calculation there.