Menggambar garis antara titik-titik pada jarak tertentu di PostGIS?

9

Saya memiliki data titik di sepanjang jalan, saya ingin mengubah titik-titik itu menjadi garis berwarna sederhana. Adakah petunjuk apa masalah ini dapat disebut atau algoritma yang dapat membantu saya menyelesaikan ini? Poin di sepanjang jalan saya ingin berubah menjadi garis.

Saya berharap menggunakan PostGISfungsi untuk melakukan ini tetapi saya terbuka untuk saran, ini adalah data dari .shpfile.

Sunting1: Diperbarui gambar untuk menunjukkan solusi ideal dari masalah ini.

Menggambar garis akan murni berdasarkan jarak antara titik-titik itu, tidak ada lagi yang bisa saya gunakan untuk mengelompokkannya. Idealnya ini adalah titik pada jarak maksimum yang ditentukan di sepanjang garis yang diproyeksikan? Dan dengan memproyeksikan garis yang saya maksud menemukan titik 1 kemudian berikutnya yang terdekat dengan itu memproyeksikan garis dan memeriksa apakah ada titik pada garis ini pada jarak maksimal ke salah satu yang sudah ada di garis.

Mahakala
sumber
1
Perangkat lunak apa yang Anda rencanakan untuk digunakan?
ArMoraer
apakah Anda mencoba mengubahnya menjadi trotoar?
DPSSpatial
Saya berharap dapat menggunakan fungsi PostGIS untuk melakukan ini tetapi saya terbuka untuk saran, ini adalah data dari file .shp.
Mahakala
1
Bisakah Anda menunjukkan dengan tepat titik mana yang ingin Anda hubungkan pada gambar Anda atau pada gambar lain? Apakah hanya dua poin dalam satu waktu? Atau tiga? Apakah jarak antara titik-titik yang harus dihubungkan selalu sama atau atau "tepat" di bawah ambang batas tertentu?
Peter Horsbøll Møller
1
Terima kasih besar kepada @dbaston dan MarHoff, saya tidak akan punya waktu untuk menguji ide-ide Anda sampai akhir April, saya berharap saya dapat membagi karunia antara tetapi saya perlu memberikan ini kepada 1 dari Anda dan dbaston memberi saya beberapa pertanyaan juga melihat ke dalam jadi saya akan menerima jawabannya. Terima kasih kepada semua orang yang meluangkan waktu untuk menjawab! Komunitas hebat untuk menjadi bagian dari :-)
Mahakala

Jawaban:

8

Anda dapat menggunakan kueri rekursif untuk menjelajahi tetangga terdekat dari setiap titik mulai dari setiap ujung garis yang terdeteksi yang ingin Anda buat.

Prasyarat : siapkan layer postgis dengan poin Anda dan poin lain dengan objek multi-linestring tunggal yang berisi jalan Anda. Dua lapisan harus berada pada CRS yang sama. Ini adalah kode untuk set data uji yang saya buat, harap modifikasi sesuai kebutuhan. (Diuji pada postgres 9.2 dan postgis 2.1)

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

masukkan deskripsi gambar di sini

