1 /**
2 * \file
3 * \brief \todo brief description
4 *
5 * Authors:
6 * Michael Sloane <?@?.?>
7 * Marco <?@?.?>
8 *
9 * Copyright 2006-2008 authors
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it either under the terms of the GNU Lesser General Public
13 * License version 2.1 as published by the Free Software Foundation
14 * (the "LGPL") or, at your option, under the terms of the Mozilla
15 * Public License Version 1.1 (the "MPL"). If you do not alter this
16 * notice, a recipient may use your version of this file under either
17 * the MPL or the LGPL.
18 *
19 * You should have received a copy of the LGPL along with this library
20 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 * You should have received a copy of the MPL along with this library
23 * in the file COPYING-MPL-1.1
24 *
25 * The contents of this file are subject to the Mozilla Public License
26 * Version 1.1 (the "License"); you may not use this file except in
27 * compliance with the License. You may obtain a copy of the License at
28 * http://www.mozilla.org/MPL/
29 *
30 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
31 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
32 * the specific language governing rights and limitations.
33 *
34 */
36 #ifndef __GEOM_CROSSING_H
37 #define __GEOM_CROSSING_H
39 #include <vector>
40 #include <2geom/rect.h>
41 #include <2geom/sweep.h>
42 #include <boost/optional/optional.hpp>
43 #include <2geom/path.h>
45 namespace Geom {
47 //Crossing between one or two paths
48 struct Crossing {
49 bool dir; //True: along a, a becomes outside.
50 double ta, tb; //time on a and b of crossing
51 unsigned a, b; //storage of indices
52 Crossing() : dir(false), ta(0), tb(1), a(0), b(1) {}
53 Crossing(double t_a, double t_b, bool direction) : dir(direction), ta(t_a), tb(t_b), a(0), b(1) {}
54 Crossing(double t_a, double t_b, unsigned ai, unsigned bi, bool direction) : dir(direction), ta(t_a), tb(t_b), a(ai), b(bi) {}
55 bool operator==(const Crossing & other) const { return a == other.a && b == other.b && dir == other.dir && ta == other.ta && tb == other.tb; }
56 bool operator!=(const Crossing & other) const { return !(*this == other); }
58 unsigned getOther(unsigned cur) const { return a == cur ? b : a; }
59 double getTime(unsigned cur) const { return a == cur ? ta : tb; }
60 double getOtherTime(unsigned cur) const { return a == cur ? tb : ta; }
61 bool onIx(unsigned ix) const { return a == ix || b == ix; }
62 };
64 typedef boost::optional<Crossing> OptCrossing;
67 /*
68 struct Edge {
69 unsigned node, path;
70 double time;
71 bool reverse;
72 Edge(unsigned p, double t, bool r) : path(p), time(t), reverse(r) {}
73 bool operator==(Edge const &other) const { return other.path == path && other.time == time && other.reverse == reverse; }
74 };
76 struct CrossingNode {
77 std::vector<Edge> edges;
78 CrossingNode() : edges(std::vector<Edge>()) {}
79 explicit CrossingNode(std::vector<Edge> es) : edges(es) {}
80 void add_edge(Edge const &e) {
81 if(std::find(edges.begin(), edges.end(), e) == edges.end())
82 edges.push_back(e);
83 }
84 double time_on(unsigned p) {
85 for(unsigned i = 0; i < edges.size(); i++)
86 if(edges[i].path == p) return edges[i].time;
87 std::cout << "CrossingNode time_on failed\n";
88 return 0;
89 }
90 };
93 typedef std::vector<CrossingNode> CrossingGraph;
95 struct TimeOrder {
96 bool operator()(Edge a, Edge b) {
97 return a.time < b.time;
98 }
99 };
101 class Path;
102 CrossingGraph create_crossing_graph(std::vector<Path> const &p, Crossings const &crs);
103 */
105 /*inline bool are_near(Crossing a, Crossing b) {
106 return are_near(a.ta, b.ta) && are_near(a.tb, b.tb);
107 }
109 struct NearF { bool operator()(Crossing a, Crossing b) { return are_near(a, b); } };
110 */
112 struct CrossingOrder {
113 unsigned ix;
114 bool rev;
115 CrossingOrder(unsigned i, bool r = false) : ix(i), rev(r) {}
116 bool operator()(Crossing a, Crossing b) {
117 if(rev)
118 return (ix == a.a ? a.ta : a.tb) <
119 (ix == b.a ? b.ta : b.tb);
120 else
121 return (ix == a.a ? a.ta : a.tb) >
122 (ix == a.a ? a.ta : a.tb);
123 }
124 };
126 typedef std::vector<Crossing> Crossings;
128 typedef std::vector<Crossings> CrossingSet;
130 template<typename C>
131 std::vector<Rect> bounds(C const &a) {
132 std::vector<Rect> rs;
133 for (unsigned i = 0; i < a.size(); i++) {
134 OptRect bb = a[i].boundsFast();
135 if (bb) {
136 rs.push_back(*bb);
137 }
138 }
139 return rs;
140 }
141 // provide specific method for Paths because paths can be closed or open. Path::size() is named somewhat wrong...
142 std::vector<Rect> bounds(Path const &a);
144 inline void sort_crossings(Crossings &cr, unsigned ix) { std::sort(cr.begin(), cr.end(), CrossingOrder(ix)); }
146 template<typename T>
147 struct Crosser {
148 virtual ~Crosser() {}
149 virtual Crossings crossings(T const &a, T const &b) { return crossings(std::vector<T>(1,a), std::vector<T>(1,b))[0]; }
150 virtual CrossingSet crossings(std::vector<T> const &a, std::vector<T> const &b) {
151 CrossingSet results(a.size() + b.size(), Crossings());
153 std::vector<std::vector<unsigned> > cull = sweep_bounds(bounds(a), bounds(b));
154 for(unsigned i = 0; i < cull.size(); i++) {
155 for(unsigned jx = 0; jx < cull[i].size(); jx++) {
156 unsigned j = cull[i][jx];
157 unsigned jc = j + a.size();
158 Crossings cr = crossings(a[i], b[j]);
159 for(unsigned k = 0; k < cr.size(); k++) { cr[k].a = i; cr[k].b = jc; }
161 //Sort & add A-sorted crossings
162 sort_crossings(cr, i);
163 Crossings n(results[i].size() + cr.size());
164 std::merge(results[i].begin(), results[i].end(), cr.begin(), cr.end(), n.begin(), CrossingOrder(i));
165 results[i] = n;
167 //Sort & add B-sorted crossings
168 sort_crossings(cr, jc);
169 n.resize(results[jc].size() + cr.size());
170 std::merge(results[jc].begin(), results[jc].end(), cr.begin(), cr.end(), n.begin(), CrossingOrder(jc));
171 results[jc] = n;
172 }
173 }
174 return results;
175 }
176 };
177 void merge_crossings(Crossings &a, Crossings &b, unsigned i);
178 void offset_crossings(Crossings &cr, double a, double b);
180 Crossings reverse_ta(Crossings const &cr, std::vector<double> max);
181 Crossings reverse_tb(Crossings const &cr, unsigned split, std::vector<double> max);
182 CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double> max);
183 CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max);
185 void clean(Crossings &cr_a, Crossings &cr_b);
187 }
189 #endif
190 /*
191 Local Variables:
192 mode:c++
193 c-file-style:"stroustrup"
194 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
195 indent-tabs-mode:nil
196 fill-column:99
197 End:
198 */
199 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :