Tiny, portable R-trees.

Navigation

Verified details

These details have been verified by PyPI
Maintainers
Avatar for invisiblefunnel from gravatar.com invisiblefunnel

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

License: MIT

Author: Daniel Whalen

Requires: Python >=3.7

Project description

Flatrtree - Python

Flatrtree is a serialization format and set of libraries for reading and writing R-trees. It's directly inspired by Flatbush and FlatGeobuf, and aims to make tiny, portable R-trees accessible in new contexts.

  • Store R-trees to disk or transport them over a network.
  • Build R-trees in one language and query them in another.
  • Query R-trees before reading the data they index.

Installation

$ pip install flatrtree

Usage

Flatrtree separates building and querying behavior. The builder doesn’t know how to query an index and the index doesn’t know how it was built. This is inspired by FlatBuffers.

import flatrtree

# Add items to a builder object
builder = flatrtree.HilbertBuilder() # or OMTBuilder or your own
for i, item in enumerate(items):
    # The first argument is an integer reference to the item being indexed
    builder.add(i, item.minx, item.miny, item.maxx, item.maxy)

degree = 10 # node capacity

# Create an R-tree object from the builder
rtree = builder.finish(degree)

# Search for items that intersect a bounding box
for i in rtree.search(minx, miny, maxx, maxy):
    item = items[i]
    # ...

# Supply a function for calculating the distance between bounding boxes
# Planar and geodetic functions are included in the library
box_dist = flatrtree.planar_box_dist

# Find the nearest neighbors with a custom halt condition
for i, dist in rtree.neighbors(x, y, box_dist):
    if dist > maxDist:
        break
    item = item[i]
    dist # units match the given box distance function

Serialization

Flatrtree uses protocol buffers for serialization, taking advantage of varint encoding to reduce the output size in bytes. There are many tradeoffs to explore for serialization and this seems like a good place to start. It wouldn’t be hard to roll your own format with something like FlatBuffers if that better fit your needs.

# Specify the level of decimal precision you need.
# The output size will decrease as precision decreases.
precision = 7

# Serialize to bytes for storage and/or transport.
data = flatrtree.serialize(rtree, precision)

# Load the R-tree from bytes.
rtree = flatrtree.deserialize(data)

Example Usage

This example builds an R-tree from a newline-delimited GeoJSON file and stores it to disk. The R-tree holds the offset of each feature from the beginning of the file.

import json
import flatrtree
from shapely.geometry import shape

builder = flatrtree.HilbertBuilder()

with open("us-block-groups.json") as f:
    pos = f.tell()
    line = f.readline()

    while line:
        feature = json.loads(line)
        geom = shape(feature["geometry"])
        minx, miny, maxx, maxy = geom.bounds

        builder.add(pos, minx, miny, maxx, maxy)

        pos = f.tell()
        line = f.readline()


rtree = builder.finish(flatrtree.DEFAULT_DEGREE)

with open("us-block-groups.json.idx", "wb") as f:
    f.write(flatrtree.serialize(rtree, precision=6))

The next example reads the R-tree from disk and searches by a bounding box to find the relevant features. By seeking directly to the GeoJSON features returned by the search, we only read and parse the required data.

import json
import flatrtree

with open("us-block-groups.json.idx", "rb") as f:
    rtree = flatrtree.deserialize(f.read())

results = []
with open("tests/us-block-groups.json") as f:
    minx, miny, maxx, maxy = -96.985931, 32.630123, -96.571198, 32.914180
    for pos in rtree.search(minx, miny, maxx, maxy):
        f.seek(pos)
        feature = json.loads(f.readline())
        results.append(feature)

The next example finds all neighbors with bounds intersecting a radius of the given point.

import json
import flatrtree

with open("us-block-groups.json.idx", "rb") as f:
    rtree = flatrtree.deserialize(f.read())

neighbors = []
with open("us-block-groups.json") as f:
    x, y = -96.985931, 32.630123
    for pos, meters in rtree.neighbors(x, y, flatrtree.geodetic_box_dist):
        if meters > 500:
            break
        f.seek(pos)
        feature = json.loads(f.readline())
        neighbors.append(feature)

Project details

Verified details

These details have been verified by PyPI
Maintainers
Avatar for invisiblefunnel from gravatar.com invisiblefunnel

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

License: MIT

Author: Daniel Whalen

Requires: Python >=3.7


Release history Release notifications | RSS feed

This version

1.0.0rc2 pre-release

1.0.0rc1 pre-release

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

