Algoritma untuk mengetahui titik belok untuk polyline

Saya mencoba mencari tahu titik belok, yaitu titik di mana kurva dalam garis mulai dan berakhir. Jika Anda melihat gambar, garis hijau mungkin jalan atau aliran, dan titik hitam adalah titik di mana kurva mulai dan berakhir.

Apa langkah tingkat tinggi untuk mengotomatiskan pembangkitan poin-poin ini? Saya memiliki desktop ArcGIS dan cukup berguna dengan ArcObjects.

Ketika kurva terdiri dari segmen garis, maka semua titik interior segmen tersebut adalah titik belok, yang tidak menarik. Sebagai gantinya, kurva harus dianggap sebagai didekati oleh simpul dari segmen tersebut. Dengan melipatgandakan kurva yang dapat didiferensiasi dua kali melalui segmen-segmen tersebut, kita dapat menghitung kelengkungannya. Titik belok, sebenarnya, adalah tempat di mana kelengkungannya nol.

Dalam contoh ada peregangan gondrong di mana kelengkungan hampir nol. Ini menunjukkan bahwa titik-titik yang diindikasikan harus mendekati ujung bentangan seperti daerah berlengkungan rendah.

Algoritme yang efektif karena itu akan melakukan spline simpul, menghitung kelengkungan di sepanjang set padat titik menengah, mengidentifikasi rentang kelengkungan mendekati nol (menggunakan beberapa perkiraan yang masuk akal dari apa artinya menjadi "dekat"), dan menandai titik akhir dari rentang tersebut .

Berikut adalah Rkode yang berfungsi untuk menggambarkan ide-ide ini. Mari kita mulai dengan string garis yang dinyatakan sebagai urutan koordinat:

xy <- matrix(c(5,20, 3,18, 2,19, 1.5,16, 5.5,9, 4.5,8, 3.5,12, 2.5,11, 3.5,3, 
               2,3, 2,6, 0,6, 2.5,-4, 4,-5, 6.5,-2, 7.5,-2.5, 7.7,-3.5, 6.5,-8), ncol=2, byrow=TRUE)

Spline koordinat x dan y secara terpisah untuk mencapai parameterisasi kurva. (Parameter akan dipanggil time.)

n <- dim(xy)[1]
fx <- splinefun(1:n, xy[,1], method="natural")
fy <- splinefun(1:n, xy[,2], method="natural")

Interpolasi splines untuk merencanakan dan menghitung:

time <- seq(1,n,length.out=511)
uv <- sapply(time, function(t) c(fx(t), fy(t)))

Kita membutuhkan fungsi untuk menghitung kelengkungan kurva parameter. Perlu memperkirakan turunan pertama dan kedua dari spline. Dengan banyak splines (seperti splines kubik) ini adalah perhitungan aljabar yang mudah. Rmenyediakan tiga turunan pertama secara otomatis. (Di lingkungan lain, seseorang mungkin ingin menghitung turunan secara numerik.)

curvature <- function(t, fx, fy) {
  # t is an argument to spline functions fx and fy.
  xp <- fx(t,1); yp <- fy(t,1)            # First derivatives
  xpp <- fx(t,2); ypp <- fy(t,2)          # Second derivatives
  v <- sqrt(xp^2 + yp^2)                  # Speed
  (xp*ypp - yp*xpp) / v^3                 # (Signed) curvature
  # (Left turns have positive curvature; right turns, negative.)
}

kappa <- abs(curvature(time, fx, fy))     # Absolute curvature of the data

Saya mengusulkan untuk memperkirakan ambang batas untuk kelengkungan nol dalam hal luasnya kurva. Setidaknya ini adalah titik awal yang baik; itu harus disesuaikan sesuai dengan tortuosity kurva (yaitu, meningkat untuk kurva yang lebih panjang). Ini nantinya akan digunakan untuk mewarnai plot sesuai dengan kelengkungan.

curvature.zero <- 2*pi / max(range(xy[,1]), range(xy[,2])) # A small threshold
i.col <- 1 + floor(127 * curvature.zero/(curvature.zero + kappa)) 
palette(terrain.colors(max(i.col)))                        # Colors

Sekarang setelah simpul telah dibulatkan dan kelengkungan dihitung, itu tetap hanya untuk menemukan titik belok . Untuk menunjukkan kepada mereka, kita dapat merencanakan simpul, plot spline, dan menandai titik belok di atasnya.

plot(xy, asp=1, xlab="x",ylab="y", type="n")
tmp <- sapply(2:length(kappa), function(i) lines(rbind(uv[,i-1],uv[,i]), lwd=2, col=i.col[i]))
points(t(sapply(time[diff(kappa < curvature.zero/2) != 0], 
       function(t) c(fx(t), fy(t)))), pch=19, col="Black")
points(xy)

Titik terbuka adalah simpul asli xydan titik hitam adalah titik belok yang secara otomatis diidentifikasi dengan algoritma ini. Karena lengkungan tidak dapat dihitung secara andal di titik akhir kurva, titik-titik tersebut tidak ditandai secara khusus.

Anda dapat menggunakan alat Densify . Untuk kasus ini, Anda memilih untuk memadatkan dengan sudut, Berikutnya, pilih sudut maksimum yang diterima dalam garis lurus. Kemudian oleskan ke baris hasil ke garis Pisahkan alat pada simpul . Akhirnya, hapus garis yang memiliki shape_length lebih kecil dari panjang jalan minimum.

Dalam gambar ini, kita melihat tiga langkah:

1- Densifikasi garis menggunakan sudut. Saya telah menggunakan 10 derajat sebagai parameter, dan kami menggunakan splitline. Dalam gambar, garis lengkung berada pada fase awal.

arcpy.Densify_edit("line" , "ANGLE" , "","",10)
arcpy.SplitLine_management("line" , "line_split")

2 - Pilih segmen di mana memiliki shape_length tidak berlebihan. Seperti yang kita lihat dalam tabel, saya belum memilih panjang yang berlebihan itu. Lalu, saya memilih mereka menjadi kelas fitur baru.

arcpy.Select_analysis("line_split" , "line_split_selected")

3 - Kami telah mengekstrak simpul yang terletak di tepi garis, yang merupakan titik belok.

arcpy.FeatureVerticesToPoints_management("line_split_selected" , "line_split_pnt" , "DANGLE")

Anda dapat menggunakan alat Generalisasi yang memiliki offset maksimum dari garis asli sebagai parameter, sehingga Anda dapat memilih offset yang sesuai dengan kasus Anda.

Jika kita beri nama baris asli "line_cur", dan yang umum "line_gen", maka kita bisa memotong "line_cur" dengan "line_gen". Hasilnya akan menjadi segmen lurus "line_cur". Lalu kita bisa membersihkan beberapa segmen yang sangat pendek dengan menghapusnya dengan kueri sql yang memilih Shape_length lebih besar dari panjang jalan minimum.