GIS find Points (long lats) that are contained by a polygon expressed as a collection of long lats

Question

I'm trying to find all data items that have long/lats that are contained by a polygon made up of an array of long lats could be many points. I know you can do this kind of stuff with the new geospacial datatypes in SQL 2008 but i'm using SQL 2005 and C#. Would this be best done on at the DB end or in C#.

Thanks.

Answer 1

It sounds like something which gives a headache if done in T-SQL (Which is more or less everything though?). Of course it depends on the complexity of the polygons and the way the data items are located but in general the easiest and a moderately efficient approach might be to do some initial calculations in C# which limits the data items in a very rough way. So something like the following.

1. Calculate the rough boundaries of the polygon in C#.
2. Get everything inside these boundaries from the SQL server.
3. Do the final accurate filtering in C#.

The performance of course depends on how well you can calculate the initial boundaries. I'd start with just a simple bounding rectangle first and see if the performance is sufficient.

Answer 2

I have some code written for SQL2000 to do this. It uses the 'angle' method for determining if a point lies within a polygon.

First, the GetAngle user defined function:

ALTER Function [dbo].[GetAngle](
@Ax Decimal(8,5), 
@Ay Decimal(8,5), 
@Bx Decimal(8,5), 
@By Decimal(8,5), 
@Cx Decimal(8,5), 
@Cy Decimal(8,5))

Returns Float As Begin

Declare @dot_product Float
Declare @cross_product Float

Declare @BAx Decimal(8,5)
Declare @BAy Decimal(8,5)
Declare @BCx Decimal(8,5)
Declare @BCy Decimal(8,5)

--' Get the vectors' coordinates.
Set @BAx = Sign(@Ax - @Bx) * dbo.CalculateDistance(@Ax, @Ay, @Bx, @Ay)
Set @BAy = Sign(@Ay - @By) * dbo.CalculateDistance(@Ax, @Ay, @Ax, @By)
Set @BCx = Sign(@Cx - @Bx) * dbo.CalculateDistance(@Cx, @Cy, @Bx, @Cy)
Set @BCy = Sign(@Cy - @By) * dbo.CalculateDistance(@Cx, @Cy, @Cx, @By)

--' Calculate the dot product.
Set @dot_product = @BAx * @BCx + @BAy * @BCy

--' Calculate the Z coordinate of the cross product.
Set @cross_product = @BAx * @BCy - @BAy * @BCx

--' Calculate the angle.
return ATn2(@cross_product, @dot_product)

End

---

Next I assume there is a table variable of Latitude/Longitude pairs and a sequence number (indicating the order in which the LAT/LONG pairs define the polygon). It's important that the first point in this table is the same as the last point in the table.

Also, I have several variables for Min and Max Latitude & Longitude. This effectively creates a bounding box so that I can quickly eliminate points NOT within a rectangular region bounding the polygon.

Select  Address.AddressId
From    @Temp As A
     Inner Join @Temp As B
      On A.SequenceNumber = B.SequenceNumber - 1
     Inner Join Address
      On Address.XCoord Between @MinLongitude And @MaxLongitude
      And Address.YCoord Between @MinLatitude And @MaxLatitude
Group By Address.AddressId
Having Abs(Sum(dbo.GetAngle(A.Longitude, A.Latitude, Address.XCoord, Address.YCoord, B.Longitude, B.Latitude))) > 3.14