klayout_geom/
boolean.rs

1//! Boolean ops on `Region`s, backed by `i_overlay`.
2//!
3//! All ops produce merged, canonicalized output. The float bridge uses
4//! `[f64; 2]` — exact for any i64 coordinate < 2^53 (chip-scale layouts
5//! never come anywhere near that).
6
7use crate::region::{polygon_from_int_contour, Region};
8use i_overlay::core::fill_rule::FillRule;
9use i_overlay::core::overlay_rule::OverlayRule;
10use i_overlay::float::single::SingleFloatOverlay;
11use klayout_core::Polygon;
12
13pub fn union(a: &Region, b: &Region) -> Region {
14    overlay(a, b, OverlayRule::Union)
15}
16
17pub fn intersection(a: &Region, b: &Region) -> Region {
18    overlay(a, b, OverlayRule::Intersect)
19}
20
21pub fn difference(a: &Region, b: &Region) -> Region {
22    overlay(a, b, OverlayRule::Difference)
23}
24
25pub fn xor(a: &Region, b: &Region) -> Region {
26    overlay(a, b, OverlayRule::Xor)
27}
28
29/// Self-merge: collapse a region into its merged canonical form.
30/// Equivalent to `union(r, &Region::empty())`.
31pub fn merge(r: &Region) -> Region {
32    overlay(r, &Region::empty(), OverlayRule::Union)
33}
34
35fn polygon_to_floats(p: &Polygon) -> Vec<Vec<[f64; 2]>> {
36    // i_overlay convention: CCW hull, CW holes. Our canonical form is the
37    // opposite (CW hull / CCW holes), so reverse on the way in.
38    let mut out: Vec<Vec<[f64; 2]>> = Vec::with_capacity(1 + p.holes.len());
39    out.push(
40        p.hull
41            .iter()
42            .rev()
43            .map(|pt| [pt.x as f64, pt.y as f64])
44            .collect(),
45    );
46    for hole in &p.holes {
47        out.push(
48            hole.iter()
49                .rev()
50                .map(|pt| [pt.x as f64, pt.y as f64])
51                .collect(),
52        );
53    }
54    out
55}
56
57fn region_to_shapes(r: &Region) -> Vec<Vec<Vec<[f64; 2]>>> {
58    r.polygons.iter().map(polygon_to_floats).collect()
59}
60
61fn overlay(a: &Region, b: &Region, rule: OverlayRule) -> Region {
62    let subj = region_to_shapes(a);
63    let clip = region_to_shapes(b);
64    // i_overlay returns Vec<shapes> where each shape = Vec<contours> and
65    // contour = Vec<[f64; 2]>. The first contour is the hull, the rest are
66    // holes.
67    let result = subj.overlay(&clip, rule, FillRule::NonZero);
68
69    let mut polys: Vec<Polygon> = Vec::with_capacity(result.len());
70    for shape in result {
71        let mut iter = shape.into_iter();
72        let Some(hull_f) = iter.next() else { continue };
73        let hull_int: Vec<(i64, i64)> = hull_f
74            .iter()
75            .map(|p| (p[0].round() as i64, p[1].round() as i64))
76            .collect();
77        let Some(mut poly) = polygon_from_int_contour(&hull_int) else { continue };
78        for hole_f in iter {
79            let hole_int: Vec<(i64, i64)> = hole_f
80                .iter()
81                .map(|p| (p[0].round() as i64, p[1].round() as i64))
82                .collect();
83            if hole_int.len() >= 3 {
84                poly.add_hole(
85                    hole_int
86                        .into_iter()
87                        .map(|(x, y)| klayout_core::Point::new(x, y)),
88                );
89            }
90        }
91        // Drop degenerate (zero-area) results from edge overlap.
92        if signed_area2(&poly) != 0 {
93            polys.push(poly);
94        }
95    }
96
97    let mut out = Region::empty();
98    out.set_polygons(polys);
99    out
100}
101
102fn signed_area2(p: &Polygon) -> i128 {
103    let mut s: i128 = 0;
104    let n = p.hull.len();
105    for i in 0..n {
106        let a = p.hull[i];
107        let b = p.hull[(i + 1) % n];
108        s += (a.x as i128) * (b.y as i128) - (b.x as i128) * (a.y as i128);
109    }
110    s
111}
klayout_geom/boolean.rs

klayout_geom/
boolean.rs
