GCC Code Coverage Report

Directory: ./
File: include/2geom/sweeper.h
Date: 2024-03-18 17:01:34
Exec Total Coverage
Lines: 41 41 100.0%
Functions: 26 26 100.0%
Branches: 44 68 64.7%
Line Branch Exec Source
1 /** @file
2 * @brief Class for implementing sweepline algorithms
3 *//*
4 * Authors:
5 * Krzysztof Kosiński <tweenk.pl@gmail.com>
6 *
7 * Copyright 2015 Authors
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it either under the terms of the GNU Lesser General Public
11 * License version 2.1 as published by the Free Software Foundation
12 * (the "LGPL") or, at your option, under the terms of the Mozilla
13 * Public License Version 1.1 (the "MPL"). If you do not alter this
14 * notice, a recipient may use your version of this file under either
15 * the MPL or the LGPL.
16 *
17 * You should have received a copy of the LGPL along with this library
18 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 * You should have received a copy of the MPL along with this library
21 * in the file COPYING-MPL-1.1
22 *
23 * The contents of this file are subject to the Mozilla Public License
24 * Version 1.1 (the "License"); you may not use this file except in
25 * compliance with the License. You may obtain a copy of the License at
26 * http://www.mozilla.org/MPL/
27 *
28 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
29 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
30 * the specific language governing rights and limitations.
31 */
32
33 #ifndef LIB2GEOM_SEEN_SWEEPER_H
34 #define LIB2GEOM_SEEN_SWEEPER_H
35
36 #include <2geom/coord.h>
37 #include <algorithm>
38 #include <vector>
39 #include <boost/intrusive/list.hpp>
40
41 namespace Geom {
42
43 // exposition only
44 template <typename Item>
45 class SweepVector {
46 public:
47 typedef typename std::vector<Item>::const_iterator ItemIterator;
48
49 SweepVector(std::vector<Item> const &v)
50 : _items(v)
51 {}
52
53 std::vector<Item> const &items() { return _items; }
54 Interval itemBounds(ItemIterator /*ii*/) { return Interval(); }
55
56 void addActiveItem(ItemIterator /*ii*/) {}
57 void removeActiveItem(ItemIterator /*ii*/) {}
58
59 private:
60 std::vector<Item> const &_items;
61 };
62
63 /** @brief Generic sweepline algorithm.
64 *
65 * This class encapsulates an algorithm that sorts the objects according
66 * to their bounds, then moves an imaginary line (sweepline) over those
67 * bounds from left to right. Objects are added to the active list when
68 * the line starts intersecting their bounds, and removed when it completely
69 * passes over them.
70 *
71 * To use this, create a class that exposes the following methods:
72 * - Range items() - returns a forward iterable range of items that will be swept.
73 * - Interval itemBounds(iterator i) - given an iterator from the above range,
74 * compute the bounding interval of the referenced item in the direction of sweep.
75 * - void addActiveItem(iterator i) - add an item to the active list.
76 * - void removeActiveItem(iterator i) - remove an item from the active list.
77 *
78 * Create the object, then instantiate this template with the above class
79 * as the template parameter, pass it the constructed object of the class,
80 * and call the process() method.
81 *
82 * A good choice for the active list is a Boost intrusive list, which allows
83 * you to get an iterator from a value in constant time.
84 *
85 * Look in path.cpp for example usage.
86 *
87 * @tparam Item The type of items to sweep
88 * @tparam SweepTraits Traits class that defines the items' bounds,
89 * how to interpret them and how to sort the events
90 * @ingroup Utilities
91 */
92 template <typename SweepSet>
93 class Sweeper {
94 public:
95 typedef typename SweepSet::ItemIterator Iter;
96
97 81 explicit Sweeper(SweepSet &set)
98 81 : _set(set)
99 {
100
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
 81 std::size_t sz = std::distance(set.items().begin(), set.items().end());
101
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 81 _entry_events.reserve(sz);
102
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 81 _exit_events.reserve(sz);
103 81 }
104
105 /** @brief Process entry and exit events.
106 * This will iterate over all inserted items, calling the methods
107 * addActiveItem and removeActiveItem on the SweepSet passed at construction
108 * according to the order of the boundaries of each item. */
109 81 void process() {
110
3/4
✓ Branch 2 taken 23 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 22 times.
 81 if (_set.items().empty()) return;
111
112
1/2
✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
 79 Iter last = _set.items().end();
113
6/8
✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 102 times.
✓ Branch 6 taken 24 times.
✓ Branch 7 taken 90 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 68 times.
✓ Branch 10 taken 22 times.
 331 for (Iter i = _set.items().begin(); i != last; ++i) {
114
1/2
✓ Branch 2 taken 170 times.
✗ Branch 3 not taken.
 252 Interval b = _set.itemBounds(i);
115 // guard against NANs
116
2/4
✓ Branch 2 taken 170 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 170 times.
✗ Branch 7 not taken.
 252 assert(b.min() == b.min() && b.max() == b.max());
117
1/2
✓ Branch 4 taken 170 times.
✗ Branch 5 not taken.
 252 _entry_events.push_back(Event(b.max(), i));
118
1/2
✓ Branch 4 taken 170 times.
✗ Branch 5 not taken.
 252 _exit_events.push_back(Event(b.min(), i));
119 }
120
121
1/2
✓ Branch 3 taken 46 times.
✗ Branch 4 not taken.
 79 std::make_heap(_entry_events.begin(), _entry_events.end());
122
1/2
✓ Branch 3 taken 46 times.
✗ Branch 4 not taken.
 79 std::make_heap(_exit_events.begin(), _exit_events.end());
123
124
1/2
✓ Branch 2 taken 46 times.
✗ Branch 3 not taken.
 79 Event next_entry = _get_next(_entry_events);
125
1/2
✓ Branch 2 taken 46 times.
✗ Branch 3 not taken.
 79 Event next_exit = _get_next(_exit_events);
126
127
6/6
✓ Branch 1 taken 150 times.
✓ Branch 2 taken 236 times.
✓ Branch 4 taken 104 times.
✓ Branch 5 taken 46 times.
✓ Branch 6 taken 340 times.
✓ Branch 7 taken 46 times.
 583 while (next_entry || next_exit) {
128
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 340 times.
 504 assert(next_exit);
129
130
7/8
✓ Branch 1 taken 236 times.
✓ Branch 2 taken 104 times.
✓ Branch 4 taken 236 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 66 times.
✓ Branch 7 taken 170 times.
✓ Branch 8 taken 170 times.
✓ Branch 9 taken 170 times.
 504 if (!next_entry || next_exit > next_entry) {
131 // exit event - remove record from active list
132
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 252 _set.removeActiveItem(next_exit.item);
133
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 252 next_exit = _get_next(_exit_events);
134 } else {
135 // entry event - add record to active list
136
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 252 _set.addActiveItem(next_entry.item);
137
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 252 next_entry = _get_next(_entry_events);
138 }
139 }
140 }
141
142 private:
143 struct Event
144 : boost::totally_ordered<Event>
145 {
146 Coord coord;
147 Iter item;
148
149 504 Event(Coord c, Iter const &i)
150 504 : coord(c), item(i)
151 504 {}
152 158 Event()
153 158 : coord(nan("")), item()
154 158 {}
155 1227 bool operator<(Event const &other) const { return coord < other.coord; }
156 bool operator==(Event const &other) const { return coord == other.coord; }
157 1841 operator bool() const { return !std::isnan(coord); }
158 };
159
160 432 static Event _get_next(std::vector<Event> &heap) {
161
2/2
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 176 times.
 432 if (heap.empty()) {
162 92 Event e;
163 92 return e;
164 }
165
1/2
✓ Branch 3 taken 176 times.
✗ Branch 4 not taken.
 340 std::pop_heap(heap.begin(), heap.end());
166 340 Event ret = heap.back();
167 340 heap.pop_back();
168 340 return ret;
169 }
170
171 SweepSet &_set;
172 std::vector<Event> _entry_events;
173 std::vector<Event> _exit_events;
174 };
175
176 } // namespace Geom
177
178 #endif // !LIB2GEOM_SEEN_SWEEPER_H
179
180 /*
181 Local Variables:
182 mode:c++
183 c-file-style:"stroustrup"
184 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
185 indent-tabs-mode:nil
186 fill-column:99
187 End:
188 */
189 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
190