Berikut langkah-langkahnya :

  1. Buat untuk setiap titik daftar setiap tetangga dan jarak mereka yang memenuhi tiga kriteria ini.

    • Jarak tidak boleh melebihi ambang batas yang ditentukan pengguna (ini akan menghindari menghubungkan ke titik yang terisolasi) masukkan deskripsi gambar di sini
      graph_full as (
      SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
      FROM points a
      LEFT JOIN points b ON a.id<>b.id
      WHERE st_distance(a.geom,b.geom) <= 15
      ),
    • Jalur langsung tidak boleh melewati jalan masukkan deskripsi gambar di sini
      graph as (
      SELECt graph_full.*
      FROM graph_full RIGHT JOIN
      roads ON st_intersects(graph_full.geom,roads.geom) = false
      ),
    • Jarak tidak boleh melebihi rasio jarak yang ditentukan pengguna dari tetangga terdekat (ini harus mengakomodasi lebih baik digitalisasi tidak teratur daripada jarak tetap) Bagian ini sebenarnya terlalu sulit untuk diterapkan, melekat pada radius pencarian tetap

    Sebut saja tabel ini "grafik"

  2. Pilih ujung titik garis dengan bergabung ke grafik dan pertahankan hanya titik yang memiliki satu entri persis dalam grafik. masukkan deskripsi gambar di sini

    eol as (
    SELECT points.* FROM
    points  JOIN
    (SELECT id, count(*) FROM graph 
    GROUP BY id
    HAVING count(*)= 1) sel
    ON points.id = sel.id),

    Sebut saja tabel ini "eol" (end of line) dengan
    mudah? bahwa hadiah untuk melakukan grafik yang bagus tetapi hal-hal yang bertahan akan menjadi gila pada langkah berikutnya

  3. Menyiapkan kueri rekursif yang akan berputar dari tetangga ke tetangga mulai dari setiap hari masukkan deskripsi gambar di sini

    • Inisialisasi kueri rekursif menggunakan tabel eol dan menambahkan penghitung untuk kedalaman, agregator untuk path, dan konstruktor geometri untuk membangun garis
    • Pindah ke iterasi berikutnya dengan beralih ke tetangga terdekat menggunakan grafik dan periksa bahwa Anda tidak pernah mundur menggunakan jalur
    • Setelah iterasi selesai, simpan hanya jalur terpanjang untuk setiap titik awal (jika dataset Anda menyertakan persimpangan potensial antara garis ekspektasi, bagian itu akan membutuhkan lebih banyak kondisi)
    recurse_eol (id, link_id, depth, path, start_id, geom) AS (--initialisation
    SELECT id, link_id, depth, path, start_id, geom FROM (
        SELECT eol.id, graph.link_id,1 as depth,
        ARRAY[eol.id, graph.link_id] as path,
        eol.id as start_id,
        graph.geom as geom,
        (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
        FROM eol JOIn graph ON eol.id = graph.id 
        ) foo
    WHERE test = true
    
    UNION ALL ---here start the recursive part
    
    SELECT id, link_id, depth, path, start_id, geom  FROM (
        SELECT graph.id, graph.link_id, r.depth+1 as depth,
        path || graph.link_id as path,
        r.start_id,
        ST_union(r.geom,graph.geom) as geom,
        (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
        FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
    WHERE test = true AND depth < 1000), --this last line is a safe guard to stop recurring after 1000 run adapt it as needed

    Sebut saja tabel ini "recurse_eol"

  4. Pertahankan hanya garis terpanjang untuk setiap titik awal dan hapus setiap jalur duplikat yang tepat Contoh: jalur 1,2,3,5 DAN 5,3,2,1 adalah garis yang sama yang ditemukan oleh dua perbedaan "ujung jalur"

    result as (SELECT start_id, path, depth, geom FROM
    (SELECT *,
    row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
    (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
    FROM recurse_eol) foo
    WHERE  test_depth = true AND test_duplicate = true)
    
    SELECT * FROM result
  5. Secara manual memeriksa kesalahan yang tersisa (titik terisolasi, garis yang tumpang tindih, jalan berbentuk aneh)


Diperbarui seperti yang dijanjikan, saya masih tidak tahu mengapa kadang-kadang permintaan rekursif tidak memberikan hasil yang sama persis ketika mulai dari lawan dari baris yang sama sehingga beberapa duplikat mungkin tetap ada di lapisan hasil seperti sekarang.

Jangan ragu untuk bertanya, saya benar-benar mengerti bahwa kode ini membutuhkan lebih banyak komentar. Ini pertanyaan lengkapnya:

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

graph_full as (
    SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
    FROM points a
    LEFT JOIN points b ON a.id<>b.id
    WHERE st_distance(a.geom,b.geom) <= 15
    ),

graph as (
    SELECt graph_full.*
    FROM graph_full RIGHT JOIN
    roads ON st_intersects(graph_full.geom,roads.geom) = false
    ),

eol as (
    SELECT points.* FROM
    points  JOIN
        (SELECT id, count(*) FROM graph 
        GROUP BY id
        HAVING count(*)= 1) sel
    ON points.id = sel.id),


recurse_eol (id, link_id, depth, path, start_id, geom) AS (
    SELECT id, link_id, depth, path, start_id, geom FROM (
        SELECT eol.id, graph.link_id,1 as depth,
        ARRAY[eol.id, graph.link_id] as path,
        eol.id as start_id,
        graph.geom as geom,
        (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
        FROM eol JOIn graph ON eol.id = graph.id 
        ) foo
    WHERE test = true

UNION ALL
    SELECT id, link_id, depth, path, start_id, geom  FROM (
        SELECT graph.id, graph.link_id, r.depth+1 as depth,
        path || graph.link_id as path,
        r.start_id,
        ST_union(r.geom,graph.geom) as geom,
        (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
        FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
    WHERE test = true AND depth < 1000),

result as (SELECT start_id, path, depth, geom FROM
    (SELECT *,
    row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
    (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
    FROM recurse_eol) foo
WHERE  test_depth = true AND test_duplicate = true)

SELECT * FROM result
MarHoff
sumber
Hai @MarHoff, terima kasih atas jawaban Anda. Saya ingin mencari sesuatu. Saya tidak mengharapkan solusi lengkap, hanya petunjuk di mana mencari jawaban. Saya ingin lebih memahami ini dan saya akan terus menggali dan mungkin memiliki lebih banyak pertanyaan nanti. Saya perlu memahami algoritme Anda dan ini akan memakan waktu lama pula bagi saya :)
Mahakala
Punya skrip yang berfungsi, pratinjau di sini qgiscloud.com/MarHoff/test_qgiscloud_bis peringatan kecil untuk de-duplikasi tetap ... Tidak ada lagi karunia, tidak ada lagi tekanan kurasa, jadi saya akan merilis rilis ketika saya bisa. Teka-teki ini menyenangkan
MarHoff
terima kasih @MarHoff, jika saya bisa, saya akan membagi hadiah ini saya tidak bisa melihat bagaimana saya bisa memberi Anda poin, tapi terima kasih banyak untuk melihat ini dan bukti Anda. Tampak asli :)
Mahakala
Selesai Terima kasih untuk teka-tekinya, dan maaf karena mengomel. Jika jawaban lain melakukannya untuk Anda, maka itu benar-benar baik, kadang sederhana adalah yang terbaik ... Jawaban saya mungkin sedikit berlebihan. Meskipun contoh yang baik menggunakan CTE + permintaan rekursif + fungsi Windows + postgis pada satu permintaan;)
MarHoff
8

Seperti yang ditunjukkan oleh @FelixIP, langkah pertama adalah menemukan poin yang akan membentuk setiap baris. Anda dapat melakukan ini dengan menghubungi ST_ClusterWithin dengan jarak pemisahan maksimum Anda:

SELECT
  row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom 
FROM (
  SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
  FROM inputs) sq

Kemudian, Anda harus menggunakan beberapa heuristik untuk membangun garis melalui semua titik di setiap cluster. Misalnya, jika Anda dapat menganggap baris yang diinginkan sebagai Y-monoton, Anda dapat mengurutkan titik di setiap kluster dan mengumpankannya ke dalam ST_MakeLine . Menggabungkan bahwa semuanya akan terlihat seperti ini:

SELECT 
  ST_MakeLine(geom ORDER BY ST_Y(geom)) AS geom
FROM (
  SELECT row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom FROM (
    SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
    FROM inputs) sq) ssq 
GROUP BY cid
dbaston
sumber
Cara untuk pergi tetapi pendekatan Y-monoton (atau bahkan beralih antara X / Y-monoton) tidak akan berfungsi dengan baik jika kumpulan data berisi jalan yang melengkung. Apakah ini masalahnya? Algoritma pemesanan adalah bagian tersulit dari pertanyaan ini, IMHO.
MarHoff
@ MarsHoff: ya jalan melengkung akan menjadi masalah, tapi saya mencoba untuk mendapatkan sebagian besar data ditransformasikan secara otomatis dan sisanya perlu dilakukan secara manual. Atau saya akan terus menggali lebih dalam topik untuk mencari solusi tetapi mungkin butuh waktu lebih lama daripada meminta seseorang untuk memperbaiki data yang tersisa. Saya perlu mengevaluasi hasil untuk dapat memutuskan. Terima kasih untuk menunjukkan ini!
Mahakala
Statut disetel Saya hanya memikirkan trik yang perlu saya periksa ...
MarHoff
Apakah ada cara kuat untuk melakukan ini yang tidak melibatkan mencoba semua urutan poin yang mungkin, dan menemukan mana yang memberikan panjang total terpendek?
dbaston
Jika set poin ini selalu mengikuti jalan, Anda memproyeksikan posisi titik ke segmen jalan (ST_Line_Locate_Point), lalu memesan poin dengan hasilnya.
Travis