Algoritma pengelompokan spasial inkremental

Saya sedang mencari algoritma pengelompokan spasial tambahan . Berikut ini adalah kasus penggunaan saya:

• pengguna membuat entri dengan posisi awal
• pengguna dapat mengubah posisi entri yang ada

Saya sekarang ingin mengimplementasikan layanan dipisahkan yang menyediakan informasi pengelompokan data ini. Layanan akan diberitahu setiap kali entri baru telah ditambahkan atau entri yang sudah ada telah dipindahkan. Apa itu algoritma pengelompokan yang bagus? Idealnya, itu harus skala hingga jumlah data yang tinggi dan jika ada trade-off antara kualitas cluster dan kompleksitas runtime, saya baik-baik saja dengan hasil yang merendahkan, dan akhirnya hasil yang konsisten (hasil basi baik-baik saja untuk beberapa waktu).

Untuk meringkas persyaratan saya:

• pengelompokan spasial berdasarkan posisi
• modifikasi tambahan pada perubahan
• tambahkan posisi baru
• ubah posisi yang ada
• kinerja runtime yang baik

Terima kasih sebelumnya!

Tujuan dari pengelompokan ini adalah untuk menyederhanakan tampilan simbol titik: ketika banyak yang berdekatan pada peta, mereka akan digantikan oleh simbol tunggal untuk menunjukkan grup.

Persyaratan menunjukkan perlunya solusi adaptif yang sederhana : simbol titik dapat diperbarui dan saat pengguna memperbesar, simbol yang berbeda akan muncul di tempat yang berbeda pada tingkat peta (atau layar).

Calon yang sangat baik jelas adalah quadtree wilayah .

Ada metode yang lebih sederhana yang akan bertindak seperti quadtree wilayah. Ini membutuhkan lebih sedikit pengkodean, tidak ada pembuatan struktur data terlebih dahulu, tetapi Anda membayar harga (kecil) dengan perlu melakukan beberapa kalkulasi on-the-fly selama zooming dan panning. Cukup kisi peta . Secara khusus, anggaplah ada simbol titik n yang akan ditarik dalam batas peta saat ini yang memiliki panjang dx dan ketinggian dy . Relatif terhadap asal peta simbol perlu digambar pada koordinat ( x [i] , y [i] ), i = 1, 2, ..., n . Memilih ukuran sel kisi dari partisi c peta menjadi kisi sel. Sel tempat lokasi (x , y ) milik berada di baris j ( y ) = Lantai [ y / c ] dan kolom j ( x ) (dihitung dari 0, dengan baris dari bawah ke atas dan kolom dari kiri ke kanan). Anda dapat menganggap sel mana saja yang menerima dua atau lebih poin sebagai "cluster". Simbol klaster dapat digambar di pusat sel, yang memiliki koordinat. ( J + c / 2, k + c / 2).

Ini mengarah ke solusi berikut, disajikan dalam pseudocode:

m = Floor(dy/c)+1
n = Floor(dx/c)+1
Dimension a[m,n] = 0
For each (x[i], y[i]) to be displayed:
    Increment( a[ j(y[i]), j(x[i]) ] )
End for
For each (x[i], y[i]) to be displayed:
    row = j(y[i])
    col = j(x[i])
    If  a[row, col] > 1:
        Draw a symbol for a cluster of k points at (c*(col+0.5), c*(row+0.5))
        a[row, col] = 0
    Else
        Draw a point symbol at (x[i], y[i])
    End if
End for

Jelas beban komputasi algoritma adalah O (# poin) dalam waktu dan O (dx * dy / c ^ 2) dalam penyimpanan. Imbalan yang terlibat dalam memilih cellsize c adalah:

1. c harus sebesar mungkin: Penyimpanan berbanding terbalik dengan c ^ 2: nilai kecil c berarti sejumlah besar RAM. (Penyimpanan dapat dikurangi menjadi O (# poin) dengan menggunakan array jarang atau kamus.)

2. c harus sebesar mungkin: Dua simbol (titik atau kelompok) tidak akan pernah lebih dekat dari c / 2.

3. c harus sekecil mungkin: setiap simbol cluster mewakili lokasi tidak lebih dari c / sqrt (2) dari itu.

4. c harus sekecil mungkin: Nilai-nilai c yang besar cenderung membuat banyak kelompok dan memungkinkan beberapa titik individual muncul.

Mari kita lakukan analisis cepat (4). Sebagai titik tolak, misalkan lokasi yang akan dipetakan terjadi secara seragam secara acak dan terpisah satu sama lain. Jumlah sel adalah N ( c ) = (Lantai ( dx / c ) +1) * (Lantai ( dy / c ) +1), yang - setidaknya untuk nilai yang lebih besar dari c - berbanding lurus dengan c ^ 2. Distribusi jumlah sel kira-kira akan mengikuti hukum Poisson dengan intensitas lambda = n / N ( c ) = n * c ^ 2 / ( dx * dy). Jumlah cluster yang diharapkan sama dengan

e ( c ) = n (1 - exp (- lambda ) (1 + lambda )).

Ini menjadi lebih kecil karena lambda menyusut menjadi 0; yaitu, selsi c semakin kecil. Maksud dari analisis ini adalah bahwa rumus sebelumnya memungkinkan Anda mengantisipasi berapa banyak kluster yang mungkin ada, sehingga Anda dapat memilih nilai awal c yang e ( c ) di bawah nilai yang dapat diterima (sementara masih cukup besar untuk membatasi RAM Persyaratan). Tidak ada solusi bentuk tertutup, tetapi beberapa langkah Newton-Raphson akan menyatu menjadi satu dengan cepat.

Pendekatan ini sangat dinamis - cukup cepat sehingga pengelompokan grid dan konsekuen dapat dihitung dengan setiap zoom dan pan, dan tidak memerlukan struktur data yang dikomputasi - sehingga "modifikasi tambahan" yang diinginkan saat data diperbarui akan terjadi secara otomatis.

Apakah Anda mencari sesuatu seperti http://dev.openlayers.org/releases/OpenLayers-2.10/examples/strategy-cluster-threshold.html ? Jika demikian, kode tidak boleh terlalu sulit untuk diikuti.