Agrupar líneas no dirigidas

16

Estoy buscando una forma eficiente de agrupar líneas independientemente de su dirección. Eso significa que una línea entre Nueva York y Los Ángeles debe estar en el mismo grupo que una línea en la otra dirección entre Los Ángeles y Nueva York. Las ubicaciones de los puntos de inicio / final deben ser similares (es decir, de San Diego a Long Island deben estar en el mismo grupo que LA-NY pero probablemente no de San Francisco a Boston) y no hay puntos intermedios. Los datos de entrada serían similares a este ejemplo:

(PorCassiopeia,dulceenlaWikipediajaponesa GFDL o CC-BY-SA-3.0 , a través de Wikimedia Commons)

Anteriormente, he tratado de ordenar las líneas por adelantado, por ejemplo. para hacer que todos corran de oeste a este, pero esto no resuelve el problema para las líneas que van de norte a sur y al revés.

¿Conoces algún algoritmo que trate este problema? He estado buscando pero además de Algorithm para calcular la dirección promedio de no dirigida segmentos No he encontrado nada remotamente útil, por lo que debo utilizar los términos de búsqueda incorrectos.

    
pregunta underdark 04.01.2017 - 21:41

3 respuestas

9

Si te entiendo bien, quieres agrupar líneas que sean casi iguales sin tener en cuenta la dirección.

Aquí hay una idea que creo que podría funcionar.

  1. divide las líneas en el punto inicial y final

  2. Agrupe los puntos y obtenga la ID del clúster

  3. Busque líneas con la misma combinación de ID de clúster. Esos son un grupo

Esto debería ser posible en PostGIS (por supuesto :-)) versión 2.3

No he probado la función ST_ClusterDBSCAN, pero debería hacer el trabajo.

Si tienes una tabla de líneas como esta:

CREATE TABLE the_lines
(
   geom geometry(linestring),
   id integer primary key
)

Y desea crear el clúster en el que los puntos de inicio y finalización tengan una separación máxima de 10 km. Y debe haber al menos 2 puntos para ser un clúster, entonces la consulta podría ser algo como:

WITH point_id AS
   (SELECT (ST_DumpPoints(geom)).geom, id FROM the_lines),
point_clusters as
   (SELECT ST_ClusterDBSCAN(geom, 10000, 2) cluster_id, id line_id FROM point_id) 
SELECT array_agg(a.line_id), a.cluster_id, b.cluster_id 
FROM point_clusters a 
     INNER JOIN point_clusters b 
     ON a.line_id = b.line_id AND a.cluster_id < b.cluster_id
GROUP BY a.cluster_id, b.cluster_id

Al unirte a a.cluster_id<b.cluster_id , obtienes un ID de clúster comparable independientemente de la dirección.

    
respondido por el Nicklas Avén 05.01.2017 - 09:29
5

¿Realmente desea agrupar únicamente por dirección, sin tener en cuenta el origen o el destino? Si es así, hay algunas formas muy simples. Quizás lo más fácil es calcular el rumbo de cada línea, duplicar eso y trazarlo como un punto en un círculo. Dado que los cojinetes de avance y retroceso difieren en 180 grados, difieren en 360 grados después de doblarse y, por lo tanto, trazan exactamente en el mismo lugar. Ahora agrupa los puntos en el plano con cualquier método que desees.

Aquí hay un ejemplo de trabajo en R , con su salida que muestra las líneas coloreadas de acuerdo con cada uno de los cuatro grupos. Por supuesto, es probable que utilice un GIS para calcular los rodamientos. Usé los rodamientos Euclidean para simplificar.

