Geospatial primitives and algorithms for Rust

Overview

geo

Build Status geo on Crates.io Coverage Status Documentation

geo

Geospatial Primitives, Algorithms, and Utilities

The geo crate provides geospatial primitive types such as Point, LineString, and Polygon, and provides algorithms and operations such as:

  • Area and centroid calculation
  • Simplification and convex hull operations
  • Euclidean and Haversine distance measurement
  • Intersection checks
  • Affine transforms such as rotation and translation.

Please refer to the documentation for a complete list.

The primitive types also provide the basis for other functionality in the Geo ecosystem, including:

Example

use geo::{line_string, polygon};
use geo::convex_hull::ConvexHull;

// An L shape
let poly = polygon![
    (x: 0.0, y: 0.0),
    (x: 4.0, y: 0.0),
    (x: 4.0, y: 1.0),
    (x: 1.0, y: 1.0),
    (x: 1.0, y: 4.0),
    (x: 0.0, y: 4.0),
    (x: 0.0, y: 0.0),
];

// Calculate the polygon's convex hull
let hull = poly.convex_hull();

assert_eq!(hull.exterior(), line_string![
    (x: 0.0, y: 0.0),
    (x: 0.0, y: 4.0),
    (x: 1.0, y: 4.0),
    (x: 4.0, y: 1.0),
    (x: 4.0, y: 0.0),
    (x: 0.0, y: 0.0),
]);

Contributing

