21re / rust-geo-booleanop Goto Github PK

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" }

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

@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.

not really an issue, but I wanted to dump a reference here too:

I made a small comparison between some boolean operation algorithms and
wanted to share the results: https://daef.github.io/poly-bool-comparison/

The expected result is this

but every now and then artifacts appear like this

The artifacts seem to depend on the order of the unified polygons. Spade's r-tree is used to union polygons in parallel.

For some reason applying union on these polygons sequentially:

causes this result:

While performing intersections on some polygons I am running into cases where the holes of some polygons are being assigned to different ones on output.

I checked against the JavaScript version that the crate is based on and it has the same problem. So I've created an issue over there as well.

The data for one of these cases can be found in this gist.

I mostly fixed this for myself, but I'm not making a PR yet because geojson needs to version-bump geo_types before your test fixtures will work with this change.

https://github.com/nick-parker/rust-geo-booleanop

The current version of geo_types::rect::Rect enforces validity, so the sbbox and cbbox initializations with inf and neg_inf panic. It's easy enough to fix by just passing separate min, max mut coords through fill_queue and then constructing the bboxes afterward.

I am getting the error "assembly segments must be eulierian" when taking the difference of two multipolygons.

I have graphed my two multipolygons in Desmos:

I am taking the difference between the red and the blue multipolygons, such that I expect the result to be the small red triangle.

Here's the two multipolygons as rust objects:

    let red = MultiPolygon::new(
        vec![
            Polygon::new ( 
                LineString(vec![
                    Coord { x: -1.3119198, y: 0.9937218 }, 
                    Coord { x: -1.3202608, y: 1.0020628 }, 
                    Coord { x: -1.3415047, y: 0.95909566 }, 
                    Coord { x: -1.3119198, y: 0.9937218 },
                ]), 
                vec![]
            ), 
            Polygon::new ( 
                LineString(vec![
                    Coord { x: -1.2180908, y: 1.1035395 }, 
                    Coord { x: -1.1915252, y: 1.1346318 }, 
                    Coord { x: -1.2249147, y: 1.1949053 }, 
                    Coord { x: -1.252885, y: 1.1383337 }, 
                    Coord { x: -1.2180908, y: 1.1035395 },
                ]), 
                vec![]
            ),
        ]
    );
    let blue = MultiPolygon::new(
        vec![
            Polygon::new ( LineString(vec![
                Coord { x: -1.1199157, y: 1.0053644 }, 
                Coord { x: -1.2621856, y: 1.2621856 }, 
                Coord { x: -1.3197794, y: 1.2052281 }, 
                Coord { x: -1.1199157, y: 1.0053644 }]), 
                vec![]
            ),
        ]
    );

Whatever is causing this operation to fail is subtle enough that what I have for you here is not enough decimal places to replicate it, I'm sorry I cannot provide a better test case right away. I will say that upgrading from f32 to f64 in my code did not fix the issue.

I am doing a lot of difference operations, so the red multipolygon was not generated by hand, but is the result of several differences. I seem to be able to do almost identical operations tens of thousands of times with different multipolygons before this issue is encountered. You can imagine there would have been other polygons, sharing edges to the left and right of the blue polygon, which have already been used to take a difference, making it such that the right piece of the red multipolygon essentially shares its exact edges with the blue triangle. Perhaps some subtlety exists where no floating point error whatsoever occurred in my special case and the two edges being exactly co-linear causes the algorithm to fail.

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

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

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.

[
  {
    "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": []
  }
]

#!/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()

I have a process which creates some polygons, and some of them are invalid and weird. But this library is unable to deal with them.

With this test:

#[test]
fn infinite_bad_geom() {
    let orig = fixture_multi_polygon("orig.geojson");
    let bad = fixture_multi_polygon("bad.geojson");
    orig.union(&bad);
}

And these files:

bad.geojson.gz
orig.geojson.gz

You get this following stack overflow:

thread 'infinite::infinite_bad_geom' has overflowed its stack
fatal runtime error: stack overflow
error: process didn't exit successfully: `/home/rory/code/rust/rust-geo-booleanop/target/debug/deps/geo_booleanop_tests-53da8e6c52baad74 'infinite::infinite_bad_geom' --nocapture` (signal: 6, SIGABRT: process abort signal)

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.

Here is the resulting union:

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: [],
}
*/

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.

EDIT: added image, added fixture, more informations

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?).

https://people.computing.clemson.edu/~vbz/cs230papers/martinez_boolean.pdf - link from README doesn't work.

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)]

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!

As far as I can tell, the geo_types::LineString in a geo_types::Polygon is supposed to have its first and last coordinates be the same. (I believe this is what the docs mean by "closed". Is that correct?)
I have found a case where poly1 and poly2 both satisfy that condition, but poly1.intersection(&poly2) does not.

Is this a bug? Or am I just doing something wrong?

Cargo.toml

...
[dependencies]
geo-types = "0.3.0"
geo-booleanop = { git = "https://github.com/21re/rust-geo-booleanop.git" }

main.rs

#![forbid(unsafe_code)]

extern crate geo_types;
extern crate geo_booleanop;

use geo_types::*;
use geo_booleanop::boolean::BooleanOp;

fn is_closed(p: &Polygon<f64>) -> bool {
    &p.exterior.0[0] == p.exterior.0.last().unwrap()
}

fn main() {
    let poly1: Polygon<f64> = 
        Polygon {
            exterior: LineString(
                vec![
                    Coordinate {
                        x: -530.,
                        y: -530.
                    },
                    Coordinate {
                        x: -530.,
                        y: 530.
                    },
                    Coordinate {
                        x: 530.,
                        y: 530.
                    },
                    Coordinate {
                        x: 530.,
                        y: -530.
                    },
                    Coordinate {
                        x: -530.,
                        y: -530.
                    }
                ]
            ),
            interiors: vec![]
        };
    let poly2: Polygon<f64> =
        Polygon {
            exterior: LineString(
                vec![
                    Coordinate {
                        x: 1.2500125250252,
                        y: -531.
                    },
                    Coordinate {
                        x: -98.,
                        y: -531.
                    },
                    Coordinate {
                        x: -98.,
                        y: 531.
                    },
                    Coordinate {
                        x: 1.250012525025,
                        y: 531.
                    },
                    Coordinate {
                        x: 1.2500125250252,
                        y: -531.
                    }
                ]
            ),
            interiors: vec![]
        };

    println!("{}", is_closed(&poly1));
    println!("{}", is_closed(&poly2));
    println!("{}", is_closed(&poly1.intersection(&poly2).0[0]));

}

Output:

true
true
false

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:
nick-parker@ae3159f

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.