c# - Scalability Location Distance Search Over 100,000 LatLng Positions Across USA -

c# - Scalability Location Distance Search Over 100,000 LatLng Positions Across USA -

scenario =

1) delivery offices spread out across usa each specifying own maximum delivery radius limit in miles.

2) target address geo converted latlng delivery destination.

goal = homecoming dataset of delivery offices (1) who's delivery radius limit falls within distance target address(2)

attempt =

as starting point problem using first-class work illustration storm consultancy in identifying closest office customer: haversine distance between 2 points

my 'offices' table stores office address along lat , lng values , maximum distance 'deliverylimit'.

the sql calculate haversine blows mind , beyond understanding! storm sql below, instead of selecting 1 row straight distance calculations, need select offices rows who's max distance delivery limit less distance between office , customer.

question1 = how add together max distance limit filter sql query returns offices delivery zone includes target location?

question2 = how can limit number of offices queried realistically in target area of usa? instance, if target location boise, idaho , offices in la, california have delivery distance limit of 300 miles. there no point in querying such offices. however, offices in washington; oregon , northern nevada states border idaho should included in search query perchance have maximum distance values reach illustration of boise, id.

the sql haversine used storm:

select top 1 *, ( 3960 * acos( cos( radians( @custlat ) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians( @custlng ) ) + sin( radians( @custlat ) ) * sin( radians( lat ) ) ) ) distance offices order distance asc

the sql illustration above selects closest office target lat/long (@custlng)

storm approached distance calculation 2 different directions. sql above first. sec keeping office coordinates in in-memory list , creating method function loop on list calculating distances , selecting closest so:

/// <summary> /// returns distance in miles or kilometers of 2 /// latitude / longitude points. /// </summary> /// <param name="pos1">location 1</param> /// <param name="pos2">location 2</param> /// <param name="unit">miles or kilometers</param> /// <returns>distance in requested unit</returns> public double haversinedistance(latlng pos1, latlng pos2, distanceunit unit) { double r = (unit == distanceunit.miles) ? 3960 : 6371; var lat = (pos2.latitude - pos1.latitude).toradians(); var lng = (pos2.longitude - pos1.longitude).toradians(); var h1 = math.sin(lat / 2) * math.sin(lat / 2) + math.cos(pos1.latitude.toradians()) * math.cos(pos2.latitude.toradians()) * math.sin(lng / 2) * math.sin(lng / 2); var h2 = 2 * math.asin(math.min(1, math.sqrt(h1))); homecoming r * h2; } public enum distanceunit { miles, kilometers };

and

var offices = getmyofficelist(); for(int = 0; i< offices.count; i++) { offices[i].distance = haversinedistance( coord, new latlng(offices[i].lat, offices[i].lng), distanceunit.miles); } var closestoffice = offices.orderby(x => x.distance).take(1).single();

scalability of import scenario end lot more 100,000 office locations, in-memory office list alternative unlikely!

if using sql2008 or newer has specific types built in create want easier. main type need utilize geography

i going create guesses @ table structure, main thing have location , deleveryarea

class="lang-sql prettyprint-override">create table offices ( officename varchar(40), location geography, deliverydistance float, --stored in miles --if on sql2008 or 2008r2 replace bufferwithcurves 1 of older buffer functions deliveryarea location.bufferwithcurves(deliverydistance * 1609.34) persisted, --1609.34 converts miles meters )

i used bufferwithcurves in above example, available on sql2012 , newer, if on 2008 or 2008r2 need utilize either bufferwithtolerance or stbuffer or manually define own area hand in insert statment.

now populate data, because made deliveryarea calculated persisted column pretty easy do. need set in location of office , radius of delivery area , calculate circle area you. utilize examples provided in question:

class="lang-sql prettyprint-override">insert offices (officename, location, deliverydistance) values ('boise, id', geography::point(43.6187102,-116.2146068, 4326), --4326 represents "lat , long" coordinate scheme 300 ) insert offices (officename, location,deliverydistance) values ('la, ca', geography::point(34.0204989,-118.4117325, 4326), 300 ) insert offices (officename, location,deliverydistance) values ('walla walla, wi', geography::point(46.0627549,-118.3337259, 4326), 300 ) insert offices (officename, location,deliverydistance) values ('baker city, or', geography::point(44.7746169,-117.8317284, 4326), 300 ) insert offices (officename, location,deliverydistance) values ('elko, nv', geography::point(40.846931,-115.7669825, 4326), 300 )

now query, if wanted find delivery areas serviced jordan vally, oregon (42.9740245,-117.0533247) query be

class="lang-sql prettyprint-override">declare @cust geography = geography::point(42.9740245,-117.0533247, 4326) select officename, location.stdistance(@cust) / 1609.34 distance, --convert miles location.lat lat, location.long lng offices deliveryarea.stcontains(@cust) = 1 order distance asc

and give offices location chose within delivery area. real nice thing scheme if instead of calculating deleveryarea based of location , delevery range give set of points outline non circular geographic area, city.

with planned spatial index solution should work 100,000 location record set. if want larn more of benefits of using geography see this question , answer.

here sql fiddle of queries set above shown in working example.

c# sql distance geo haversine