Indeks spasial RTree tidak menghasilkan perhitungan persimpangan yang lebih cepat

9

Saya punya beberapa kode yang saya gunakan untuk menentukan Shapely Polygon / MultiPolygons berpotongan dengan sejumlah Shapely LineStrings. Melalui jawaban atas pertanyaan ini , kodenya telah berubah dari ini:

import fiona
from shapely.geometry import LineString, Polygon, MultiPolygon, shape

# Open each layer
poly_layer = fiona.open('polygon_layer.shp')
line_layer = fiona.open('line_layer.shp')

# Convert to lists of shapely geometries
the_lines = [shape(line['geometry']) for line in line_layer]
the_polygons = [(poly['properties']['GEOID'], shape(poly['geometry'])) for poly in poly_layer]

# Check for Polygons/MultiPolygons that the LineString intersects with
covered_polygons = {}
for poly_id, poly in the_polygons:
    for line in the_lines:
        if poly.intersects(line):
            covered_polygons[poly_id] = covered_polygons.get(poly_id, 0) + 1

di mana setiap persimpangan yang mungkin diperiksa, untuk ini:

import fiona
from shapely.geometry import LineString, Polygon, MultiPolygon, shape
import rtree

# Open each layer
poly_layer = fiona.open('polygon_layer.shp')
line_layer = fiona.open('line_layer.shp')

# Convert to lists of shapely geometries
the_lines = [shape(line['geometry']) for line in line_layer]
the_polygons = [(poly['properties']['GEOID'], shape(poly['geometry'])) for poly in poly_layer]

# Create spatial index
spatial_index = rtree.index.Index()
for idx, poly_tuple in enumerate(the_polygons):
    _, poly = poly_tuple
    spatial_index.insert(idx, poly.bounds)

# Check for Polygons/MultiPolygons that the LineString intersects with
covered_polygons = {}
for line in the_lines:
    for idx in list(spatial_index.intersection(line.bounds)):
        if the_polygons[idx][1].intersects(line):
            covered_polygons[idx] = covered_polygons.get(idx, 0) + 1

di mana indeks spasial digunakan untuk mengurangi jumlah pemeriksaan persimpangan.

Dengan shapefile yang saya miliki (sekitar 4000 poligon, dan 4 baris), kode asli melakukan 12936 .intersection()pemeriksaan dan membutuhkan waktu sekitar 114 detik untuk dijalankan. Sepotong kode kedua yang menggunakan indeks spasial hanya melakukan 1816 .intersection()pemeriksaan tetapi juga membutuhkan waktu sekitar 114 detik untuk dijalankan.

Kode untuk membangun indeks spasial hanya membutuhkan waktu 1-2 detik untuk dijalankan, sehingga pemeriksaan 1816 pada potongan kode kedua menghabiskan waktu yang hampir sama untuk melakukan sebagaimana 12936 memeriksa dalam kode asli (sejak pemuatan shapefile dan mengkonversi ke geometri Shapely adalah sama di kedua bagian kode).

Saya tidak dapat melihat alasan mengapa indeks spasial akan membuat .intersects()cek lebih lama, jadi saya bingung mengapa ini terjadi.

Saya hanya bisa berpikir bahwa saya menggunakan indeks spasial RTree secara tidak benar. Pikiran?

derNincompoop
sumber

Jawaban:

6

Jawaban saya pada dasarnya didasarkan pada jawaban lain oleh @ gen di sini:

Penggabungan Spasial yang Lebih Efisien dengan Python tanpa QGIS, ArcGIS, PostGIS, dll

Dia mengusulkan solusi yang sama menggunakan dua metode berbeda, dengan atau tanpa indeks spasial.

Dia (dengan benar) menyatakan:

Apa bedanya ?

  • Tanpa indeks, Anda harus mengulangi semua geometri (poligon dan titik).
  • Dengan indeks spasial pembatas ( Indeks Tata Ruang RTree ), Anda beralih hanya melalui geometri yang memiliki peluang untuk berpotongan dengan geometri Anda saat ini ('filter' yang dapat menghemat banyak perhitungan dan waktu ...)
  • tetapi Indeks Spasial bukan tongkat ajaib. Ketika sebagian besar dataset harus diambil, Indeks Spasial tidak dapat memberikan manfaat kecepatan apa pun.

Kalimat-kalimat ini cukup jelas, tetapi saya lebih suka mengutip @gene daripada mengusulkan kesimpulan yang sama seperti milik saya (jadi, semua kreditnya adalah hasil kerjanya yang brilian!).

Untuk pemahaman yang lebih baik tentang indeks spasial Rtree, Anda dapat mengambil beberapa informasi berguna berikut tautan ini:

Pengantar hebat lainnya tentang penggunaan indeks spasial mungkin artikel ini oleh @Nathan Woodrow .

mgri
sumber
Saya mengerti indeks spasial akan bekerja paling baik ketika mampu mengecilkan geometri minat menjadi sesedikit mungkin. Itu sebabnya saya membandingkan jumlah geometri yang menarik ketika menggunakan metode naif (12936) dengan jumlah geometri saat menggunakan indeks spasial (1816). The intersects()Metode membutuhkan waktu lebih lama ketika indeks spasial yang digunakan (lihat perbandingan waktu di atas), itulah sebabnya saya tidak yakin jika saya menggunakan indeks spasial tidak benar. Dari membaca dokumentasi dan posting yang terhubung saya pikir saya, tetapi saya berharap seseorang dapat menunjukkan jika saya tidak.
derNincompoop
Pernyataan terakhir Anda adalah: "Saya hanya bisa berpikir bahwa saya menggunakan indeks spasial Rtree secara tidak benar.", Jadi saya pikir Anda bingung tentang penggunaan indeks spasial dan saya menggarisbawahi artinya dalam jawaban saya (yang bukan tema). Anda mencoba melakukan semacam analisis statistik, tetapi jumlah geometri dan upaya yang terlibat tidak cukup untuk memahami masalah dengan lebih baik. Perilaku ini mungkin tergantung dari jumlah geometri yang terlibat (jumlah yang sangat sedikit untuk menghargai kekuatan indeks spasial) atau dari mesin Anda.
mgri
4

Tambahkan saja ke mgri jawab.

Penting untuk memahami apa itu indeks spasial ( Bagaimana Cara Menerapkan Kotak Bounding untuk Shapely & Fiona? ). Dengan contoh saya di Bagaimana cara efisien menentukan mana dari ribuan poligon bersinggungan dengan linestring

masukkan deskripsi gambar di sini

Anda dapat membuat indeks spasial dengan poligon

idx = index.Index()
for feat in poly_layer:
    geom = shape(feat['geometry'])
    id = int(feat['id'])
    idx.insert(id, geom.bounds,feat)

Batas indeks spasial (batas poligon berwarna hijau)

masukkan deskripsi gambar di sini

Atau dengan LineStrings

  idx = index.Index()
  for feat in line_layer:
      geom = shape(feat['geometry'])
      id = int(feat['id'])
      idx.insert(id, geom.bounds,feat)

Batas indeks spasial (LineString terikat warna merah)

masukkan deskripsi gambar di sini

Sekarang, Anda beralih hanya melalui geometri yang memiliki kesempatan untuk berpotongan dengan geometri Anda saat ini (berwarna kuning)

masukkan deskripsi gambar di sini

Saya menggunakan di sini indeks spasial LineStrings (hasilnya sama tetapi dengan contoh Anda 4000 poligon dan 4 baris ....).

for feat1 in poly_layer:
    geom1 = shape(feat1['geometry'])
    for id in idx.intersection(geom1.bounds):
        feat2 = line_layer[id]
        geom2 = shape(feat2['geometry'])
        if geom2.intersects(geom1):
            print 'Polygon {} intersects line {}'.format(feat1['id'], feat2['id'])

  Polygon 2 intersects line 0
  Polygon 3 intersects line 0
  Polygon 6 intersects line 0
  Polygon 9 intersects line 0

