MySQL-реализация алгоритма лучевого каста?

Ответ 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

Надеюсь, это может помочь кому-то.

Ответ 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

Учебник UDF для MS Visual С++
http://rpbouman.blogspot.com/2007/09/creating-mysql-udfs-with-microsoft.html

Учебник UDF в Delphi:
Создание UDF для MySQL в Delphi

Исходный код относительно алгоритма лучевого каста
Псевдокод: http://rosettacode.org/wiki/Ray-casting_algorithm
Статья в drDobbs (обратите внимание на ссылку на код в верхней части статьи): http://drdobbs.com/cpp/184409586
Delphi (фактически FreePascal): http://www.cabiatl.com/mricro/raycast/

Ответ 3

На всякий случай одна функция MySQL, которая принимает MULTIPOLYGON как вход: 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

Ответ 4

Я хотел использовать приведенную выше хранимую процедуру mywithin в таблице полигонов, так что вот команды, которые нужно сделать именно это.

После импорта шейп файла, содержащего полигоны в mysql, используя ogr2ogr следующим образом

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

вы можете использовать MBRwithin для предварительной фильтрации вашей таблицы и mywithin, чтобы закончить следующим образом

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);

где @testpoint создается, например, из

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

Ответ 5

Теперь это Пространственное расширение как MySQL5.6.1 и выше. См. function_st-contains в Docs.

Ответ 6

В ответ на функцию zarun для нахождения lat/long внутри многоугольника.

У меня была таблица свойств с информацией lat/long. Поэтому мне пришлось получить записи, чей lat/long лежит в многоугольных латах /longs (которые я получил от Google API). Сначала я был немым, как использовать функцию Заруна. Итак, вот запрос решения для него.

• Таблица: свойства
• Поля: id, широта, долгота, кровати и т.д.
• Query:

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;

Надеюсь, это сэкономит время для таких глупцов, как я;)

Ответ 7

Вот версия, которая работает с MULTIPOLYGONS (адаптация Zarun, которая работает только для 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;