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!

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

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!

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

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

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

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:

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:

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

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

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:

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

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:

to

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

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

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.

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

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:

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:

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

I've also updated the readme a little bit.

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

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

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.

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

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