Anda juga dapat menggunakan generator ( example.py )

def build_ind():
     with fiona.open('polygon_layer.shp') as shapes:
         for s in shapes:
             geom = shape(s['geometry'])
             id = int(s['id'])
             yield (id, geom.bounds, s)

 p= index.Property()
 tree = index.Index(build_ind(), properties=p)
 # first line of line_layer
 first = shape(line_layer.next()['geometry'])
 # intersection of first with polygons
 tuple(tree.intersection(first.bounds))
 (6, 2, 3, 9)

Anda dapat memeriksa skrip GeoPandas sjoin.py untuk memahami penggunaan Rtree .

Ada banyak solusi tetapi jangan lupakan itu

  • Indeks Spasial bukan tongkat sihir ...
gen
sumber
Ketika saya menggunakan metode naif (di mana saya melakukan tes persimpangan antara setiap kombinasi Polygon dan LineString) saya akhirnya melakukan 12936 tes tersebut. Ketika saya menggunakan indeks spasial, saya hanya perlu melakukan 1.816 tes. Saya percaya ini berarti bahwa indeks spasial memang memberikan nilai dalam kasus penggunaan ini. Namun, ketika saya menghitung kode, melakukan tes 1816 membutuhkan AS LONG dengan melakukan 12936 tes. Bukankah kode dengan indeks spasial lebih cepat karena ada lebih dari 11000 lebih sedikit tes yang dilakukan?
derNincompoop
Jadi saya melihat ke dalam ini dan menemukan bahwa ~ 11000 tes yang dilakukan oleh hanya kode naif membutuhkan waktu kurang dari 1 detik untuk melakukan, sedangkan tes 1816 yang dilakukan oleh kedua set kode membutuhkan waktu 112 detik untuk dilakukan. Sekarang saya mengerti apa yang Anda maksud dengan 'Indeks Spasial bukan tongkat ajaib' - meskipun itu mengurangi jumlah tes yang dibutuhkan, yang dibutuhkan adalah yang paling berkontribusi pada waktu itu.
derNincompoop
2

Sunting: Untuk memperjelas jawaban ini, saya salah meyakini bahwa semua tes persimpangan memakan waktu yang kira-kira sama. Ini bukan kasusnya. Alasan saya tidak mendapatkan kecepatan yang saya harapkan dari menggunakan indeks spasial adalah bahwa pemilihan tes persimpangan adalah yang paling lama dilakukan di tempat pertama.

Seperti yang dikatakan oleh gen dan mgri, indeks spasial bukanlah tongkat ajaib. Meskipun indeks spasial mengurangi jumlah tes persimpangan yang perlu dilakukan dari 12936 menjadi hanya 1816, tes 1816 adalah tes yang mengambil sebagian besar waktu untuk menghitung di tempat pertama.

Indeks spasial digunakan dengan benar, tetapi asumsi bahwa setiap tes persimpangan memakan waktu yang kira-kira sama adalah yang salah. Waktu yang dibutuhkan oleh uji persimpangan dapat sangat bervariasi (0,05 detik versus 0,000007 detik).

derNincompoop
sumber
1
Anda tidak dapat memperhitungkan bagaimana indeks spasial memengaruhi kecepatan persimpangan lebih lanjut karena hanya milik kompleksitas geometri yang terlibat. Untuk kasus Anda, jika geometri "A" dan "B" berpotongan dalam 0,05 detik, mereka masih akan berpotongan dalam 0,05 detik bahkan jika Anda sebelumnya menggunakan indeks spasial (ini jelas merupakan pernyataan teoritis, karena saya pikir Anda tahu bahwa pemrosesan apa pun di dalam prosesor terkait dengan banyak faktor lain!).
mgri