Buscando Algoritmo para detectar círculos y principio y final del círculo?

24

Tengo muchos datos de vuelo de los pilotos de planeadores en forma de correcciones GPS en un intervalo fijo. Me gustaría analizar la ruta de vuelo y detectar el inicio y el final del 'círculo' que hará el piloto de planeador cuando encuentre térmicas.

Idealmente, un algoritmo me daría un punto inicial y final en la línea, definiendo un "círculo". Estos puntos podrían ser iguales a uno de los arreglos de gps y no necesitan ser interpolados.

Simplemente podría caminar a lo largo de la ruta de vuelo, verificar la velocidad de giro y tener algunos criterios para decidir si el planeador está dando vueltas o no.

Como estoy usando PostgreSQL con la extensión PostGIS, tenía curiosidad por saber si hay un mejor enfoque para este problema. Ya tengo un procedimiento para calcular el ángulo de dos segmentos de línea:

CREATE OR REPLACE FUNCTION angle_between(
  _p1 GEOMETRY(PointZ,4326),
  _p2 GEOMETRY(PointZ,4326),
  _p3 GEOMETRY(PointZ,4326)
) RETURNS DECIMAL AS $$
DECLARE
  az1 FLOAT;
  az3 FLOAT;
BEGIN
  az1 = st_azimuth(_p2,_p1);
  az3 = st_azimuth(_p2,_p3);
IF az3 > az1 THEN
  RETURN (
      degrees(az3 - az1)::decimal - 180
  );
ELSE
  RETURN (
      degrees(az3 - az1)::decimal + 180
  );
END IF;
END;
$$ LANGUAGE plpgsql;

Debería ser posible recorrer todos los segmentos de línea y verificar, cuando la suma de los ángulos es mayor que 360 ​​o menor que -360 grados. Entonces podría usar st_centroid para detectar el centro del círculo, si es necesario.

¿Hay un mejor enfoque?


Según lo solicitado, cargué un ejemplo de vuelo .

Una ruta de vuelo de muestra

pgross
fuente
1
Mirando a su alrededor pateó Hough Circle Transform. Hay una discusión similar (con un polígono) postgis usuario aquí: lists.osgeo.org/pipermail/postgis-users/2015-February/…
Barrett
Gracias a los dos. Echaré un vistazo a la Transformada de Hough. La discusión en osgeo.org supone que ya sé dónde comienza y termina el círculo, si lo entendí correctamente.
pgross
¿Has visto esto: gis.stackexchange.com/questions/37058
Devdatta Tengshe
@DevdattaTengshe Sí, pero gracias de todos modos. Ese sería un enfoque en el que tendría que calcular las splines y la curvatura externamente, ¿verdad? Por externo, no quiero decir como un procedimiento o consulta directamente en la base de datos. Como los vuelos no cambian, una vez que estén en la base de datos, esta sería una opción.
pgross
¿Puedes publicar algunos datos de muestra como un archivo .sql?
dbaston

Respuestas:

14

No podía dejar de pensar en esto ... pude idear un Procedimiento almacenado para hacer el conteo del bucle. ¡La ruta de ejemplo contiene 109 bucles!

Estos son los puntos de vuelo que se muestran con los centroides de bucle en rojo: ingrese la descripción de la imagen aquí

Básicamente, se ejecuta a través de los puntos en el orden en que fueron capturados y construye una línea a medida que itera a través de los puntos. Cuando la línea que estamos construyendo crea un bucle (usando ST_BuildArea), contamos un bucle y comenzamos a construir una línea nuevamente desde ese punto.

Esta función devuelve un conjunto de registros de cada bucle que contiene el número de bucle, su geometría, su punto de inicio / finalización y su centroide (también lo limpié un poco e hice mejores nombres de variables):

DROP FUNCTION test.find_loop_count(flightid int);

create function test.find_Loop_count(
    IN flightid      int,
    OUT loopnumber   int,
    OUT loopgeometry geometry,
    OUT loopstartend geometry,
    OUT loopcentroid geometry
    ) 
  RETURNS SETOF record AS
$BODY$

-- s schema 'test' must exist
-- a table 'points' of flight points must exist
--  we are going to iterate through the point path, building a line as we go
--   If the line creates a loop then we count a loop and start over building a new line
--     add the intersection point to the returning recordset
--     add the centroid of the loop to the resulting recordset
-- pass in the flight ID of the flight that you wish to count its loops for example:
--   SELECT * FROM find_loop_count(37);

DECLARE
    rPoint              RECORD;
    gSegment            geometry = NULL;
    gLastPoint          geometry = NULL;
    gLoopPolygon        geometry = NULL;
    gIntersectionPoint  geometry = NULL;
    gLoopCentroid       geometry = NULL;
    iLoops              integer := 0;
