parry3d::transformation

Function polygons_intersection_points

Source 
pub fn polygons_intersection_points(
    poly1: &[Point2<f32>],
    poly2: &[Point2<f32>],
) -> Result<Vec<Vec<Point2<f32>>>, PolygonsIntersectionError>
Expand description

Computes the intersection points of two possibly non-convex polygons.

This function handles both convex and non-convex (concave) polygons, making it more general than convex_polygons_intersection_points. However, it requires that:

  • Neither polygon self-intersects
  • Both polygons are oriented counter-clockwise

The result is a vector of polygons, where each polygon represents one connected component of the intersection. In most cases there will be only one component, but complex intersections can produce multiple separate regions.

§Important Notes

  • Non-convex support: This function works with concave polygons
  • Multiple components: Returns a Vec<Vec<Point2<Real>>> because the intersection of two concave polygons can produce multiple separate regions
  • No self-intersection: Input polygons must not self-intersect
  • Counter-clockwise winding: Both polygons must be oriented counter-clockwise
  • Performance: Slower than convex_polygons_intersection_points. If both polygons are convex, use that function instead.

§Arguments

  • poly1 - First polygon as a slice of vertices
  • poly2 - Second polygon as a slice of vertices

§Returns

  • Ok(Vec<Vec<Point2<Real>>>) - A vector of intersection polygons (usually just one)
  • Err(PolygonsIntersectionError::InfiniteLoop) - If the polygons are ill-formed

§Examples

§Example 1: Two non-convex polygons

// L-shaped polygon
let l_shape = vec![
    Point2::origin(),
    Point2::new(3.0, 0.0),
    Point2::new(3.0, 1.0),
    Point2::new(1.0, 1.0),
    Point2::new(1.0, 3.0),
    Point2::new(0.0, 3.0),
];

// Square overlapping the L-shape
let square = vec![
    Point2::new(0.5, 0.5),
    Point2::new(2.5, 0.5),
    Point2::new(2.5, 2.5),
    Point2::new(0.5, 2.5),
];

let result = polygons_intersection_points(&l_shape, &square).unwrap();

// Should have intersection regions
assert!(!result.is_empty());

§Example 2: Convex polygons (also works)

let triangle = vec![
    Point2::origin(),
    Point2::new(4.0, 0.0),
    Point2::new(2.0, 3.0),
];

let square = vec![
    Point2::new(1.0, 0.5),
    Point2::new(3.0, 0.5),
    Point2::new(3.0, 2.0),
    Point2::new(1.0, 2.0),
];

let result = polygons_intersection_points(&triangle, &square).unwrap();
assert_eq!(result.len(), 1); // One intersection region

§Errors

Returns PolygonsIntersectionError::InfiniteLoop if:

  • Either polygon self-intersects
  • The polygons have degenerate or duplicate edges
  • The winding order is inconsistent

§See Also