Contributions are welcome! Have a look at the issues, and open a pull request if you'd like to add an algorithm or some functionality.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments
  • Create `Intersection` algorithm trait

    Create `Intersection` algorithm trait

    It might be the case (in the case of intersecting two polygons) that the operation will return a polygon or a linestring or a point or nothing, the return type will need to reflect this. Maybe something like this?

    trait Intersection<...> {
        fn intersection(&self, other) -> Option<IntersectionResult> {
            ...
        }
    }
    
    // not a fan of "Result" here since it sounds similar to std::result::Result
    enum IntersectionResult {   
        Polygon(Polygon),
        LineString(LineString),
        Point(Point),
    }
    

    Note that this is different from the Intersects trait which simply returns a bool indicating if two geometries intersect at any point

    enhancement 
    opened by frewsxcv 39
  • Add Concave Hull algorithm

    Add Concave Hull algorithm

    As part of https://github.com/dabreegster/abstreet/issues/198, I've been working on adding an implementation of the Concave Hull algorithm primarily inspired by https://github.com/mapbox/concaveman. This implementation doesn't completely copy concaveman but it does ape the notion of using R trees in order to avoid a linear search through the points although my use of R trees relies on a circular envelope rather than the rectangular envelope that concaveman seems to use.

    opened by RestitutorOrbis 36
  • ClosestPoint for Triangle, Rect, GeometryCollection types & Geometry enum

    ClosestPoint for Triangle, Rect, GeometryCollection types & Geometry enum

    • [x] I agree to follow the project's code of conduct.
    • [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

    This pull request addresses issue #544 The ClosestPoint method was implemented for the remaining members of the Geometry enum ie., Triangle, Rect and GeometryCollection and then implemented for the enum itself.

    opened by pkopparla 33
  • Clean up rstar versioned dependencies

    Clean up rstar versioned dependencies

    Explicitly declare rstar_0_8 and rstar_0_9 to make it clearer which version is being used. For backward compatibility, the rstar is now a feature that enables rstar_0_8

    • [x] I agree to follow the project's code of conduct.
    • [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

    opened by nyurik 19
  • DE-9IM Proposal

    DE-9IM Proposal

    per https://github.com/georust/geo/issues/513 I've written up a proposal about an addition I'd like to make to geo - introducing a DE-9IM module, and using it to help drive and correct some of our relation traits: e.g. Contains, Intersects. It would also make it much easier to add future traits like Disjoint, Touches, Crosses, etc.

    Read the full proposal here: https://gist.github.com/michaelkirk/3ac4afe651fe24ad229dec0b56ec8f9d

    (a gist allows easier editing than updating issue text in situ).

    Please take a look! I spent some time adding context, in hope that it would be accessible to you even if you don't know what DE-9IM is.

    The idea is that after getting a little feedback on the proposal, I'll add some specific issues to this tracking issue.

    opened by michaelkirk 19
  • Add new `Transform` algorithm for transforming a geometry with PROJ.

    Add new `Transform` algorithm for transforming a geometry with PROJ.

    • [x] I agree to follow the project's code of conduct.
    • [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.
      • I will do this if we decide we want this
    • [x] Add entry to table of contents in lib.rs
    opened by frewsxcv 17
  • Incorporate `rust-geo-booleanop` algorithms directly into `geo`?

    Incorporate `rust-geo-booleanop` algorithms directly into `geo`?

    https://github.com/21re/rust-geo-booleanop

    Related: https://github.com/georust/geo/issues/80, https://github.com/georust/geo/issues/81

    Reach out to the maintainer? Add as a dependency? Offer to take over the crate? Copy and paste and update our license files?

    idea 
    opened by frewsxcv 17
  • don't mix x/y and lat/lon

    don't mix x/y and lat/lon

    The Point struct has both x/y and lat/lon getter methods. This can be confusing when both are used in the same method.

    Additionally i think using lat/lon is very dangerous in general. My experience is that many people think x = lat and y = lon ...

    geo-types 
    opened by jdroenner 17
  • Is the performance of boolean operation algorithms good enough?

    Is the performance of boolean operation algorithms good enough?

    I've seen a mention of maybe replacing the boolean operation algorithms for example here: https://github.com/georust/geo/issues/620

    What is the general state of the boolean operation algorithms from a performance perspective in this crate?

    Reason is I ran a (somewhat simple) comparison test between this crate and npm's Turf crate. The intersect algorithm on polygons of Turf seems to be magnitudes faster even though it is written in typescript. I had a look at the source, and one reason I saw is the turf algorithm does a bounding box comparison before the actual intersect.

    I would have no problem doing this myself, but it leads me to the question: Are you guys happy with the current algorithms? What can I expect in the future?

    Add-on question: Is it possible to retrieve the resulting intersection when doing the intersection between two polygons?

    opened by erikpols 16
  • Merge wkt repository with history as /wkt dir

    Merge wkt repository with history as /wkt dir

    If we agree to merge this, the wkt repo should be archived, and all issues should be moved to this repo. I believe it would be good to merge it here because:

    • geo-test-fixtures requires wkt, and wkt requires geo-types - creating a circular dependency between two repos, making development more complicated and error-prone
    • this is a commonly used geo feature
    • this is a pure Rust lib

    This merges the entire history of the wkt repository from

    https://github.com/georust/wkt/tree/dbd80f22099fc11ad69a1d072c3516f9a1ca4376

    as a /wkt directory, and adds the CI and adds path links from Crates.toml files:

    • wkt/Cargo.toml - link to /geo-types
    • geo-test-fixtures/Cargo.toml - link to /wkt

    • [x] I agree to follow the project's code of conduct. ~- [ ] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.~

    opened by nyurik 15
  • Feat/boolean ops

    Feat/boolean ops

    • [x] I agree to follow the project's code of conduct.
    • [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

    PR to import the boolean-ops code from geo-crossings. The impl. is not a 100% accurate to fixed-precision errors, but seems to handle the degenerate cases encountered in rust-geo-booleanop. When comparing the difference in outputs between the two algos, both algos panic in a few cases. The hope is to eventually improve some of the internal data-structures to be a 100% robust.

    The performance, is about 1.25-1.5x worse when using the splay-tree, and about 1.5-2x if using vanilla btree. However, splay-tree seems to trigger an extra panic (not on the test cases, but while comparing outputs between the two impls), so I'm inclined to stick with vanilla BTree. Eventually, I hope we can figure out a intrusive impl. of BTree (eg. btree_slab) that is both performant, and fixes the fp accuracy issues.

    opened by rmanoka 14
  • Implemented

    Implemented "Closest Point" from a `Point` on a `Geometry` using spherical geometry.

    • [X] I agree to follow the project's code of conduct.
    • [X] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

    Essentially implementing ClosestPoint trait for spherical geometry. I named the new trait HaversineClosestPoint.

    There is a slight (intentional) difference in behavior in the case when a segment (arc)'s length is very close to zero, the spherical algorithm will return Closest::SinglePoint instead of Closest::Indeterminate. I think even if the segment has degenerated to a point, there is still a closest point.

    opened by bbetov 0
  • Make `SimplifyVw` algorithm naming consistent.

    Make `SimplifyVw` algorithm naming consistent.

    • [x] I agree to follow the project's code of conduct.
    • [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

    Fixes: https://github.com/georust/geo/issues/575

    Changed:

    • SimplifyVW -> SimplifyVw
    • SimplifyVWPreserve -> SimplifyVwPreserve
    • simplifyvw -> simplify_vw

    Unchanged:

    • SimplifyVwIdx
    opened by frewsxcv 0
  • Panic: could not compare segments

    Panic: could not compare segments

    When processing OSM data, sometimes we have bad geometry, and using the library for interior_point causes a panic. Normally, feeding bad geometry to a geometry library should return an error, not a panic, as this is a standard thing to expect.

    I have to recover from the panic with panic::catch_unwind, which is not ideal.

    https://github.com/georust/geo/blob/3b0d5738f54bd8964f7d1f573bd63dc114587dc4/geo/src/algorithm/sweep/active.rs#L54

    [2022-12-04T19:14:40.661064000Z geo::algorithm::sweep::active] could not compare segments:
            Active(Segment{ LPt((444882789.06824327, 332473624.5), (444882817.0, 332473624.5))
            of Line { start: Coordinate { x: 444881047.0, y: 332473624.5 }, end: Coordinate { x: 444882817.0, y: 332473624.5 } }
             [NON/NON] })
            Active(Segment{ LPt((444882200.0, 332474331.0), (444882789.06824327, 332473624.5))
            of Line { start: Coordinate { x: 444882817.0, y: 332473591.0 }, end: Coordinate { x: 444882200.0, y: 332474331.0 } }
            [1st] [NON/NON] })
    thread '<unnamed>' panicked at 'unable to compare active segments!', /Users/n/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.23.0/src/algorithm/sweep/active.rs:54:13
    
    bug geo 
    opened by hallahan 0
  • Provide utility functions to find reasonable epsilon values for `Simplify`

    Provide utility functions to find reasonable epsilon values for `Simplify`

    https://github.com/georust/geo/issues/940#issuecomment-1332274260

    https://stackoverflow.com/questions/57052434/can-i-guess-the-appropriate-epsilon-for-rdp-ramer-douglas-peucker

    enhancement geo 
    opened by frewsxcv 0
Owner
GeoRust
A collection of geospatial tools and libraries written in Rust
GeoRust
Zero-Copy reading and writing of geospatial data.

GeoZero Zero-Copy reading and writing of geospatial data. GeoZero defines an API for reading geospatial data formats without an intermediate represent

GeoRust 155 Dec 29, 2022
Geo-rasterize - a pure-rust 2D rasterizer for geospatial applications

geo-rasterize: a pure-rust 2D rasterizer for geospatial applications This crate is intended for folks who have some vector data (like a geo::Polygon)

null 23 Dec 26, 2022
Fast Geospatial Feature Storage API

Hecate OpenStreetMap Inspired Data Storage Backend Focused on Performance and GeoJSON Interchange Hecate Feature Comparison Feature Hecate ESRI MapSer

Mapbox 243 Dec 19, 2022
An advanced geospatial data analysis platform

Bringing the power of Whitebox GAT to the world at large This page is related to the stand-alone command-line program and Python scripting API for geo

John Lindsay 683 Jan 5, 2023
Optimized geometry primitives for Microsoft platforms with the same memory layout as DirectX and Direct2D and types.

geoms Geometry for Microsoft platforms - a set of geometry primitives with memory layouts optimized for native APIs (Win32, Direct2D, and Direct3D). T

Connor Power 2 Dec 11, 2022
Convert {sf} geometry to Rust native primitives

sfconversions A minimal Rust library to convert geometry objects from the R package {sf} into geo-types geometry primitives using extendr. Provides si

Josiah Parry 7 Mar 27, 2023
TIFF decoding and encoding library in pure Rust

image-tiff TIFF decoding and encoding library in pure Rust Supported Features Baseline spec (other than formats and tags listed below as not supported

image-rs 66 Dec 30, 2022
A single-binary, GPU-accelerated LLM server (HTTP and WebSocket API) written in Rust

Poly Poly is a versatile LLM serving back-end. What it offers: High-performance, efficient and reliable serving of multiple local LLM models Optional

Tommy van der Vorst 13 Nov 5, 2023
Blazing fast and lightweight PostGIS vector tiles server

Martin Martin is a PostGIS vector tiles server suitable for large databases. Martin is written in Rust using Actix web framework. Requirements Install

Urbica 921 Jan 7, 2023
OpenStreetMap flatdata format and compiler

osmflat Flat OpenStreetMap (OSM) data format providing an efficient random data access through memory mapped files. The data format is described and i

null 31 Dec 7, 2022
A traffic simulation game exploring how small changes to roads affect cyclists, transit users, pedestrians, and drivers.

A/B Street Ever been stuck in traffic on a bus, wondering why is there legal street parking instead of a dedicated bus lane? A/B Street is a game expl

A/B Street 6.8k Jan 4, 2023
Calculates a stars position and velocity in the cartesian coordinate system.

SPV Calculates a stars position and velocity in the cartesian coordinate system. Todo Expand the number of available operation Batch processing by tak

Albin Sjögren 11 Feb 18, 2022
Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism" written in OCaml

bidi-higher-rank-poly Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorph

Søren Nørbæk 23 Oct 18, 2022
A set of tools for generating isochrones and reverse isochrones from geographic coordinates

This library provides a set of tools for generating isochrones and reverse isochrones from geographic coordinates. It leverages OpenStreetMap data to construct road networks and calculate areas accessible within specified time limits.

null 3 Feb 22, 2024
Rust crate for performing coordinate transforms

Synopsis A Rust crate use for performing coordinate transformations. The crate relies on nalgebra vectors to perform the coordinate transformations. C

Dave 25 Aug 20, 2022
An fast, offline reverse geocoder (>1,000 HTTP requests per second) in Rust.

Rust Reverse Geocoder A fast reverse geocoder in Rust. Inspired by Python reverse-geocoder. Links Crate 2.0.0 Docs 1.0.1 Docs Description rrgeo takes

Grant Miner 91 Dec 29, 2022
Rust bindings for GDAL

gdal [] GDAL bindings for Rust. So far, you can: open a raster dataset for reading/writing get size and number of bands get/set projection and geo-tra

GeoRust 211 Jan 4, 2023
Rust bindings for the latest stable release of PROJ

PROJ Coordinate transformation via bindings to the PROJ v7.2.1 API. Two coordinate transformation operations are currently provided: projection (and i

GeoRust 96 Dec 21, 2022
Geohash for Rust

Rust-Geohash Rust-Geohash is a Rust library for Geohash algorithm. Ported from node-geohash module. Documentation Docs Check the API doc at docs.rs Li

GeoRust 74 Sep 8, 2022