none
Performing Spatial Queries on the Client? RRS feed

  • Question

  • I have a requirement to be able to filter the points that I show on my maps based on a spatial criteria (can be a rectangle for simplicity). So for example, I display x # points on the map and then the user wants to draw a rectangle and I need to know which of my points is within the rectangle. This can be done on the server, either through a requery of the database or filtering using data stored in Session, however, I wanted to know if anyone has attempted to do this type of query on the client in a scalable way i.e. using spatial indexes/trees to determine which points are in the polygon (similar to how it's done in a spatially-enabled database). Comparing lat/long of each point to the bounding box doesn't seem scalable to me so I would rather not do it that way.
    Sasha dos Santos Software Engineer Pro Tech Monitoring, Inc. http://www.ptm.com
    • Moved by Ricky_Brundritt Friday, March 9, 2012 5:59 PM (From:Bing Maps: Map Control and Web services Development)
    Thursday, April 21, 2011 2:56 PM

Answers

  • The size of your data set will determine which method you should use to get optimal performance. If you have thousands of points to check against the polygon, then it will likely be better to just make a simple ajax call to the server and perform the check within a spatial database. If you have only a couple hundred points, then just use some JavaScript within the page to check the points.

    The latest published release of http://vetoolkit.codeplex.com contains some JavaScript code that checks whether a point is within a specified polygon. It's the "VEToolkit.Math.IsInPolygon" method and there is a simple example of using it included in the v6.2.012509.1053 release download.

    I have never seen the RTree project before, but may be an option to get better performance out of JavaScript to perform this on slightly larger data sets. However, the performance of JavaScript in the browsers that are still mainstream (IE7/8, Firefox 3/3.5) isn't quite there yet to perform a lot of data intensive operations on the client. Plus, those browsers do not support multi-threading within JavaScript so any long running (500ms or more) loops will cause the user to think the browser has locked up. Yes the performance if IE9 is awesome, but not many people are using it yet.


    Microsoft MVP - Bing Maps
    Blog: http://pietschsoft.com | Web.Maps.VE - ASP.NET AJAX Bing Maps Server Control
    Saturday, April 23, 2011 1:40 PM
  • You can easily optimize this. The clustering algorithm I wrote does the same kind of math as your doing as a part of it's operation using the map view as the rectangle and it can easily handle 10,000+ pushpins without any noticable performance issues in IE. IE does the math in under 100ms. Things like using do/while loops, multiplication rather than division, and using pixel coordinates rather than lat/longs can make a big difference. 
    Windows Live Developer MVP - http://rbrundritt.wordpress.com | http://inknowledge.co.uk
    • Proposed as answer by rbrundritt Tuesday, June 7, 2011 5:37 PM
    • Marked as answer by Ricky_Brundritt Tuesday, June 7, 2011 5:40 PM
    Tuesday, June 7, 2011 3:16 PM

All replies

  • Assuming you're talking about the javascript control, you could try this:

    https://github.com/imbcmdth/RTree/raw/master/src/rtree.js

    However, if I'm honest I'd either do it using a simple P-i-P query on the client, or using a spatial database on the server.


    twitter: @alastaira blog: http://alastaira.wordpress.com/
    Thursday, April 21, 2011 5:02 PM
    Moderator
  • Yes, it's the Javascript Control.  Thanks. Unfortunately, I don't think the R-tree code works in IE. I can't run any of the examples on his page in IE 8.

    Sasha dos Santos Software Engineer Pro Tech Monitoring, Inc. http://www.ptm.com
    Thursday, April 21, 2011 5:25 PM
  • The size of your data set will determine which method you should use to get optimal performance. If you have thousands of points to check against the polygon, then it will likely be better to just make a simple ajax call to the server and perform the check within a spatial database. If you have only a couple hundred points, then just use some JavaScript within the page to check the points.

    The latest published release of http://vetoolkit.codeplex.com contains some JavaScript code that checks whether a point is within a specified polygon. It's the "VEToolkit.Math.IsInPolygon" method and there is a simple example of using it included in the v6.2.012509.1053 release download.

    I have never seen the RTree project before, but may be an option to get better performance out of JavaScript to perform this on slightly larger data sets. However, the performance of JavaScript in the browsers that are still mainstream (IE7/8, Firefox 3/3.5) isn't quite there yet to perform a lot of data intensive operations on the client. Plus, those browsers do not support multi-threading within JavaScript so any long running (500ms or more) loops will cause the user to think the browser has locked up. Yes the performance if IE9 is awesome, but not many people are using it yet.


    Microsoft MVP - Bing Maps
    Blog: http://pietschsoft.com | Web.Maps.VE - ASP.NET AJAX Bing Maps Server Control
    Saturday, April 23, 2011 1:40 PM
  • > Comparing lat/long of each point to the bounding box doesn't seem scalable to me so I would rather not do it that way.

    It is very simple arithmetic, and may be much more effective than you think.

    Sunday, April 24, 2011 9:34 AM
  • I ended up doing the simple arithmetic. The max number of points that has come up in the live is about 6000 points. It is very very fast in Chrome and not so fast in IE, but acceptable. I suggested to my users that they use Chrome because the JavaScript engine is far superior to IE (faster by at least a factor of 10).
    Sasha dos Santos Software Engineer Pro Tech Monitoring, Inc. http://www.ptm.com
    Tuesday, June 7, 2011 1:45 PM
  • You can easily optimize this. The clustering algorithm I wrote does the same kind of math as your doing as a part of it's operation using the map view as the rectangle and it can easily handle 10,000+ pushpins without any noticable performance issues in IE. IE does the math in under 100ms. Things like using do/while loops, multiplication rather than division, and using pixel coordinates rather than lat/longs can make a big difference. 
    Windows Live Developer MVP - http://rbrundritt.wordpress.com | http://inknowledge.co.uk
    • Proposed as answer by rbrundritt Tuesday, June 7, 2011 5:37 PM
    • Marked as answer by Ricky_Brundritt Tuesday, June 7, 2011 5:40 PM
    Tuesday, June 7, 2011 3:16 PM
  • I hadn't even considered using pixel coordinates vs. lat/longs. I will take a look at your code, thanks.
    Sasha dos Santos Software Engineer Pro Tech Monitoring, Inc. http://www.ptm.com
    Tuesday, June 7, 2011 3:22 PM