Panic on clip operation

[petersohn]

The following code panics. It tries to calculate clip for two geometries: a MultiPolygon containing two polygons that share a common edge, and a MultiLineString (I could reduce the latter to a single line segment).

use geo::{BooleanOps, MultiLineString, MultiPolygon};

fn main() {
    let p: MultiPolygon = serde_json::from_str(
        r###"
[
    {
      "exterior": [
        {
          "x": 6.6322207,
          "y": 45.3989067
        },
        {
          "x": 6.6321662,
          "y": 45.3985289
        },
        {
          "x": 6.632198,
          "y": 45.3980443
        },
        {
          "x": 6.6323042,
          "y": 45.3976988
        },
        {
          "x": 6.632397,
          "y": 45.3975054
        },
        {
          "x": 6.6317152,
          "y": 45.397207
        },
        {
          "x": 6.6314034,
          "y": 45.3969161
        },
        {
          "x": 6.6310307,
          "y": 45.3967459
        },
        {
          "x": 6.6309416,
          "y": 45.3970552
        },
        {
          "x": 6.6314229,
          "y": 45.3979076
        },
        {
          "x": 6.6318818,
          "y": 45.3988548
        },
        {
          "x": 6.6322207,
          "y": 45.3989067
        }
      ],
      "interiors": []
    },
    {
      "exterior": [
        {
          "x": 6.6323953,
          "y": 45.3987234
        },
        {
          "x": 6.6323378,
          "y": 45.3989153
        },
        {
          "x": 6.6322207,
          "y": 45.3989067
        },
        {
          "x": 6.6318818,
          "y": 45.3988548
        },
        {
          "x": 6.6322392,
          "y": 45.4001182
        },
        {
          "x": 6.6323193,
          "y": 45.4007802
        },
        {
          "x": 6.6322762,
          "y": 45.4015879
        },
        {
          "x": 6.6319272,
          "y": 45.4020968
        },
        {
          "x": 6.6323646,
          "y": 45.4024108
        },
        {
          "x": 6.6336433,
          "y": 45.40104
        },
        {
          "x": 6.6333669,
          "y": 45.4009995
        },
        {
          "x": 6.6330465,
          "y": 45.4008567
        },
        {
          "x": 6.6326829,
          "y": 45.4003462
        },
        {
          "x": 6.6324734,
          "y": 45.3997238
        },
        {
          "x": 6.6324281,
          "y": 45.3989607
        },
        {
          "x": 6.6324484,
          "y": 45.3988529
        },
        {
          "x": 6.6325764,
          "y": 45.3988146
        },
        {
          "x": 6.6323953,
          "y": 45.3987234
        }
      ],
      "interiors": []
    }
  ]
"###,
    )
    .unwrap();

    let l: MultiLineString = serde_json::from_str(
        r###"
[
    [
      {
        "x": 6.6315782,
        "y": 45.3978329
      },
      {
        "x": 6.6322564,
        "y": 45.3996708
      }
    ]
  ]
    "###,
    )
    .unwrap();

    let c = p.clip(&l, true);
    println!("{:?}", c);
}

The data is from OpenStreetMap. Here is a link to the geometries. The line is the segment of the line on the map that intersects the common edge of the areas.

Here is a backtrace.

thread 'main' panicked at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/active.rs:48:13:
unable to compare active segments!
stack backtrace:
   0: rust_begin_unwind
   1: core::panicking::panic_fmt
   2: <geo::algorithm::sweep::active::Active<T> as core::cmp::Ord>::cmp
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/active.rs:48:13
   3: core::slice::<impl [T]>::binary_search::{{closure}}
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/slice/mod.rs:2790:35
   4: core::slice::<impl [T]>::binary_search_by
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/slice/mod.rs:2855:23
   5: core::slice::<impl [T]>::binary_search
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/slice/mod.rs:2790:9
   6: geo::algorithm::sweep::vec_set::VecSet<geo::algorithm::sweep::active::Active<T>>::index_of
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/vec_set.rs:27:9
   7: geo::algorithm::sweep::proc::Sweep<C>::handle_event
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:232:30
   8: geo::algorithm::sweep::proc::Sweep<C>::handle_event
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:183:40
   9: geo::algorithm::sweep::proc::Sweep<C>::next_event::{{closure}}
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:46:13
  10: core::option::Option<T>::map
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/option.rs:1072:29
  11: geo::algorithm::sweep::proc::Sweep<C>::next_event
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:44:9
  12: <geo::algorithm::sweep::iter::CrossingsIter<C> as core::iter::traits::iterator::Iterator>::next
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/iter.rs:170:26
  13: geo::algorithm::bool_ops::op::Proc<T,S>::sweep
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/bool_ops/op.rs:68:30
  14: <geo_types::geometry::multi_polygon::MultiPolygon<T> as geo::algorithm::bool_ops::BooleanOps>::clip
             at /home/petersohn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/bool_ops/mod.rs:108:9
  15: test::main
             at ./src/main.rs:160:13
  16: core::ops::function::FnOnce::call_once
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/ops/function.rs:250:5

