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