BEGIN
    -- for each line segment in Point Path
    FOR rPoint IN 
        WITH
            pts as (
                SELECT location as geom,datetime,row_number() OVER () as rnum 
                FROM test.points 
                WHERE flight_id=flightid
                ORDER BY 2) 
            SELECT ST_AsText(ST_MakeLine(ARRAY[a.geom, b.geom])) AS geom, a.rnum, b.rnum 
            FROM pts as a, pts as b 
            WHERE a.rnum = b.rnum-1 AND b.rnum > 1
        LOOP

        -- if this is the start of a new line then start the segment otherwise add the point to the segment
        if gSegment is null then
            gSegment=rPoint.geom;
        elseif rPoint.geom::geometry=gLastPoint::geometry then
        -- do not add this point to the segment because it is at the same location as the last point
        else
        -- add this point to the line
        gSegment=ST_Makeline(gSegment,rPoint.geom);
        end if;
        -- ST_BuildArea will return true if the line segment is noded and closed
        --  we must also flatten the line to 2D
        --  lets also make sure that there are more than three points in our line to define a loop
        gLoopPolygon=ST_BuildArea(ST_Node(ST_Force2D(gSegment)));
        if gLoopPolygon is not NULL and ST_Numpoints(gSegment) > 3 then
        -- we found a loop
        iLoops:=iLoops+1;

        -- get the intersection point (start/end)
        gIntersectionPoint=ST_Intersection(gSegment::geometry,rPoint.geom::geometry);

        -- get the centroid of the loop
        gLoopCentroid=ST_Centroid(gLoopPolygon);

        -- start building a new line
        gSegment=null;

        LOOPNUMBER   := iLoops;
        LOOPGEOMETRY := gLoopPolygon;
        LOOPSTARTEND := gIntersectionPoint;
        LOOPCENTROID := gLoopCentroid;

        RETURN NEXT;
        end if;
        -- keep track of last segment
        gLastPoint=rPoint.geom;
    END LOOP;
    RAISE NOTICE 'Total loop count is %.', iLoops;
END;
$BODY$
  LANGUAGE plpgsql STABLE
  COST 100
  ROWS 1000;

Esta es una función simple para devolver solo el recuento de bucles:

DROP FUNCTION test.find_loop_count(flightid int);

create function test.find_Loop_count(flightid int) RETURNS integer AS $$
-- s schema 'test' must exist
-- a table 'points' of flight points must exist
--  we are going to iterate through the line path, building the line as we go
--   If the line creates a loop then we count a loop and start over building a new line
-- pass in the flight ID of the flight that you wish to count its loops for example:
--   SELECT find_loop_count(37);

DECLARE
    segment RECORD;
    s geometry = NULL;
    lastS geometry = NULL;
    b geometry = NULL;
    loops integer := 1;
BEGIN
    -- for each line segment is Point Path
    FOR segment IN 
        WITH
            pts as (
                SELECT location as geom,datetime,row_number() OVER () as rnum 
                FROM test.points 
                WHERE flight_id=flightid
                ORDER BY 2) 
            SELECT ST_AsText(ST_MakeLine(ARRAY[a.geom, b.geom])) AS geom, a.rnum, b.rnum 
            FROM pts as a, pts as b 
            WHERE a.rnum = b.rnum-1 AND b.rnum > 1
        LOOP

        -- if this is the start of a new line then make s be the segment otherwise add the segment to s
        if s is null then
            s=segment.geom;
        elseif segment.geom::geometry=lastS::geometry then
        else
            s=ST_Makeline(s,segment.geom);
        end if;
        -- ST_BuildArea will return true if the line segment is noded and closed
        --  we must also flatten the line to 2D
        b=ST_BuildArea(st_node(ST_Force2D(s)));
        if b is not NULL and st_numpoints(s) > 3 then
            RAISE NOTICE 's: %', s;
            RAISE NOTICE 'vvvvv %',st_numpoints(s);
            RAISE NOTICE 'I found a loop! Loop count is now %', loops;
            RAISE NOTICE '^^^^^';
            s=null;
            loops:=loops +1;
        end if;
        lastS=segment.geom;
    END LOOP;
    RAISE NOTICE 'Total loop count is %.', loops-1;
    RETURN loops-1;
END;
$$ LANGUAGE plpgsql;

kttii
fuente
Esto se ve muy prometedor. Muchas gracias. Tendré que mejorarlo, ya que no estoy interesado en la cantidad de círculos sino en los puntos de inicio / finalización. Pero eso debería ser fácilmente posible de regresar, supongo.
pgross
Eso suena bastante inteligente. ¿Cómo maneja la situación en la que un bucle se cruza con otro bucle? ¿O estás saltando los puntos iniciales una vez que localizas un bucle?
Peter Horsbøll Møller
@ PeterHorsbøllMøller Analiza cuándo la línea hace un bucle (ST_BuildArea solo devolverá verdadero cuando la línea crea un área cerrada) en lugar de buscar intersecciones.
kttii
@pgross ¡Uy cierto! Me desvié un poco y me olvidé de los puntos de inicio / final, pero sí, esa es una determinación bastante fácil ahora que los bucles se distinguen.
kttii
@pgross Me parece que probablemente obtendría ubicaciones más razonables de las térmicas ubicando el ST_Centroid de cada ciclo en lugar de ubicar el inicio / final de cada ciclo. ¿Qué piensas? Por supuesto, la función podría proporcionar las tres estadísticas.
kttii
3

Noté que el archivo gpx tiene una marca de tiempo que podría ser explotada. Quizás el siguiente enfoque podría funcionar.

Make a linesegement with Vi,Vi+1
Make it Polyline
Proceed to Vi+2,Vi+3 check intersection with Polyline
  if it intersects 
      find the point of intersection-Designate this as start/end point of the loop
      Make this intersection point as Vi and Vi+1 would next gpx point per time sequence  
  if the linesegement does not intersect with polyyline then  increment 'i' 
addcolor
fuente
Me resultó difícil usar ST_Intersects debido a círculos superpuestos que me llevaron a usar ST_BuildArea.
kttii
Te di la recompensa ya que tu respuesta generalmente está en el mismo camino.
kttii