Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Panic in the intersection function #1053

Closed
wzjsun opened this issue Aug 10, 2023 · 3 comments
Closed

Panic in the intersection function #1053

wzjsun opened this issue Aug 10, 2023 · 3 comments

Comments

@wzjsun
Copy link

wzjsun commented Aug 10, 2023

Code to reproduce::

use geo::{BooleanOps, Polygon, Coord, LineString};

#[test]
fn test() {
        // Reproduction occurs when intersecting Polygon<f32> types, but Polygon<f64> does not reproduce.
	let geo1 = Polygon::<f32>::new(LineString(vec![Coord { x: 0.0, y: 0.0 }, Coord { x: 0.0, y: 200.0 }, Coord { x: 200.0, y: 200.0 }, Coord { x: 200.0, y: 0.0 }, Coord { x: 0.0, y: 0.0 }]), vec![] );
	let geo2 = Polygon::<f32>::new(LineString(vec![Coord { x: -0.17588139, y: 0.0015348792 }, Coord { x: 1.5845897, y: 201.73154 }, Coord { x: 200.1759, y: 199.99846 }, Coord { x: 198.41544, y: -1.7315454 }, Coord { x: -0.17588139, y: 0.0015348792 }]), vec![] );
	let r = geo1.intersection(&geo2);
	println!("r=================={:?}", r);
}

Output::

---- test stdout ----
thread 'test' panicked at 'segment not found in active-vec-set: 1', C:\Users\chuanyan\.cargo\registry\src\github.com-1ecc6299db9ec823\geo-0.26.0\src\algorithm\sweep\vec_set.rs:22:14 
@RobWalt
Copy link
Contributor

RobWalt commented Sep 26, 2023

You encountered one of the many issues that are still left open with the implementation of BoolOps in geo. Please refer to #976

Edit: And thanks for the example test! 👍

@RobWalt
Copy link
Contributor

RobWalt commented Oct 31, 2023

I added this as a test to #1089 and it passes.

michaelkirk added a commit that referenced this issue Oct 28, 2024
We've had several reports of crashes in our BooleanOps implementation
over the years. Some of them have been addressed, but there remains a
long tail of crashes.

FIXES #913, #948, #976, #1053, #1064, #1103, #1104, #1127, #1174, #1189, 1193

The root of the issue (as I understand it) is that floating point
rounding errors break the invariants of our sweep line algorithm. After
a couple years, it seems like a "simple" resolution is not in sight.

In the meanwhile, the i_overlay crate appeared. It uses a strategy that
maps floating point geometries to a scaled fixed point grid, which
nicely avoids the kind of problems we were having.

Related changes included:

Included are some tests that cover all reports in the issue tracker of the existing BoolOps panic'ing

JTS supports Bops between all geometry types. We support a more limited
set:

1. Two 2-Dimensional geometries `boolean_op`.
2. A 1-Dimenstinoal geometry with a 2-D geometry, which we call `clip`.

So this maps JTS's Line x Poly intersection tests to our Clip method.

- rm unused sweep code now that old boolops is gone

  I marked a couple fields as `allow(unused)` because they are used for
  printing debug repr in tests.

Speed up benches by only benching local boolop impl by default
@michaelkirk
Copy link
Member

I just merged #1234 which replaces our BoolOps implementation with one backed by the i_overlay crate. This should resolve the issue you're seeing. Let us know if it recurs. You can use it now if you use the unreleased geo crate, otherwise we expect it to be part of the upcoming v0.29.0 release.

urschrei pushed a commit to urschrei/geo that referenced this issue Nov 6, 2024
We've had several reports of crashes in our BooleanOps implementation
over the years. Some of them have been addressed, but there remains a
long tail of crashes.

FIXES georust#913, georust#948, georust#976, georust#1053, georust#1064, georust#1103, georust#1104, georust#1127, georust#1174, georust#1189, 1193

The root of the issue (as I understand it) is that floating point
rounding errors break the invariants of our sweep line algorithm. After
a couple years, it seems like a "simple" resolution is not in sight.

In the meanwhile, the i_overlay crate appeared. It uses a strategy that
maps floating point geometries to a scaled fixed point grid, which
nicely avoids the kind of problems we were having.

Related changes included:

Included are some tests that cover all reports in the issue tracker of the existing BoolOps panic'ing

JTS supports Bops between all geometry types. We support a more limited
set:

1. Two 2-Dimensional geometries `boolean_op`.
2. A 1-Dimenstinoal geometry with a 2-D geometry, which we call `clip`.

So this maps JTS's Line x Poly intersection tests to our Clip method.

- rm unused sweep code now that old boolops is gone

  I marked a couple fields as `allow(unused)` because they are used for
  printing debug repr in tests.

Speed up benches by only benching local boolop impl by default
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants