Results 1 to 13 of 13
  1. #1
    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. #2
    Join Date
    Nov 2004
    Location
    on the wrong server
    Posts
    8,835
    Provided Answers: 6
    Is your latitude and longitude kept in a table? Are there other fields in the table?
    What are they?
    “If one brings so much courage to this world the world has to kill them or break them, so of course it kills them. The world breaks every one and afterward many are strong at the broken places. But those that will not break it kills. It kills the very good and the very gentle and the very brave impartially. If you are none of these you can be sure it will kill you too but there will be no special hurry.” Earnest Hemingway, A Farewell To Arms.

  3. #3
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    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. #4
    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. #5
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    Convex AND concave?
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  6. #6
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  7. #7
    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.
    I love deadlines. I like the whooshing sound they make as they fly by. Douglas Adams

  8. #8
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    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. #9
    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.
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  10. #10
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  11. #11
    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?
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  12. #12
    Join Date
    Jan 2005
    Location
    TempDb
    Posts
    228
    Sure rdjabarov, let's see an example.
    I love deadlines. I like the whooshing sound they make as they fly by. Douglas Adams

  13. #13
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    An interesting challenge, but not much point to it unless Namita posts back to say whether its possible to change the way the data is stored. Like I said, I have an algorithm for finding points in a triangle, but unless the polygons can be restructured as collections of triangles, there is not much point in writing it up.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •