Menghaluskan poligon di peta kontur?

Berikut adalah peta kontur yang tersedia untuk semua poligon levelnya.

Mari kita tanyakan bagaimana cara menghaluskan poligon menjaga semua simpul dipertahankan di lokasi yang tepat?

Memang kontur dibuat di atas data kisi, Anda dapat menyarankan untuk memuluskan data kisi dan karenanya kontur yang dihasilkan akan lebih halus. Perhatikan bahwa ini tidak berfungsi sesuai keinginan saya karena fungsi penghalusan seperti filter Gaussian akan menghapus paket kecil data dan akan mengubah rentang variabel ketiga mis. Tinggi yang tidak diperbolehkan dalam aplikasi saya.

Sebenarnya saya sedang mencari sepotong kode (lebih disukai dengan Python ) yang dapat melakukan smoothing dari poligon 2D (semua jenis: cembung, cekung, berpotongan diri dll) cukup menyakitkan (lupa halaman kode) dan akurat.

FYI, ada fungsi di ArcGIS yang melakukan ini dengan sempurna, tetapi menggunakan aplikasi komersial pihak ketiga bukanlah pilihan saya untuk pertanyaan ini.

1)

Scipy.interpolate:

Seperti yang Anda lihat, splines yang dihasilkan (merah) tidak memuaskan!

2)

Ini hasilnya menggunakan kode yang diberikan di sini . Itu tidak berfungsi dengan baik!

3)

Bagi saya solusi terbaik haruslah sesuatu seperti gambar berikut di mana sebuah persegi sedang dihaluskan secara bertahap dengan mengubah hanya satu nilai. Saya berharap konsep serupa untuk menghaluskan segala bentuk poligon.

Memuaskan kondisi yang spline melewati poin:

4)

Ini adalah implementasi saya dari "ide ide" baris demi baris dengan Python pada datanya. Mungkin ada beberapa bug karena hasilnya tidak bagus.

K = 2 adalah bencana dan untuk k> = 4.

5)

Saya menghapus satu titik di lokasi bermasalah dan spline yang dihasilkan sekarang identik dengan milik whuber. Tetapi masih menjadi pertanyaan mengapa metode ini tidak bekerja untuk semua kasus?

6)

Perataan yang baik untuk data whuber dapat berupa sebagai berikut (digambar oleh perangkat lunak grafik vektor) di mana titik ekstra telah ditambahkan dengan lancar (bandingkan dengan pembaruan

4):

7)

Lihat hasil dari versi Python dari kode whuber untuk beberapa bentuk ikon:

Perhatikan bahwa metode ini tampaknya tidak berfungsi untuk polyline. Untuk sudut polyline (kontur) hijau adalah yang saya inginkan tetapi mendapat merah. Ini perlu diatasi karena peta kontur selalu polylines meskipun polyline tertutup dapat diperlakukan sebagai poligon seperti pada contoh saya. Juga bukan masalah yang muncul di pembaruan 4 belum diatasi.

8) [yang terakhir]

Inilah solusi terakhir (tidak sempurna!):

Ingatlah bahwa Anda harus melakukan sesuatu tentang area yang ditunjukkan oleh bintang. Mungkin ada bug dalam kode saya atau metode yang diusulkan perlu pengembangan lebih lanjut untuk mempertimbangkan semua situasi dan untuk memberikan hasil yang diinginkan.

Sebagian besar metode untuk spline urutan angka akan spline poligon. Caranya adalah membuat splines "menutup" dengan lancar di titik akhir. Untuk melakukan ini, "bungkus" simpul di sekitar ujungnya. Kemudian spline koordinat x dan y secara terpisah.

Berikut adalah contoh yang berfungsi di R. Ini menggunakan splineprosedur kubik default yang tersedia dalam paket statistik dasar. Untuk kontrol lebih banyak, gantilah hampir semua prosedur yang Anda inginkan: pastikan itu merambat melalui angka-angka (yaitu, interpolasi mereka) daripada hanya menggunakannya sebagai "titik kontrol."

#
# Splining a polygon.
#
#   The rows of 'xy' give coordinates of the boundary vertices, in order.
#   'vertices' is the number of spline vertices to create.
#              (Not all are used: some are clipped from the ends.)
#   'k' is the number of points to wrap around the ends to obtain
#       a smooth periodic spline.
#
#   Returns an array of points. 
# 
spline.poly <- function(xy, vertices, k=3, ...) {
    # Assert: xy is an n by 2 matrix with n >= k.

    # Wrap k vertices around each end.
    n <- dim(xy)[1]
    if (k >= 1) {
        data <- rbind(xy[(n-k+1):n,], xy, xy[1:k, ])
    } else {
        data <- xy
    }

    # Spline the x and y coordinates.
    data.spline <- spline(1:(n+2*k), data[,1], n=vertices, ...)
    x <- data.spline$x
    x1 <- data.spline$y
    x2 <- spline(1:(n+2*k), data[,2], n=vertices, ...)$y

    # Retain only the middle part.
    cbind(x1, x2)[k < x & x <= n+k, ]
}

Untuk menggambarkan penggunaannya, mari kita buat poligon kecil (tapi rumit).

#
# Example polygon, randomly generated.
#
set.seed(17)
n.vertices <- 10
theta <- (runif(n.vertices) + 1:n.vertices - 1) * 2 * pi / n.vertices
r <- rgamma(n.vertices, shape=3)
xy <- cbind(cos(theta) * r, sin(theta) * r)

Spline menggunakan kode sebelumnya. Untuk membuat spline lebih halus, tambah jumlah simpul dari 100; untuk membuatnya kurang lancar, kurangi jumlah simpul.

s <- spline.poly(xy, 100, k=3)

Untuk melihat hasilnya, kami memplot (a) poligon asli dengan tanda hubung merah, menunjukkan celah antara simpul pertama dan terakhir (yaitu, tidak menutup polyline batasnya); dan (b) spline berwarna abu-abu, sekali lagi menunjukkan celahnya. (Karena jaraknya sangat kecil, titik akhirnya disorot dengan titik-titik biru.)

plot(s, type="l", lwd=2, col="Gray")
lines(xy, col="Red", lty=2, lwd=2)
points(xy, col="Red", pch=19)
points(s, cex=0.8)
points(s[c(1,dim(s)[1]),], col="Blue", pch=19)

Saya tahu ini adalah posting lama, tetapi muncul di Google untuk sesuatu yang saya cari, jadi saya pikir saya akan memposting solusi saya.

Saya tidak melihat ini sebagai latihan pemasangan kurva 2D, melainkan latihan 3D. Dengan mempertimbangkan data sebagai 3D, kami dapat memastikan bahwa kurva tidak saling bersilangan, dan dapat menggunakan informasi dari kontur lain untuk meningkatkan perkiraan kami untuk yang saat ini.

Ekstrak iPython berikut menggunakan interpolasi kubik yang disediakan oleh SciPy. Perhatikan bahwa nilai z yang saya plot tidak penting, selama semua kontur sama tingginya.

In [1]: %pylab inline
        pylab.rcParams['figure.figsize'] = (10, 10)
        Populating the interactive namespace from numpy and matplotlib

In [2]: import scipy.interpolate as si

        xs = np.array([0.0, 0.0, 4.5, 4.5,
                       0.3, 1.5, 2.3, 3.8, 3.7, 2.3,
                       1.5, 2.2, 2.8, 2.2,
                       2.1, 2.2, 2.3])
        ys = np.array([0.0, 3.0, 3.0, 0.0,
                       1.1, 2.3, 2.5, 2.3, 1.1, 0.5,
                       1.1, 2.1, 1.1, 0.8,
                       1.1, 1.3, 1.1])
        zs = np.array([0,   0,   0,   0,
                       1,   1,   1,   1,   1,   1,
                       2,   2,   2,   2,
                       3,   3,   3])
        pts = np.array([xs, ys]).transpose()

        # set up a grid for us to resample onto
        nx, ny = (100, 100)
        xrange = np.linspace(np.min(xs[zs!=0])-0.1, np.max(xs[zs!=0])+0.1, nx)
        yrange = np.linspace(np.min(ys[zs!=0])-0.1, np.max(ys[zs!=0])+0.1, ny)
        xv, yv = np.meshgrid(xrange, yrange)
        ptv = np.array([xv, yv]).transpose()

        # interpolate over the grid
        out = si.griddata(pts, zs, ptv, method='cubic').transpose()

        def close(vals):
            return np.concatenate((vals, [vals[0]]))

        # plot the results
        levels = [1, 2, 3]
        plt.plot(close(xs[zs==1]), close(ys[zs==1]))
        plt.plot(close(xs[zs==2]), close(ys[zs==2]))
        plt.plot(close(xs[zs==3]), close(ys[zs==3]))
        plt.contour(xrange, yrange, out, levels)
        plt.show()

Hasil di sini tidak terlihat yang terbaik, tetapi dengan begitu sedikit titik kontrol mereka masih valid sempurna. Perhatikan bagaimana garis hijau dipasang keluar untuk mengikuti kontur biru yang lebih luas.

Saya menulis hampir persis paket yang Anda cari ... tapi itu di Perl, dan lebih dari satu dekade yang lalu: GD :: Polyline . Ini menggunakan kurva Bezier 2D kubik, dan akan "memuluskan" Poligon sewenang-wenang atau "Polyline" (nama saya kemudian untuk apa yang sekarang biasa disebut "LineString").

Algoritma itu dua langkah: diberi titik di Polygon, tambahkan dua titik kontrol Bezier antara setiap titik; lalu panggil algoritma sederhana untuk membuat perkiraan sedikit demi sedikit dari spline.

Bagian kedua mudah; bagian pertama adalah sedikit seni. Berikut adalah wawasan: mempertimbangkan "control segmen" a Vertex N: vN. Segmen kontrol adalah tiga co-linear poin: [cNa, vN, cNb]. Titik pusat adalah titik. Kemiringan seg kontrol ini sama dengan kemiringan dari Vertex N-1 ke Vertex N + 1. Panjang bagian kiri segmen ini adalah 1/3 panjang dari Vertex N-1 ke Vertex N, dan panjang bagian kanan segmen ini adalah 1/3 panjang dari Vertex N ke Vertex N +1.

Jika kurva asli empat simpul: [v1, v2, v3, v4]maka setiap sudut sekarang mendapatkan segmen kontrol dalam bentuk: [c2a, v2, c2b]. Rangkai semuanya seperti ini: [v1, c1b, c2a, v2, c2b, c3a, v3, c3b, c4a, v4]dan kukus empat sekaligus sebagai empat poin Bezier:, [v1, c1b, c2a, v2]lalu [v2, c2b, c3a, v3], dan seterusnya. Karena [c2a, v2, c2b]bersifat co-linear, kurva yang dihasilkan akan halus di setiap dhuwur.

Jadi ini juga memenuhi persyaratan Anda untuk parameter "keketatan" kurva: gunakan nilai yang lebih kecil dari 1/3 untuk kurva "lebih ketat", yang lebih besar untuk cocok "loopier". Dalam kedua kasus, kurva yang dihasilkan selalu melewati titik-titik asli yang diberikan.

Ini menghasilkan kurva halus yang "membatasi" Polygon asli. Saya juga punya beberapa cara untuk "menuliskan" kurva yang halus ... tapi saya tidak melihatnya dalam kode CPAN.

Lagi pula, saya saat ini tidak memiliki versi yang tersedia dalam Python, saya juga tidak memiliki angka. TAPI ... jika / ketika saya melakukan port ini ke Python, saya pasti akan memposting di sini.