Algoritmo para encontrar puntos de inflexión para una polilínea

22

Estoy tratando de averiguar los puntos de inflexión, es decir, los puntos donde las curvas en una línea comienzan y terminan. Si observa la imagen, la línea verde puede ser una carretera o un arroyo, y los puntos negros son los puntos donde comienzan y terminan las curvas.

¿Cuáles serían los pasos de alto nivel para automatizar la generación de estos puntos? Tengo ArcGIS de escritorio y soy bastante práctico con ArcObjects.

    
pregunta Devdatta Tengshe 18.10.2012 - 13:54

3 respuestas

15

Cuando la curva se compone de segmentos de línea, todos los puntos interiores de esos segmentos son puntos de inflexión, lo que no es interesante. En su lugar, debe pensarse que la curva se aproxima a los vértices de esos segmentos. Al dividir una curva por partes dos veces diferenciable a través de esos segmentos, podemos calcular la curvatura. Un punto de inflexión, hablando estrictamente, es entonces un lugar donde la curvatura es cero.

En el ejemplo, hay tramos largos en los que la curvatura es casi cero. Esto sugiere que los puntos indicados deben aproximarse a los extremos de tales tramos de regiones de baja curvatura.

Por lo tanto, un algoritmo efectivo dividirá los vértices, calculará la curvatura a lo largo de un conjunto denso de puntos intermedios, identificará rangos de curvatura cercana a cero (utilizando una estimación razonable de lo que significa estar "cerca") y marcará los puntos finales de esos rangos.

Aquí está trabajando el código R para ilustrar estas ideas. Comencemos con una cadena de líneas expresada como una secuencia de coordenadas:

xy <- matrix(c(5,20, 3,18, 2,19, 1.5,16, 5.5,9, 4.5,8, 3.5,12, 2.5,11, 3.5,3, 
               2,3, 2,6, 0,6, 2.5,-4, 4,-5, 6.5,-2, 7.5,-2.5, 7.7,-3.5, 6.5,-8), ncol=2, byrow=TRUE)

Spline las coordenadas x y y por separado para lograr una parametrización de la curva. (El parámetro se llamará time .)

n <- dim(xy)[1]
fx <- splinefun(1:n, xy[,1], method="natural")
fy <- splinefun(1:n, xy[,2], method="natural")

Interpolar las splines para trazar y calcular:

time <- seq(1,n,length.out=511)
uv <- sapply(time, function(t) c(fx(t), fy(t)))

Necesitamos una función para calcular la curvatura de una curva parametrizada. Necesita estimar la primera y segunda derivadas de la spline. Con muchas splines (como las splines cúbicas) este es un cálculo algebraico fácil. R proporciona los primeros tres derivados automáticamente. (En otros entornos, uno podría querer calcular los derivados numéricamente).

curvature <- function(t, fx, fy) {
  # t is an argument to spline functions fx and fy.
  xp <- fx(t,1); yp <- fy(t,1)            # First derivatives
  xpp <- fx(t,2); ypp <- fy(t,2)          # Second derivatives
  v <- sqrt(xp^2 + yp^2)                  # Speed
  (xp*ypp - yp*xpp) / v^3                 # (Signed) curvature
  # (Left turns have positive curvature; right turns, negative.)
}

kappa <- abs(curvature(time, fx, fy))     # Absolute curvature of the data

Propongo estimar un umbral para curvatura cero en términos de la extensión de la curva. Este al menos es un buen punto de partida; debe ajustarse de acuerdo con la tortuosidad de la curva (es decir, aumentada para curvas más largas). Esto se usará más adelante para colorear los gráficos según la curvatura.

curvature.zero <- 2*pi / max(range(xy[,1]), range(xy[,2])) # A small threshold
i.col <- 1 + floor(127 * curvature.zero/(curvature.zero + kappa)) 
palette(terrain.colors(max(i.col)))                        # Colors

Ahora que los vértices se han dividido y se ha calculado la curvatura, solo queda para encontrar los puntos de inflexión . Para mostrarlos podemos trazar los vértices, trazar la spline y marcar los puntos de inflexión en él.

plot(xy, asp=1, xlab="x",ylab="y", type="n")
tmp <- sapply(2:length(kappa), function(i) lines(rbind(uv[,i-1],uv[,i]), lwd=2, col=i.col[i]))
points(t(sapply(time[diff(kappa < curvature.zero/2) != 0], 
       function(t) c(fx(t), fy(t)))), pch=19, col="Black")
points(xy)

Los puntos abiertos son los vértices originales en xy y los puntos negros son los puntos de inflexión identificados automáticamente con este algoritmo. Debido a que la curvatura no se puede calcular de manera confiable en los puntos finales de la curva, esos puntos no están especialmente marcados.

    
respondido por el whuber 18.10.2012 - 18:40
3

Puede utilizar la herramienta de Densificación . Para este caso, elige densificar por ángulo. A continuación, elija el ángulo máximo aceptado en una línea recta. Luego aplique a la línea de resultados la herramienta Línea dividida en vértices . Finalmente, elimine las líneas que tienen shape_length más pequeña la longitud mínima de la carretera.

Enestaimagen,vemostrespasos:

1-Densificalalíneausandoángulo.Heusado10gradoscomoparámetro,yusamossplitline.Enlaimagen,lalíneacurvaestáensufaseinicial.

arcpy.Densify_edit("line" , "ANGLE" , "","",10)
arcpy.SplitLine_management("line" , "line_split")

2- Selecciona los segmentos donde shape_length no es redundante. Como vemos en la tabla, no he seleccionado esas longitudes redundantes. Luego, los selecciono en una nueva clase de entidad.

arcpy.Select_analysis("line_split" , "line_split_selected")

3- Hemos extraído los vértices ubicados en los bordes de las líneas, que son puntos de inflexión.

arcpy.FeatureVerticesToPoints_management("line_split_selected" , "line_split_pnt" , "DANGLE")
    
respondido por el geogeek 18.10.2012 - 19:05
1

Puede utilizar la herramienta Generalize que tiene la desplazamiento máximo de la línea original como parámetro, para que pueda elegir el desplazamiento que se ajuste a su caso.

Sinombramoslalíneaoriginal"line_cur" y la generalizada "line_gen", entonces podríamos recortar "line_cur" por "line_gen". El resultado será el segmento recto de "line_cur". Luego podríamos limpiar algunos segmentos muy cortos eliminándolos con una consulta de SQL que selecciona Shape_length mayor que la longitud mínima de la carretera.

    
respondido por el geogeek 18.10.2012 - 18:45

Lea otras preguntas en las etiquetas