MySQL implementation of ray-casting Algorithm?

Question

We need to figure out a quick and fairly accurate method for point-in-polygon for lat/long values and polygons over google maps. After some research - came across some posts about mysql geometric extensions, and did implement that too -

SELECT id, Contains( PolyFromText( 'POLYGON(".$polygonpath.")' ) , PointFromText( concat( \"POINT(\", latitude, \" \", longitude, \")\" ) ) ) AS
            CONTAINS
FROM tbl_points

That did not however work with polygons made up of a large number of points :(

After some more research - came across a standard algorithm called the Ray-casting algorithm but before trying developing a query for that in MySQL, wanted to take my chances if someone had already been through that or came across a useful link which shows how to implement the algorithm in MySQL / SQL-server.

So, cutting it short - question is:

Can anyone please provide the MySQL/SQL-server implementation of Ray casting algorithm?

Additional detail:

• Polygons are either of concave, convex or complex.
• Targeting quick execution over 100% accuracy.

Answer 1

The following function (MYSQL version of Raycasting algorithm) rocked my world :

CREATE FUNCTION myWithin(p POINT, poly POLYGON) RETURNS INT(1) DETERMINISTIC 
BEGIN 
DECLARE n INT DEFAULT 0; 
DECLARE pX DECIMAL(9,6); 
DECLARE pY DECIMAL(9,6); 
DECLARE ls LINESTRING; 
DECLARE poly1 POINT; 
DECLARE poly1X DECIMAL(9,6); 
DECLARE poly1Y DECIMAL(9,6); 
DECLARE poly2 POINT; 
DECLARE poly2X DECIMAL(9,6); 
DECLARE poly2Y DECIMAL(9,6); 
DECLARE i INT DEFAULT 0; 
DECLARE result INT(1) DEFAULT 0; 
SET pX = X(p); 
SET pY = Y(p); 
SET ls = ExteriorRing(poly); 
SET poly2 = EndPoint(ls); 
SET poly2X = X(poly2); 
SET poly2Y = Y(poly2); 
SET n = NumPoints(ls); 
WHILE i<n DO 
SET poly1 = PointN(ls, (i+1)); 
SET poly1X = X(poly1); 
SET poly1Y = Y(poly1); 
IF ( ( ( ( poly1X <= pX ) && ( pX < poly2X ) ) || ( ( poly2X <= pX ) && ( pX < poly1X ) ) ) && ( pY > ( poly2Y - poly1Y ) * ( pX - poly1X ) / ( poly2X - poly1X ) + poly1Y ) ) THEN 
SET result = !result; 
END IF; 
SET poly2X = poly1X; 
SET poly2Y = poly1Y; 
SET i = i + 1; 
END WHILE; 
RETURN result; 
End; 

Add

  DELIMITER ;; 

before the function as required. The usage for the function is:

 SELECT myWithin(point, polygon) as result;

where

 point  = Point(lat,lng) 
 polygon = Polygon(lat1 lng1, lat2 lng2, lat3 lng3, .... latn lngn, lat1 lng1)

Please note that the polygon ought to be closed (normally it is closed if you're retrieving a standard kml or googlemap data but just make sure it is - note lat1 lng1 set is repeated at the end)

I did not have points and polygons in my database as geometric fields, so I had to do something like:

 Select myWithin(PointFromText( concat( "POINT(", latitude, " ", longitude, ")" ) ),PolyFromText( 'POLYGON((lat1 lng1, ..... latn lngn, lat1 lng1))' ) ) as result

I hope this might help someone.

Answer 2

I would write a custom UDF that implements the ray-casting algorithm in C or Delphi or whatever high level tool you use:

Links for writing a UDF
Here's sourcecode for a MySQL gis implementation that looks up point on a sphere (use it as a template to see how to interact with the spatial datatypes in MySQL).
http://www.lenzg.net/archives/220-New-UDF-for-MySQL-5.1-provides-GIS-functions-distance_sphere-and-distance_spheroid.html

From the MySQL manual:
http://dev.mysql.com/doc/refman/5.0/en/adding-functions.html

UDF tutorial for MS Visual C++
http://rpbouman.blogspot.com/2007/09/creating-mysql-udfs-with-microsoft.html

UDF tutorial in Delphi:
Creating a UDF for MySQL in Delphi

Source-code regarding the ray-casting algorithm
Pseudo-code: http://rosettacode.org/wiki/Ray-casting_algorithm
Article in drDobbs (note the link to code at the top of the article): http://drdobbs.com/cpp/184409586
Delphi (actually FreePascal): http://www.cabiatl.com/mricro/raycast/