implementing a proximity search in sql server

let’s use a sample database for the known points.  i’m using sql server 2005 express which is free.  here’s my table structure for known points (for this sample):

   1:  CREATE TABLE [dbo].[Locations](
   2:      [LocationId] [int] IDENTITY(1,1) NOT NULL,
   3:      [LocationName] [nvarchar](50) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
   4:      [Address] [nvarchar](50) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
   5:      [City] [nvarchar](50) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
   6:      [State] [nvarchar](2) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
   7:      [Zip] [nvarchar](9) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
   8:      [Latitude] [float] NOT NULL,
   9:      [Longitude] [float] NOT NULL,
  10:      [XAxis] [float] NOT NULL,
  11:      [YAxis] [float] NOT NULL,
  12:      [ZAxis] [float] NOT NULL,
  13:   CONSTRAINT [PK_Locations] PRIMARY KEY CLUSTERED 
  14:  (
  15:      [LocationId] ASC
  16:  )WITH (PAD_INDEX  = OFF, IGNORE_DUP_KEY = OFF) ON [PRIMARY]
  17:  ) ON [PRIMARY]

once you have the locations, there are two key steps here: 1) geocoding those locations and 2) establishing the proximity calculations for the axis points.  the first is rather simple.  you essentially have to use a geocoding service to perform the action.  in my application i use my geocode provider and the yahoo geocode apis.  i’ve found them to be accurate and current.  google also has some as well.  both are ‘free’ (certain number of transactions) but you have to register your application.  i think yahoo is also implementing referrer-based checking as well, which might be a consideration.  either way, these will geocode your address.

suggestion: you can abstract this from your users very easily.  when they enter an address to save into your application UI, take an intermediary step to verify and geocode the address…once you have the lat/long then you are ready to save it to the database.

the next step is calculating the axis.  i’m honestly not going to sit here and pretend to tell you that i’m a geospacial expert on the laws of longitude, because i’m not.  basically the math that is performed makes calculations based on the radius and axis point of the earth.  no, i’m serious.  you’ll see later one of the parameters is earth radius.  once you have the known lat/long of your addresses, then you have to calc the axis points.  to simplify this for me, i created three functions in sql server like this one:

   1:  CREATE FUNCTION [dbo].[XAxis] 
   2:      (
   3:      @lat float,
   4:      @lon float
   5:      )
   6:  RETURNS float
   7:  AS
   8:      BEGIN
   9:      RETURN COS(4 * (4 * atn2(1, 5) - atn2(1, 239)) / 180 * @lat) * COS(4 * (4 * atn2(1, 5) - atn2(1, 239)) / 180 * @lon)
  10:      END

the others are similar and you can get the scripts at the bottom of this post.  once you have those in your database for reusability, you have two options: stored procedure or trigger.  stored procedure (or rather, implementing within your insert/update routine) is probably most ideal.  you want to ensure the axis calculations (and also the geocoding) maintains integrity.  after all, if the user updates the address, you want to update all that information!  so within your stored proc you can simply update the XAxis, YAxis, and ZAxis fields using these functions using something like:

   1:  UPDATE Locations SET XAxis = dbo.XAxis(@lat, @long)

you could also do this in a trigger (as i was using), but it was pointed out to me (thanks bert) that using an AFTER UPDATE trigger might send this in an infinite loop as my trigger was performing an update statement itself.  stored proc is the way to go if you can.  i’ve included the INSERT trigger in the files just for your perusal though.

okay, with that done, you should have a sequence of when an address is entered (again possibly adding the intermediary step of geocoding for the user) you now have all the information you need.  now when your user needs to perform a “find near me” query the process is simple.

first, you’ll need to geocode their asking point.  again, this is simple and can be accomplished by various geocoding apis.  once you have the lat/long of the asking point, you can feed them to the stored proc that will use your previous proximity information and find the ones nearest you.  here’s the stored proc:

   1:  CREATE PROCEDURE [dbo].[FindNearby]
   2:     @CenterLat float, 
   3:     @CenterLon float, 
   4:     @SearchDistance float, 
   5:     @EarthRadius float
   6:  AS
   7:  declare @CntXAxis float
   8:  declare @CntYAxis float
   9:  declare @CntZAxis float
  10:   
  11:  set @CntXAxis = cos(radians(@CenterLat)) * cos(radians(@CenterLon))
  12:  set @CntYAxis = cos(radians(@CenterLat)) * sin(radians(@CenterLon))
  13:  set @CntZAxis = sin(radians(@CenterLat))
  14:   
  15:  select *,  ProxDistance = @EarthRadius * acos( XAxis*@CntXAxis + 
  16:    YAxis*@CntYAxis + ZAxis*@CntZAxis)
  17:  from  Locations
  18:  where  (@EarthRadius * acos( XAxis*@CntXAxis + YAxis*@CntYAxis + 
  19:    ZAxis*@CntZAxis) <= @SearchDistance) AND latitude is not null
  20:  order by ProxDistance ASC

