MySQL实现光线投射算法？

Question

我们需要找到一种快速且相当准确的方法,用于谷地图上的纬度/长值和多边形的多边形点.经过一些研究 - 发现了一些关于mysql几何扩展的帖子,并且也实现了 -

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

然而,这并不适用于由大量点组成的多边形:(

在进行了一些更多的研究之后 - 遇到了一种称为Ray-casting算法的标准算法,但是在尝试在MySQL中开发查询之前,想要抓住机会,如果有人已经通过这个或者遇到了一个显示如何实现的有用链接MySQL/SQL-server中的算法.

因此,缩短它 - 问题是:

任何人都可以提供Ray/Cast-algorithm的MySQL/SQL-server实现吗？

其他细节:

• 多边形是凹面,凸面或复杂的.
• 定位快速执行超过100%的准确性.

Answer 1

以下功能(MYSQL版本的Raycasting算法)震撼了我的世界:

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; 

加

  DELIMITER ;; 

在功能之前根据需要.该功能的用途是:

 SELECT myWithin(point, polygon) as result;

哪里

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

请注意,多边形应该是关闭的(如果您正在检索标准kml或googlemap数据,但通常会关闭它,但确保它是 - 请注意lat1 lng1 set在最后重复)

我的数据库中没有点和多边形作为几何字段,因此我必须执行以下操作:

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

我希望这可以帮助某人.

Answer 2

我会编写一个自定义UDF,用C或Delphi或您使用的任何高级工具实现光线投射算法:

编写UDF的链接
这是一个查找球体的MySQL gis实现的源代码(使用它作为模板来查看如何与MySQL中的空间数据类型进行交互).
http://www.lenzg.net/archives/220-New-UDF-for-MySQL-5.1-provides-GIS-functions-distance_sphere-and-distance_spheroid.html

从MySQL手册:http:
//dev.mysql.com/doc/refman/5.0/en/adding-functions.html

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

Delphi中的UDF教程:在Delphi中
为MySQL创建UDF

有关光线投射算法的源代码
伪代码:http:
//rosettacode.org/wiki/Ray-casting_algorithm drDobbs中的文章(请注意文章顶部代码的链接):http://drdobbs.com / cpp/184409586
Delphi(实际上是FreePascal):http://www.cabiatl.com/mricro/raycast/