Agrupando linhas não direcionadas

Estou procurando uma maneira eficiente de agrupar linhas independentemente de sua direção. Isso significa que uma linha entre Nova York e Los Angeles deve estar no mesmo cluster que uma linha na outra direção entre Los Angeles e Nova York. Os locais dos pontos de início e de término devem ser semelhantes (ou seja, San Diego para Long Island devem estar no mesmo cluster que LA-NY, mas provavelmente não San Francisco para Boston) e não há pontos intermediários. Os dados de entrada seriam semelhantes a este exemplo:

(Por Cassiopeia sweet na Wikipedia japonesa GFDL ou CC-BY-SA-3.0 , via Wikimedia Commons)

Eu já tentei classificar as linhas com antecedência, por exemplo, para executá-las todas de oeste para leste, mas isso não resolve o problema das linhas de norte para sul e vice-versa.

Você conhece algum algoritmo que lida com esse problema? Eu estive procurando, mas além do Algoritmo, para calcular a direção média dos segmentos não direcionados , não encontrei nada útil remotamente, por isso devo estar usando os termos de pesquisa incorretos.

Se bem entendi, você deseja agrupar linhas que são praticamente as mesmas, sem respeitar a direção.

Aqui está uma ideia que eu acho que poderia funcionar.

1. divida as linhas no ponto inicial e final

2. Agrupe os pontos e obtenha o ID do cluster

3. Encontre linhas com a mesma combinação de ID do cluster. Esses são um cluster

Isso deve ser possível no PostGIS (é claro :-)) versão 2.3

Não testei a função ST_ClusterDBSCAN, mas ela deve fazer o trabalho.

Se você tem uma tabela de linhas como esta:

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

E você deseja criar o cluster no qual os pontos inicial e final estão a 10 km, no máximo. E deve haver pelo menos 2 pontos para haver um cluster, então a consulta pode 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

Ao se juntar a a.cluster_id<b.cluster_idvocê, você obtém um ID de cluster comparável, independentemente da direção.

Deseja realmente agrupar apenas por direção, sem nenhuma consideração de origem ou destino? Nesse caso, existem algumas maneiras muito simples. Talvez o mais fácil seja calcular o rumo de cada linha, dobrar isso e plotá-lo como um ponto em um círculo. Como os rolamentos para frente e para trás diferem em 180 graus, eles diferem em 360 graus após dobrar e, portanto, plotam exatamente no mesmo local. Agora agrupe os pontos no plano usando o método que desejar.

Aqui está um exemplo prático R, com sua saída mostrando as linhas coloridas de acordo com cada um dos quatro grupos. É claro que você provavelmente usaria um SIG para calcular os rolamentos - usei rolamentos 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))
)

Seu esclarecimento da pergunta indica que você deseja que o cluster seja baseado nos segmentos de linha reais , no sentido de que quaisquer dois pares de origem-destino (OD) devem ser considerados "próximos" quando ambas as origens estão próximas e os dois destinos estão próximos , independentemente de qual ponto é considerado origem ou destino .

Essa formulação sugere que você já tenha uma noção da distância d entre dois pontos: pode ser a distância que o avião voa, a distância no mapa, o tempo de viagem de ida e volta ou qualquer outra métrica que não mude quando O e D são comutado. A única complicação é que os segmentos não têm representações únicas: eles correspondem a pares não ordenados {O, D}, mas devem ser representados como pares ordenados , (O, D) ou (D, O). Portanto, podemos tomar a distância entre dois pares ordenados (O1, D1) e (O2, D2) como uma combinação simétrica das distâncias d (O1, O2) ed (D1, D2), como sua soma ou o quadrado raiz da soma de seus quadrados. Vamos escrever essa combinação como

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

Basta definir a distância entre pares não ordenados como a menor das duas distâncias possíveis:

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

Nesse ponto, você pode aplicar qualquer técnica de agrupamento com base em uma matriz de distância.

Como exemplo, calculei todas as 190 distâncias ponto a ponto no mapa para 20 das cidades mais populosas dos EUA e solicitei oito agrupamentos usando um método hierárquico. (Para simplificar, usei cálculos de distância euclidiana e apliquei os métodos padrão no software que estava usando: na prática, você desejará escolher distâncias apropriadas e métodos de agrupamento para o seu problema). Aqui está a solução, com os clusters indicados pela cor de cada segmento de linha. (As cores foram atribuídas aleatoriamente aos clusters.)

Aqui está o Rcódigo que produziu este exemplo. Sua entrada é um arquivo de texto com os campos "Longitude" e "Latitude" para as cidades. (Para rotular as cidades na figura, também inclui um campo "Chave").

#
# 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)