you’ll notice the parameters of radius and earth radius.  since i’m using miles, i use the earth radius of 3961 miles.  you can search on live.com and other places for another number, but this seemed to be a general consensus of the radius of the earth in miles.  i put this in my configuration file in case i needed to change it.  no, not in case the earth changed, but in case it needed to be kilometers.  the SearchDistance param needs to be in the same unit of measurement as the earth radius.  feed those and your lat/long in and you get those near the point — as well as the approximate distance in the same unit of measure.  boom, you are done.  do with the data as you wish.

 

Methods for a location proximity search using GPS (WGS-84) mathematics in ASP.NET

This provides a fast Zip code proximity search and forgoes the massive FLOPS required by numerical methods. I would not call it a true distance search since it is an analytical approximation of our non-analytical reality, but it is much better than most of the code you find online that assumes the Earth is a perfect sphere.

This can be very handy for clients who want to get a general idea of how close the business entities are to each other, but don’t want to break the bank by paying $8k per year for the MapPoint API, or simply do not need that level of detail or precision.

Zip code data in the US can be bought for $40 a year. Do not trust the latitudes and longitudes that are used by the UN for their LOCODE system, they are highly inaccurate. If you need international location data, you will have to find another source.

Also remember that the centroid latitude and longitudes for Zip codes may fall out of the physical Zip code area, depending on its geometry. As you implement this, keep in mind that its primary purpose is for a fast proximity search, and is based on the foundation of the analytical model behind a GPS interpreter. If you need a true GPS level of precision in your application, I recommend looking at this Code Project article, which uses an existing GPS interpreter for commercial purposes.
Theory

The earth is an oblate spheroid because of the flattening that results from its rotation, as I have depicted using MATLAB. The image is hollowed out so that you can clearly see the difference between this and the spherical model that is used in code online everywhere:

A big problem with many of the searches that you will find online is that this assumption induces great error. You can imagine superimposing a sphere on the image above, and then taking a plane normal to the point of interest. First of all, your ‘surface’ of the Earth is already greatly exaggerated with a spherical model. Then when you take a normal surface (as many code examples online do, to calculate max and min latitude and longitude), those points on the normal surface are even further exaggerated.

By using the mathematics approved in WGS-84, and used in GPS, we can get a much better approximation. The height above sea level (altitude) is not considered here, because I assume that you do not have topographical data. This is a source of error in the Ellipsoid analytical model, but it also exists in the common spherical model to further exaggerate its mathematical flaws.

The mathematical error of this WGS-84 Ellipsoid model is depicted below:

Remember that the distance is a bird’s-eye view in all cases, so you will want to specify that in your search results so that the users don�t confuse this proximity figure with the road/travel distance.

You can obtain postal code latitude/longitude data for $40 a year now, and without paying for a more sophisticated service which maintains road distances, addresses, and altitude data, this is an accurate proximity search that far outperforms the typical ‘perfect sphere’ model without making your processor cry. Please download the single source code class for all of the gory details. I will only illustrate the concepts in this article.
Extension

Large search radius- If you ever need to search more than 1/4th of the globe, I would recommend breaking this algorithm into pieces instead of throwing an exception. You could handle the search area in a piecewise fashion, with the same analytics here and combine the results upon completion. You would need to determine an optimal frequency for which to create new radii of curvature (then use the local ellipse defined by those radii). With an approach like that, you could break down the curvilinear plane into well defined pieces, without going for a full-blown differential numerical approximation, which would be much more FLOPSy. My guess is that such an extension is purely academic. If you have a requirement for your system to search more than 1/4th of the globe, it’s probably a system that requires an unsurpassed level of precision anyway, and it’s probably for a client who has $8k per year to blow on the MapPoint API, or some other enterprise solution. Still…as we all know, who can predict what the clients will ask for next? 🙂 So I thought it was prudent to leave you a breadcrumb trail for this issue. Make sure if you go this route that you accurately model the error and educate your client on it, if you do need to make your way back home from this gingerbread house.

Access to altitude data- If you have altitude data these closed form equations could be modified for better accuracy. You can refer to the WGS-84 manual [927 Kb] to derive your equations. Look at the section on coordinate systems and Geodesy in the appendix.
Data

I’m assuming that you will write the scripting for your own data architecture, so I have replaced my sproc calls and data layer calls. You may also want to find a class online that converts a DataView to a DataTable for sorting purposes. There’s a very popular function online for C#, which is easy to find.
The code

The methods are very straightforward. They are well commented, so I will not delve into much detail here. You will have to obtain your own data. The UN maintains ‘LOCODE’ data that is handy for international business. You will see in the location object some properties that I am taking straight from that data. I recommend using the following tables in your architecture:

* Regions
* Countries
* Subdivisions (International term for States, Provinces, Cantons, etc.)
* Currencies
* Location Entry Criteria
* Counties
* Location (City/Town names and features, optional County FK)
* Postal Codes (with centroid latitude, longitude, LocationID FK)

All of my code of interest is in the Location object which gives me everything I want to know about a place or area on the globe.
Collapse

#region Declarations
private int regionID;
private string regionName;
private int countryID;
private string countryCode;
private string countryName;
private int primaryCurrencyID;
private string primaryCurrencyCode;
private string primaryCurrencyName;
private int secondaryCurrencyID;
private string secondaryCurrencyCode;
private string secondaryCurrencyName;
private int subdivisionID;
private string subdivisionCode;
private string subdivisionName;
private string subdivisionType;
private int countyID;
private string countyName;
private int locationID;
private string cityName;
private bool hasPort;
private bool hasRailTerminal;
private bool hasRoadTerminal;
private bool hasAirport;
private bool hasBorderCrossing;
private bool hasPostalExchangeOffice;
private string postalCode;
private double longitude;
private double latitude;
private string address;
private string addressee;
//private string language;

//private string productName;

#endregion

You can also create a collection of these objects, because I use CollectionBase:
Collapse

#region Collections
///

/// Collection of Location objects

///

public Location this[int i]
{
get {return (Location)List[i];}
set {List[i] = value;}
}

///

/// Adds a Location object to the collection

///

///
Completed Location object

public void AddLocation(Location L)
{
List.Add(L);
}

///

/// Removes a Location object from the collection

///

///
Completed Location object

public void RemoveLocation(Location L)
{
List.Remove(L);
}
#endregion

Constants that are used in the formulas:
Collapse

#region Constants
//Equatorial radius of the earth from WGS 84

//in meters, semi major axis = a

internal int a = 6378137;
//flattening = 1/298.257223563 = 0.0033528106647474805

//first eccentricity squared = e = (2-flattening)*flattening

internal double e = 0.0066943799901413165;
//Miles to Meters conversion factor (take inverse for opposite)

internal double milesToMeters = 1609.347;
//Degrees to Radians converstion factor (take inverse for opposite)

internal double degreesToRadians = Math.PI/180;
#endregion

Now you can use the search postal code to return the latitude and longitude that is the centroid of your search ellipse. The radii of curvature functions determine your reference ellipsoid for the latitude of the search. An exception is thrown if the accuracy is severely compromised by the search parameters.

Function: public DataTable FindNearbyLocations(string centroidPostalCode, double searchRadius, bool isMetric).
Collapse

//lat naught and lon naught are the geodetic parameters in radians

double lat0 =
Convert.ToDouble(centroidDT.Rows[0][“Latitude”])*degreesToRadians;
double lon0 =
Convert.ToDouble(centroidDT.Rows[0][“Longitude”])*degreesToRadians;

//Find reference ellipsoid radii

double Rm = calcMeridionalRadiusOfCurvature(lat0);
double Rpv = calcRoCinPrimeVertical(lat0);

//Throw exception if search radius is greater than 1/4 of globe and

//thus breaks accuracy of model (mostly pertinent for russia, alaska,

//canada, peru, etc.)

