MySQL реализация алгоритма литья лучей?

Нам нужно найти быстрый и довольно точный метод для точки-полигона для значений широты и долготы и полигонов на картах Google. После некоторого исследования - натолкнулся на несколько постов о геометрических расширениях mysql и реализовал это тоже -

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

Это, однако, не работает с полигонами, состоящими из большого количества точек:(

После еще нескольких исследований - натолкнулся на стандартный алгоритм, называемый алгоритмом преобразования лучей, но прежде чем пытаться разработать запрос для этого в MySQL, я хотел рискнуть, если кто-то уже прошел через это или наткнулся на полезную ссылку, которая показывает, как реализовать алгоритм в MySQL / SQL-сервере.

Итак, вкратце - вопрос таков:

Кто-нибудь может предоставить, пожалуйста, реализацию MySQL / SQL-сервера алгоритма приведения лучей?

Дополнительные детали:

  • Полигоны бывают вогнутыми, выпуклыми или сложными.
  • Ориентация на быстрое выполнение со 100% точностью.
Источник

7 ответов

Решение

Следующая функция (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

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

Источник

Я написал бы пользовательский UDF, который реализует алгоритм приведения лучей в C или Delphi или любой другой инструмент высокого уровня, который вы используете:

Ссылки для написания UDF
Вот исходный код для реализации MySQL ГИС, которая ищет точку на сфере (используйте его в качестве шаблона, чтобы увидеть, как взаимодействовать с типами пространственных данных в 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 C++
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/

Источник

На всякий случай, одна функция 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
Источник

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

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

  • Таблица: свойства
  • Поля: id, широта, долгота, кровати и т. Д.
  • Запрос:
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;

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

Источник

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

Теперь это пространственное расширение начиная с MySQL5.6.1 и выше. См. Function_st-содержит в Документах.

Источник

Я хотел использовать вышеупомянутую хранимую процедуру 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, ")" ) ));
Источник
Другие вопросы по тегам