jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <LibGfx/DisjointRectSet.h>
28
29namespace Gfx {
30
31void DisjointRectSet::add(const Rect& new_rect)
32{
33 for (auto& rect : m_rects) {
34 if (rect.contains(new_rect))
35 return;
36 }
37
38 m_rects.append(new_rect);
39 if (m_rects.size() > 1)
40 shatter();
41}
42
43void DisjointRectSet::shatter()
44{
45 Vector<Rect, 32> output;
46 output.ensure_capacity(m_rects.size());
47 bool pass_had_intersections = false;
48 do {
49 pass_had_intersections = false;
50 output.clear_with_capacity();
51 for (size_t i = 0; i < m_rects.size(); ++i) {
52 auto& r1 = m_rects[i];
53 for (size_t j = 0; j < m_rects.size(); ++j) {
54 if (i == j)
55 continue;
56 auto& r2 = m_rects[j];
57 if (!r1.intersects(r2))
58 continue;
59 pass_had_intersections = true;
60 auto pieces = r1.shatter(r2);
61 for (auto& piece : pieces)
62 output.append(piece);
63 m_rects.remove(i);
64 for (; i < m_rects.size(); ++i)
65 output.append(m_rects[i]);
66 goto next_pass;
67 }
68 output.append(r1);
69 }
70 next_pass:
71 swap(output, m_rects);
72 } while (pass_had_intersections);
73}
74
75}