Along the route performance issues

Balasaheb Molawade 136

Hi,

We are currently using Bing Maps to plot routes and identify records along the route. To achieve this, we are utilizing the following method:

Microsoft.Maps.SpatialMath.Geometry.buffer(routePath, parseFloat(alongRouteDist), alongRouteDistUnit);

While this approach works well for shorter routes and fewer records, we encounter performance issues when the route is long or the number of records is large. In such cases, the browser becomes sluggish and occasionally hangs altogether.

Is there an efficient solution or optimization technique to address this issue?

Thanks

Manas Mohanty (Quadrant Resource LLC) 215 Reputation points Microsoft Vendor

2025-01-29T09:30:19.69+00:00
Hi Balasaheb Molawade!

Welcome to the Microsoft Q&A and thank you for posting your questions here.

You can follow below process to identify the records along route

Create routes between two or more location with waypoints.

Use Bing Maps Local Insights API to find local business entities or points of interest within a certain distance or travel time from the route in the mentioned waypoints.

You can create multiple short routes using Microsoft.Maps.Directions Module and Collect records from routes using Microsoft.Maps.LocalInsights

Kindly refer below docs for reference.

waypoint-class

calculate-driving-directions

directions-module-examples

Thank you.
Manas Mohanty (Quadrant Resource LLC) 215 Reputation points Microsoft Vendor

2025-01-30T05:02:38.7566667+00:00

Hi Balasaheb Molawade!

We are checking to see if the above pointer helped.

Thank you.
Manas Mohanty (Quadrant Resource LLC) 215 Reputation points Microsoft Vendor

2025-01-31T06:12:40.23+00:00

Hi Balasaheb Molawade!

We have not heard from you yet. Hope the pointers were helpful to you.

Thank you.
Balasaheb Molawade 136 Reputation points

2025-01-31T06:14:23.89+00:00

Hi Manas,

Thanks for your response, but it will not work because we plot the route and want to display records from our records collection along the route. It works, but it takes time when the route is long. We are looking for a faster way to find records along the route.

Thanks!
Manas Mohanty (Quadrant Resource LLC) 215 Reputation points Microsoft Vendor

2025-01-31T06:55:00.1533333+00:00

Hi Balasaheb Molawade!

Thank you for replying.

You can split larger to smaller routes with two/three waypoint which will reduce the processing time and accumulate details for entire route incrementally. right?

Thank you.

1 answer

rbrundritt 18,926 Microsoft Employee

This type of calculation is pretty resource intensive. As you have noticed it works fine to a certain point, but the more data and longer the lines, the slower it becomes, especially when using JavaScript. To handle larger data sets you should consider doing this calculation on the server side, ideally in a spatial database where spatial indexing can be used. This would allow for significantly more complex route areas and more data points.

That said, if you must do this in JavaScript here are some optimization ideas you can try:

Do an initial filtering of your data points so that you don't have to test all of them. A simple starting point is to get the bounding box of the route path, buffer it by your distance to account for places where the route line may be near an edge of the bounding box. Then do an initial filter of your data points. This should be fast since you have a much smaller polygon to compare against (simply min/max comparison of lat/lon). After that you can then do a comparison using your buffer polygon with just the filtered subset of points. A bounding box is likely to have a lot of irrelevant area depending on the shape of the route line, so you could potentially look at other shapes that might more tightly wrap the route path area roughly.
Reduce the resolution of the generated buffer. I suspect that the generated buffer could have thousands, possibly tens of thousands of points. Lowering the resolution would create a margin of error, but would allow for the calculations to happen much faster. You could potentially buffer by a larger amount initially, reduce the resolution of the polygon, use that as an initial filter, then do a test with the high resolution buffer against the initially filtered results. A similar technique is often used in spatial databases for performance.
Instead of doing a filter using a single bounding box, consider calculating a handful of bounding boxes along the route. You could start off with a grid, calculate all the cells the route path passes through. Then use those cells/bounding boxes as an initial filter. This would significantly reduce the number of points that would have to be checked against the high-resolution polygon. However, there would be tradeoffs. If you used too high of a resolution grid, you may end up doing a lot more calculations.
Instead of using a polygon, calculate the actual straight-line distances from the points to route path, then do a simple check to see if that is within the desired distance. https://turfjs.org/docs/7.0.0/api/pointToLineDistance I'm not certain this will be faster. I have a feeling this solution would vary depending on the length of the line and number of points. It may be faster in some scenarios (maybe when you have long paths and lots of points).
Similar to the above, you could break the route up into line segments (two lat/lon points per segment), then loop over these and the points and calculate the distance to your data set points. As soon as a point is within your distance range, you can skip checking the rest of the line segments.

