Rust implementation of the Martinez-Rueda Polygon Clipping Algorithm

Overview

Build Status crates.io

Boolean operations on geo shapes

This is an implementation of the Martinez-Rueda Polygon Clipping Algorithm in rust to integrate smoothly into the already exsting geospatial library georust/geo.

In fact the implementation closely follows the "reference" implementation in JavaScript: https://github.com/w8r/martinez. Most of the concepts and fixtures have been taken from there.

At the moment the implementation contains its own splay tree implementation (adapted from https://github.com/alexcrichton/splay-rs) as the JavaScript implementation also uses a splay-tree. This might be refactored out in the future in favor of the standard collection types (like BTreeSet).

IMPORTANT: How to report bugs

Please be aware (so far) this implementation is based on the JavaScript version. If you find a bug (i.e. two polygons not producing the expected result), chances are that the original algorithm has the same problem. So please first check with https://github.com/w8r/martinez and file a report there. Once there is a fix I will happily backport it to the rust version.

If you do not know how to do that (You understand rust but not javascript? ... I mean ... seriously?), you may take a look at this example: https://gist.github.com/untoldwind/e95b7eff8ad61527a5dc4bdd889169b0

I.e. just create package.json, ìnsert your example coordinates in main.js and then do npm install followed by node main.js

Usage

Pretty straightforward:

geo-booleanop = "0.2.1"
extern create geo;
extern crate geo_booleanop;

use geo_booleanop::boolean::BooleanOp;

fn main() {
    let poly1 : geo::Polygon<f64> = ...
    let poly2 : geo::Polygon<f64> = ...

    let intersect = poly1.intersection(&poly2);
    let union = poly1.union(&poly2);
    let diff = poly1.difference(&poly2);
    let xor = poly1.xor(&poly2);

    ...
}

MultiPolygon is supported as well.

Comments
  • Remove libc dependency

    Remove libc dependency

    I am using this library in a WASM program. Because of that, I needed to remove the dependency on libc in order to compile to the WASM target. I replaced the nextafter functions in src/boolean/helper.rs with my native rust implementation float_next_after. You can check that package and its functionality at https://gitlab.com/bronsonbdevost/next_afterf. All tests are still passing.

    Sorry that the Cargo.lock file came along with this PR (I think it should usually be in .gitignore). Let me know if there is anything I can do to remove that.

    Thank you for this great package!

    opened by Bronson-Brown-deVost 11
  • Incorrect union on small example

    Incorrect union on small example

    Hi and thanks for maintaining this very useful library.

    I ran into some incorrect results while computing the union of a large number of polygons, and I think I managed to isolate a simple example out of my larger data set.

    This is the two polygons (blue and green) being merged. Note the shared horizontal edge in the middle. image

    Here is the resulting union:

    image

    Repro code:

    #[macro_use]
    extern crate geo_types;
    
    use geo_booleanop::boolean::BooleanOp;
    
    fn main() {
        let big = polygon![
            (x: 416., y: 256.),
            (x: 432., y: 240.),
            (x: 432., y: 224.),
            (x: 448., y: 280.),
            (x: 480., y: 208.),
            (x: 480., y: 256.),
        ];
    
        let small = polygon![
            (x: 400., y: 272.),
            (x: 416., y: 256.),
            (x: 480., y: 256.),
            (x: 480., y: 272.),
        ];
    
        let union = small.union(&big);
        for p in union.into_iter() {
            dbg!(p);
        }
    }
    
    /*
    Output:
    
    [src\main.rs:27] p = Polygon {
        exterior: LineString(
            [
                Coordinate {
                    x: 400.0,
                    y: 272.0,
                },
                Coordinate {
                    x: 416.0,
                    y: 256.0,
                },
                Coordinate {
                    x: 432.0,
                    y: 240.0,
                },
                Coordinate {
                    x: 432.0,
                    y: 224.0,
                },
                Coordinate {
                    x: 441.14285714285717,
                    y: 256.0,
                },
                Coordinate {
                    x: 458.66666666666663,
                    y: 256.0,
                },
                Coordinate {
                    x: 480.0,
                    y: 208.0,
                },
                Coordinate {
                    x: 480.0,
                    y: 256.0,
                },
                Coordinate {
                    x: 480.0,
                    y: 272.0,
                },
                Coordinate {
                    x: 451.55555555555554,
                    y: 272.0,
                },
                Coordinate {
                    x: 448.0,
                    y: 280.0,
                },
                Coordinate {
                    x: 445.7142857142857,
                    y: 272.0,
                },
                Coordinate {
                    x: 400.0,
                    y: 272.0,
                },
            ],
        ),
        interiors: [],
    }
    */
    
    opened by agersant 7
  • Using BooleanOp with geo

    Using BooleanOp with geo

    Hello!

    I'd like to ask a beginner question which I haven't found answer for (or I was looking for it badly 😅)

    I use geo (not geo_types) in my project, and while trying to perform an intersection operation like this:

    use geo::Polygon;
    use geo_booleanop::boolean::BooleanOp;
    
    pub fn clip(polygon: &Polygon<f64>, fill_shapes: &[Polygon<f64>]) {
        let value = fill_shapes.iter()
            .map(|shape| polygon.intersection(shape));
    }
    

    I get an error from the VSCode:

    no method named `intersection` found for reference `&geo::Polygon<f64>` in the current scope
    

    I see that, contrary to the README of this project, geo_booleanop uses geo_types instead of geo. Is it possible to use this library with geo?

    Thank you for help!

    opened by afternoon2 5
  • Union does not create polygon with holes

    Union does not create polygon with holes

    I'm not sure if this a misuse on my side, a problem in the Rust port, or already an issue for the JS implementation. When taking the union of e.g. the following polygons

    debug_polys_input

    I would expect to get 1 polygon with 1 hole. However the output is 2 polygons instead, both having an exterior with empty interiors:

    debug_polys_output

    Code to reproduce:

    extern crate geo;
    extern crate geo_booleanop;
    extern crate serde;
    extern crate serde_json;
    
    use geo_booleanop::boolean::BooleanOp;
    use geo::{polygon};
    use std::fs::File;
    
    
    fn main() {
    
        let polygons = vec![
            polygon![
                (x:   0., y:   0.),
                (x: 100., y:   0.),
                (x: 100., y:  10.),
                (x:   0., y:  10.),
            ],
            polygon![
                (x:  90., y:   0.),
                (x: 100., y:   0.),
                (x: 100., y: 100.),
                (x:  90., y: 100.),
            ],
            polygon![
                (x:   0., y:  90.),
                (x: 100., y:  90.),
                (x: 100., y: 100.),
                (x:   0., y: 100.),
            ],
            polygon![
                (x:   0., y:   0.),
                (x:  10., y:   0.),
                (x:  10., y: 100.),
                (x:   0., y: 100.),
            ],
        ];
    
        let mut union = geo::MultiPolygon::<f32>(vec![]);
        for poly in &polygons {
            union = union.union(poly);
        }
    
        let f = File::create("debug_polys_input.json").unwrap();
        serde_json::to_writer_pretty(f, &polygons).unwrap();
    
        let f = File::create("debug_polys_output.json").unwrap();
        serde_json::to_writer_pretty(f, &union).unwrap();
    }
    

    Is there a problem how the library interprets holes?

    I'm using the latest versions of geo/geo-types/geo-booleanups.

    JSON output data
    [
      {
        "exterior": [
          {
            "x": 0.0,
            "y": 0.0
          },
          {
            "x": 10.0,
            "y": 0.0
          },
          {
            "x": 90.0,
            "y": 0.0
          },
          {
            "x": 100.0,
            "y": 0.0
          },
          {
            "x": 100.0,
            "y": 10.0
          },
          {
            "x": 100.0,
            "y": 90.0
          },
          {
            "x": 100.0,
            "y": 100.0
          },
          {
            "x": 90.0,
            "y": 100.0
          },
          {
            "x": 10.0,
            "y": 100.0
          },
          {
            "x": 0.0,
            "y": 100.0
          },
          {
            "x": 0.0,
            "y": 90.0
          },
          {
            "x": 0.0,
            "y": 10.0
          },
          {
            "x": 0.0,
            "y": 0.0
          }
        ],
        "interiors": []
      },
      {
        "exterior": [
          {
            "x": 10.0,
            "y": 10.0
          },
          {
            "x": 90.0,
            "y": 10.0
          },
          {
            "x": 90.0,
            "y": 90.0
          },
          {
            "x": 10.0,
            "y": 90.0
          },
          {
            "x": 10.0,
            "y": 10.0
          }
        ],
        "interiors": []
      }
    ]
    
    Python plotting code
    #!/usr/bin/env python
    
    from __future__ import print_function
    
    import matplotlib.pyplot as plt
    import json
    import sys
    
    
    if len(sys.argv) != 2:
        print("ERROR: Wrong number of arguments.")
        sys.exit(1)
    
    else:
        filename = sys.argv[1]
    
        data = json.load(open(filename))
    
        fig, ax = plt.subplots(1, 1, figsize=(10, 8))
    
        for i, poly in enumerate(data):
            exterior = poly["exterior"]
            interiors = poly["interiors"]
    
            xs = [p["x"] for p in exterior]
            ys = [p["y"] for p in exterior]
    
            ax.plot(xs, ys, "o-", label="Polygon {}".format(i + 1))
    
        plt.legend(loc="best")
        plt.tight_layout()
    
        filename_out = filename.replace(".json", ".png")
        plt.savefig(filename_out)
    
        plt.show()
    
    opened by bluenote10 5
  • [WIP- 2 tests failing] Update for geo_types 0.4

    [WIP- 2 tests failing] Update for geo_types 0.4

    I am unsure of why the two tests are failing and am looking for another set of eyes on this.

    I would like to use this crate and would like to use an up-to-date geo crate, so I updated this crate to use the latest geo_types.

    opened by boydjohnson 4
  • Simplified feature type tests

    Simplified feature type tests

    Just a small cleanup: This PR converts the existing "feature type" tests (poly, poly_with_hole, multi_poly, multi_poly_with_hole) into test cases using the generic test case system. This makes test case handling more consistent, reduces code, and allows for easier visualization:

    test_cases.pdf

    opened by bluenote10 3
  • Update the crate

    Update the crate

    @untoldwind, is there any chance you could update the current crate to reflect the changes to master. I have some crates with dependencies on this that I would like to be able to publish.

    opened by Bronson-Brown-deVost 2
  • Feature/improved contour connection logic

    Feature/improved contour connection logic

    Some improvements as a result of #14. Again I'm trying to document the changes for other Martinez developers.

    @daef's experiment showed that there were many issues related to holes in xor operations. The fundamental problem is:

    image

    The algorithm outputs a single contour as indicated by the path. The result isn't entirely wrong if interpreting the result with odd-even rule, but:

    • it is not what one would expect (either two polygons or one big with a hole).
    • it violates e.g. GeoJSON and can mess up tooling -- e.g. my plots don't see the hole.

    The reason comes down to how the algorithm connects edges when multiple edges meet at one vertex. In general, the algorithm groups all segments that belong to the vertex, ordering them according to the default ordering (right/end events before left/start events, bottom to top). For instance, in this example 4 right events (red) and 4 left events (green) meet at a vertex, resulting in the indicated ordering:

    image

    With the current implementation if we would enter the vertex from e.g. segment 6, it follows the first unprocessed segment, searching first in upward direction (7, 8) then in downward direction (5, 4, ...).

    This explains the behavior in the two-triangle-example. At the first intersection, we take a right turn (entering at segment 3 and segment 4 is unprocessed):

    image

    On the other hand, the second intersection becomes a "straight" passage, because the transition from segment 2 to 3 basically switches from clockwise iteration (right events) to counter-clockwise (left events):

    image

    It looks like we would get better contours by following a convention of consistently taking the left-most (or right-most) segment.

    Note that there is no need to compute angles and do the sorting from scratch. The event ordering has all the information required, we only have to account for the jump from right to left events. The function precompute_iteration_order basically precomputes for each segment at index i the corresponding segment index j which is its left-most segment neighbor. The function basically implements the pattern:

    image

    If a vertex consists of purely left or right events, the chain loops over directly:

    image

    Searching for the next free segment in the main connect_edges functions simplifies to following this index chain.

    The change has no measurable performance impact on the existing benchmarks, but it can be even faster than the old implementation in cases with many segments meeting at one point (because the precomputed iteration order reduce the number of operations required for searching a successor).

    The PR also contains a small bugfix related to the prev_in_result logic, which lead to a crash in some of @daef's examples. Overall the results for the XOR operation change from:

    image

    to

    image

    I've added a few of his examples as test cases. Modified / new test cases: test_cases.pdf

    opened by bluenote10 2
  • Refactor connect edges

    Refactor connect edges

    This PR follows the ideas of https://github.com/w8r/martinez/pull/113, combined with a few more fixes, and translated into a more Rust friendly structure. Basically the JS implementation was missing a key step of the Martinez algorithm in the second stage -- the implementation of the 4 possible cases for determining parent contours (Fig. 4 in the paper):

    image

    The idea is that for each start point of a contour we look at the lower ("previous in result") contour and check:

    • if there is no contour below => current contour must be an exterior contour (case 1).
    • if there is a lower contour, but it is an inside-outside transition => current contour must also be an exterior contour (case 3).
    • if there is a lower contour, and it is an outside-inside transition => in this case, the current contour is a hole, and depending on whether the lower contour is also a hole or an exterior contour we can establish the parent/hole relationship (cases 2 & 4).

    I also tried to document the ideas with code comments as best I could.

    This PR fixes / affects:

    • #7
    • https://github.com/w8r/martinez/issues/96
    • https://github.com/w8r/martinez/issues/93
    • https://github.com/w8r/martinez/issues/71
    • https://github.com/w8r/martinez/issues/69
    • https://github.com/w8r/martinez/issues/68
    • https://github.com/w8r/martinez/issues/61
    • The 'fatal3' test case, which now has proper holes instead of all exterior rings.
    • A few more new test cases involving polygon nesting that were tricky to get right.

    Here is a visualization of all new / modified test cases:

    test_cases.pdf

    A few minor changes:

    • The biggest debugging struggle for me was caused by the inability to display/debug print the Float trait. Omitting the Debug/Display traits from Float doesn't do anyone a favor who gets to debug Float based code. Hope it is fine to extend the trait, because Float will be almost exclusively instantiated by f32 or f64 anyhow.
    • I've added the Python plotting script I use for visualizing the test cases in a scripts subfolder. It is ~200 LOC and I thought it might be useful for anyone testing the algrithm. I have also documented how the test scheme works in a short readme.
    opened by bluenote10 2
  • Newest version is not released to crates.io

    Newest version is not released to crates.io

    The newest commit including a bump of the geo dependency does not seem to be included in the latest release published to crates.io — this causes a major headache when using the currently latest version of geo and throws one into the deep dependency hell that cargo digs for oneself ...

    In order to not end up in hell, I'd appreciate a new release to cargo so I don't have to pull the latest release from GitHub all the time 😜

    For everyone that stumbles upon this bug report in the meantime, you may use this to alleviate your pain temporarily:

    geo-booleanop = { git = "https://github.com/21re/rust-geo-booleanop" }
    
    opened by TilBlechschmidt 1
  • Fix typo related to intersections at endpoints

    Fix typo related to intersections at endpoints

    This PR mainly fixes a small typo in the translation of the JS algorithm to Rust. I already noticed that the Rust algorithm had a small difference compared to the JS on test case issue103. Basically it produced a spurious vertex next to another vertex. Not fully wrong, because it still followed the same shape, but not needed for the result:

    image

    Tracking down the issue turned out that it is simply a && that should have been || (see JS side here). I have also added a new test case:

    image

    Comparing the before and after coordinates at this case case, we can see that the spurious vertices around the correct vertices disappear:

    image

    I've also updated the readme a little bit.

    opened by bluenote10 1
  • Consider re-exporting geo_types so this crate can be used without additional dependencies

    Consider re-exporting geo_types so this crate can be used without additional dependencies

    I would like to use this crate without further dependencies (I only need the union functionality really). I can do this currently if I modify the first line of /lib/src/boolean/mod.rs to:

    pub use geo_types::{Coordinate, LineString, MultiPolygon, Polygon};
    

    As an aside, I tried just using the latest version of geo_types in addition to this crate in my Cargo.toml and it failed to import/recognise the BooleanOp trait on the Polygon type. The above would also resolve this issue (unless there's something obvious I am missing?).

    opened by AlanRace 1
  • Panic: index out of bounds

    Panic: index out of bounds

    My app generates polygons many times a second. Sometimes it panics with the following:

    index-c3cba34161ffd897.js:406 panicked at 'index out of bounds: the len is 1 but the index is 4294967295', /home/user/.cargo/git/checkouts/rust-geo-booleanop-3fbb75e5fa6cd1f8/188f016/lib/src/boolean/connect_edges.rs:180:38
    

    It only seems to happen when taking the difference. Below are some vertices that have caused the issue:

    p1 = [(-87.89134, 223.90228), (-93.1746, -213.39839), (-99.17416, -213.32591), (-93.8909,  223.97476)]
    p2 = [(-30.8955, 223.21368), (-33.432434, 13.228989), (-153.42368, -14.678665), (-150.88675, 224.66336)]
    
    opened by intendednull 3
  • Canonical segment orientation for robust intersections

    Canonical segment orientation for robust intersections

    Currently, this test fails:

        #[test]
        fn test_intersection_order() {
            for _ in 0..1000 {
                let a1 = random_coord();
                let a2 = random_coord();
                let b1 = random_coord();
                let b2 = random_coord();
                let p1234 = intersection(a1, a2, b1, b2); 
                assert_eq!(p1234, intersection(a2, a1, b1, b2));
                assert_eq!(p1234, intersection(a1, a2, b2, b1));
                assert_eq!(p1234, intersection(a2, a1, b2, b1));
                assert_eq!(p1234, intersection(b1, b2, a1, a2));
                assert_eq!(p1234, intersection(b1, b2, a2, a1));
                assert_eq!(p1234, intersection(b2, b1, a1, a2));
                assert_eq!(p1234, intersection(b2, b1, a2, a1));
            }
        }
    }
    

    The accumulation of floating point errors in intersection depends on the order of its arguments, when all 8 permutations ought to be the exact same intersection.

    If we change the intersection function to enforce a canonical orientation for the two line segments before performing its calculations, this test will pass and naive equality checks on intersection results will be reliable.

    We perform most of the comparisons necessary to enforce such a convention already in constructing the intersection bounding box. See this commit in my fork: https://github.com/nick-parker/rust-geo-booleanop/commit/ae3159ffdfdfdb21fb166e1ff932cee46730bd03

    Would this sort of robustness be helpful? I haven't dug into the main library enough to know yet, and my branch breaks a bunch of tests right now because it changes the orientation of eg some Overlap results.

    opened by nick-parker 6
  • no method named `union` found

    no method named `union` found

    I'm getting this error. I've tried both 0.2.1 and 0.1.4

    warning: unused imports: `GeoJson`, `Value`
     --> src/main.rs:2:15
      |
    2 | use geojson::{GeoJson, Value};
      |               ^^^^^^^  ^^^^^
      |
      = note: `#[warn(unused_imports)]` on by default
    
    error[E0599]: no method named `union` found for struct `geo_types::polygon::Polygon<{float}>` in the current scope
      --> src/main.rs:21:23
       |
    21 |     let union = poly1.union(&poly2);
       |                       ^^^^^ method not found in `geo_types::polygon::Polygon<{float}>`
    
    warning: unused import: `geo_booleanop::boolean::BooleanOp`
     --> src/main.rs:3:5
      |
    3 | use geo_booleanop::boolean::BooleanOp;
      |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    
    error: aborting due to previous error
    
    For more information about this error, try `rustc --explain E0599`.
    error: could not compile `geo-test-rust`.
    
    To learn more, run the command again with --verbose.
    
    

    Clone and build this repo to reproduce https://github.com/inclooder/rust-geo-test

    opened by inclooder 5
  • panic: Sweep line misses event to be removed

    panic: Sweep line misses event to be removed

    When aggregating some simple (convex, <6 vertices) polygons via repeated unions I get this panic:

    thread 'main' panicked at 'Sweep line misses event to be removed', src/main.rs:1:1
    

    I managed to create a .geojson fixture that provokes the panic:

    The black polygon is my aggregate, the orange one the one I want to union. Nudging the marked vertex unpanics the situation.

    image

    EDIT: added image, added fixture, more informations

    opened by daef 26
Owner
21re
21re
An implementation of WICG Import Maps specification

import_map A Rust implementation of WICG Import Maps specification. This crates is used in Deno project. The implementation is tested against WPT test

Deno Land 20 Nov 21, 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
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
Geospatial primitives and algorithms for Rust

geo Geospatial Primitives, Algorithms, and Utilities The geo crate provides geospatial primitive types such as Point, LineString, and Polygon, and pro

GeoRust 989 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
Rust read/write support for well-known text (WKT)

wkt Rust read/write support for well-known text (WKT). License Licensed under either of Apache License, Version 2.0 (LICENSE-APACHE or http://www.apac

GeoRust 40 Dec 11, 2022
Google Encoded Polyline encoding & decoding in Rust.

polyline Google Encoded Polyline encoding & decoding in Rust. A Note on Coordinate Order This crate uses Coordinate and LineString types from the geo-

GeoRust 14 Dec 11, 2022
Geocoding library for Rust.

geocoding Rust utilities to enrich addresses, cities, countries, and landmarks with geographic coordinates through third-party geocoding web services.

GeoRust 55 Dec 12, 2022
Rust read/write support for GPS Exchange Format (GPX)

gpx gpx is a library for reading and writing GPX (GPS Exchange Format) files. It uses the primitives provided by geo-types to allow for storage of GPS

GeoRust 63 Dec 5, 2022
Geospatial primitives and algorithms for Rust

geo Geospatial Primitives, Algorithms, and Utilities The geo crate provides geospatial primitive types such as Point, LineString, and Polygon, and pro

GeoRust 990 Jan 1, 2023
Rust bindings for GEOS

geos Rust bindings for GEOS C API. The supported geos version is >= 3.5 Disclaimer GEOS can be a tad strict on the validity on the input geometry and

GeoRust 75 Dec 11, 2022
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
Spatial Data Structures for Rust

spade Documentation Using spade Examples Project state Performance License Spade (SPAtial DatastructurEs, obviously!) implements a few nifty data stru

Stefan Altmayer 195 Dec 21, 2022
Fast 2D Delaunay triangulation in Rust. A port of Delaunator.

delaunator-rs A very fast static 2D Delaunay triangulation library for Rust. A port of Delaunator. Documentation Example use delaunator::{Point, trian

Vladimir Agafonkin 123 Dec 20, 2022
port of MapBox's earcut triangulation code to Rust language

Earcutr This is a port of the MapBox company's Earcut computer code, which triangulates polygons. Please see https://github.com/mapbox/earcut for more

don bright 41 Dec 26, 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 208 Dec 27, 2022