Point in Polygon and Bounding Box search against data in the Customer Service Site

Currently when storing data in the customer service site you have the ability to query your point location data by entity id, property, radius search, and find near route. There are two key search functionalities missing. The first is bounding box searching, and the second is point in polygon searches. A bounding box is simple 4 sided regular polygon and as such if we can perform a point in polygon search we can use the same algorithm to perform a bounding box search. This post is going to outline two methods that can be used to perform such a search against data that is stored in the Customer Service Site.

Method 1

Lets start off with a polygon (blue). If we find the maximum and minimum latitude and longitude coordinates that this polygon has we can create a bounding box (green) that encloses the polygon. We can then calculate the center point and radius from center point to a corner of this bounding box. Once we know this information we can then enclose this bounding box with a circle (red). The information used to create this circle can be used with the radius search tools that are currently available.

image

If you perform a radius search using the calculated information you will end up with a lot of extra data points. You can filter this data points by running them through a point in polygon algorithm like the one outlined here: http://msdn.microsoft.com/en-us/library/cc451895.aspx. You can then return the filtered data to the user. Using this method your polygon must fit inside a bounding box whose sides are no longer than 353.55 miles. The benefit of this approach is that there are only a few calculations required initially. One down side is that there is a lot of extra data that could be potentially returned.

Method 2

The second method is very similar to the first. The maximum and minimum latitude and longitude coordinates of the polygon are used to create a bounding box so that the center of the polygon can be calculated. However, instead of calculating the radius from the center point to a corner of the bounding box, we can loop through and calculate the radii’s from the center point to each point in the polygon. The largest radius can then be used to perform a radius search.

image

Using this approach should reduce the amount of data that is returned by radius search as it is able to enclose the polygon tighter than that previous method. The down side is the number of calculations that need to be performed initially. For complex polygons this can result in slower performance. Using this method  you are limited to a maximum radius of 250 miles.

Conclusion

Using either of these methods will allow you to perform both bounding box and point in polygon searches against your data in the customer service site. Which method should you use. If you are performing bounding box searches or are using complex, predefined polygons then the first method would be ideal. If youare letting the user create the polygon chances are there will only be a limited number of points and as such method 2 would be ideal.

I have put together an example that allows you to draw out polygons using the right mouse button (press the left mouse button when done). After you have drawn a polygon you can then use either method to query the FourthCoffeeShops data source. You can down load the sample code here: http://cid-e7dba9a4bfd458c5.skydrive.live.com/self.aspx/VE%20Sample%20code/CSSFindByPolygon.zip

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s