MySQL реализация алгоритма литья лучей? - PullRequest
Новая
       11

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

13 голосов
/ 27 сентября 2011

Нам нужно найти быстрый и достаточно точный метод для точки-полигона для значений широты и долготы и полигонов на картах 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 ]

18 голосов
/ 10 октября 2011

Следующая функция (версия алгоритма Raycasting для MYSQL) потрясла мой мир: 

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

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

5 голосов
/ 04 октября 2011

Я бы написал пользовательский 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 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/

2 голосов
/ 02 ноября 2012

На всякий случай, одна функция 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
1 голос
/ 08 мая 2014

Вот версия, которая работает с МНОГОПОЛИГОНАМИ (адаптация Zarun'а, которая работает только для ПОЛИГОНОВ). 

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;
1 голос
/ 26 октября 2013

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

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

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

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

1 голос
/ 19 февраля 2013

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

1 голос
/ 08 июня 2012

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

Похожие темы

...