1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
/*
 * Copyright (c) 2020-2021 Thomas Kramer.
 *
 * This file is part of LibrEDA
 * (see https://codeberg.org/libreda).
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

//! Collection of useful algorithms for layout processing.

use crate::prelude::{Rect, REdge};
use itertools::Itertools;
use num_traits::{Bounded, Zero};

/// Decompose a set of manhattanized polygons into non-overlapping horizontal rectangles.
/// The polygons in form of an iterator over all the edges.
/// A point is considered inside the polygon when the polygon wraps around it a non-zero number of times.
///
/// # Example
/// ```
///     use libreda_db::prelude::*;
///     use libreda_db::layout::algorithms::decompose_rectangles;
///     // Use a polygon like the following.
///     //    +--+
///     //    |  |
///     // +--+  |
///     // |     |
///     // +-----+
///     let poly = SimpleRPolygon::try_new(vec![
///         (0, 0), (2, 0), (2, 2), (1, 2), (1, 1), (0, 1)
///     ].iter().map(|t| Point::from(t)).collect()).unwrap();
///
///     // Decompose the polygon into non-overlapping horizontal rectangles.
///     let rects = decompose_rectangles(poly.edges());
///     assert_eq!(rects, vec![Rect::new((0, 0), (2, 1)), Rect::new((1, 1), (2, 2))]);
/// ```
pub fn decompose_rectangles<T, I>(redges: I) -> Vec<Rect<T>>
    where T: Ord + Bounded + Copy + Zero,
          I: Iterator<Item=REdge<T>> {
    // Sweep through the vertical edges from left to right. Keep track of 'open' rectangles.
    // A rectangle is opened when a left boundary is encountered and closed when a right boundary is encountered.
    // Construct a rectangle once a right boundary is encountered.

    {
        // Extract the vertical edges.
        let vertical_edges: Vec<_> = redges
            .filter(|e| e.is_vertical() && e.start != e.end)
            .map(|e| {
                let is_left = e.start > e.end;
                if is_left {
                    (e.reversed(), true)
                } else {
                    (e, false)
                }
            })
            // Sort edges from left to right, then by the y-coordinate of start and end point.
            .sorted_by_key(|(e, _is_left)| (e.offset, e.start, e.end))
            .collect();

        // Store the open rectangle as a tuple (y-start, y-end, inside count, x-position of opening vertical edge).
        let mut open_rects: Vec<(T, T, isize, T)> = vec![(T::min_value(), T::max_value(), 0, T::min_value())];
        let mut results = Vec::new();

        // Return the position of the new entry.
        fn split_intervals<T: PartialOrd + Copy>(intervals: &mut Vec<(T, T, isize, T)>, split_location: T) -> usize {
            // Find the interval which contains the split location.
            let (pos, &(a, b, value, x)) = intervals.iter()
                .enumerate()
                .find(|(_pos, &(a, b, _val, _x))| a <= split_location && split_location < b)
                .expect("Intervals must span the whole value range without gap.");

            if split_location == a || split_location == b {
                // Split location is equal to an end-point of the interval. No need to split there.
                pos
            } else {
                // Split location is inside the interval. Split the interval.
                let i1 = (a, split_location, value, x);
                let i2 = (split_location, b, value, x);
                intervals[pos] = i2;
                intervals.insert(pos, i1);
                pos + 1
            }
        }

        // Merge neighbouring intervals with the same value.
        fn merge_intervals<T: PartialEq + Copy>(intervals: &mut Vec<(T, T, isize, T)>) {
            debug_assert!(intervals.len() >= 1);
            let mut write_index = 0;
            let mut value = (intervals[0].2, intervals[0].3);
            for i in 1..intervals.len() {
                let (start, end, count, x) = intervals[i];
                let current_value = (count, x);
                intervals[write_index].1 = end;

                if current_value != value {
                    intervals[write_index].1 = start;
                    write_index += 1;
                    intervals[write_index] = intervals[i];
                    value = current_value;
                } else {
                    // Merge the intervals.
                }
            }

            // Crop the vector to the right size.
            intervals.truncate(write_index + 1);
        }

        // Process all vertical edges.
        for (current_edge, is_left) in vertical_edges {
            debug_assert!(current_edge.start < current_edge.end);

            {
                let pos = split_intervals(&mut open_rects, current_edge.start);
                split_intervals(&mut open_rects, current_edge.end);

                // Find all newly opened rectangles and store the x position of their left edge.
                open_rects.iter_mut()
                    .skip(pos)// Skip intervals which come before the current interval.
                    .take_while(|(_a, b, _value, _x)| b <= &current_edge.end)// Find intervals which overlap with the current interval.
                    .filter(|(a, _b, value, _x)| a >= &current_edge.start && *value == 0)
                    .for_each(|(_a, _b, _value, x)| {
                        *x = current_edge.offset;
                    });
            }

            let increment = if is_left {
                // Enter rectangle.
                1
            } else {
                // Exit rectangle.
                -1
            };

            {
                // Find rectangles that are closed by this boundary.
                // Find this by computing the intersection of the y-interval of the right boundary
                // with all open intervals that are about to be closed (which have value = -increment).

                let increment_inv = -increment;
                let closed_rects = open_rects.iter()
                    .take_while(|(_a, b, _value, _x)| b <= &current_edge.end)
                    .filter(|(a, _b, value, _x)| a >= &current_edge.start && value == &increment_inv)
                    .map(|&(a, b, _value, x_start)| {
                        // Compute the intersection of the intervals [a, b] and [e.start, e.end].
                        let y_start = a.max(current_edge.start);
                        let y_end = b.min(current_edge.end);
                        let x_end = current_edge.offset;
                        debug_assert!(x_start != T::min_value());
                        Rect::new((x_start, y_start), (x_end, y_end))
                    });

                results.extend(closed_rects);
            }

            // Update the inside-count for open rectangles that interact with the current edge.
            open_rects.iter_mut()
                .take_while(|(_a, b, _value, _x)| b <= &current_edge.end)
                .filter(|(a, _b, _value, _x)| a >= &current_edge.start)
                .for_each(|(_, _, count, x)| {
                    *count += increment;

                    if *count == 0 {
                        // Reset the x-coordinate of the left boundary (there's none now).
                        *x = T::min_value();
                    }
                });


            // Simplify the intervals.
            merge_intervals(&mut open_rects);
        }

        results
    }
}

#[test]
fn test_decompose_rectangles_trivial() {
    // Test trivial cases: Empty polygon and rectangle.
    use crate::prelude::Point;
    use crate::prelude::SimpleRPolygon;

    let empty: SimpleRPolygon<i32> = SimpleRPolygon::empty();
    let rects = decompose_rectangles(empty.edges());
    assert_eq!(rects, vec![]);

    // Test with reversed polygon.
    let rect = SimpleRPolygon::try_new(vec![
        (0, 0), (2, 0), (2, 2), (0, 2)
    ].iter().map(|t| Point::from(t)).collect()).unwrap();
    let rects = decompose_rectangles(rect.reversed().edges());
    assert_eq!(rects, vec![Rect::new((0, 0), (2, 2))]);
}

#[test]
fn test_decompose_rectangles() {
    use crate::prelude::Point;
    use crate::prelude::SimpleRPolygon;
    //    +--+
    //    |  |
    // +--+  |
    // |     |
    // +-----+
    let poly = SimpleRPolygon::try_new(vec![
        (0, 0), (2, 0), (2, 2), (1, 2), (1, 1), (0, 1)
    ].iter().map(|t| Point::from(t)).collect()).unwrap();
    let rects = decompose_rectangles(poly.edges());
    assert_eq!(rects, vec![Rect::new((0, 0), (2, 1)), Rect::new((1, 1), (2, 2))]);

    // Test with reversed polygon.
    let rects = decompose_rectangles(poly.reversed().edges());
    assert_eq!(rects, vec![Rect::new((0, 0), (2, 1)), Rect::new((1, 1), (2, 2))]);
}

#[test]
fn test_decompose_rectangles_overlapping() {
    use crate::prelude::IntoEdges;

    let rects = vec![
        Rect::new((0i32, 0), (10, 10)),
        Rect::new((0, 0), (5, 5)),
    ];

    let decomposed = decompose_rectangles(rects.iter().flat_map(|r| r.into_edges()));
    assert_eq!(decomposed, vec![Rect::new((0, 0), (10, 10))]);
}