MySQL实现光线投射算法? [英] MySQL implementation of ray-casting Algorithm?
问题描述
我们需要为谷歌地图上的经/纬度值和多边形找到一种快速且相当准确的多边形点方法.经过研究-遇到了一些有关mysql几何扩展的帖子,并且也实现了-
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 :(
经过更多研究-遇到了一种称为Ray-casting算法的标准算法,但在尝试在MySQL中为该算法开发查询之前,想抓住我的机会,如果有人已经通过它或遇到了一个有用的链接,该链接显示了如何在MySQL/SQL-server中实现该算法.
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:
任何人都可以提供Ray强制转换算法的MySQL/SQL-server实现吗?
其他详细信息:
- 多边形可以是凹形,凸形或复杂形.
- 目标是执行速度超过100%的准确性.
推荐答案
以下功能(Raycasting算法的MYSQL版本)震撼了我的世界:
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;
添加
DELIMITER ;;
在需要该功能之前. 该函数的用法是:
before the function as required. The usage for the function is:
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)
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.
这篇关于MySQL实现光线投射算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!