rust_rectangle_dividing/
dividing.rs

1use num_traits::{Num, NumAssignOps, NumOps};
2
3use crate::{
4    area::Area,
5    axis::{Axis, SizeForAxis},
6    rectangle::RectangleSize,
7    rotate::QuarterRotation,
8    weight::normalize_weights,
9};
10
11pub trait Dividing<T> {
12    /// dividing a rectangle into two rectangles (vertical)
13    fn divide_vertical(&self, x: T) -> (Self, Self)
14    where
15        Self: Sized;
16
17    /// dividing a rectangle into two rectangles (horizontal)
18    fn divide_horizontal(&self, y: T) -> (Self, Self)
19    where
20        Self: Sized;
21
22    /// dividing a rectangle into two rectangles specified by axis
23    fn divide(&self, v: T, axis: Axis) -> (Self, Self)
24    where
25        Self: Sized,
26    {
27        match axis {
28            Axis::Vertical => self.divide_vertical(v),
29            Axis::Horizontal => self.divide_horizontal(v),
30        }
31    }
32
33    /// dividing a rectangle into specified number of rectangles specified by axis
34    fn divide_by_values_and_axis(&self, values: &Vec<T>, axis: Axis) -> Vec<Self>
35    where
36        Self: Sized + RectangleSize<T> + Clone,
37        T: Copy + Num + NumAssignOps,
38    {
39        let mut remaining = self.clone();
40        let mut divided: Vec<Self> = Vec::new();
41        for v in values {
42            let (divided1, divided2) = remaining.divide(*v, axis);
43            divided.push(divided1);
44            remaining = divided2;
45        }
46        divided.push(remaining.clone());
47        divided
48    }
49
50    /// dividing a rectangle into specified weights of rectangles specified by axis
51    fn divide_by_weights_and_axis(&self, weights: &[T], axis: Axis) -> Vec<Self>
52    where
53        Self: Sized + RectangleSize<T> + Clone + SizeForAxis<T>,
54        T: Copy + for<'a> std::iter::Sum<&'a T> + Num + NumAssignOps + NumOps,
55    {
56        if weights.is_empty() {
57            return vec![];
58        }
59        if weights.len() == 1 {
60            return vec![self.clone()];
61        }
62        let normalized_weights_ = normalize_weights(weights);
63        let size: T = self.size_for_axis(axis);
64        let mut values: Vec<T> = normalized_weights_.iter().map(|w| *w * size).collect();
65        // last value is not used
66        values.pop();
67        self.divide_by_values_and_axis(&values, axis)
68    }
69
70    fn divide_vertical_then_horizontal_with_weights(
71        &self,
72        weights: &[T],
73        aspect_ratio: T,
74        boustrophedon: bool,
75    ) -> Vec<Self>
76    where
77        Self: Sized + RectangleSize<T> + Clone + SizeForAxis<T> + Area<T>,
78        T: Copy + for<'a> std::iter::Sum<&'a T> + Num + NumAssignOps + std::cmp::PartialOrd,
79    {
80        let norm_weights = normalize_weights(weights);
81        let total_area = self.area();
82        let height = self.height();
83
84        let mut dividing_weights: Vec<Vec<T>> = Vec::new();
85
86        let mut remaining_weights = norm_weights;
87        let mut picked_weights: Vec<T> = Vec::new();
88        let mut divided: Vec<Self> = Vec::new();
89
90        remaining_weights.reverse(); // pop() removes item from the end of the vector, so reverse it
91                                     // pick weights until the aspect ratio is satisfied
92        while let Some(picked_weight) = remaining_weights.pop() {
93            picked_weights.push(picked_weight);
94            let weights_in_group = picked_weights.iter().sum::<T>();
95            let picked_area: T = total_area * weights_in_group;
96            let width = picked_area / height;
97            let first_item_height = picked_weights[0] / weights_in_group * height;
98            let first_item_aspect_ratio = width / first_item_height;
99            if first_item_aspect_ratio >= aspect_ratio {
100                dividing_weights.push(picked_weights.clone());
101                picked_weights = Vec::new();
102            }
103        }
104        if !picked_weights.is_empty() {
105            dividing_weights.push(picked_weights.clone());
106        }
107
108        let group_weights: Vec<T> = dividing_weights.iter().map(|w| w.iter().sum()).collect();
109        let vertical_divided = self.divide_by_weights_and_axis(&group_weights, Axis::Vertical);
110        let mut forward = true;
111        for (divided_part, weights) in vertical_divided.iter().zip(dividing_weights.iter_mut()) {
112            if !forward {
113                weights.reverse();
114            }
115            let mut horizontal_divided =
116                divided_part.divide_by_weights_and_axis(weights, Axis::Horizontal);
117            if !forward {
118                horizontal_divided.reverse();
119            }
120            divided.extend(horizontal_divided);
121            if boustrophedon {
122                forward = !forward;
123            }
124        }
125        divided
126    }
127
128    fn divide_horizontal_then_vertical_with_weights(
129        &self,
130        weights: &[T],
131        aspect_ratio: T,
132        boustrophedon: bool,
133    ) -> Vec<Self>
134    where
135        Self: Sized + RectangleSize<T> + Clone + SizeForAxis<T> + Area<T> + QuarterRotation,
136        T: Copy
137            + Num
138            + NumOps
139            + NumAssignOps
140            + std::cmp::PartialOrd
141            + for<'a> std::iter::Sum<&'a T>,
142    {
143        // rotate, divide vertical, rotate back again means divide horizontal
144        let rotated = self.rotate_clockwise();
145        let rotated_aspect_ratio = T::one() / aspect_ratio;
146        let divided = rotated.divide_vertical_then_horizontal_with_weights(
147            weights,
148            rotated_aspect_ratio,
149            boustrophedon,
150        );
151        divided
152            .iter()
153            .map(|r| r.rotate_counter_clockwise())
154            .collect()
155    }
156}
157
158pub(crate) trait VerticalDividingHelper<T> {
159    fn divide_vertical_helper(&self, x: T) -> (Self, Self)
160    where
161        Self: Sized;
162}
163
164impl<T, U> Dividing<T> for U
165where
166    U: QuarterRotation + VerticalDividingHelper<T>,
167    T: Copy,
168{
169    fn divide_vertical(&self, x: T) -> (Self, Self) {
170        self.divide_vertical_helper(x)
171    }
172
173    fn divide_horizontal(&self, y: T) -> (Self, Self) {
174        // rotate, divide vertical, rotate back again means divide horizontal
175        let rotated = self.rotate_clockwise();
176        let (a, b) = rotated.divide_vertical(y);
177        (a.rotate_counter_clockwise(), b.rotate_counter_clockwise())
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use num_traits::Float;
184
185    use super::*;
186    use crate::aspect_ratio::AspectRatio;
187    use crate::axis_aligned_rectangle::AxisAlignedRectangle;
188    use crate::component::Component;
189    use crate::point::Point;
190    use crate::rectangle::Rectangle;
191    use crate::weight::normalize_weights;
192
193    #[test]
194    fn test_divide_vertical() {
195        let point = Point::new(2, 3);
196        let rect = Rectangle::new(4, 5);
197        let (rect_a, rect_b) = AxisAlignedRectangle::new(&point, &rect).divide_vertical(2);
198        assert_eq!(rect_a.origin(), point);
199        assert_eq!(rect_a.rect(), Rectangle::new(2, 5));
200        assert_eq!(rect_b.origin(), Point::new(4, 3));
201        assert_eq!(rect_b.rect(), Rectangle::new(2, 5));
202
203        let point = Point::new(2, 3);
204        let rect = Rectangle::new(4, 5);
205        let (rect_a, rect_b) = AxisAlignedRectangle::new(&point, &rect).divide_vertical(1);
206        assert_eq!(rect_a.origin(), point);
207        assert_eq!(rect_a.rect(), Rectangle::new(1, 5));
208        assert_eq!(rect_b.origin(), Point::new(3, 3));
209        assert_eq!(rect_b.rect(), Rectangle::new(3, 5));
210    }
211
212    #[test]
213    fn test_divide_horizontal() {
214        let point = Point::new(2, 3);
215        let rect = Rectangle::new(4, 5);
216        let (rect_a, rect_b) = AxisAlignedRectangle::new(&point, &rect).divide_horizontal(1);
217        assert_eq!(rect_a.origin(), point);
218        assert_eq!(rect_a.rect(), Rectangle::new(4, 1));
219        assert_eq!(rect_b.origin(), Point::new(2, 4));
220        assert_eq!(rect_b.rect(), Rectangle::new(4, 4));
221
222        let point = Point::new(2, 3);
223        let rect = Rectangle::new(4, 5);
224        let (rect_a, rect_b) = AxisAlignedRectangle::new(&point, &rect).divide_horizontal(2);
225        assert_eq!(rect_a.origin(), point);
226        assert_eq!(rect_a.rect(), Rectangle::new(4, 2));
227        assert_eq!(rect_b.origin(), Point::new(2, 5));
228        assert_eq!(rect_b.rect(), Rectangle::new(4, 3));
229    }
230
231    #[test]
232    fn test_divide_nth() {
233        // test vertical
234        let point = Point::new(2.0, 3.0);
235        let rect = Rectangle::new(6.0, 2.0);
236        let a_rect = AxisAlignedRectangle::new(&point, &rect);
237        let divided = a_rect.divide_by_values_and_axis(&vec![1.0, 2.0], Axis::Vertical);
238        assert_eq!(divided[0].origin(), point);
239        assert_eq!(divided[0].rect(), Rectangle::new(1.0, 2.0));
240        assert_eq!(divided[1].origin(), Point::new(3.0, 3.0));
241        assert_eq!(divided[1].rect(), Rectangle::new(2.0, 2.0));
242        assert_eq!(divided[2].origin(), Point::new(5.0, 3.0));
243        assert_eq!(divided[2].rect(), Rectangle::new(3.0, 2.0));
244        assert_no_overlaps(&a_rect, &divided);
245        assert_eq!(divided.len(), 3);
246        // sum of divided rectangles should equal original rectangle
247        assert_eq!(
248            divided[0].width() + divided[1].width() + divided[2].width(),
249            a_rect.width()
250        );
251        // all divided rectangles should have the same height
252        assert_eq!(divided[0].height(), a_rect.height());
253        assert_eq!(divided[1].height(), a_rect.height());
254        assert_eq!(divided[2].height(), a_rect.height());
255        // the sum of the x and width of the  divided rectangle should equal the x of the next divided rectangle
256        assert_eq!(divided[0].x() + divided[0].width(), divided[1].x());
257        assert_eq!(divided[1].x() + divided[1].width(), divided[2].x());
258        assert_eq!(
259            a_rect.x() + a_rect.width(),
260            divided[2].x() + divided[2].width()
261        );
262
263        // test horizontal
264        let point = Point::new(2.0, 3.0);
265        let rect = Rectangle::new(2.0, 6.0);
266        let a_rect = AxisAlignedRectangle::new(&point, &rect);
267        let divided = a_rect.divide_by_values_and_axis(&vec![3.0, 2.0], Axis::Horizontal);
268        assert_eq!(divided[0].origin(), point);
269        assert_eq!(divided[0].rect(), Rectangle::new(2.0, 3.0));
270        assert_eq!(divided[1].origin(), Point::new(2.0, 6.0));
271        assert_eq!(divided[1].rect(), Rectangle::new(2.0, 2.0));
272        assert_eq!(divided[2].origin(), Point::new(2.0, 8.0));
273        assert_eq!(divided[2].rect(), Rectangle::new(2.0, 1.0));
274        assert_no_overlaps(&a_rect, &divided);
275        assert_eq!(divided.len(), 3);
276        // sum of divided rectangles should equal original rectangle
277        assert_eq!(
278            divided[0].height() + divided[1].height() + divided[2].height(),
279            a_rect.height()
280        );
281        // all divided rectangles should have the same width
282        assert_eq!(divided[0].width(), a_rect.width());
283        assert_eq!(divided[1].width(), a_rect.width());
284        assert_eq!(divided[2].width(), a_rect.width());
285        // the sum of the y and height of the  divided rectangle should equal the y of the next divided rectangle
286        assert_eq!(divided[0].y() + divided[0].height(), divided[1].y());
287        assert_eq!(divided[1].y() + divided[1].height(), divided[2].y());
288        assert_eq!(
289            a_rect.y() + a_rect.height(),
290            divided[2].y() + divided[2].height()
291        );
292    }
293
294    #[test]
295    fn test_divide_vertical_then_horizontal_with_weights() {
296        let rect = Rectangle::new(100.0, 100.0);
297        let weights = vec![1.0, 1.0, 1.0, 1.0];
298        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.0, false);
299        assert_weights_dividing(&rect, &divided, &weights);
300        assert_eq!(divided[0], Rectangle::new(50.0, 50.0));
301        assert_eq!(divided[1], Rectangle::new(50.0, 50.0));
302        assert_eq!(divided[2], Rectangle::new(50.0, 50.0));
303        assert_eq!(divided[3], Rectangle::new(50.0, 50.0));
304
305        // not divided case
306        let rect = Rectangle::new(100.0, 100.0);
307        let weights = vec![1.0];
308        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.0, false);
309        assert_weights_dividing(&rect, &divided, &weights);
310        assert_eq!(divided[0], rect);
311
312        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(100.0, 100.0));
313        let weights = vec![1.0, 1.0, 1.0, 1.0];
314        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.0, false);
315        assert_weights_dividing(&rect, &divided, &weights);
316        assert_no_overlaps(&rect, &divided);
317        assert_respect_aspect_ratio(&divided, &weights, 1.0);
318        assert_eq!(
319            divided[0],
320            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(50.0, 50.0))
321        );
322        assert_eq!(
323            divided[1],
324            AxisAlignedRectangle::new(&Point::new(0.0, 50.0), &Rectangle::new(50.0, 50.0))
325        );
326        assert_eq!(
327            divided[2],
328            AxisAlignedRectangle::new(&Point::new(50.0, 0.0), &Rectangle::new(50.0, 50.0))
329        );
330        assert_eq!(
331            divided[3],
332            AxisAlignedRectangle::new(&Point::new(50.0, 50.0), &Rectangle::new(50.0, 50.0))
333        );
334
335        // not divided case
336        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(100.0, 100.0));
337        let weights = vec![1.0];
338        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.0, false);
339        assert_weights_dividing(&rect, &divided, &weights);
340        assert_no_overlaps(&rect, &divided);
341        assert_eq!(divided[0], rect);
342
343        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(9.0, 8.0));
344        let weights = vec![4.0, 4.0, 1.0, 1.0, 1.0, 1.0];
345        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.5, false);
346        assert_weights_dividing(&rect, &divided, &weights);
347        assert_no_overlaps(&rect, &divided);
348        assert_respect_aspect_ratio(&divided, &weights, 1.5);
349        assert_eq!(
350            divided[0].round(),
351            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(6.0, 4.0))
352        );
353        assert_eq!(
354            divided[1].round(),
355            AxisAlignedRectangle::new(&Point::new(0.0, 4.0), &Rectangle::new(6.0, 4.0))
356        );
357        assert_eq!(
358            divided[2].round(),
359            AxisAlignedRectangle::new(&Point::new(6.0, 0.0), &Rectangle::new(3.0, 2.0))
360        );
361        assert_eq!(
362            divided[3].round(),
363            AxisAlignedRectangle::new(&Point::new(6.0, 2.0), &Rectangle::new(3.0, 2.0))
364        );
365        assert_eq!(
366            divided[4].round(),
367            AxisAlignedRectangle::new(&Point::new(6.0, 4.0), &Rectangle::new(3.0, 2.0))
368        );
369        assert_eq!(
370            divided[5].round(),
371            AxisAlignedRectangle::new(&Point::new(6.0, 6.0), &Rectangle::new(3.0, 2.0))
372        );
373
374        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(300.0, 200.0));
375        let weights = vec![4.0, 3.0, 2.0, 1.0];
376        let divided = rect.divide_vertical_then_horizontal_with_weights(&weights, 1.0, false);
377        assert_weights_dividing(&rect, &divided, &weights);
378        assert_no_overlaps(&rect, &divided);
379        assert_eq!(
380            divided[0].round(),
381            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(210.0, 114.0))
382        );
383        assert_eq!(
384            divided[1].round(),
385            AxisAlignedRectangle::new(&Point::new(0.0, 115.0), &Rectangle::new(210.0, 85.0))
386        );
387        assert_eq!(
388            divided[2].round(),
389            AxisAlignedRectangle::new(&Point::new(210.0, 0.0), &Rectangle::new(90.0, 133.0))
390        );
391        assert_eq!(
392            divided[3].round(),
393            AxisAlignedRectangle::new(&Point::new(210.0, 134.0), &Rectangle::new(90.0, 66.0))
394        );
395    }
396
397    #[test]
398    fn test_divide_horizontal_then_vertical_with_weights() {
399        let rect = Rectangle::new(100.0, 100.0);
400        let weights = vec![1.0, 1.0, 1.0, 1.0];
401        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0, false);
402        assert_weights_dividing(&rect, &divided, &weights);
403        assert_eq!(divided[0], Rectangle::new(50.0, 50.0));
404        assert_eq!(divided[1], Rectangle::new(50.0, 50.0));
405        assert_eq!(divided[2], Rectangle::new(50.0, 50.0));
406        assert_eq!(divided[3], Rectangle::new(50.0, 50.0));
407
408        // not divided case
409        let rect = Rectangle::new(100.0, 100.0);
410        let weights = vec![1.0];
411        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0, false);
412        assert_weights_dividing(&rect, &divided, &weights);
413        assert_eq!(divided[0], rect);
414
415        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(100.0, 100.0));
416        let weights = vec![1.0, 1.0, 1.0, 1.0];
417        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0, false);
418        assert_weights_dividing(&rect, &divided, &weights);
419        assert_no_overlaps(&rect, &divided);
420        assert_respect_aspect_ratio(&divided, &weights, 1.0);
421        assert_eq!(
422            divided[0],
423            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(50.0, 50.0))
424        );
425        assert_eq!(
426            divided[1],
427            AxisAlignedRectangle::new(&Point::new(50.0, 0.0), &Rectangle::new(50.0, 50.0))
428        );
429        assert_eq!(
430            divided[2],
431            AxisAlignedRectangle::new(&Point::new(0.0, 50.0), &Rectangle::new(50.0, 50.0))
432        );
433        assert_eq!(
434            divided[3],
435            AxisAlignedRectangle::new(&Point::new(50.0, 50.0), &Rectangle::new(50.0, 50.0))
436        );
437
438        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(8.0, 9.0));
439        let weights = vec![4.0, 4.0, 1.0, 1.0, 1.0, 1.0];
440        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0 / 1.5, false);
441        assert_weights_dividing(&rect, &divided, &weights);
442        assert_no_overlaps(&rect, &divided);
443        assert_respect_aspect_ratio(&divided, &weights, 1.0 / 1.5);
444        assert_eq!(
445            divided[0].round(),
446            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(4.0, 6.0))
447        );
448        assert_eq!(
449            divided[1].round(),
450            AxisAlignedRectangle::new(&Point::new(4.0, 0.0), &Rectangle::new(4.0, 6.0))
451        );
452        assert_eq!(
453            divided[2].round(),
454            AxisAlignedRectangle::new(&Point::new(0.0, 6.0), &Rectangle::new(2.0, 3.0))
455        );
456        assert_eq!(
457            divided[3].round(),
458            AxisAlignedRectangle::new(&Point::new(2.0, 6.0), &Rectangle::new(2.0, 3.0))
459        );
460        assert_eq!(
461            divided[4].round(),
462            AxisAlignedRectangle::new(&Point::new(4.0, 6.0), &Rectangle::new(2.0, 3.0))
463        );
464        assert_eq!(
465            divided[5].round(),
466            AxisAlignedRectangle::new(&Point::new(6.0, 6.0), &Rectangle::new(2.0, 3.0))
467        );
468
469        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(300.0, 200.0));
470        let weights = vec![4.0, 3.0, 2.0, 1.0];
471        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0, false);
472        assert_weights_dividing(&rect, &divided, &weights);
473        assert_no_overlaps(&rect, &divided);
474        assert_eq!(
475            divided[0].round(),
476            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(133.0, 180.0))
477        );
478        assert_eq!(
479            divided[1].round(),
480            AxisAlignedRectangle::new(&Point::new(134.0, 0.0), &Rectangle::new(99.0, 180.0))
481        );
482        assert_eq!(
483            divided[2].round(),
484            AxisAlignedRectangle::new(&Point::new(234.0, 0.0), &Rectangle::new(66.0, 180.0))
485        );
486        assert_eq!(
487            divided[3].round(),
488            AxisAlignedRectangle::new(&Point::new(0.0, 180.0), &Rectangle::new(300.0, 20.0))
489        );
490    }
491
492    #[test]
493    fn test_divide_many() {
494        // various pattern
495        let rects = vec![
496            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(100.0, 100.0)),
497            AxisAlignedRectangle::new(&Point::new(100.0, 0.0), &Rectangle::new(100.0, 300.0)),
498            AxisAlignedRectangle::new(&Point::new(0.0, 100.0), &Rectangle::new(300.0, 100.0)),
499            AxisAlignedRectangle::new(&Point::new(0.0, 100.0), &Rectangle::new(300.0, 300.0)),
500        ];
501        let various_weights = vec![vec![
502            24.0, 23.0, 22.0, 21.0, 20.0, 19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0,
503            10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0,
504        ]];
505        let various_aspect_ratio = vec![0.5, 1.0, 2.0];
506        for rect in &rects {
507            for weights in &various_weights {
508                let divided = rect.divide_by_weights_and_axis(weights, Axis::Vertical);
509                assert_weights_dividing(rect, &divided, weights);
510                assert_no_overlaps(rect, &divided);
511            }
512        }
513        for rect in &rects {
514            for weights in &various_weights {
515                for aspect_ratio in &various_aspect_ratio {
516                    for boustrophedon in &[false, true] {
517                        let divided = rect.divide_vertical_then_horizontal_with_weights(
518                            weights,
519                            *aspect_ratio,
520                            *boustrophedon,
521                        );
522                        assert_respect_aspect_ratio(&divided, weights, *aspect_ratio);
523                        assert_weights_dividing(rect, &divided, weights);
524                        assert_no_overlaps(rect, &divided);
525                        assert_respect_aspect_ratio(&divided, weights, rect.aspect_ratio());
526
527                        let divided = rect.divide_horizontal_then_vertical_with_weights(
528                            weights,
529                            *aspect_ratio,
530                            *boustrophedon,
531                        );
532                        assert_respect_aspect_ratio(&divided, weights, *aspect_ratio);
533                        assert_weights_dividing(rect, &divided, weights);
534                        assert_no_overlaps(rect, &divided);
535                        assert_respect_aspect_ratio(&divided, weights, rect.aspect_ratio());
536                    }
537                }
538            }
539        }
540    }
541
542    #[test]
543    fn test_boustrophedon() {
544        let rect = AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(8.0, 9.0));
545        let weights = vec![4.0, 4.0, 1.0, 1.0, 1.0, 1.0];
546        let divided = rect.divide_horizontal_then_vertical_with_weights(&weights, 1.0 / 1.5, true);
547        assert_weights_dividing(&rect, &divided, &weights);
548        assert_no_overlaps(&rect, &divided);
549        assert_respect_aspect_ratio(&divided, &weights, 1.0 / 1.5);
550        assert_eq!(
551            divided[0].round(),
552            AxisAlignedRectangle::new(&Point::new(0.0, 0.0), &Rectangle::new(4.0, 6.0))
553        );
554        assert_eq!(
555            divided[1].round(),
556            AxisAlignedRectangle::new(&Point::new(4.0, 0.0), &Rectangle::new(4.0, 6.0))
557        );
558        assert_eq!(
559            divided[2].round(),
560            AxisAlignedRectangle::new(&Point::new(6.0, 6.0), &Rectangle::new(2.0, 3.0))
561        );
562        assert_eq!(
563            divided[3].round(),
564            AxisAlignedRectangle::new(&Point::new(4.0, 6.0), &Rectangle::new(2.0, 3.0))
565        );
566        assert_eq!(
567            divided[4].round(),
568            AxisAlignedRectangle::new(&Point::new(2.0, 6.0), &Rectangle::new(2.0, 3.0))
569        );
570        assert_eq!(
571            divided[5].round(),
572            AxisAlignedRectangle::new(&Point::new(0.0, 6.0), &Rectangle::new(2.0, 3.0))
573        );
574    }
575
576    fn assert_weights_dividing<T, D>(original: &D, divided: &[D], weights: &[T])
577    where
578        D: Dividing<T> + Area<T>,
579        T: Copy
580            + std::fmt::Debug
581            + Num
582            + NumAssignOps
583            + NumOps
584            + std::iter::Sum<T>
585            + for<'a> std::iter::Sum<&'a T>
586            + std::cmp::PartialOrd<f64>,
587    {
588        // check that the number of divided rectangles is equal to the number of weights
589        assert_eq!(divided.len(), weights.len());
590
591        // check that the sum of divided areas is equal to the original area
592        let original_area = original.area();
593        let divided_area: T = divided.iter().map(|r| r.area()).sum();
594        // assert_eq!(original_area, divided_area);
595        assert!((original_area - divided_area) < 0.1);
596
597        // check that the sum of divided weights is equal to the original weight
598        let original_normalized_weights = normalize_weights(weights);
599        let divided_areas: Vec<T> = divided.iter().map(|r| r.area()).collect();
600        let divided_area_by_weights = normalize_weights(&divided_areas);
601
602        // assert_eq!(original_normalized_weights, divided_area_by_weights);
603        let diffs: Vec<T> = original_normalized_weights
604            .iter()
605            .zip(divided_area_by_weights.iter())
606            .map(|(w1, w2)| (*w1 - *w2) * (*w1 - *w2))
607            .collect();
608
609        for diff in diffs {
610            assert!(diff < 0.1);
611        }
612
613        // assert_eq!(original_normalized_weights, divided_area_by_weights);
614    }
615
616    fn assert_no_overlaps<T>(
617        original: &AxisAlignedRectangle<T>,
618        divided: &[AxisAlignedRectangle<T>],
619    ) where
620        T: Copy
621            + std::fmt::Debug
622            + Num
623            + NumAssignOps
624            + NumOps
625            + Float
626            + std::iter::Sum<T>
627            + for<'a> std::iter::Sum<&'a T>,
628    {
629        // check all divided rectangles are inside the original rectangle
630        for d in divided {
631            assert!(original.enclodes(&d.round()));
632        }
633        // check no overlap between divided rectangles
634        for (d1, d2) in divided.iter().zip(divided.iter().skip(1)) {
635            assert!(!d1.round().overlaps(&d2.round()));
636        }
637    }
638
639    fn assert_respect_aspect_ratio<T>(
640        divided: &[AxisAlignedRectangle<T>],
641        weights: &[T],
642        aspect_ratio: T,
643    ) where
644        T: Copy
645            + std::fmt::Debug
646            + std::cmp::PartialEq
647            + for<'a> std::iter::Sum<&'a T>
648            + Num
649            + NumAssignOps
650            + NumOps
651            + Float
652            + std::cmp::PartialOrd<f64>,
653    {
654        let normalized_weights = normalize_weights(weights);
655        for (d, w) in divided.iter().zip(normalized_weights.iter()) {
656            let asis_aspect_ratio = d.aspect_ratio();
657            let diff = (asis_aspect_ratio - aspect_ratio).abs();
658            // ideal diff must be 1.0 (same aspect ratio) but the real diff is not 1.0
659            // assert that the diff is not too big, not too small
660            // larger weights are expected to the diff must be smaller, smaller weights are expected to the diff must be smaller
661            assert!(diff * *w < 0.5);
662        }
663    }
664}
rust_rectangle_dividing/dividing.rs

rust_rectangle_dividing/
dividing.rs
