光线投射算法的MySQL实现？

Question

我们需要找出一个快速和相当准确的方法点在多边形上的lat/长值和多边形的谷歌地图。经过一些研究

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

然而，这并不适用于由大量点组成的多边形：

经过更多的研究，我们发现了一种名为射线投射算法的标准算法，但在尝试在MySQL中开发该算法的查询之前，如果有人已经经历过这种情况，或者遇到了一个有用的链接，说明了如何在MySQL /server中实现该算法，那么我想抓住这个机会。

所以，简单地说，问题是：

谁能提供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集在末尾重复)

我的数据库中没有点和多边形作为几何字段，所以我不得不这样做：

 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中的空间数据类型交互)。

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

关于光线投射算法的源代码

伪码：算法

drDobbs中的文章(请注意文章顶部的代码链接)：http://drdobbs.com/cpp/184409586

德尔菲(实际上是FreePascal)：http://www.cabiatl.com/mricro/raycast/

Answer 3

以防万一，一个接受多个MySQL输入的http://forums.mysql.com/read.php?23,286574,286574函数：http://forums.mysql.com/read.php?23,286574,286574

DELIMITER $$

CREATE DEFINER=`root`@`localhost` FUNCTION `GISWithin`(pt POINT, mp MULTIPOLYGON) RETURNS int(1)
    DETERMINISTIC
BEGIN 

DECLARE str, xy TEXT; 
DECLARE x, y, p1x, p1y, p2x, p2y, m, xinters DECIMAL(16, 13) DEFAULT 0; 
DECLARE counter INT DEFAULT 0; 
DECLARE p, pb, pe INT DEFAULT 0; 

SELECT MBRWithin(pt, mp) INTO p; 

IF p != 1 OR ISNULL(p) THEN 
    RETURN p; 
END IF; 

SELECT X(pt), Y(pt), ASTEXT(mp) INTO x, y, str; 
SET str = REPLACE(str, 'POLYGON((',''); 
SET str = REPLACE(str, '))', ''); 
SET str = CONCAT(str, ','); 

SET pb = 1; 
SET pe = LOCATE(',', str); 
SET xy = SUBSTRING(str, pb, pe - pb); 
SET p = INSTR(xy, ' '); 
SET p1x = SUBSTRING(xy, 1, p - 1); 
SET p1y = SUBSTRING(xy, p + 1); 
SET str = CONCAT(str, xy, ','); 

WHILE pe > 0 DO 
    SET xy = SUBSTRING(str, pb, pe - pb); 
    SET p = INSTR(xy, ' '); 
    SET p2x = SUBSTRING(xy, 1, p - 1); 
    SET p2y = SUBSTRING(xy, p + 1); 

    IF p1y < p2y THEN SET m = p1y; ELSE SET m = p2y; END IF; 

    IF y > m THEN 
        IF p1y > p2y THEN SET m = p1y; ELSE SET m = p2y; END IF; 
        IF y <= m THEN 
            IF p1x > p2x THEN SET m = p1x; ELSE SET m = p2x; END IF; 
            IF x <= m THEN 
                IF p1y != p2y THEN 
                    SET xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x; 
                END IF; 
                IF p1x = p2x OR x <= xinters THEN 
                    SET counter = counter + 1; 
                END IF; 
            END IF; 
        END IF; 
    END IF; 

    SET p1x = p2x; 
    SET p1y = p2y; 
    SET pb = pe + 1; 
    SET pe = LOCATE(',', str, pb); 
END WHILE; 

RETURN counter % 2; 

END