Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Sql Server Programming

Some complex Transact-SQL


Hi!
I have a database containing polygons and coordinates
and need to determine which polygon contains
a given point:
CREATE TABLE polygons
(
    pol_id INT NOT NULL IDENTITY,
....
)
CREATE TABLE points
(
    pol_id INT NOT NULL, /* references above table */
    pnt_no TINYINT NOT NULL, /* 1...N - order no of vertices */
    pnt_x INT NOT NULL, /* x/y coordinates */
    pnt_y INT NOT NULL,
....
)

Currently, in my C# program, I'm retrieving _all_ polygons/coordinates
from the db and iterating record by record to perform check. I use this
algorithm to test:
 http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

And my question:
    Is there a way to implement this code (or any other) in T-SQL to get
only one matched record/polygon?

Hi

> And my question:
>    Is there a way to implement this code (or any other) in T-SQL to get
> only one matched record/polygon?

If I uderstood you
SELECT <columns> FROM polygons INNER JOIN points ON polygons. pol_id
=points.pol_id

"TumurS" <spam_tu@magicnet.mn> wrote in message

news:%23pYxOyLqHHA.2652@TK2MSFTNGP02.phx.gbl...

If I understand your requirements, something like this

DECLARE @x INT
DECLARE @y INT

SET @x=123
SET @y=456;

WITH PolyLines(pol_id,pnt_no,xs,ys,xe,ye) AS
(SELECT a.pol_id,
        a.pnt_no,
        a.pnt_x,
        a.pnt_y,
        b.pnt_x,
        b.pnt_y
 FROM points a
 INNER JOIN points b ON b.pol_id=a.pol_id AND b.pnt_no=a.pnt_no+1
 UNION ALL
 SELECT a.pol_id,
        a.pnt_no,
        a.pnt_x,
        a.pnt_y,
        b.pnt_x,
        b.pnt_y
 FROM points a
 INNER JOIN points b ON b.pol_id=a.pol_id AND b.pnt_no=1
 WHERE NOT EXISTS (SELECT * FROM points c WHERE c.pol_id=a.pol_id AND
c.pnt_no>a.pnt_no))
SELECT pol_id,
       @x AS X,
       @y AS Y
FROM PolyLines
WHERE ((ys<=@y AND @y<ye) OR (ye<=@y AND @y<ys))
  AND (@x < (xe - xs) * (@y - ys) / (ye - ys) + xs)
GROUP BY pol_id
HAVING COUNT(*)%2=1

-----------------------------------------------Reply-----------------------------------------------

>> Is there a way to implement this code (or any other) in T-SQL to get only one matched record/polygon? <<

Google up Steve Kass, me and polygons in the newsgroups.  We did this
years ago.  Here is a clip from SQL FOR SMARTIES, but I recall that
Steve had a better answer since his worked for concave polygons.

30.04. Points inside Polygons

While not actually part of graph theory, this seemed to be the
reasonable place to put this section since it is also related to
spatial queries.  A polygon can be describes as a set of corner point
in an (x, y) co-ordinate system.  The usual query is to tell if a
given point is inside of outside of the polygon.

This algorithm is due to Darel R. Finley.  The main advantage it has
is that it can be done in Standard SQL without trigonometry
functions.  The disadvantage is that it does not work for concave
polygons. The work-around is to dissect the convex polygons into
concave polygons, then add column for the name of the original area.

-- set up polygon, with any ordering of the corners
CREATE TABLE Polygon
(x FLOAT NOT NULL,
 y FLOAT NOT NULL,
 PRIMARY KEY (x, y));

INSERT INTO Polygon
VALUES (2.00, 2.00),
       (1.00, 4.00),
       (3.00, 6.00),
       (6.00, 4.00),
       (5.00, 2.00);

--set up some sample points
CREATE TABLE Points
(xx FLOAT NOT NULL,
 yy FLOAT NOT NULL,
 location VARCHAR(10) NOT NULL,  -- answer the question in advance!
 PRIMARY KEY (xx, yy));
INSERT INTO Points
VALUES (2.00, 2.00, 'corner'),
       (1.00, 5.00, 'outside'),
       (3.00, 3.00, 'inside'),
       (3.00, 4.00, 'inside'),
       (5.00, 1.00, 'outside'),
       (3.00, 2.00, 'side');

-- do the query
SELECT P1.xx, P1.yy, p1.location, SIGN(
SUM
 (CASE WHEN (polyY.y < P1.yy AND polyY.x >= P1.yy
           OR polyY.x < P1.yy AND  polyY.y >= P1.yy)
       THEN CASE WHEN polyX.y + (P1.yy - polyY.y)
                     /(polyY.x - polyY.y) * (polyX.x - polyX.y) <
P1.xx
                 THEN 1 ELSE 0 END
       ELSE 0 END))AS flag
  FROM Polygon AS polyY, Polygon AS polyX, Points AS P1
GROUP BY P1.xx, P1.yy, p1.location;

When flag = 1, the point is inside, when flag = 0, it is outside.

 xx   yy  location  flag
 ========================
 1.0  5.0   outside  0
 2.0  2.0   corner   0
 3.0  3.0   inside   1
 3.0  4.0   inside   1
 5.0  1.0   outside  0
 3.0  2.0   side     1

Sides are counted as inside, but if you want to count the corner
points as inside, then start the CASE expression with:

CASE WHEN EXISTS
         (SELECT * FROM Polygon
           WHERE x = P1.xx AND y = P1.yy)
     THEN 1 ..".

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc