Cálculo del ancho promedio del polígono?

41

Estoy interesado en examinar el ancho promedio de un polígono que representa la superficie de la carretera. También tengo la línea central de la carretera como un vector (que a veces no está exactamente en el centro). En este ejemplo, la línea central de la carretera está en rojo y el polígono es azul:

ingrese la descripción de la imagen aquí

Un enfoque de fuerza bruta en el que he pensado es amortiguar la línea en pequeños incrementos, intersecar el amortiguador con una rejilla de rejilla, intersecar el polígono de la carretera con una rejilla de rejilla, calcular el área intersectada para ambas medidas de intersección y seguir haciendo esto hasta El error es pequeño. Sin embargo, este es un enfoque burdo, y me pregunto si hay una solución más elegante. Además, esto ocultaría el ancho de una carretera grande y una carretera pequeña.

Estoy interesado en una solución que use ArcGIS 10, PostGIS 2.0 o QGIS. He visto esta pregunta y descargué la herramienta de Dan Patterson para ArcGIS10, pero no pude calcular lo que quiero con ella.

Acabo de descubrir la herramienta de geometría de límite mínimo en ArcGIS 10 que me permite producir los siguientes polígonos verdes:

ingrese la descripción de la imagen aquí

Esto parece una buena solución para carreteras que siguen una cuadrícula, pero no funcionaría de otra manera, por lo que todavía estoy interesado en otras sugerencias.

djq
fuente
¿Descartó posibles soluciones en la barra lateral? es decir, gis.stackexchange.com/questions/2880/… aparentemente marcado como una respuesta trivial a una publicación potencialmente duplicada
@DanPatterson No vi ninguna pregunta como esta (muchas están relacionadas, por supuesto). ¿Quiso decir que mi pregunta fue marcada? No entendí tu segunda línea.
DJ
Esa pregunta relacionada, @Dan, se refiere a una interpretación diferente del "ancho" (bueno, en realidad, la interpretación no está perfectamente clara). Las respuestas allí parecen centrarse en encontrar el ancho en el punto más ancho, en lugar de un ancho promedio.
whuber
Como @whuber quiere centralizar aquí las discusiones, cerrando otras preguntas, sugiero que la pregunta se edite para que la gente entienda " la estimación del ancho promedio de una tira rectangular "
Peter Krauss
@Peter: Como una tira rectangular es, a fortiori, un polígono, el título más general debería mantenerse.
whuber

Respuestas:

41

Parte del problema es encontrar una definición adecuada de "ancho promedio". Varios son naturales pero diferirán, al menos ligeramente. Para simplificar, considere las definiciones basadas en propiedades que son fáciles de calcular (lo que va a descartar aquellas basadas en la transformación del eje medial o secuencias de buffers, por ejemplo).

Como ejemplo, considere que la intuición arquetípica de un polígono con un "ancho" definido es un pequeño amortiguador (digamos de radio r con extremos cuadrados) alrededor de una polilínea larga y bastante recta (digamos de longitud L ). Pensamos en 2r = w como su ancho. Así:

  • Su perímetro P es aproximadamente igual a 2L + 2w;

  • Su área A es aproximadamente igual a w L.

El ancho wy la longitud L pueden recuperarse como raíces de la cuadrática x ^ 2 - (P / 2) x + A; en particular, podemos estimar

  • w = (P - Cuadrado (P ^ 2 - 16A)) / 4 .

Cuando esté seguro de que el polígono es realmente largo y delgado, como una aproximación adicional , puede tomar 2L + 2w para igualar 2L, de donde

  • w (en bruto) = 2A / P.

El error relativo en esta aproximación es proporcional a w / L: cuanto más delgado sea el polígono, cuanto más cerca esté w / L de cero, y mejor será la aproximación.

Este enfoque no solo es extremadamente simple (solo divide el área por el perímetro y multiplica por 2), con cualquiera de las fórmulas, no importa cómo esté orientado el polígono o dónde está situado (porque tales movimientos euclidianos no cambian ni el área ni el área). perímetro).

Puede considerar usar cualquiera de estas fórmulas para estimar el ancho promedio de cualquier polígono que represente segmentos de calles. El error que comete en la estimación original de w (con la fórmula cuadrática) se produce porque el área A también incluye pequeñas cuñas en cada curva de la polilínea original. Si la suma de los ángulos de curvatura es t radianes (esta es la curvatura absoluta total de la polilínea), entonces realmente

  • P = 2L + 2w + 2 Pi tw y

  • A = L w + Pi tw ^ 2.

Conéctelos a la solución anterior (fórmula cuadrática) y simplifique. Cuando se despeja el humo, ¡la contribución del término de curvatura t ha desaparecido! Lo que originalmente parecía una aproximación es perfectamente preciso para los búferes de polilínea que no se cruzan entre sí (con extremos cuadrados). Para polígonos de ancho variable, esta es, por lo tanto, una definición razonable de ancho promedio.

whuber
fuente
Gracias @whuber que es una gran respuesta y me ha ayudado a pensarlo mucho más claramente.
djq
@whuber: estoy escribiendo un artículo y necesitaría dar una referencia adecuada ('académica') al método que describe aquí. ¿Tienes esa referencia? ¿Esta medida tiene un nombre? ¡Si no, puedo nombrarlo por ti! ¿Qué pasa con la "medida de ancho de Huber"?
julien
@julien No tengo referencias. Este formato podría funcionar: MISC {20279, TITLE = {Calculating width width of polygon?}, AUTHOR = {whuber ( gis.stackexchange.com/users/664/whuber )}, HOWPUBLISHED = {GIS}, NOTE = {URL: gis.stackexchange.com/q/20279/664 (versión: 2013-08-13)}, EPRINT = { gis.stackexchange.com/q/20279 }, URL = { gis.stackexchange.com/q/20279 }}
whuber
1
Esta es una respuesta fabulosa y muy simple y bien explicada. ¡Gracias!
Amball
18

Aquí muestro poca optimización sobre la solución @whuber, y estoy poniendo en términos de "ancho de búfer", porque es útil para integrar la solución de un problema más general: ¿Hay una función inversa st_buffer, que devuelve una estimación de ancho?

CREATE FUNCTION buffer_width(
        -- rectangular strip mean width estimator
    p_len float,   -- len of the central line of g
    p_geom geometry, -- g
    p_btype varchar DEFAULT 'endcap=flat' -- st_buffer() parameter
) RETURNS float AS $f$
  DECLARE
    w_half float;
    w float;    
  BEGIN
         w_half := 0.25*ST_Area(p_geom)/p_len;
         w      := 0.50*ST_Area( ST_Buffer(p_geom,-w_half,p_btype) )/(p_len-2.0*w_half);
     RETURN w_half+w;
  END
$f$ LANGUAGE plpgsql IMMUTABLE;

Para este problema, la pregunta acerca @celenius ancho de la calle , swla solución es

 sw = buffer_width(ST_Length(g1), g2)

donde swestá el "ancho promedio", g1la línea central de g2, y la calle g2es un POLÍGONO . Utilicé solo la biblioteca estándar OGC, probé con PostGIS y resolví otras aplicaciones prácticas serias con la misma función buffer_width.

DEMOSTRACIÓN

A2es el área de g2, L1la longitud de la línea central ( g1) de g2.

Suponiendo que podemos generar g2por g2=ST_Buffer(g1,w), y que g1es una recta, también lo g2es un rectángulo con longitud L1y ancho 2*w, y

    A2 = L1*(2*w)   -->  w = 0.5*A2/L1

No es la misma fórmula de @whuber, porque aquí whay una mitad del g2ancho del rectángulo ( ). Es un buen estimador, pero como podemos ver en las pruebas (a continuación), no es exacto, y la función lo usa como una pista, para reducir el g2área y como un estimador final.

Aquí no evaluamos buffers con "endcap = square" o "endcap = round", que necesitan una suma A2 de un área de un buffer de puntos con el mismo w.

REFERENCIAS: en un foro similar de 2005 , W. Huber explica soluciones similares y otras.

PRUEBAS Y RAZONES

Para líneas rectas, los resultados, como se esperaba, son exactos. Pero para otras geometrías, los resultados pueden ser decepcionantes. La razón principal es, quizás, que todo el modelo es para rectángulos exactos, o para geometrías que se pueden aproximar a un "rectángulo de franja". Aquí un "kit de prueba" para verificar los límites de esta aproximación (ver wfactoren los resultados anteriores).

 SELECT *, round(100.0*(w_estim-w)/w,1) as estim_perc_error
    FROM (
        SELECT btype, round(len,1) AS len, w, round(w/len,3) AS wfactor,
               round(  buffer_width(len, gbase, btype)  ,2) as w_estim ,
               round(  0.5*ST_Area(gbase)/len       ,2) as w_near
        FROM (
         SELECT
            *, st_length(g) AS len, ST_Buffer(g, w, btype) AS gbase
         FROM (
               -- SELECT ST_GeomFromText('LINESTRING(50 50,150 150)') AS g, -- straight
               SELECT ST_GeomFromText('LINESTRING(50 50,150 150,150 50,250 250)') AS g,
            unnest(array[1.0,10.0,20.0,50.0]) AS w
              ) AS t, 
             (SELECT unnest(array['endcap=flat','endcap=flat join=bevel']) AS btype
             ) AS t2
        ) as t3
    ) as t4;

RESULTADOS

CON RECTÁNGULOS (la línea central es una LÍNEA RECTA):

         btype          |  len  |  w   | wfactor | w_estim | w_near | estim_perc_error 
------------------------+-------+------+---------+---------+--------+------------------
 endcap=flat            | 141.4 |  1.0 |   0.007 |       1 |      1 |                0
 endcap=flat join=bevel | 141.4 |  1.0 |   0.007 |       1 |      1 |                0
 endcap=flat            | 141.4 | 10.0 |   0.071 |      10 |     10 |                0
 endcap=flat join=bevel | 141.4 | 10.0 |   0.071 |      10 |     10 |                0
 endcap=flat            | 141.4 | 20.0 |   0.141 |      20 |     20 |                0
 endcap=flat join=bevel | 141.4 | 20.0 |   0.141 |      20 |     20 |                0
 endcap=flat            | 141.4 | 50.0 |   0.354 |      50 |     50 |                0
 endcap=flat join=bevel | 141.4 | 50.0 |   0.354 |      50 |     50 |                0

CON OTRAS GEOMETRÍAS (línea central doblada):

         btype          | len |  w   | wfactor | w_estim | w_near | estim_perc_error 
 -----------------------+-----+------+---------+---------+--------+------------------
 endcap=flat            | 465 |  1.0 |   0.002 |       1 |      1 |                0
 endcap=flat join=bevel | 465 |  1.0 |   0.002 |       1 |   0.99 |                0
 endcap=flat            | 465 | 10.0 |   0.022 |    9.98 |   9.55 |             -0.2
 endcap=flat join=bevel | 465 | 10.0 |   0.022 |    9.88 |   9.35 |             -1.2
 endcap=flat            | 465 | 20.0 |   0.043 |   19.83 |  18.22 |             -0.9
 endcap=flat join=bevel | 465 | 20.0 |   0.043 |   19.33 |  17.39 |             -3.4
 endcap=flat            | 465 | 50.0 |   0.108 |   46.29 |  40.47 |             -7.4
 endcap=flat join=bevel | 465 | 50.0 |   0.108 |   41.76 |  36.65 |            -16.5

 wfactor= w/len
 w_near = 0.5*area/len
 w_estim is the proposed estimator, the buffer_width function.

Acerca de btypever la guía ST_Buffer , con buenas ilustraciones y los LINESTRING utilizados aquí.

CONCLUSIONES :

  • el estimador de w_estimsiempre es mejor que w_near;
  • para g2geometrías "cercanas a rectangulares" , está bien, cualquierwfactor
  • para otras geometrías (cerca de "tiras rectangulares"), use el límite wfactor=~0.01para 1% de error en w_estim. Hasta este factor de factor, use otro estimador.

Precaución y prevención

¿Por qué ocurre el error de estimación? Cuando se utiliza ST_Buffer(g,w), se espera, por el "modelo de tira rectangular", que la nueva área añadida por el buffer de ancho wse trata w*ST_Length(g)o w*ST_Perimeter(g)... Cuando no está, por lo general por enchapados (ver líneas cruzadas) o por "labrar", es cuando La estimación de la wfalla promedio . Este es el mensaje principal de las pruebas.

Para detectar este problema en cualquier rey del búfer , verifique el comportamiento de la generación del búfer:

SELECT btype, w, round(100.0*(a1-len1*2.0*w)/a1)::varchar||'%' AS straight_error,  
                 round(100.0*(a2-len2*2.0*w)/a2)::varchar||'%' AS curve2_error,
                 round(100.0*(a3-len3*2.0*w)/a3)::varchar||'%' AS curve3_error
FROM (
 SELECT
    *, st_length(g1) AS len1, ST_Area(ST_Buffer(g1, w, btype)) AS a1,
    st_length(g2) AS len2, ST_Area(ST_Buffer(g2, w, btype)) AS a2,
    st_length(g3) AS len3, ST_Area(ST_Buffer(g3, w, btype)) AS a3
 FROM (
       SELECT ST_GeomFromText('LINESTRING(50 50,150 150)') AS g1, -- straight
              ST_GeomFromText('LINESTRING(50 50,150 150,150 50)') AS g2,
              ST_GeomFromText('LINESTRING(50 50,150 150,150 50,250 250)') AS g3,
              unnest(array[1.0,20.0,50.0]) AS w
      ) AS t, 
     (SELECT unnest(array['endcap=flat','endcap=flat join=bevel']) AS btype
     ) AS t2
) as t3;

RESULTADOS

         btype          |  w   | straight_error | curve2_error | curve3_error 
------------------------+------+----------------+--------------+--------------
 endcap=flat            |  1.0 | 0%             | -0%          | -0%
 endcap=flat join=bevel |  1.0 | 0%             | -0%          | -1%
 endcap=flat            | 20.0 | 0%             | -5%          | -10%
 endcap=flat join=bevel | 20.0 | 0%             | -9%          | -15%
 endcap=flat            | 50.0 | 0%             | -14%         | -24%
 endcap=flat join=bevel | 50.0 | 0%             | -26%         | -36%

        alerta

Peter Krauss
fuente
13

Si puede unir los datos de su polígono a los datos de su línea central (ya sea espacial o tabular), simplemente sume las áreas de polígono para cada alineación de la línea central y divida por la longitud de la línea central.

Scro
fuente
¡es verdad! En este caso, mis líneas centrales no tienen la misma longitud, pero siempre podría unirlas como una sola y dividirlas por polígono.
DJ
Si sus datos están en postgreSQL / postGIS y tiene un campo de identificación de calle para líneas centrales y polígonos, entonces no es necesario fusionar / dividir, y al usar funciones de agregado, su respuesta está a solo una consulta de distancia. Soy lento en SQL, o publicaría un ejemplo. Avíseme si así es como va a resolver, y lo ayudaré a resolverlo (si es necesario)
Scro
Gracias Scro, actualmente no está en PostGIS, pero es bastante rápido de cargar. Creo que probaré el enfoque de @ whuber primero pero lo compararé con los resultados de PostGIS (y gracias por la oferta de ayuda SQL, pero yo debería ser capaz de gestionar). Principalmente tratando de aclarar el enfoque en mi cabeza primero.
DJ
+1 Esta es una solución simple y agradable para circunstancias en las que está disponible.
whuber
9

Desarrollé una fórmula para el ancho promedio de un polígono y la puse en una función Python / ArcPy. Mi fórmula se deriva de (pero se extiende sustancialmente) la noción más directa de ancho promedio que he visto discutido en otra parte; es decir, el diámetro de un círculo que tiene la misma área que su polígono. Sin embargo, en la pregunta anterior y en mi proyecto, estaba más interesado en el ancho del eje más estrecho. Además, estaba interesado en el ancho promedio para formas potencialmente complejas, no convexas.

Mi solución fue:

(perimeter / pi) * area / (perimeter**2 / (4*pi))
= 4 * area / perimeter

Es decir:

(Diameter of a circle with the same perimeter as the polygon) * Area / (Area of a circle with the same perimeter as the polygon)

La función es:

def add_average_width(featureClass, averageWidthField='Width'):
    '''
    (str, [str]) -> str

    Calculate the average width of each feature in the feature class. The width
        is reported in units of the feature class' projected coordinate systems'
        linear unit.

    Returns the name of the field that is populated with the feature widths.
    '''
    import arcpy
    from math import pi

    # Add the width field, if necessary
    fns = [i.name.lower() for i in arcpy.ListFields(featureClass)]
    if averageWidthField.lower() not in fns:
        arcpy.AddField_management(featureClass, averageWidthField, 'DOUBLE')

    fnsCur = ['SHAPE@LENGTH', 'SHAPE@AREA', averageWidthField]
    with arcpy.da.UpdateCursor(featureClass, fnsCur) as cur:
        for row in cur:
            perim, area, width = row
            row[-1] = ((perim/pi) * area) / (perim**2 / (4 * pi))
            cur.updateRow(row)

    return averageWidthField

Aquí hay un mapa exportado con el ancho promedio (y algunos otros atributos de geometría para referencia) en una variedad de formas usando la función de arriba:

ingrese la descripción de la imagen aquí

Tom
fuente
44
Si simplificas la expresión, será justa area / perimeter * 4.
culebrón
Gracias, @ culebrón. Estaba buscando la claridad del concepto sobre la simplicidad de la fórmula, y nunca pensé en simplificar la ecuación. Esto debería ahorrarme algo de tiempo de procesamiento.
Tom
0

