Mengelompokkan garis tidak diarahkan

Saya mencari cara yang efisien untuk mengelompokkan garis yang terlepas dari arahnya. Itu berarti bahwa garis antara New York dan Los Angeles harus berada dalam kelompok yang sama dengan garis ke arah lain antara Los Angeles dan New York. Lokasi titik awal / akhir harus serupa (mis. San Diego ke Long Island harus berada dalam kelompok yang sama dengan LA-NY tetapi mungkin bukan San Francisco ke Boston) dan tidak ada titik menengah. Input data akan mirip dengan contoh ini:

(Oleh Cassiopeia manis di Wikipedia Jepang GFDL atau CC-BY-SA-3.0 , via Wikimedia Commons)

Saya sebelumnya telah mencoba untuk mengurutkan garis di muka, misalnya untuk membuat mereka semua berjalan dari barat ke timur, tetapi ini tidak menyelesaikan masalah untuk jalur yang berjalan dari utara ke selatan dan sebaliknya.

Apakah Anda tahu ada algoritma yang menangani masalah ini? Saya telah mencari tetapi selain Algoritma untuk menghitung arah rata-rata segmen yang tidak diarahkan, saya belum menemukan sesuatu yang membantu, jadi saya harus menggunakan istilah pencarian yang salah.

Jika saya mengerti Anda benar, Anda ingin mengelompokkan garis yang hampir sama tanpa memperhatikan arah.

Ini ide yang menurut saya bisa berhasil.

1. bagi garis menjadi titik awal dan titik akhir

2. Klaster poin dan dapatkan id cluster

3. Temukan baris dengan kombinasi id cluster yang sama. Itu adalah sebuah cluster

Ini harus dimungkinkan dalam PostGIS (tentu saja :-)) versi 2.3

Saya belum menguji fungsi ST_ClusterDBSCAN, tetapi harus melakukan pekerjaan.

Jika Anda memiliki tabel garis seperti ini:

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

Dan Anda ingin membuat cluster di mana titik awal dan akhir berjarak maksimum 10 km. Dan harus ada setidaknya 2 poin untuk menjadi sebuah cluster maka kueri dapat berupa sesuatu seperti:

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

Dengan bergabung dengan a.cluster_id<b.cluster_idAnda, dapatkan id cluster yang sebanding, tidak bergantung pada arah.

Apakah Anda benar-benar ingin mengelompokkan berdasarkan petunjuk, tanpa mempertimbangkan asal atau tujuan? Jika demikian, ada beberapa cara yang sangat sederhana. Mungkin yang termudah adalah menghitung bantalan setiap garis, menggandakannya, dan memplotnya sebagai titik pada lingkaran. Karena bantalan ke depan-belakang berbeda 180 derajat, mereka berbeda 360 derajat setelah digandakan dan karenanya memplot tepat di tempat yang sama. Sekarang mengelompokkan titik-titik di pesawat menggunakan metode apa pun yang Anda suka.

Berikut adalah contoh kerja R, dengan outputnya menunjukkan garis-garis berwarna sesuai dengan masing-masing empat cluster. Tentu saja Anda mungkin akan menggunakan GIS untuk menghitung bantalan - Saya menggunakan bantalan Euclidean untuk kesederhanaan.

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

Klarifikasi pertanyaan Anda menunjukkan bahwa Anda ingin pengelompokan didasarkan pada segmen garis yang sebenarnya , dalam arti bahwa dua pasangan asal-tujuan (OD) harus dianggap "dekat" ketika salah satu dari kedua asal dekat dan kedua tujuan dekat. , terlepas dari titik mana yang dianggap asal atau tujuan .

Formulasi ini menunjukkan Anda sudah memiliki rasa jarak d antara dua titik: itu bisa berupa jarak ketika pesawat terbang, jarak pada peta, waktu perjalanan pulang pergi, atau metrik lain yang tidak berubah ketika O dan D sedang diaktifkan. Satu-satunya komplikasi adalah bahwa segmen tidak memiliki representasi unik: mereka sesuai dengan pasangan tidak berurutan {O, D} tetapi harus direpresentasikan sebagai pasangan berurutan , baik (O, D) atau (D, O). Karena itu, kita dapat mengambil jarak antara dua pasangan berurutan (O1, D1) dan (O2, D2) menjadi beberapa kombinasi simetris dari jarak d (O1, O2) dan d (D1, D2), seperti jumlah atau kuadratnya akar jumlah kotak mereka. Mari kita tuliskan kombinasi ini sebagai

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

Cukup tentukan jarak antara pasangan tak berurutan menjadi yang lebih kecil dari dua jarak yang mungkin:

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

Pada titik ini Anda dapat menerapkan teknik pengelompokan apa pun berdasarkan matriks jarak.

Sebagai contoh, saya menghitung semua 190 jarak point-to-point di peta untuk 20 kota paling padat di AS dan meminta delapan cluster menggunakan metode hierarkis. (Untuk kesederhanaan saya menggunakan perhitungan jarak Euclidean dan menerapkan metode default pada perangkat lunak yang saya gunakan: dalam praktiknya Anda akan ingin memilih jarak yang tepat dan metode pengelompokan untuk masalah Anda). Inilah solusinya, dengan kluster yang ditunjukkan oleh warna setiap segmen garis. (Warna ditugaskan secara acak ke kluster.)

Berikut adalah Rkode yang menghasilkan contoh ini. Inputnya adalah file teks dengan bidang "Longitude" dan "Latitude" untuk kota-kota. (Untuk memberi label kota-kota pada gambar, itu juga termasuk bidang "Kunci".)

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