rbrundritt 18,926 Reputation points Microsoft Employee

2025-02-06T01:02:37.1333333+00:00

Thinking about this some more I believe calculating the shortest distance to the route path with a short circuit if the distance is within a specified range (less than your search distance). Additionally, this could be potentially offloaded into a web worker and parallelized for better performance. I'll take a look at putting together a code sample that does this with GeoJSON so that it's reusable with any map solution.

If you plan to do several near route calculations on the same set of points (e.g. several different routes), then creating a spatial index such as an SRTree would provide more performance, however, if you are only doing this calculation once the overhead of creating the index isn't worth it.

Other than that, the only other way you could potentially make this faster would be by offloading this server side in a spatial database.
rbrundritt 18,926 Reputation points Microsoft Employee

2025-02-06T17:20:31.2233333+00:00

Doing some experimenting I found calculating the distance from point to line is only faster then the line is low resolution. So in your case it's not a good approach. It looks like the buffer polygon approach is still the best approach. We can still look at optimizations such as initial bounding box filters and parellization using web workers.

rbrundritt 18,926 Microsoft Employee

I made a lot of progress and found a relatively easy method that significantly improves performance. You can try out my test app here: https://rbrundritt.azurewebsites.net/Demos/SpatialMath/NearRouteFilter/index.html You can see the source code in the index.html file via the dev tools in the browser.

Test case scenario:

Route path: Seattle to Orlando, ~3000 miles in length consisting of 41,177 coordinates.
Point data: 100,000 points randomly positioned within a bounding box of the USA.
Search buffer radius: 5km (I tried 1km as well but didn't see much difference. If you are use a proportionately larger search radius, performance may degrade since less points would be prefiltered).

I purposely choose a route that crosses the USA diagonally as this would create a very large bounding box.

Methodology for subpath bbox prefilter: Instead of creating a grid and then selecting each cell that the route passes through a simpilar method was used. The route path was divided into subpaths based on coordinate indicies. The bounding box of these subpaths were calculated, then buffered. This does lead to neighbouring bounding boxes overlapping, however that isn't an issue since we short circuit the prefilter the first time a point is found to be in any of these bounding boxes. In the worst case scenario all points would be within the prefilter area and also go through the standard point in polygon filter, thus taking longer than usual, however this is an edge case that would likely only happen when points are close together or a very large search buffer radius is used.

Method	Avg Time (ms)	Notes
Standard buffer polygon filter	15683	Base scenario
Single bbox prefilter	8205	1.9X improvement. This could easily be much faster for routes that don't have such a large bounding box.
4 subpath bbox prefilter	2321	6.7x improvement
8 subpath bbox prefilter	1783	8.8x improvement
16 subpath bbox prefilter	1627	9.6x improvement.
32 subpath bbox prefilter	1463	10.7x improvement.

NOTE: It may seem logical that the more supbath bboxes you create the faster things will become, however, the overhead of creating and testing these bounding boxes will eventually degrade performance. I recommend using 8 or 16 subpaths and no more.

Parallization via web workers

Here I tried offloading the filtering to a web worker to get the calculation off the UI thread but found that due to the size of data we are working with there is a lot of overhead getting it to the worker and thus the workers generally were slower. I tried calculating the subpath bounding boxes and route buffer once and passing those instead so those calculations were only done once but that didn't seem to make much difference. With this in mind, unless you are finding that other UI is freezing up noticably when doing the calculations I would skip the web workers. If you do decide to use a web worker to keep the UI from freezing, keep it simple and use only 1. The added complexity and overhead of multiple web workers in this scenario are unlikely to provide any benefit on any device other than the most powerful ones.

I performed all these tests times each and calculated the average compute time. I used Microsoft Edge version (132.0.2957.140) on a Surface Book 3 (I7 4 core CPU, 32GB RAM), so performance will vary by device accordingly.

Share via

Along the route performance issues

1 answer

Parallization via web workers

Your answer