[brianreavis]

Here's another likely-related stacktrace I experienced today using different data:

thread 'Async Compute Task Pool (2)' panicked at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/vec_set.rs:29:14:
segment not found in active-vec-set: 5
stack backtrace:
 0: rust_begin_unwind
             at /rustc/aedd173a2c086e558c2b66d3743b344f977621a7/library/std/src/panicking.rs:647:5
   1: core::panicking::panic_fmt
             at /rustc/aedd173a2c086e558c2b66d3743b344f977621a7/library/core/src/panicking.rs:72:14
   2: core::result::unwrap_failed
             at /rustc/aedd173a2c086e558c2b66d3743b344f977621a7/library/core/src/result.rs:1649:5
   3: core::result::Result<T,E>::expect
             at /rustc/aedd173a2c086e558c2b66d3743b344f977621a7/library/core/src/result.rs:1030:23
   4: geo::algorithm::sweep::vec_set::VecSet<geo::algorithm::sweep::active::Active<T>>::index_of
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/vec_set.rs:27:9
   5: geo::algorithm::sweep::proc::Sweep<C>::handle_event
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:232:30
   6: geo::algorithm::sweep::proc::Sweep<C>::next_event::{{closure}}
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:46:13
   7: core::option::Option<T>::map
             at /rustc/aedd173a2c086e558c2b66d3743b344f977621a7/library/core/src/option.rs:1072:29
   8: geo::algorithm::sweep::proc::Sweep<C>::next_event
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/proc.rs:44:9
   9: <geo::algorithm::sweep::iter::CrossingsIter<C> as core::iter::traits::iterator::Iterator>::next
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/sweep/iter.rs:170:26
  10: geo::algorithm::bool_ops::op::Proc<T,S>::sweep
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/bool_ops/op.rs:68:30
  11: <geo_types::geometry::multi_polygon::MultiPolygon<T> as geo::algorithm::bool_ops::BooleanOps>::boolean_op
             at /Users/brianreavis/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.27.0/src/algorithm/bool_ops/mod.rs:94:9
  12: geo::algorithm::bool_ops::BooleanOps::intersection

[AntoineRenaud91]

Hi, I encountered a similar bug:

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

fn main() {
   let poly1 = Polygon::new(
        LineString::new(vec![
            Coord {
                x: -10339459.518507583,
                y: 3672178.7824083967,
            },
            Coord {
                x: -10172502.686420029,
                y: 3169028.9498966974,
            },
            Coord {
                x: -10002503.513328442,
                y: 3498113.19617442,
            },
        ]),
        vec![],
    );
    let poly2 = Polygon::new(
        LineString::new(vec![
            Coord {
                x: -10644125.090349106,
                y: 3510000.058398463,
            },
            Coord {
                x: -10010375.27222986,
                y: 3502179.60931681,
            },
            Coord {
                x: -10018249.493188547,
                y: 3506247.294314978,
            },
            Coord {
                x: -10018249.49318854,
                y: 3506247.294314993,
            },
            Coord {
                x: -10320063.446714956,
                y: 3765929.7827082784,
            }
        ]),
        vec![],
    );
    poly2.union(&poly1);
}

with stack trace:

thread 'main' panicked at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/vec_set.rs:29:14:
segment not found in active-vec-set: 1
stack backtrace:
   0: rust_begin_unwind
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/std/src/panicking.rs:645:5
   1: core::panicking::panic_fmt
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/panicking.rs:72:14
   2: core::result::unwrap_failed
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/result.rs:1654:5
   3: core::result::Result<T,E>::expect
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/result.rs:1034:23
   4: geo::algorithm::sweep::vec_set::VecSet<geo::algorithm::sweep::active::Active<T>>::index_of
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/vec_set.rs:27:9
   5: geo::algorithm::sweep::proc::Sweep<C>::handle_event
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/proc.rs:232:30
   6: geo::algorithm::sweep::proc::Sweep<C>::next_event::{{closure}}
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/proc.rs:46:13
   7: core::option::Option<T>::map
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/option.rs:1073:29
   8: geo::algorithm::sweep::proc::Sweep<C>::next_event
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/proc.rs:44:9
   9: <geo::algorithm::sweep::iter::CrossingsIter<C> as core::iter::traits::iterator::Iterator>::next
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/sweep/iter.rs:170:26
  10: geo::algorithm::bool_ops::op::Proc<T,S>::sweep
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/bool_ops/op.rs:81:30
  11: <geo_types::geometry::polygon::Polygon<T> as geo::algorithm::bool_ops::BooleanOps>::boolean_op
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/bool_ops/mod.rs:69:9
  12: geo::algorithm::bool_ops::BooleanOps::union
             at /home/arenaud/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.28.0/src/algorithm/bool_ops/mod.rs:33:9
  13: crashpolygeo::main
             at ./src/main.rs:46:5
  14: core::ops::function::FnOnce::call_once
             at /rustc/9b00956e56009bab2aa15d7bff10916599e3d6d6/library/core/src/ops/function.rs:250:5