# Thread: SQL query: Select all the points within a Closed polygon

1. Registered User
Join Date
Apr 2003
Posts
43

## Unanswered: SQL query: Select all the points within a Closed polygon

HI:

Is there any algorithim, which can help me write a script or SQL that will select all the points within a Closed Polygon.

This polygon and point data have latitude and longitude information

Help will be appreciated.

Thanks
Namita

2. Annie's Dog Walker
Join Date
Nov 2004
Location
on the wrong server
Posts
8,842
Is your latitude and longitude kept in a table? Are there other fields in the table?
What are they?

3. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
Because the math behind spherical topography is significantly different from plane topography, the problem is quite different, especially for arbitrary polygons. I think that I'd have to do a Mercator projection for the polygon, then test the individual projections of the points against that.

-PatP

4. Registered User
Join Date
Apr 2003
Posts
43
the polygon only has the latitude and longitude where as the point data has latitude, longitude as well as RF data.

5. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
Convex AND concave?

6. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
You are going to need more information to define your polygon than just latitude and longitude, anyway. For instance, these seven points:

Code:
```    .   .

.   .   .

.   .```
...can form six different polygons, each being a hexagon with one missing triangle. Without knowing how the points are related their is no way to tell which piece is missing, and thus whether any point is inside the polygon or outside of it.

7. Registered User
Join Date
Jan 2005
Location
TempDb
Posts
228
This is intriguing. For two dimensional (and possibly three, i can't think beyond there dimensions) can that be accomplished with a starting point and then a rule that determines each subsequent point?

For example, using your succinct example, if the starting point is always the smallest x value, and the rule is move right (increasing x values) by choosing the next highest x where x >= x0, ordered by x ASC, y ASC; then move left (decreasing x values) by choosing the lowest x where x < Max(point reached) and y < Min(point reached) ordered by x DESC, y DESC would yield:
Code:
```   .   .
/ \ / \
.   .   .
\     /
. --.```
Code:
```Set NoCount On

Declare @points Table(y int, x int)
Declare @results Table(monotonicallyIncreasingValue int identity (1,1), x int, y int)
Declare @x0 int, @y0 int, @xMax int, @yMin int

Select @x0 = -2, @y0 = 0
Insert @points (x, y)
Select -2, 0
Union
Select -1, 1
Union
Select -1, -1
Union
Select 0, 0
Union
Select 1, 1
Union
Select 1, -1
Union
Select 2, 0

Select @xMax = Max(x), @yMin = Min(y)
From @points
Where y >= @y0 and x >= @x0

Insert @results (x,y)
Select x, y
From @points
Where y >= @y0 and x >= @x0
Order By x, y

Insert @results (x,y)
Select x, y
From @points
Where (y < @yMin And x < @xMax) Or (x = @x0 And y = @y0)
Order By x desc, y desc

Select @x0 As '@x0', @y0 As '@y0', @xMax As '@xMax', @yMin as '@yMin'

Select x, y
From @results
Order By monotonicallyIncreasingValue```
Last edited by MaxA; 02-20-05 at 14:22.

8. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
It gets lots better when you have to think about "is the polygon near the equator, or near the pole?" It gets better, because if the polygon is near the pole, which edge is near the pole, or more accurately which point on the polygon is nearest the pole?

If you think about how a traditional "orange peel" Mercator projection works, it effectively "spreads" the spherical topography onto a planar surface with portions of the surface itself missing. This is forced because there are more sample spaces near the equator than there are near the poles. When you consider how the modern "exploded" projection works, it maps equal areas evenly, which distorts the original image.

Spherical topography is relatively easy to visuallize, but at least in my opinion it is horrible to compute.

-PatP

9. Registered User
Join Date
Jul 2003
Location
San Antonio, TX
Posts
3,662
Hey Max, this is awesome, but in the database world, where the design preceeded programming, shouldn't each polygon be defined in a polygon_master, while the dimensions and point coordinates be transcribed in some sort of a polygon_details and linked back to polygon_master through a foreign key? This way you don't have to rely on a rule of starting x to be the smallest value for x, etc.

10. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
I think in order to accomplish this he will need to break each polygon up and store it as a collection of component triangles.

Finding an algorithm that will determine whether a point it in a triangle is not difficult, but I can't come up with a general solution for N sides.

11. Registered User
Join Date
Jul 2003
Location
San Antonio, TX
Posts
3,662
It's all in the structure, man, it's all in the structure. Think of it as how the teacher gave you the problem in the fifth grade for the first time...wait a minute...Fifth grade is NOT taking geometry in this country...Oh well, just think of, OK?

12. Registered User
Join Date
Jan 2005
Location
TempDb
Posts
228
Sure rdjabarov, let's see an example.

13. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595