Понимание использования пространственных индексов с RTree?

13

У меня проблемы с пониманием использования пространственных индексов с RTree.

Пример: у меня есть 300 буферизованных точек, и мне нужно знать область пересечения каждого буфера с помощью полигонального шейп-файла. Шейп-файл полигонов имеет> 20000 полигонов. Было предложено использовать пространственные индексы для ускорения процесса.

ТАК ... Если я создам пространственный индекс для своего многоугольного шейп-файла, будет ли он каким-то образом "прикреплен" к файлу или индекс будет автономным? То есть после его создания я могу просто запустить функцию пересечения для файла полигонов и получить более быстрые результаты? Будет ли пересечение «видеть», что существуют пространственные индексы, и знать, что делать? Или мне нужно запустить его в индексе, а затем связать эти результаты с моим исходным файлом многоугольника через FID или что-то подобное?

Документация RTree мне не очень помогает (вероятно, потому что я только учусь программированию). Они показывают, как создать индекс, читая созданные вручную точки, а затем запрашивая его относительно других созданных вручную точек, который возвращает идентификаторы, содержащиеся в окне. Имеет смысл. Но они не объясняют, как это может относиться к какому-то оригинальному файлу, из которого пришел бы индекс.

Я думаю, что это должно пойти примерно так:

  1. Вытащите bbox для каждого полигонального объекта из моего шейп-файла полигонов и поместите их в пространственный индекс, предоставив им идентификатор, совпадающий с их идентификатором в шейп-файле.
  2. Запросите этот индекс, чтобы получить пересекающиеся идентификаторы.
  3. Затем повторно запустите мое пересечение только тех объектов в моем исходном шейп-файле, которые были идентифицированы путем запроса моего индекса (не уверен, как бы я выполнил эту последнюю часть).

У меня есть правильная идея? Я что-то упустил?


Сейчас я пытаюсь заставить этот код работать с одним точечным шейп-файлом, который содержит только один точечный объект, и одним многоугольным шейп-файлом, который содержит> 20000 многоугольных объектов.

Я импортирую шейп-файлы, используя Fiona, добавляю пространственный индекс, используя RTree, и пытаюсь сделать пересечение, используя Shapely.

Мой тестовый код выглядит так:

#point shapefile representing location of desired focal statistic
traps = fiona.open('single_pt_speed_test.shp', 'r') 

#polygon shapefile representing land cover of interest 
gl = MultiPolygon([shape(pol['geometry']) for pol in fiona.open('class3_aa.shp', 'r')]) 

#search area
areaKM2 = 20

#create empty spatial index
idx = index.Index()

#set initial search radius for buffer
areaM2 = areaKM2 * 1000000
r = (math.sqrt(areaM2/math.pi))

#create spatial index from gl
for i, shape in enumerate(gl):
    idx.insert(i, shape.bounds)

#query index for ids that intersect with buffer (will eventually have multiple points)
for point in traps:
        pt_buffer = shape(point['geometry']).buffer(r)
        intersect_ids = pt_buffer.intersection(idx)

Но я продолжаю получать TypeError: объект 'Polygon' не вызывается

CSB
источник
1
Пространственный индекс является интегральным и прозрачным для набора данных (содержится, а не один объект с точки зрения пользователя). Программное обеспечение, которое выполняет пересечения, знает и будет использовать пространственные индексы для создания короткого списка для выполнения реального пересечения с помощью быстрого информирования программное обеспечение, особенности которого следует рассмотреть для более тщательного изучения и которые явно далеко не пересекаются. То, как вы его создадите, зависит от вашего программного обеспечения и вашего типа данных ... пожалуйста, предоставьте больше информации по этим пунктам для более конкретной помощи. Для файла формы это файл .shx.
Майкл Стимсон
4
.shx не является пространственным индексом. Это просто файл смещения динамического доступа записи переменной ширины. .sbn / .sbx - это пара пространственных индексов шейп-файлов ArcGIS, хотя спецификация для них не была выпущена.
Винс
1
Также .qixявляется картсервер / GDAL / OGR / SpatiaLite квадрантов индекс
Mike T
Ваша идея идеально подходит для Spatialite, который не имеет реального пространственного индекса. Большинство других форматов, если они вообще поддерживают пространственные индексы, делают это прозрачно.
user30184
2
Вы продолжаете получать TypeError: 'Polygon' object is not callableпример обновления, потому что перезаписываете shapeфункцию, которую вы импортировали из shapely, объектом Polygon, который вы создаете с помощью этой строки:for i, shape in enumerate(gl):
user2856

Ответы:

12

Это суть этого. R-дерево позволяет сделать очень быстрый первый проход и дает набор результатов, которые будут иметь «ложные срабатывания» (ограничивающие рамки могут пересекаться, когда геометрия точно не пересекается). Затем вы просматриваете набор кандидатов (выбирая их из шейп-файла по их индексу) и выполняете математически точный тест пересечения с использованием, например, Shapely. Это та же самая стратегия, которая используется в пространственных базах данных, таких как PostGIS.