flatrtree-1.0.0rc2.tar.gz (121.7 kB view hashes)

Uploaded Source

Built Distributions

flatrtree-1.0.0rc2-pp39-pypy39_pp73-win_amd64.whl (182.0 kB view hashes)

Uploaded PyPy Windows x86-64

flatrtree-1.0.0rc2-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (198.9 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (203.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-pp39-pypy39_pp73-macosx_10_9_x86_64.whl (182.1 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

flatrtree-1.0.0rc2-pp38-pypy38_pp73-win_amd64.whl (182.9 kB view hashes)

Uploaded PyPy Windows x86-64

flatrtree-1.0.0rc2-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (199.0 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (203.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (182.3 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

flatrtree-1.0.0rc2-pp37-pypy37_pp73-win_amd64.whl (182.9 kB view hashes)

Uploaded PyPy Windows x86-64

flatrtree-1.0.0rc2-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (199.1 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (203.7 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (182.3 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

flatrtree-1.0.0rc2-cp311-cp311-win_amd64.whl (232.7 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

flatrtree-1.0.0rc2-cp311-cp311-win32.whl (220.7 kB view hashes)

Uploaded CPython 3.11 Windows x86

flatrtree-1.0.0rc2-cp311-cp311-musllinux_1_1_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

flatrtree-1.0.0rc2-cp311-cp311-musllinux_1_1_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

flatrtree-1.0.0rc2-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (751.4 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-cp311-cp311-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (733.3 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-cp311-cp311-macosx_10_9_x86_64.whl (259.5 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

flatrtree-1.0.0rc2-cp311-cp311-macosx_10_9_universal2.whl (387.6 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ universal2 (ARM64, x86-64)

flatrtree-1.0.0rc2-cp310-cp310-win_amd64.whl (234.9 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

flatrtree-1.0.0rc2-cp310-cp310-win32.whl (222.2 kB view hashes)

Uploaded CPython 3.10 Windows x86

flatrtree-1.0.0rc2-cp310-cp310-musllinux_1_1_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

flatrtree-1.0.0rc2-cp310-cp310-musllinux_1_1_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

flatrtree-1.0.0rc2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (740.0 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (731.9 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-cp310-cp310-macosx_10_9_x86_64.whl (260.6 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

flatrtree-1.0.0rc2-cp310-cp310-macosx_10_9_universal2.whl (389.6 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ universal2 (ARM64, x86-64)

flatrtree-1.0.0rc2-cp39-cp39-win_amd64.whl (238.0 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

flatrtree-1.0.0rc2-cp39-cp39-win32.whl (224.6 kB view hashes)

Uploaded CPython 3.9 Windows x86

flatrtree-1.0.0rc2-cp39-cp39-musllinux_1_1_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

flatrtree-1.0.0rc2-cp39-cp39-musllinux_1_1_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

flatrtree-1.0.0rc2-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (750.9 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (744.0 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-cp39-cp39-macosx_10_9_x86_64.whl (263.5 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

flatrtree-1.0.0rc2-cp39-cp39-macosx_10_9_universal2.whl (395.4 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ universal2 (ARM64, x86-64)

flatrtree-1.0.0rc2-cp38-cp38-win_amd64.whl (237.2 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

flatrtree-1.0.0rc2-cp38-cp38-win32.whl (224.4 kB view hashes)

Uploaded CPython 3.8 Windows x86

flatrtree-1.0.0rc2-cp38-cp38-musllinux_1_1_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

flatrtree-1.0.0rc2-cp38-cp38-musllinux_1_1_i686.whl (1.4 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

flatrtree-1.0.0rc2-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (750.9 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (743.7 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-cp38-cp38-macosx_10_9_x86_64.whl (261.6 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

flatrtree-1.0.0rc2-cp38-cp38-macosx_10_9_universal2.whl (392.2 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ universal2 (ARM64, x86-64)

flatrtree-1.0.0rc2-cp37-cp37m-win_amd64.whl (235.9 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

flatrtree-1.0.0rc2-cp37-cp37m-win32.whl (223.1 kB view hashes)

Uploaded CPython 3.7m Windows x86

flatrtree-1.0.0rc2-cp37-cp37m-musllinux_1_1_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

flatrtree-1.0.0rc2-cp37-cp37m-musllinux_1_1_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ i686

flatrtree-1.0.0rc2-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (707.0 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

flatrtree-1.0.0rc2-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (696.6 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

flatrtree-1.0.0rc2-cp37-cp37m-macosx_10_9_x86_64.whl (259.3 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page