cluster.undirected <- function(x, ...) { # # Compute the bearing and double it. # theta <- atan2(x[, 4] - x[, 2], x[, 3] - x[, 1]) * 2 # # Convert to a point on the unit circle. # z <- cbind(cos(theta), sin(theta)) # # Cluster those points. # kmeans(z, ...) } # # Create some data. # n <- 100 set.seed(17) pts <- matrix(rnorm(4*n, c(-2,0,2,0), sd=1), ncol=4, byrow=TRUE) colnames(pts) <- c("x.O", "y.O", "x.D", "y.D") # # Plot them. # plot(rbind(pts[1:n,1:2], pts[1:n,3:4]), pch=19, col="Gray", xlab="X", ylab="Y") # # Plot the clustering solution. # n.centers <- 4 s <- cluster.undirected(pts, centers=n.centers) colors <- hsv(seq(1/6, 5/6, length.out=n.centers), 0.8, 0.6, 0.25) invisible(sapply(1:n, function(i) lines(pts[i, c(1,3)], pts[i, c(2,4)], col=colors[s$cluster[i]], lwd=2)) )     
respondido por el whuber 04.01.2017 - 23:29
4

Su aclaración de la pregunta indica que le gustaría que la agrupación se base en los segmentos de línea reales, en el sentido de que cualquiera de los dos pares origen-destino (OD) debe considerarse "cerrado" cuando o ambos orígenes están cerca y ambos destinos están cerca, independientemente del punto que se considere origen o destino .

Esta formulación sugiere que ya tiene una idea de la distancia d entre dos puntos: podría ser la distancia a la que vuela el avión, la distancia en el mapa, el tiempo de viaje de ida y vuelta o cualquier otra métrica. eso no cambia cuando O y D se cambian. La única complicación es que los segmentos no tienen representaciones únicas: corresponden a pares desordenados {O, D}, pero deben representarse como pares ordenados (O, D ) o (D, O). Por lo tanto, podemos tomar la distancia entre dos pares ordenados (O1, D1) y (O2, D2) como una combinación simétrica de las distancias d (O1, O2) yd (D1, D2), como su suma o el cuadrado Raíz de la suma de sus cuadrados. Vamos a escribir esta combinación como

distance((O1,D1), (O2,D2)) = f(d(O1,O2), d(D1,D2)).

Simplemente defina la distancia entre pares desordenados para que sea la menor de las dos distancias posibles:

distance({O1,D1}, {O2,D2}) = min(f(d(O1,O2)), d(D1,D2)), f(d(O1,D2), d(D1,O2))).

En este punto, puede aplicar cualquier técnica de agrupación basada en una matriz de distancia.

Como ejemplo, calculé las 190 distancias punto a punto en el mapa para 20 de las ciudades más pobladas de los EE. UU. y solicité ocho conglomerados utilizando un método jerárquico. (Para simplificar, utilicé los cálculos de distancia de Euclides y apliqué los métodos predeterminados en el software que estaba usando: en la práctica, querrá elegir las distancias adecuadas y los métodos de agrupación para su problema). Aquí está la solución, con grupos indicados por el color de cada segmento de línea. (Los colores se asignaron al azar a los grupos).

AquíestáelcódigoRqueprodujoesteejemplo.Suentradaesunarchivodetextoconloscampos"Longitud" y "Latitud" para las ciudades. (Para etiquetar las ciudades en la figura, también incluye un campo "Clave").

#
# Obtain an array of point pairs.
#
X <- read.csv("F:/Research/R/Projects/US_cities.txt", stringsAsFactors=FALSE)
pts <- cbind(X$Longitude, X$Latitude)

# -- This emulates arbitrary choices of origin and destination in each pair
XX <- t(combn(nrow(X), 2, function(i) c(pts[i[1],], pts[i[2],])))
k <- runif(nrow(XX)) < 1/2
XX <- rbind(XX[k, ], XX[!k, c(3,4,1,2)])
#
# Construct 4-D points for clustering.
# This is the combined array of O-D and D-O pairs, one per row.
#
Pairs <- rbind(XX, XX[, c(3,4,1,2)])
#
# Compute a distance matrix for the combined array.
#
D <- dist(Pairs)
#
# Select the smaller of each pair of possible distances and construct a new
# distance matrix for the original {O,D} pairs.
#
m <- attr(D, "Size")
delta <- matrix(NA, m, m)
delta[lower.tri(delta)] <- D
f <- matrix(NA, m/2, m/2)
block <- 1:(m/2)
f <- pmin(delta[block, block], delta[block+m/2, block])
D <- structure(f[lower.tri(f)], Size=nrow(f), Diag=FALSE, Upper=FALSE, 
               method="Euclidean", call=attr(D, "call"), class="dist")
#
# Cluster according to these distances.
#
H <- hclust(D)
n.groups <- 8
members <- cutree(H, k=2*n.groups)
#
# Display the clusters with colors.
#
plot(c(-131, -66), c(28, 44), xlab="Longitude", ylab="Latitude", type="n")
g <- max(members)
colors <- hsv(seq(1/6, 5/6, length.out=g), seq(1, 0.25, length.out=g), 0.6, 0.45)
colors <- colors[sample.int(g)]
invisible(sapply(1:nrow(Pairs), function(i) 
  lines(Pairs[i, c(1,3)], Pairs[i, c(2,4)], col=colors[members[i]], lwd=1))
)
#
# Show the points for reference
#
positions <- round(apply(t(pts) - colMeans(pts), 2, 
                         function(x) atan2(x[2], x[1])) / (pi/2)) %% 4
positions <- c(4, 3, 2, 1)[positions+1]
points(pts, pch=19, col="Gray", xlab="X", ylab="Y")
text(pts, labels=X$Key, pos=positions, cex=0.6)
    
respondido por el whuber 05.01.2017 - 19:33

Lea otras preguntas en las etiquetas