sgillies
источник
1
Хороший каламбур (GiST)! GiST обычно описывается как вариант B-Tree, но Postgresql имеет реализацию R-Tree GiST. Хотя вики не обязательно является лучшей ссылкой для цитирования, у нее есть хорошая диаграмма для объяснения поиска ограничивающих рамок.
MappaGnosis
Возможно, стоит изучить ручной способ использования индекса R-дерева, как описано в шагах 2 и 3. Этот блог о OGC GeoPackage, который также поддерживает R-дерево, поскольку отдельные таблицы базы данных показывают некоторый SQL и снимки экрана openjump.blogspot.fi / 2014/02 /… .
user30184
9

Вы почти получили это, но сделали небольшую ошибку. Вам нужно использовать intersectionметод для пространственного индекса, а не передавать индекс intersectionметоду в буферизованной точке. Как только вы нашли список объектов, в которых ограничивающие прямоугольники перекрываются, вам нужно проверить, действительно ли ваша буферизованная точка пересекает геометрию.

import fiona
from shapely.geometry import mapping
import rtree
import math

areaM2 = areaKM2 * 1000000
r = (math.sqrt(areaM2/math.pi))

# open both layers
with fiona.open('single_pt_speed_test.shp', 'r') as layer_pnt:
    with fiona.open('class3_aa.shp', 'r') as layer_land:

        # create an empty spatial index object
        index = rtree.index.Index()

        # populate the spatial index
        for fid, feature in layer_land.items():
            geometry = shape(feature['geometry'])
            idx.insert(fid, geometry.bounds)

        for feature in layer_pnt:
            # buffer the point
            geometry = shape(feature['geometry'])
            geometry_buffered = geometry.buffer(r)

            # get list of fids where bounding boxes intersect
            fids = [int(i) for i in index.intersection(geometry_buffered.bounds)]

            # access the features that those fids reference
            for fid in fids:
                feature_land = layer_land[fid]
                geometry_land = shape(feature_land['geometry'])

                # check the geometries intersect, not just their bboxs
                if geometry.intersects(geometry_land):
                    print('Found an intersection!')  # do something useful here

Если вы заинтересованы в поиске точек, которые находятся на минимальном расстоянии от вашего класса земли, вы можете использовать distanceметод вместо этого (поменяйте местами соответствующий раздел из предыдущего).

for feature in layer_pnt:
    geometry = shape(feature['geometry'])

    # expand bounds by r in all directions
    bounds = [a+b*r for a,b in zip(geometry.bounds, [-1, -1, 1, 1])]

    # get list of fids where bounding boxes intersect
    fids = [int(i) for i in index.intersection(geometry_buffered.bounds)]

    for fid in fids:
        feature_land = layer_land[fid]
        geometry_land = shape(feature_land['geometry'])

        # check the geometries are within r metres
        if geometry.distance(geometry_land) <= r:
            print('Found a match!')

Если создание пространственного индекса занимает много времени, и вы собираетесь делать это несколько раз, вам следует изучить сериализацию индекса в файл. Документация описывает, как это сделать: http://toblerity.org/rtree/tutorial.html#serializing-your-index-to-a-file

Вы также можете посмотреть на массовую загрузку ограничивающих рамок в дерево с помощью генератора, например:

def gen(collection):
    for fid, feature in collection.items():
        geometry = shape(feature['geometry'])
        yield((fid, geometry.bounds, None))
index = rtree.index.Index(gen(layer_land))
Snorfalorpagus
источник
2

Да, это идея. Вот выдержка из этого руководства по использованию пространственного индекса r-дерева в Python , с использованием shapely, Fiona и геопанд:

R-дерево представляет отдельные объекты и их ограничивающие рамки («r» означает «прямоугольник») как самый низкий уровень пространственного индекса. Затем он агрегирует близлежащие объекты и представляет их с помощью ограничивающего прямоугольника на следующем более высоком уровне индекса. На еще более высоких уровнях r-дерево агрегирует ограничивающие блоки и представляет их посредством ограничивающего прямоугольника, итеративно, пока все не будет вложено в один ограничивающий прямоугольник верхнего уровня. Для поиска r-дерево берет окно запроса и, начиная с верхнего уровня, видит, какие (если есть) ограничивающие рамки пересекают его. Затем он расширяет каждый пересекающийся ограничивающий прямоугольник и видит, какие из дочерних ограничивающих прямоугольников внутри него пересекают блок запроса. Это продолжается рекурсивно, пока все пересекающиеся блоки не будут найдены до самого низкого уровня, и не найдет соответствующие объекты с самого низкого уровня.

ЭОС
источник