if (Rpv*Math.Cos(lat0)*Math.PI/2 < searchRadius) { throw new ApplicationException(“Search radius was too great to ” + “achieve an accurate result with this model.”); } //Find boundaries for curvilinear plane that encloses search ellipse double latMax = (searchRadius/Rm+lat0)/degreesToRadians; double lonMax = (searchRadius/(Rpv*Math.Cos(lat0))+lon0)/degreesToRadians; double latMin = (lat0-searchRadius/Rm)/degreesToRadians; double lonMin = (lon0-searchRadius/(Rpv*Math.Cos(lat0)))/degreesToRadians; //Return postal codes in curvilinear plane SqlParameter one2 = new SqlParameter(“@latMin”,System.Data.SqlDbType.Decimal, 9, ParameterDirection.Input, false, ((System.Byte)(18)), ((System.Byte)(5)), “”, System.Data.DataRowVersion.Current, latMin); SqlParameter two2 = new SqlParameter(“@latMax”,System.Data.SqlDbType.Decimal, 9, ParameterDirection.Input, false, ((System.Byte)(18)), ((System.Byte)(5)), “”, System.Data.DataRowVersion.Current, latMax); SqlParameter three2 = new SqlParameter(“@lonMin”,System.Data.SqlDbType.Decimal, 9, ParameterDirection.Input, false, ((System.Byte)(18)), ((System.Byte)(5)), “”, System.Data.DataRowVersion.Current, lonMin); SqlParameter four2 = new SqlParameter(“@lonMax”,System.Data.SqlDbType.Decimal, 9, ParameterDirection.Input, false, ((System.Byte)(18)), ((System.Byte)(5)), “”, System.Data.DataRowVersion.Current, lonMax); object[] Param2 = new object[4]{one2,two2,three2,four2}; DataTable resultPostalCodesDT = new DataTable(“ResultPostalCodes”); resultPostalCodesDT = helper.ReadOnlySproc(helper.YOUR_CONNECTION, “dbo.[YOUR_SPROC]”,Param2); resultPostalCodesDT.Columns.Add(“DistanceToCentroid”, System.Type.GetType(“System.Double”)); //Now calc distances from centroid, and remove results that were returned //in the curvilinear plane, but are outside of the ellipsoid geodetic if (resultPostalCodesDT.Rows.Count > 0)
{
for (int i=0;i
searchRadius)
{
resultPostalCodesDT.Rows.RemoveAt(i);
i–;
}
}
if (isMetric == false)
{
foreach(DataRow r in resultPostalCodesDT.Rows)
{
r[“DistanceToCentroid”] =
Convert.ToDouble(r[“DistanceToCentroid”])/milesToMeters;
}
}
resultPostalCodesDT.DefaultView.Sort = “DistanceToCentroid”;
DataTable finalResults = new DataTable(“finalResults”);
finalResults = YOUR_CUSTOM_UTILITY_CLASS.ConvertDataViewToDataTable(
resultPostalCodesDT.DefaultView);
return finalResults;
}
else
{
return null;
}

Here are the functions for your information that involve the radii of curvature and distance calculations:
Collapse

///

/// Calculates the Radius of curvature in the

/// prime vertical for the reference ellipsoid

///

///

/// This is the vector that defines the normal surface

/// to any point on the ellipsoid. It extends from

/// from the polar axis to that point. It is used for the

/// longitude, in differentiation of east distances, dE

///

///
Geodetic latitude in radians

/// Length of radius of curvature in the

/// prime vertical

public double calcRoCinPrimeVertical(double lat0)
{
double Rn = a/Math.Sqrt(1-e*Math.Pow(Math.Sin(lat0),2));
return Rn;
}

///

/// Calculates the meridional radius of

/// curvature for the reference ellipsoid

///

///

/// This is the radius of a circle that fits the earth

/// curvature in the meridian at the latitude chosen.

/// It is used for latitude, in differentiation of

/// north distances, dN

///

///
Geodetic latitude in radians

/// Length of meridional radius of

/// curvature

public double calcMeridionalRadiusOfCurvature(double lat0)
{
double Rm =
a*(1-e)/Math.Pow(1-e*(Math.Pow(Math.Sin(lat0),2)),1.5);
return Rm;
}

///

/// Calculates the true birds-eye view length of the arc

/// between two positions on the globe using parameters from WGS 84,

/// used in aviation and GPS.

///

///

/// An accurate BIRDS EYE numerical approximation with error

/// approaching less than 10 feet at a 50 miles search radius

/// and only 60 ft at 400 mile search radius. Error is on the

/// order of (searchRadius/equatorialRadius)^2.

/// Only accurate for distances

/// less than 1/4 of the globe (~10,000 km at the equator,

/// and approaching 0 km at the poles).

/// Geoid height above sea level is assumed to be zero, which is

/// the only deviation from GPS, and another source of error.

///

///
Meridional Radius of Curvature

/// at the centroid latitude

///
Radius of Curvature in the Prime

/// Vertical at the centroid latitude

///
Centroid latitude

///
Centroid longitude

///
Destination latitude

///
Destination longitude

/// Distance in meters from the arc between

/// the two points on the globe

