Grupowanie nieukierunkowanych linii

Szukam skutecznego sposobu zgrupowania linii niezależnie od ich kierunku. Oznacza to, że linia między Nowym Jorkiem a Los Angeles powinna znajdować się w tym samym klastrze, co linia w innym kierunku między Los Angeles i Nowym Jorkiem. Lokalizacje punktów początkowych / końcowych powinny być podobne (tj. San Diego do Long Island powinny znajdować się w tej samej grupie co LA-NY, ale prawdopodobnie nie San Francisco do Bostonu) i nie ma punktów pośrednich. Dane wejściowe byłyby podobne do tego przykładu:

(Autor: Cassiopeia sweet z japońskiej Wikipedii GFDL lub CC-BY-SA-3.0 , za pośrednictwem Wikimedia Commons)

Wcześniej próbowałem posortować linie z wyprzedzeniem, np. Aby wszystkie biegły z zachodu na wschód, ale to nie rozwiązuje problemu dla linii biegnących z północy na południe i na odwrót.

Czy znasz jakiś algorytm radzący sobie z tym problemem? Szukałem, ale oprócz algorytmu do obliczania średniego kierunku przekierowanych segmentów nie znalazłem nic zdalnie pomocnego, więc muszę używać niewłaściwych wyszukiwanych terminów.

Jeśli dobrze cię rozumiem, chcesz zgrupować linie, które są mniej więcej takie same bez względu na kierunek.

Oto pomysł, który moim zdaniem mógłby zadziałać.

1. podziel linie w punkcie początkowym i końcowym

2. Zbierz punkty i uzyskaj identyfikator klastra

3. Znajdź linie o tej samej kombinacji identyfikatora klastra. To są gromady

Powinno to być możliwe w PostGIS (oczywiście :-)) w wersji 2.3

Nie testowałem funkcji ST_ClusterDBSCAN, ale powinna działać.

Jeśli masz taką tabelę wiersza:

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

I chcesz utworzyć klaster, w którym punkty początkowy i końcowy znajdują się w odległości maksymalnie 10 km od siebie. Aby klaster mógł istnieć co najmniej 2 punkty, zapytanie może wyglądać następująco:

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

Łącząc się a.cluster_id<b.cluster_id, otrzymasz porównywalny identyfikator klastra niezależnie od kierunku.

Czy naprawdę chcesz skupiać się wyłącznie według kierunku, bez względu na pochodzenie lub miejsce docelowe? Jeśli tak, istnieje kilka bardzo prostych sposobów. Być może najłatwiej jest obliczyć namiar każdej linii, podwoić ją i narysować jako punkt na okręgu. Ponieważ łożyska do przodu i do tyłu różnią się o 180 stopni, różnią się o 360 stopni po podwojeniu, a zatem drukują w dokładnie tym samym miejscu. Teraz skup punkty w płaszczyźnie za pomocą dowolnej metody.

Oto działający przykład R, którego wynik pokazuje linie pokolorowane zgodnie z każdym z czterech klastrów. Oczywiście prawdopodobnie użyłbyś GIS do obliczenia łożysk - dla uproszczenia użyłem łożysk euklidesowych.

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

Wyjaśnienie pytania wskazuje, że chciałbyś, aby klastrowanie opierało się na rzeczywistych segmentach linii , w tym sensie, że dowolne dwie pary początek-miejsce docelowe (OD) powinny być uważane za „zamknięte”, gdy oba początki są bliskie, a oba miejsca docelowe są bliskie , niezależnie od tego, który punkt uważa się za początek lub cel podróży .

Ta formuła sugeruje, że masz już wyczucie odległości d między dwoma punktami: może to być odległość podczas lotu samolotu, odległość na mapie, czas podróży w obie strony lub jakikolwiek inny parametr, który nie zmienia się, gdy O i D są zamieniono. Jedyną komplikacją jest to, że segmenty nie mają unikalnych reprezentacji: odpowiadają one nieuporządkowanym parom {O, D}, ale muszą być reprezentowane jako pary uporządkowane , (O, D) lub (D, O). Możemy zatem przyjąć odległość między dwiema uporządkowanymi parami (O1, D1) i (O2, D2), aby być jakąś symetryczną kombinacją odległości d (O1, O2) id (D1, D2), takich jak ich suma lub kwadrat pierwiastek z sumy ich kwadratów. Napiszmy tę kombinację jako

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

Wystarczy zdefiniować odległość między nieuporządkowanymi parami, aby była mniejsza z dwóch możliwych odległości:

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

W tym momencie możesz zastosować dowolną technikę grupowania opartą na macierzy odległości.

Jako przykład obliczyłem wszystkie 190 odległości punkt-punkt na mapie dla 20 najbardziej zaludnionych amerykańskich miast i poprosiłem o osiem klastrów przy użyciu metody hierarchicznej. (Dla uproszczenia użyłem euklidesowych obliczeń odległości i zastosowałem domyślne metody w używanym przeze mnie oprogramowaniu: w praktyce będziesz chciał wybrać odpowiednie odległości i metody grupowania dla swojego problemu). Oto rozwiązanie z klastrami oznaczonymi kolorem każdego segmentu linii. (Kolory zostały losowo przypisane do klastrów).

Oto Rkod, który wytworzył ten przykład. Jego dane wejściowe to plik tekstowy z polami „Długość geograficzna” i „Szerokość geograficzna” dla miast. (Aby oznaczyć miasta na rysunku, zawiera również pole „Klucz”).

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