Otra solución con eje medial aproximado:

  1. Calcular el eje medial aproximado del polígono;
  2. Obtenga la longitud del eje medial aproximado;
  3. Obtenga la distancia desde ambos extremos del eje hasta el borde del polígono;
  4. Suma la longitud y las distancias del eje desde el paso 3: es la longitud aproximada del polígono;
  5. Ahora puede dividir el área del polígono por esta longitud y obtener el ancho promedio del polígono.

El resultado seguramente será incorrecto para aquellos polígonos donde el eje medial aproximado no es una sola línea continua, por lo que puede verificarlo antes del paso 1 y regresar NULLo algo así.

ejemplos

Aquí hay un ejemplo de la función PostgreSQL (nota: necesita instalar extensiones postgis y postgis_sfcgal ):

CREATE FUNCTION ApproximatePolygonLength(geom geometry)
RETURNS float AS $$
    SELECT
        CASE
            /* in case when approximate medial axis is empty or simple line
             * return axis length
             */
            WHEN (ST_GeometryType(axis.axis) = 'ST_LineString' OR ST_IsEmpty(axis.axis))
                THEN axis_length.axis_length
                    + start_point_distance.start_point_distance
                    + end_point_distance.end_point_distance
            /* else geometry is too complex to define length */
            ELSE NULL
        END AS length
    FROM
        LATERAL (
            SELECT
                ST_MakeValid(geom) AS valid_geom
        ) AS valid_geom,
        LATERAL (
            SELECT
                /* `ST_LineMerge` returns:
                 *  - `GEOMETRYCOLLECTION EMPTY`, if `ST_ApproximateMedialAxis` is an empty line (i.e. for square);
                 *  - `LINESTRING ...`, if `ST_ApproximateMedialAxis` is a simple line;
                 *  - `MULTILINESTRING ...`, if `ST_ApproximateMedialAxis` is a complex line
                 *     that can not be merged to simple line. In this case we should return `NULL`.
                 */
                ST_LineMerge(
                    ST_ApproximateMedialAxis(
                        valid_geom.valid_geom
                    )
                ) AS axis
        ) AS axis,
        LATERAL (
            SELECT
                ST_Boundary(valid_geom.valid_geom) AS border
        ) AS border,
        LATERAL (
            SELECT
                ST_Length(axis.axis) AS axis_length
        ) AS axis_length,
        LATERAL (
            SELECT
                ST_IsClosed(axis.axis) AS axis_is_closed
        ) AS axis_is_closed,
        LATERAL (
            SELECT
                CASE WHEN axis_is_closed.axis_is_closed THEN 0
                ELSE
                    ST_Distance(
                        border.border,
                        CASE ST_GeometryType(axis.axis)
                            WHEN 'ST_LineString' THEN ST_StartPoint(axis.axis)
                            /* if approximate medial axis is empty (i.e. for square),
                             * get centroid of geometry
                             */
                            ELSE ST_Centroid(valid_geom.valid_geom)
                        END
                    )
                END AS start_point_distance
        ) AS start_point_distance,
        LATERAL (
            SELECT
                CASE WHEN axis_is_closed.axis_is_closed THEN 0
                ELSE
                    ST_Distance(
                        border.border,
                        CASE ST_GeometryType(axis.axis)
                            WHEN 'ST_LineString' THEN ST_EndPoint(axis.axis)
                            /* if approximate medial axis is empty (i.e. for square),
                             * get centroid of geometry
                             */
                            ELSE ST_Centroid(valid_geom.valid_geom)
                        END
                    )
                END AS end_point_distance
        ) AS end_point_distance;
$$ LANGUAGE SQL;

CREATE FUNCTION ApproximatePolygonWidth(geom geometry)
RETURNS float AS $$
    SELECT
        CASE
            WHEN length IS NULL THEN NULL
            ELSE area.area / length.length
        END AS width
    FROM
        (
            SELECT ApproximatePolygonLength(geom) AS length
        ) AS length,
        (
            SELECT
                ST_Area(
                    ST_MakeValid(geom)
                ) AS area
        ) AS area;
$$ LANGUAGE SQL;

Desventaja:

Esta solución no funcionará con casos en los que el polígono es casi rectangular y el ser humano puede definir intuitivamente su longitud, pero el eje medial aproximado tiene pequeñas ramas cerca del borde y, por lo tanto, el algoritmo devuelve Ninguno.

Ejemplo:

ejemplo roto

Andrey Semakin
fuente