physdes/
vlsi_ops.rs

1//! VLSI-specific geometric operations
2//!
3//! This module provides operations commonly used in VLSI physical design and layout.
4
5use crate::{Point, Polygon};
6
7/// Represents a rectangle in 2D space defined by its minimum (bottom-left)
8/// and maximum (top-right) corner points.
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct Rectangle<T> {
11    /// The minimum (bottom-left) corner point
12    pub min: Point<T, T>,
13    /// The maximum (top-right) corner point
14    pub max: Point<T, T>,
15}
16
17impl<T: Clone + Ord + Copy + std::ops::Add<Output = T>> Rectangle<T> {
18    /// Creates a new rectangle from min and max points
19    ///
20    /// # Arguments
21    ///
22    /// * `min` - The minimum (bottom-left) corner
23    /// * `max` - The maximum (top-right) corner
24    ///
25    /// # Examples
26    ///
27    /// ```
28    /// use physdes::{Point, vlsi_ops::Rectangle};
29    ///
30    /// let rect = Rectangle::new(
31    ///     Point::new(0, 0),
32    ///     Point::new(10, 20)
33    /// );
34    /// ```
35    pub fn new(min: Point<T, T>, max: Point<T, T>) -> Self {
36        assert!(min.xcoord <= max.xcoord && min.ycoord <= max.ycoord);
37        Rectangle { min, max }
38    }
39
40    /// Creates a rectangle from origin, width, and height
41    pub fn from_dimensions(origin: Point<T, T>, width: T, height: T) -> Self {
42        Rectangle::new(
43            origin,
44            Point::new(origin.xcoord + width, origin.ycoord + height),
45        )
46    }
47
48    /// Checks if this rectangle overlaps with another
49    ///
50    /// Two rectangles overlap iff their projections on both axes overlap:
51    ///
52    /// $$\[a_x,b_x\] \cap \[c_x,d_x\] \neq \varnothing \land \[a_y,b_y\] \cap \[c_y,d_y\] \neq \varnothing$$
53    ///
54    /// # Examples
55    ///
56    /// ```
57    /// use physdes::{Point, vlsi_ops::Rectangle};
58    ///
59    /// let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
60    /// let rect2 = Rectangle::new(Point::new(5, 5), Point::new(15, 15));
61    /// assert!(rect1.overlaps(&rect2));
62    ///
63    /// let rect3 = Rectangle::new(Point::new(20, 20), Point::new(30, 30));
64    /// assert!(!rect1.overlaps(&rect3));
65    /// ```
66    pub fn overlaps(&self, other: &Self) -> bool {
67        self.min.xcoord <= other.max.xcoord
68            && self.max.xcoord >= other.min.xcoord
69            && self.min.ycoord <= other.max.ycoord
70            && self.max.ycoord >= other.min.ycoord
71    }
72
73    /// Checks if this rectangle contains another rectangle
74    ///
75    /// $$A \supseteq B \iff A_{\min x} \le B_{\min x} \land A_{\max x} \ge B_{\max x}$$
76    pub fn contains(&self, other: &Self) -> bool {
77        self.min.xcoord <= other.min.xcoord
78            && self.max.xcoord >= other.max.xcoord
79            && self.min.ycoord <= other.min.ycoord
80            && self.max.ycoord >= other.max.ycoord
81    }
82
83    /// Checks if this rectangle contains a point
84    pub fn contains_point(&self, point: &Point<T, T>) -> bool {
85        point.xcoord >= self.min.xcoord
86            && point.xcoord <= self.max.xcoord
87            && point.ycoord >= self.min.ycoord
88            && point.ycoord <= self.max.ycoord
89    }
90
91    /// Computes the intersection with another rectangle
92    ///
93    /// $$A \cap B = \[\\max(x_{A\\min}, x_{B\\min}),\; \\min(x_{A\\max}, x_{B\\max})\] \times \[\\max(y_{A\\min}, y_{B\\min}),\; \\min(y_{A\\max}, y_{B\\max})\]$$
94    ///
95    /// Returns `None` if the rectangles don't overlap
96    pub fn intersect(&self, other: &Self) -> Option<Self>
97    where
98        T: std::ops::Add<Output = T>,
99    {
100        if !self.overlaps(other) {
101            return None;
102        }
103
104        Some(Rectangle::new(
105            Point::new(
106                self.min.xcoord.max(other.min.xcoord),
107                self.min.ycoord.max(other.min.ycoord),
108            ),
109            Point::new(
110                self.max.xcoord.min(other.max.xcoord),
111                self.max.ycoord.min(other.max.ycoord),
112            ),
113        ))
114    }
115
116    /// Computes the area of the rectangle
117    ///
118    /// $$A = w \times h = (x_{\max} - x_{\min}) \times (y_{\max} - y_{\min})$$
119    pub fn area(&self) -> T
120    where
121        T: std::ops::Sub<Output = T> + std::ops::Mul<Output = T>,
122    {
123        let width = self.max.xcoord - self.min.xcoord;
124        let height = self.max.ycoord - self.min.ycoord;
125        width * height
126    }
127
128    /// Computes the bounding rectangle of two rectangles
129    ///
130    /// $$\text{bbox}(A,B) = \[\\min(x_{A\\min}, x_{B\\min}),\; \\max(x_{A\\max}, x_{B\\max})\] \times \[\\min(y_{A\\min}, y_{B\\min}),\; \\max(y_{A\\max}, y_{B\\max})\]$$
131    pub fn bounding_rect(&self, other: &Self) -> Self {
132        Rectangle::new(
133            Point::new(
134                self.min.xcoord.min(other.min.xcoord),
135                self.min.ycoord.min(other.min.ycoord),
136            ),
137            Point::new(
138                self.max.xcoord.max(other.max.xcoord),
139                self.max.ycoord.max(other.max.ycoord),
140            ),
141        )
142    }
143
144    /// Converts to a Polygon
145    pub fn to_polygon(&self) -> Polygon<T>
146    where
147        T: Clone + std::ops::Add<Output = T> + num_traits::Num + std::ops::AddAssign + Ord,
148    {
149        Polygon::new(&[
150            self.min,
151            Point::new(self.max.xcoord, self.min.ycoord),
152            self.max,
153            Point::new(self.min.xcoord, self.max.ycoord),
154        ])
155    }
156}
157
158/// Detects if any pair of rectangles overlap using the line sweep algorithm.
159///
160/// The algorithm uses a sweep line approach:
161/// 1. Create events for left and right edges of each rectangle
162/// 2. Sort events by x-coordinate
163/// 3. Sweep from left to right, maintaining active rectangles
164/// 4. Check y-overlap when a new rectangle becomes active
165///
166/// # Arguments
167///
168/// * `rectangles` - A slice of rectangles to check for overlaps
169///
170/// # Returns
171///
172/// The indices of two overlapping rectangles if found, otherwise `None`
173///
174/// # Examples
175///
176/// ```
177/// use physdes::{Point, vlsi_ops::{Rectangle, detect_overlap}};
178///
179/// let rects = vec![
180///     Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
181///     Rectangle::new(Point::new(5, 5), Point::new(15, 15)),
182///     Rectangle::new(Point::new(20, 20), Point::new(30, 30)),
183/// ];
184/// let result = detect_overlap(&rects);
185/// assert!(result.is_some());
186/// assert_eq!(result.unwrap(), (0, 1));
187/// ```
188pub fn detect_overlap<T>(rectangles: &[Rectangle<T>]) -> Option<(usize, usize)>
189where
190    T: Copy + Ord,
191{
192    if rectangles.len() < 2 {
193        return None;
194    }
195
196    // Create events: (x_coord, is_start, rect_index)
197    let mut events: Vec<(T, bool, usize)> = Vec::with_capacity(rectangles.len() * 2);
198    for (idx, rect) in rectangles.iter().enumerate() {
199        events.push((rect.min.xcoord, true, idx));
200        events.push((rect.max.xcoord, false, idx));
201    }
202
203    events.sort_by_key(|a| a.0);
204
205    // Active rectangles: (rect_index, y_min, y_max)
206    let mut active: Vec<(usize, T, T)> = Vec::new();
207
208    for &(_x, is_start, idx) in &events {
209        let rect = &rectangles[idx];
210
211        if is_start {
212            // Check y-overlap with all active rectangles
213            for &(other_idx, other_y_min, other_y_max) in &active {
214                if rect.min.ycoord <= other_y_max && other_y_min <= rect.max.ycoord {
215                    return Some((other_idx, idx));
216                }
217            }
218            active.push((idx, rect.min.ycoord, rect.max.ycoord));
219        } else {
220            // O(1) removal: swap with back and pop
221            for i in 0..active.len() {
222                if active[i].0 == idx {
223                    active.swap_remove(i);
224                    break;
225                }
226            }
227        }
228    }
229
230    None
231}
232
233/// Calculates Manhattan distance between two points
234///
235/// $$d = |x_1 - x_2| + |y_1 - y_2|$$
236///
237/// The Manhattan distance is the sum of the absolute differences of coordinates.
238/// This is commonly used in VLSI routing where wires can only run horizontally or vertically.
239///
240/// # Arguments
241///
242/// * `p1` - First point
243/// * `p2` - Second point
244///
245/// # Examples
246///
247/// ```
248/// use physdes::{Point, vlsi_ops::manhattan_distance};
249///
250/// let p1 = Point::new(0, 0);
251/// let p2 = Point::new(3, 4);
252/// let dist = manhattan_distance(&p1, &p2);
253/// assert_eq!(dist, 7); // |3-0| + |4-0| = 7
254/// ```
255pub fn manhattan_distance<T>(p1: &Point<T, T>, p2: &Point<T, T>) -> T
256where
257    T: Ord + Copy + std::ops::Sub<Output = T> + std::ops::Add<Output = T>,
258{
259    let dx = if p1.xcoord > p2.xcoord {
260        p1.xcoord - p2.xcoord
261    } else {
262        p2.xcoord - p1.xcoord
263    };
264    let dy = if p1.ycoord > p2.ycoord {
265        p1.ycoord - p2.ycoord
266    } else {
267        p2.ycoord - p1.ycoord
268    };
269    dx + dy
270}
271
272/// Checks if two rectangles satisfy minimum spacing requirements
273///
274/// # Arguments
275///
276/// * `rect1` - First rectangle
277/// * `rect2` - Second rectangle
278/// * `min_spacing` - Minimum required spacing
279///
280/// # Examples
281///
282/// ```
283/// use physdes::{Point, vlsi_ops::{Rectangle, check_spacing}};
284///
285/// let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
286/// let rect2 = Rectangle::new(Point::new(10, 0), Point::new(20, 10));
287///
288/// // These rectangles touch (spacing = 0)
289/// assert!(!check_spacing(&rect1, &rect2, 1));
290///
291/// let rect3 = Rectangle::new(Point::new(12, 0), Point::new(22, 10));
292/// // These have spacing of 2
293/// assert!(check_spacing(&rect1, &rect3, 1));
294/// ```
295pub fn check_spacing<T>(rect1: &Rectangle<T>, rect2: &Rectangle<T>, min_spacing: T) -> bool
296where
297    T: Ord + Copy + std::ops::Sub<Output = T> + std::ops::Add<Output = T>,
298{
299    if rect1.overlaps(rect2) {
300        return false;
301    }
302
303    // Calculate horizontal spacing
304    let horiz_spacing = if rect1.max.xcoord <= rect2.min.xcoord {
305        rect2.min.xcoord - rect1.max.xcoord
306    } else if rect2.max.xcoord <= rect1.min.xcoord {
307        rect1.min.xcoord - rect2.max.xcoord
308    } else {
309        T::clone(&min_spacing) // Overlapping in x, check y
310    };
311
312    // Calculate vertical spacing
313    let vert_spacing = if rect1.max.ycoord <= rect2.min.ycoord {
314        rect2.min.ycoord - rect1.max.ycoord
315    } else if rect2.max.ycoord <= rect1.min.ycoord {
316        rect1.min.ycoord - rect2.max.ycoord
317    } else {
318        T::clone(&min_spacing) // Overlapping in y, check x
319    };
320
321    horiz_spacing >= min_spacing && vert_spacing >= min_spacing
322}
323
324/// Computes the minimum bounding rectangle of a set of rectangles
325///
326/// $$\text{bbox} = \left\[\\min_i x_{i\\min},\; \\max_i x_{i\\max}\\right\] \times \left\[\\min_i y_{i\\min},\; \\max_i y_{i\\max}\\right\]$$
327///
328/// # Arguments
329///
330/// * `rects` - Slice of rectangles
331///
332/// # Examples
333///
334/// ```
335/// use physdes::{Point, vlsi_ops::{Rectangle, bounding_rect}};
336///
337/// let rects = vec![
338///     Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
339///     Rectangle::new(Point::new(5, 5), Point::new(15, 15)),
340/// ];
341///
342/// let bbox = bounding_rect(&rects).unwrap();
343/// assert_eq!(bbox.min, Point::new(0, 0));
344/// assert_eq!(bbox.max, Point::new(15, 15));
345/// ```
346pub fn bounding_rect<T>(rects: &[Rectangle<T>]) -> Option<Rectangle<T>>
347where
348    T: Ord + Copy + std::ops::Add<Output = T>,
349{
350    if rects.is_empty() {
351        return None;
352    }
353
354    let mut min_x = rects[0].min.xcoord;
355    let mut min_y = rects[0].min.ycoord;
356    let mut max_x = rects[0].max.xcoord;
357    let mut max_y = rects[0].max.ycoord;
358
359    for rect in &rects[1..] {
360        min_x = min_x.min(rect.min.xcoord);
361        min_y = min_y.min(rect.min.ycoord);
362        max_x = max_x.max(rect.max.xcoord);
363        max_y = max_y.max(rect.max.ycoord);
364    }
365
366    Some(Rectangle::new(
367        Point::new(min_x, min_y),
368        Point::new(max_x, max_y),
369    ))
370}
371
372/// Computes total area covered by rectangles, accounting for overlaps
373///
374/// # Examples
375///
376/// ```
377/// use physdes::{Point, vlsi_ops::{Rectangle, total_area}};
378///
379/// let rects = vec![
380///     Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
381///     Rectangle::new(Point::new(5, 5), Point::new(15, 15)),
382/// ];
383///
384/// let area = total_area(&rects);
385/// // First rect: 100, second rect: 100, overlap: 25, total: 175
386/// assert_eq!(area, 175);
387/// ```
388pub fn total_area(rects: &[Rectangle<i32>]) -> i32 {
389    if rects.is_empty() {
390        return 0;
391    }
392
393    let mut total = 0;
394    for (i, rect) in rects.iter().enumerate() {
395        total += rect.area();
396        // Subtract overlaps with previously counted rectangles
397        for other in &rects[..i] {
398            if let Some(intersection) = rect.intersect(other) {
399                total -= intersection.area();
400            }
401        }
402    }
403
404    total
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410
411    #[test]
412    fn test_rectangle_creation() {
413        let rect = Rectangle::new(Point::new(0, 0), Point::new(10, 20));
414        assert_eq!(rect.min, Point::new(0, 0));
415        assert_eq!(rect.max, Point::new(10, 20));
416    }
417
418    #[test]
419    fn test_rectangle_overlap() {
420        let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
421        let rect2 = Rectangle::new(Point::new(5, 5), Point::new(15, 15));
422        assert!(rect1.overlaps(&rect2));
423
424        let rect3 = Rectangle::new(Point::new(20, 20), Point::new(30, 30));
425        assert!(!rect1.overlaps(&rect3));
426    }
427
428    #[test]
429    fn test_rectangle_area() {
430        let rect = Rectangle::new(Point::new(0, 0), Point::new(10, 20));
431        assert_eq!(rect.area(), 200);
432    }
433
434    #[test]
435    fn test_manhattan_distance() {
436        let p1 = Point::new(0, 0);
437        let p2 = Point::new(3, 4);
438        assert_eq!(manhattan_distance(&p1, &p2), 7);
439
440        let p3 = Point::new(5, 0);
441        assert_eq!(manhattan_distance(&p1, &p3), 5);
442    }
443
444    #[test]
445    fn test_check_spacing() {
446        let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
447        let rect2 = Rectangle::new(Point::new(10, 0), Point::new(20, 10));
448        assert!(!check_spacing(&rect1, &rect2, 1));
449
450        let rect3 = Rectangle::new(Point::new(12, 0), Point::new(22, 10));
451        assert!(check_spacing(&rect1, &rect3, 1));
452    }
453
454    #[test]
455    fn test_bounding_rect() {
456        let rects = vec![
457            Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
458            Rectangle::new(Point::new(5, 5), Point::new(15, 15)),
459        ];
460
461        let bbox = bounding_rect(&rects).unwrap();
462        assert_eq!(bbox.min, Point::new(0, 0));
463        assert_eq!(bbox.max, Point::new(15, 15));
464    }
465
466    #[test]
467    fn test_total_area() {
468        let rects = vec![
469            Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
470            Rectangle::new(Point::new(5, 5), Point::new(15, 15)),
471        ];
472
473        let area = total_area(&rects);
474        assert_eq!(area, 175);
475    }
476
477    #[test]
478    fn test_from_dimensions() {
479        let origin = Point::new(5, 10);
480        let rect = Rectangle::from_dimensions(origin, 20, 30);
481        assert_eq!(rect.min, origin);
482        assert_eq!(rect.max, Point::new(25, 40));
483    }
484
485    #[test]
486    fn test_rectangle_contains() {
487        let rect = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
488        let inner = Rectangle::new(Point::new(2, 2), Point::new(8, 8));
489        let outer = Rectangle::new(Point::new(-5, -5), Point::new(15, 15));
490
491        assert!(rect.contains(&inner));
492        assert!(!rect.contains(&outer));
493    }
494
495    #[test]
496    fn test_rectangle_contains_point() {
497        let rect = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
498        let inside = Point::new(5, 5);
499        let outside = Point::new(15, 15);
500        let on_edge = Point::new(10, 5);
501
502        assert!(rect.contains_point(&inside));
503        assert!(!rect.contains_point(&outside));
504        assert!(rect.contains_point(&on_edge));
505    }
506
507    #[test]
508    fn test_bounding_rect_method() {
509        let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
510        let rect2 = Rectangle::new(Point::new(5, 5), Point::new(15, 15));
511        let bbox = rect1.bounding_rect(&rect2);
512
513        assert_eq!(bbox.min, Point::new(0, 0));
514        assert_eq!(bbox.max, Point::new(15, 15));
515    }
516
517    #[test]
518    fn test_to_polygon() {
519        let rect = Rectangle::new(Point::new(0, 0), Point::new(10, 20));
520        let polygon = rect.to_polygon();
521
522        assert_eq!(polygon.vertices().len(), 4);
523        assert!(polygon.is_rectilinear());
524    }
525
526    #[test]
527    fn test_bounding_rect_empty() {
528        let rects: Vec<Rectangle<i32>> = vec![];
529        assert!(bounding_rect(&rects).is_none());
530    }
531
532    #[test]
533    fn test_total_area_empty() {
534        let rects: Vec<Rectangle<i32>> = vec![];
535        assert_eq!(total_area(&rects), 0);
536    }
537
538    #[test]
539    fn test_manhattan_distance_reverse() {
540        // Test case where p2 > p1 (different branch)
541        let p1 = Point::new(5, 3);
542        let p2 = Point::new(1, 0);
543        assert_eq!(manhattan_distance(&p1, &p2), 7); // |5-1| + |3-0| = 7
544    }
545
546    #[test]
547    fn test_manhattan_distance_same() {
548        // Test case where coordinates are equal
549        let p1 = Point::new(5, 5);
550        let p2 = Point::new(5, 5);
551        assert_eq!(manhattan_distance(&p1, &p2), 0);
552    }
553
554    #[test]
555    fn test_check_spacing_vertical() {
556        // Test vertical spacing
557        let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
558        let rect2 = Rectangle::new(Point::new(0, 10), Point::new(10, 20));
559        assert!(!check_spacing(&rect1, &rect2, 1)); // touching
560
561        let rect3 = Rectangle::new(Point::new(0, 12), Point::new(10, 22));
562        assert!(check_spacing(&rect1, &rect3, 1)); // spacing of 2
563    }
564
565    #[test]
566    fn test_check_spacing_overlapping() {
567        // Test case where rectangles overlap
568        let rect1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
569        let rect2 = Rectangle::new(Point::new(5, 5), Point::new(15, 15));
570        assert!(!check_spacing(&rect1, &rect2, 1)); // overlapping
571    }
572
573    #[test]
574    fn test_rectangle_intersect_non_overlapping() {
575        let r1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
576        let r2 = Rectangle::new(Point::new(20, 20), Point::new(30, 30));
577        assert!(r1.intersect(&r2).is_none());
578    }
579
580    #[test]
581    fn test_detect_overlap_empty() {
582        let rects: Vec<Rectangle<i32>> = vec![];
583        assert!(detect_overlap(&rects).is_none());
584    }
585
586    #[test]
587    fn test_detect_overlap_single() {
588        let rects = vec![Rectangle::new(Point::new(0, 0), Point::new(10, 10))];
589        assert!(detect_overlap(&rects).is_none());
590    }
591
592    #[test]
593    fn test_detect_overlap_non_overlapping() {
594        let rects = vec![
595            Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
596            Rectangle::new(Point::new(20, 20), Point::new(30, 30)),
597        ];
598        assert!(detect_overlap(&rects).is_none());
599    }
600
601    #[test]
602    fn test_detect_overlap_three_rects() {
603        // First and third overlap, second is in between
604        let rects = vec![
605            Rectangle::new(Point::new(0, 0), Point::new(10, 10)),
606            Rectangle::new(Point::new(15, 15), Point::new(25, 25)),
607            Rectangle::new(Point::new(5, 5), Point::new(12, 12)), // overlaps with first
608        ];
609        let result = detect_overlap(&rects);
610        assert!(result.is_some());
611        // Should find overlap between 0 and 2 (or 2 and 0)
612        let (i, j) = result.unwrap();
613        assert!((i == 0 && j == 2) || (i == 2 && j == 0));
614    }
615
616    #[test]
617    fn test_check_spacing_x_overlap_y_separate() {
618        // Rectangles that overlap in x but are separated in y
619        let r1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
620        let r2 = Rectangle::new(Point::new(5, 20), Point::new(15, 30));
621        // x: [0,10] and [5,15] overlap; y: [0,10] and [20,30] separated by 10
622        assert!(check_spacing(&r1, &r2, 10));
623        assert!(!check_spacing(&r1, &r2, 11));
624    }
625
626    #[test]
627    fn test_check_spacing_vertical_overlap_horizontal_separate() {
628        // Rectangles that overlap in y but are separated in x
629        let r1 = Rectangle::new(Point::new(0, 0), Point::new(10, 10));
630        let r2 = Rectangle::new(Point::new(20, 5), Point::new(30, 15));
631        assert!(check_spacing(&r1, &r2, 10));
632        assert!(!check_spacing(&r1, &r2, 11));
633    }
634}
physdes/vlsi_ops.rs

physdes/
vlsi_ops.rs
