diff options
Diffstat (limited to 'src/3rdparty/2geom/include/2geom/sweeper.h')
| -rw-r--r-- | src/3rdparty/2geom/include/2geom/sweeper.h | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/include/2geom/sweeper.h b/src/3rdparty/2geom/include/2geom/sweeper.h new file mode 100644 index 0000000..233d181 --- /dev/null +++ b/src/3rdparty/2geom/include/2geom/sweeper.h @@ -0,0 +1,189 @@ +/** @file + * @brief Class for implementing sweepline algorithms + *//* + * Authors: + * Krzysztof Kosiński <tweenk.pl@gmail.com> + * + * Copyright 2015 Authors + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + */ + +#ifndef LIB2GEOM_SEEN_SWEEPER_H +#define LIB2GEOM_SEEN_SWEEPER_H + +#include <2geom/coord.h> +#include <algorithm> +#include <vector> +#include <boost/intrusive/list.hpp> + +namespace Geom { + +// exposition only +template <typename Item> +class SweepVector { +public: + typedef typename std::vector<Item>::const_iterator ItemIterator; + + SweepVector(std::vector<Item> const &v) + : _items(v) + {} + + std::vector<Item> const &items() { return _items; } + Interval itemBounds(ItemIterator /*ii*/) { return Interval(); } + + void addActiveItem(ItemIterator /*ii*/) {} + void removeActiveItem(ItemIterator /*ii*/) {} + +private: + std::vector<Item> const &_items; +}; + +/** @brief Generic sweepline algorithm. + * + * This class encapsulates an algorithm that sorts the objects according + * to their bounds, then moves an imaginary line (sweepline) over those + * bounds from left to right. Objects are added to the active list when + * the line starts intersecting their bounds, and removed when it completely + * passes over them. + * + * To use this, create a class that exposes the following methods: + * - Range items() - returns a forward iterable range of items that will be swept. + * - Interval itemBounds(iterator i) - given an iterator from the above range, + * compute the bounding interval of the referenced item in the direction of sweep. + * - void addActiveItem(iterator i) - add an item to the active list. + * - void removeActiveItem(iterator i) - remove an item from the active list. + * + * Create the object, then instantiate this template with the above class + * as the template parameter, pass it the constructed object of the class, + * and call the process() method. + * + * A good choice for the active list is a Boost intrusive list, which allows + * you to get an iterator from a value in constant time. + * + * Look in path.cpp for example usage. + * + * @tparam Item The type of items to sweep + * @tparam SweepTraits Traits class that defines the items' bounds, + * how to interpret them and how to sort the events + * @ingroup Utilities + */ +template <typename SweepSet> +class Sweeper { +public: + typedef typename SweepSet::ItemIterator Iter; + + explicit Sweeper(SweepSet &set) + : _set(set) + { + std::size_t sz = std::distance(set.items().begin(), set.items().end()); + _entry_events.reserve(sz); + _exit_events.reserve(sz); + } + + /** @brief Process entry and exit events. + * This will iterate over all inserted items, calling the methods + * addActiveItem and removeActiveItem on the SweepSet passed at construction + * according to the order of the boundaries of each item. */ + void process() { + if (_set.items().empty()) return; + + Iter last = _set.items().end(); + for (Iter i = _set.items().begin(); i != last; ++i) { + Interval b = _set.itemBounds(i); + // guard against NANs + assert(b.min() == b.min() && b.max() == b.max()); + _entry_events.push_back(Event(b.max(), i)); + _exit_events.push_back(Event(b.min(), i)); + } + + std::make_heap(_entry_events.begin(), _entry_events.end()); + std::make_heap(_exit_events.begin(), _exit_events.end()); + + Event next_entry = _get_next(_entry_events); + Event next_exit = _get_next(_exit_events); + + while (next_entry || next_exit) { + assert(next_exit); + + if (!next_entry || next_exit > next_entry) { + // exit event - remove record from active list + _set.removeActiveItem(next_exit.item); + next_exit = _get_next(_exit_events); + } else { + // entry event - add record to active list + _set.addActiveItem(next_entry.item); + next_entry = _get_next(_entry_events); + } + } + } + +private: + struct Event + : boost::totally_ordered<Event> + { + Coord coord; + Iter item; + + Event(Coord c, Iter const &i) + : coord(c), item(i) + {} + Event() + : coord(nan("")), item() + {} + bool operator<(Event const &other) const { return coord < other.coord; } + bool operator==(Event const &other) const { return coord == other.coord; } + operator bool() const { return !std::isnan(coord); } + }; + + static Event _get_next(std::vector<Event> &heap) { + if (heap.empty()) { + Event e; + return e; + } + std::pop_heap(heap.begin(), heap.end()); + Event ret = heap.back(); + heap.pop_back(); + return ret; + } + + SweepSet &_set; + std::vector<Event> _entry_events; + std::vector<Event> _exit_events; +}; + +} // namespace Geom + +#endif // !LIB2GEOM_SEEN_SWEEPER_H + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |