1 /** 2 * \file 3 * \brief Path intersection graph 4 *//* 5 * Authors: 6 * Krzysztof Kosiński <tweenk.pl@gmail.com> 7 * 8 * Copyright 2015 Authors 9 * 10 * This library is free software; you can redistribute it and/or 11 * modify it either under the terms of the GNU Lesser General Public 12 * License version 2.1 as published by the Free Software Foundation 13 * (the "LGPL") or, at your option, under the terms of the Mozilla 14 * Public License Version 1.1 (the "MPL"). If you do not alter this 15 * notice, a recipient may use your version of this file under either 16 * the MPL or the LGPL. 17 * 18 * You should have received a copy of the LGPL along with this library 19 * in the file COPYING-LGPL-2.1; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 21 * You should have received a copy of the MPL along with this library 22 * in the file COPYING-MPL-1.1 23 * 24 * The contents of this file are subject to the Mozilla Public License 25 * Version 1.1 (the "License"); you may not use this file except in 26 * compliance with the License. You may obtain a copy of the License at 27 * http://www.mozilla.org/MPL/ 28 * 29 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY 30 * OF ANY KIND, either express or implied. See the LGPL or the MPL for 31 * the specific language governing rights and limitations. 32 */ 33 34 #ifndef SEEN_LIB2GEOM_INTERSECTION_GRAPH_H 35 #define SEEN_LIB2GEOM_INTERSECTION_GRAPH_H 36 37 #include <set> 38 #include <vector> 39 #include <boost/ptr_container/ptr_vector.hpp> 40 #include <boost/intrusive/list.hpp> 41 #include <2geom/forward.h> 42 #include <2geom/pathvector.h> 43 44 namespace Geom { 45 46 class PathIntersectionGraph 47 { 48 // this is called PathIntersectionGraph so that we can also have a class for polygons, 49 // e.g. PolygonIntersectionGraph, which is going to be significantly faster 50 public: 51 PathIntersectionGraph(PathVector const &a, PathVector const &b, Coord precision = EPSILON); 52 53 PathVector getUnion(); 54 PathVector getIntersection(); 55 PathVector getAminusB(); 56 PathVector getBminusA(); 57 PathVector getXOR(); 58 59 /// Returns the number of intersections used when computing Boolean operations. 60 std::size_t size() const; 61 std::vector<Point> intersectionPoints(bool defective = false) const; windingPoints()62 std::vector<Point> windingPoints() const { 63 return _winding_points; 64 } 65 void fragments(PathVector &in, PathVector &out) const; valid()66 bool valid() const { return _graph_valid; } 67 68 private: 69 enum InOutFlag { 70 INSIDE, 71 OUTSIDE, 72 BOTH 73 }; 74 75 struct IntersectionVertex { 76 boost::intrusive::list_member_hook<> _hook; 77 boost::intrusive::list_member_hook<> _proc_hook; 78 PathVectorTime pos; 79 Point p; // guarantees that endpoints are exact 80 IntersectionVertex *neighbor; 81 InOutFlag next_edge; 82 unsigned which; 83 bool defective; 84 }; 85 86 typedef boost::intrusive::list 87 < IntersectionVertex 88 , boost::intrusive::member_hook 89 < IntersectionVertex 90 , boost::intrusive::list_member_hook<> 91 , &IntersectionVertex::_hook 92 > 93 > IntersectionList; 94 95 typedef boost::intrusive::list 96 < IntersectionVertex 97 , boost::intrusive::member_hook 98 < IntersectionVertex 99 , boost::intrusive::list_member_hook<> 100 , &IntersectionVertex::_proc_hook 101 > 102 > UnprocessedList; 103 104 struct PathData { 105 IntersectionList xlist; 106 std::size_t path_index; 107 int which; 108 InOutFlag status; 109 PathDataPathData110 PathData(int w, std::size_t pi) 111 : path_index(pi) 112 , which(w) 113 , status(BOTH) 114 {} 115 }; 116 117 struct IntersectionVertexLess; 118 typedef IntersectionList::iterator ILIter; 119 typedef IntersectionList::const_iterator CILIter; 120 121 PathVector _getResult(bool enter_a, bool enter_b); 122 void _handleNonintersectingPaths(PathVector &result, unsigned which, bool inside); 123 void _prepareArguments(); 124 bool _prepareIntersectionLists(Coord precision); 125 void _assignEdgeWindingParities(Coord precision); 126 void _assignComponentStatusFromDegenerateIntersections(); 127 void _removeDegenerateIntersections(); 128 void _verify(); 129 130 ILIter _getNeighbor(ILIter iter); 131 PathData &_getPathData(ILIter iter); 132 133 PathVector _pv[2]; 134 boost::ptr_vector<IntersectionVertex> _xs; 135 boost::ptr_vector<PathData> _components[2]; 136 UnprocessedList _ulist; 137 bool _graph_valid; 138 std::vector<Point> _winding_points; 139 140 friend std::ostream &operator<<(std::ostream &, PathIntersectionGraph const &); 141 }; 142 143 std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig); 144 145 } // namespace Geom 146 147 #endif // SEEN_LIB2GEOM_PATH_GRAPH_H 148 /* 149 Local Variables: 150 mode:c++ 151 c-file-style:"stroustrup" 152 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) 153 indent-tabs-mode:nil 154 fill-column:99 155 End: 156 */ 157 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : 158