Implementación MySQL del algoritmo Ray-Casting?

Question

Tenemos que encontrar un método rápido y bastante preciso para punto-en-polígono para latitud y longitud de los valores y polígonos en los mapas de Google. Después de algunas investigaciones - se encontró con algunos mensajes sobre MySQL extensiones geométricas, y puso en práctica eso también -

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

Eso no obstante trabajar con polígonos formados por un gran número de puntos :(

Después de un poco más de investigación - encontré un algoritmo estándar llamado el algoritmo Ray-casting pero antes de intentar desarrollar una consulta para eso en MySQL, quería arriesgarme si alguien ya había pasado por eso o si encontraba un enlace útil que muestra cómo implementar el algoritmo en MySQL/SQL-server.

Así que, resumiendo, la pregunta es:

¿Alguien puede proporcionar la implementación de MySQL/servidor SQL del algoritmo de transmisión de rayos?

detalle adicional:

• Los polígonos son cualquiera de cóncava, convexa o compleja.
• Dirigiendo la ejecución rápida con más del 100% de precisión.

Answer 1

La siguiente función (versión de MySQL del algoritmo raycasting) sacudido mi mundo:

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; 

Añadir

DELIMITER ;; 

antes de la función según sea necesario. El uso de la función es:

SELECT myWithin(point, polygon) as result; 

donde

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

Tenga en cuenta que el polígono debe ser cerrado (normalmente se cierra si está recuperando un conjunto de datos KML o GoogleMap estándar, pero sólo asegúrese de que sea - en cuenta Lat1 conjunto lng1 se repite al final)

no tenía puntos y polígonos en mi base de datos como campos geométricas, por lo que tenía que hacer algo como:

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

Espero que esto pueda ayudar a alguien.

Answer 2

me gustaría escribir una UDF personalizado que implementa el algoritmo de rayos-bastidor en C o Delphi o cualquier herramienta de alto nivel que utilice:

Enlaces para escribir una UDF
Esto es código fuente de un SIG MySQL implementación que busca un punto en una esfera (úsela como plantilla para ver cómo interactuar con los tipos de datos espaciales en MySQL).
http://www.lenzg.net/archives/220-New-UDF-for-MySQL-5.1-provides-GIS-functions-distance_sphere-and-distance_spheroid.html

Desde el manual de MySQL:
http://dev.mysql.com/doc/refman/5.0/en/adding-functions.html

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

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

Fuente de código con respecto a la algoritmo de lanzamiento de rayos
pseudo-código: http://rosettacode.org/wiki/Ray-casting_algorithm
artículo en drDobbs (Nota: el vínculo con el código en la parte superior del artículo): http://drdobbs.com/cpp/184409586
Delphi (en realidad FreePascal): http://www.cabiatl.com/mricro/raycast/

Answer 3

Quería utilizar el procedimiento mywithin almacenado anteriormente en una tabla de polígonos, así que aquí están los comandos para hacer precisamente eso.

Después de importar un archivo de formas que contiene polígonos en MySQL utilizando ogr2ogr de la siguiente manera

ogr2ogr -f "mysql" MYSQL:"mydbname,host=localhost,user=root,password=mypassword,port=3306" -nln "mytablename" -a_srs "EPSG:4326" /path/to/shapefile.shp 

a continuación, puede utilizar MBRwithin pre-filtrar su mesa y mywithin para terminar la siguiente manera

DROP TEMPORARY TABLE IF EXISTS POSSIBLE_POLYS; 
CREATE TEMPORARY TABLE POSSIBLE_POLYS(OGR_FID INT,SHAPE POLYGON); 
INSERT INTO POSSIBLE_POLYS (OGR_FID, SHAPE) SELECT mytablename.OGR_FID,mytablename.SHAPE FROM mytablename WHERE MBRwithin(@testpoint,mytablename.SHAPE); 

DROP TEMPORARY TABLE IF EXISTS DEFINITE_POLY; 
CREATE TEMPORARY TABLE DEFINITE_POLY(OGR_FID INT,SHAPE POLYGON); 
INSERT INTO DEFINITE_POLY (OGR_FID, SHAPE) SELECT POSSIBLE_POLYS.OGR_FID,POSSIBLE_POLYS.SHAPE FROM POSSIBLE_POLYS WHERE mywithin(@testpoint,POSSIBLE_POLYS.SHAPE); 

donde se crea @testpoint , por ejemplo, desde

SET @longitude=120; 
SET @latitude=-30; 
SET @testpoint =(PointFromText(concat("POINT(", @longitude, " ", @latitude, ")"))); 

Answer 4

Por las dudas, una función MySQL que acepta MULTIPOLYGON como una entrada: 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 

Answer 5

Ahora es un extensión espacial como de MySQL5.6.1 y superior. Consulte function_st-contains en Docs.

Answer 6

En respuesta a la función de zarun para encontrar latitud/longitud dentro del polígono.

Tenía una tabla de propiedades con información de latitud/longitud. Así que tuve que obtener los registros cuyas lat/long se encuentra dentro de polígono lats/longs (que obtuve de Google API). Al principio, era tonto cómo usar la función Zarun. Así que aquí está la consulta de solución para ello.

• Tabla: propiedades
• campos: Identificación del, latitud, longitud, camas, etc ...
• Consulta:

SELECT id 
FROM properties 
WHERE myWithin(
    PointFromText(concat("POINT(", latitude, " ", longitude, ")")), 
    PolyFromText('POLYGON((37.628134 -77.458334,37.629867 -77.449021,37.62324 -77.445416,37.622424 -77.457819,37.628134 -77.458334))') 
) = 1 limit 0,50; 

Esperamos que se puede ahorrar tiempo para tontos como yo;)

Answer 7

Aquí hay una versión que funciona con MULTIPOLYGONS (una adaptación de Zarun que solo funciona para POLYGONS).

CREATE FUNCTION GISWithin(p POINT, multipoly MULTIPOLYGON) RETURNS INT(1) DETERMINISTIC 
BEGIN 
DECLARE n,i,m,x INT DEFAULT 0; 
DECLARE pX,pY,poly1X,poly1Y,poly2X,poly2Y DECIMAL(13,10); 
DECLARE ls LINESTRING; 
DECLARE poly MULTIPOLYGON; 
DECLARE poly1,poly2 POINT; 
DECLARE result INT(1) DEFAULT 0; 
SET pX = X(p); 
SET pY = Y(p); 
SET m = NumGeometries(multipoly); 
WHILE x<m DO 
SET poly = GeometryN(multipoly,x); 
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; 
SET x = x + 1; 
END WHILE; 
RETURN result; 
End;