Agrupación de líneas no dirigidas

Question

Estoy buscando una forma eficiente de agrupar líneas independientemente de su dirección. Esto significa que una línea entre Nueva York y Los Ángeles debería 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 iniciales y finales deben ser similares (es decir, San Diego a Long Island debería estar en el mismo cluster que LA-NY pero probablemente no San Francisco a Boston) y no hay puntos intermedios. Los datos de entrada serían similares a los de este ejemplo:

(Por Cassiopeia sweet en la Wikipedia japonesa GFDL o CC-BY-SA-3.0 , vía Wikimedia Commons)

Anteriormente he intentado ordenar las líneas de antemano, por ejemplo, para que todas vayan de oeste a este, pero esto no resuelve el problema de las líneas que van de norte a sur y al revés.

¿Conoce algún algoritmo que trate este problema? He estado buscando pero además de Algoritmo para calcular la dirección media de los segmentos no dirigidos No he encontrado nada remotamente útil, así que debo estar utilizando los términos de búsqueda equivocados.

Answer 1

Si te entiendo bien quieres agrupar líneas que sean más o menos iguales sin respetar la dirección.

Esta es una idea que creo que podría funcionar.

1. dividir las líneas en punto inicial y punto final

2. Agrupar los puntos y obtener el id de cluster

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

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 se quiere crear el cluster donde los puntos de inicio y final estén separados por un máximo de 10 km. Y debe haber al menos 2 puntos para ser un clúster entonces la consulta podría ser algo así:

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 unirse con a.cluster_id<b.cluster_id se obtiene un identificador de grupo comparable independientemente de la dirección.

Answer 2

¿Realmente quiere agruparse únicamente por la dirección, sin tener en cuenta el origen o el destino? Si es así, hay algunas formas muy sencillas. Quizá la más sencilla sea calcular el rumbo de cada línea, duplicarlo y trazarlo como un punto en un círculo. Como los rumbos hacia delante y hacia atrás difieren en 180 grados, después de duplicarlos difieren en 360 grados y, por lo tanto, se trazan exactamente en el mismo lugar. Ahora agrupa los puntos en el plano utilizando el método que quieras.

Este es un ejemplo de trabajo en R y su salida muestra las líneas coloreadas según cada uno de los cuatro clusters. Por supuesto, es probable que se utilice un SIG para calcular los rumbos; yo he utilizado rumbos euclidianos 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))
)

Answer 3

Su aclaración de la pregunta indica que le gustaría que la agrupación se basara en el segmentos de línea En el sentido de que dos pares origen-destino (O-D) cualesquiera deben considerarse "cercanos" cuando 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 tienes una idea de la distancia d entre dos puntos: puede ser la distancia al volar el avión, la distancia en el mapa, el tiempo de viaje de ida y vuelta o cualquier otra métrica que no cambie cuando se intercambian O y D. La única complicación es que los segmentos no tienen representaciones únicas: corresponden a desordenado pares {O,D} pero deben representarse como pedido pares, ya sea (O,D) o (D,O). Por lo tanto, podríamos tomar la distancia entre dos pares ordenados (O1,D1) y (O2,D2) como alguna combinación simétrica de las distancias d(O1,O2) y d(D1,D2), como su suma o la raíz cuadrada de la suma de sus cuadrados. Escribamos esta combinación como

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

Simplemente define la distancia entre pares no ordenados como 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 se 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 EE.UU. y solicité ocho clusters utilizando un método jerárquico. (Para simplificar, utilicé los cálculos de la distancia euclidiana y apliqué los métodos por defecto del software que utilizaba: en la práctica, deberá elegir las distancias y los métodos de agrupación adecuados para su problema). Aquí está la solución, con los clusters indicados por el color de cada segmento de línea. (Los colores se asignaron al azar a los clusters).

Aquí está el R código que produjo este ejemplo. Su entrada es un archivo de texto con los campos "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)