public double calcDistanceLatLons(double Rm, double Rpv, double lat0,
double lon0, double lat, double lon)
{
double distance = Math.Sqrt(Math.Pow(Rm,2)*Math.Pow(lat-lat0,2)+
Math.Pow(Rpv,2)*Math.Pow(Math.Cos(lat0),2)*Math.Pow(lon-lon0,2));
return distance;
}

 

Generate random 5 digit number using asp.net

public string GetRandomString(int seed)
    {
        //use the following string to control your set of alphabetic characters to choose from
        //for example, you could include uppercase too
        const string alphabet = "abcdefghijklmnopqrstuvwxyz";

        // Random is not truly random,
        // so we try to encourage better randomness by always changing the seed value
        Random rnd = new Random((seed + DateTime.Now.Millisecond));

        // basic 5 digit random number
        string result = rnd.Next(10000, 99999).ToString();

        // single random character in ascii range a-z
        string alphaChar = alphabet.Substring(rnd.Next(0, alphabet.Length-1),1);

        // random position to put the alpha character
        int replacementIndex = rnd.Next(0, (result.Length - 1));
        result = result.Remove(replacementIndex, 1).Insert(replacementIndex, alphaChar);

        return result;
    }

 

Extend session using javascript in c#

protected void Page_Load(object sender, EventArgs e)
{

int SessionTimeout = Session.Timeout;

StringBuilder d = new StringBuilder();
d.Append(“<script>\n”);
d.Append(“function BeforeTimeout()\n{\n”);
d.Append(“setTimeout(‘CheckSession()’,60000*” + Convert.ToString(SessionTimeout – 1) + “)\n}\n”);
d.Append(“\n”);
d.Append(“function CheckSession()\n{\n”);
d.Append(“var flag=confirm(‘Your session is about to expire. Do you want to extent it?’)\n”);
d.Append(“if (flag)\n{\n”);
d.Append(“window.location.href='” + Page.Request.Url + “‘\n}\n}\n”);
d.Append(“window.onload=BeforeTimeout \n”);
d.Append(“</script>\n”);

Header.InnerHtml = d.ToString();
//}
}

Search

 

Import Excel Data Into An ASP.NET GridView using OLEDB

using System.Data.OleDb;
using System.Data;

public partial class UploadD : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
string cnstr = “Provider=Microsoft.Jet.Oledb.4.0;Data Source=C:\a.xls;”
+ “Extended Properties=Excel 8.0”;
OleDbConnection oledbConn = new OleDbConnection(cnstr);
string strSQL = “SELECT * FROM [Sheet$]”;

OleDbCommand cmd = new OleDbCommand(strSQL, oledbConn);
DataSet ds = new DataSet();
OleDbDataAdapter da = new OleDbDataAdapter(cmd);
da.Fill(ds);
GridView1.DataSource = ds;
GridView1.DataBind();
}
}

 

Generate thumbnail using dotnet

using System.Drawing;

using System.Drawing.Design;

Use the following code to create High Quality Thumbnail/Resize the image.

string originalFilePath = "C:\\originalimage.jpg"; //Replace with your image path

string thumbnailFilePath = string.Empty;

Size newSize = new Size(120,90); // Thumbnail size (width = 120) (height = 90)

using (Bitmap bmp = new Bitmap(originalFilePath))

{

    thumbnailFilePath = "C:\\thumbnail.jpg"; //Change the thumbnail path if you want

    using (Bitmap thumb = new Bitmap((System.Drawing.Image)bmp, newSize))

    {

        using (Graphics g = Graphics.FromImage(thumb)) // Create Graphics object from original Image

        {

            g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;

            g.InterpolationMode = System.Drawing.Drawing2D.InterpolationMode.High;

            g.CompositingQuality = System.Drawing.Drawing2D.CompositingQuality.HighQuality;

            //Set Image codec of JPEG type, the index of JPEG codec is "1"

            System.Drawing.Imaging.ImageCodecInfo codec = System.Drawing.Imaging.ImageCodecInfo.GetImageEncoders()[1];

            //Set the parameters for defining the quality of the thumbnail... here it is set to 100%

            System.Drawing.Imaging.EncoderParameters eParams = new System.Drawing.Imaging.EncoderParameters(1);

            eParams.Param[0] = new System.Drawing.Imaging.EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 100L);

            //Now draw the image on the instance of thumbnail Bitmap object

            g.DrawImage(bmp, new Rectangle(0, 0, thumb.Width, thumb.Height));

            thumb.Save(thumbnailFilePath, codec, eParams);

        }

    }

}