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>
44 namespace Geom {
46 //Crossing between one or two paths
47 struct Crossing {
48 bool dir; //True: along a, a becomes outside.
49 double ta, tb; //time on a and b of crossing
50 unsigned a, b; //storage of indices
51 Crossing() : dir(false), ta(0), tb(1), a(0), b(1) {}
52 Crossing(double t_a, double t_b, bool direction) : dir(direction), ta(t_a), tb(t_b), a(0), b(1) {}
53 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) {}
54 bool operator==(const Crossing & other) const { return a == other.a && b == other.b && dir == other.dir && ta == other.ta && tb == other.tb; }
55 bool operator!=(const Crossing & other) const { return !(*this == other); }
57 unsigned getOther(unsigned cur) const { return a == cur ? b : a; }
58 double getTime(unsigned cur) const { return a == cur ? ta : tb; }
59 double getOtherTime(unsigned cur) const { return a == cur ? tb : ta; }
60 bool onIx(unsigned ix) const { return a == ix || b == ix; }
61 };
63 typedef boost::optional<Crossing> OptCrossing;
66 /*
67 struct Edge {
68 unsigned node, path;
69 double time;
70 bool reverse;
71 Edge(unsigned p, double t, bool r) : path(p), time(t), reverse(r) {}
72 bool operator==(Edge const &other) const { return other.path == path && other.time == time && other.reverse == reverse; }
73 };
75 struct CrossingNode {
76 std::vector<Edge> edges;
77 CrossingNode() : edges(std::vector<Edge>()) {}
78 explicit CrossingNode(std::vector<Edge> es) : edges(es) {}
79 void add_edge(Edge const &e) {
80 if(std::find(edges.begin(), edges.end(), e) == edges.end())
81 edges.push_back(e);
82 }
83 double time_on(unsigned p) {
84 for(unsigned i = 0; i < edges.size(); i++)
85 if(edges[i].path == p) return edges[i].time;
86 std::cout << "CrossingNode time_on failed\n";
87 return 0;
88 }
89 };
92 typedef std::vector<CrossingNode> CrossingGraph;
94 struct TimeOrder {
95 bool operator()(Edge a, Edge b) {
96 return a.time < b.time;
97 }
98 };
100 class Path;
101 CrossingGraph create_crossing_graph(std::vector<Path> const &p, Crossings const &crs);
102 */
104 /*inline bool are_near(Crossing a, Crossing b) {
105 return are_near(a.ta, b.ta) && are_near(a.tb, b.tb);
106 }
108 struct NearF { bool operator()(Crossing a, Crossing b) { return are_near(a, b); } };
109 */
111 struct CrossingOrder {
112 unsigned ix;
113 CrossingOrder(unsigned i) : ix(i) {}
114 bool operator()(Crossing a, Crossing b) {
115 return (ix == a.a ? a.ta : a.tb) <
116 (ix == b.a ? b.ta : b.tb);
117 }
118 };
120 typedef std::vector<Crossing> Crossings;
122 typedef std::vector<Crossings> CrossingSet;
124 template<typename C>
125 std::vector<Rect> bounds(C const &a) {
126 std::vector<Rect> rs;
127 for (unsigned i = 0; i < a.size(); i++) {
128 OptRect bb = a[i].boundsFast();
129 if (bb) {
130 rs.push_back(*bb);
131 }
132 }
133 return rs;
134 }
136 inline void sort_crossings(Crossings &cr, unsigned ix) { std::sort(cr.begin(), cr.end(), CrossingOrder(ix)); }
138 template<typename T>
139 struct Crosser {
140 virtual ~Crosser() {}
141 virtual Crossings crossings(T const &a, T const &b) { return crossings(std::vector<T>(1,a), std::vector<T>(1,b))[0]; }
142 virtual CrossingSet crossings(std::vector<T> const &a, std::vector<T> const &b) {
143 CrossingSet results(a.size() + b.size(), Crossings());
145 std::vector<std::vector<unsigned> > cull = sweep_bounds(bounds(a), bounds(b));
146 for(unsigned i = 0; i < cull.size(); i++) {
147 for(unsigned jx = 0; jx < cull[i].size(); jx++) {
148 unsigned j = cull[i][jx];
149 unsigned jc = j + a.size();
150 Crossings cr = crossings(a[i], b[j]);
151 for(unsigned k = 0; k < cr.size(); k++) { cr[k].a = i; cr[k].b = jc; }
153 //Sort & add A-sorted crossings
154 sort_crossings(cr, i);
155 Crossings n(results[i].size() + cr.size());
156 std::merge(results[i].begin(), results[i].end(), cr.begin(), cr.end(), n.begin(), CrossingOrder(i));
157 results[i] = n;
159 //Sort & add B-sorted crossings
160 sort_crossings(cr, jc);
161 n.resize(results[jc].size() + cr.size());
162 std::merge(results[jc].begin(), results[jc].end(), cr.begin(), cr.end(), n.begin(), CrossingOrder(jc));
163 results[jc] = n;
164 }
165 }
166 return results;
167 }
168 };
169 void merge_crossings(Crossings &a, Crossings &b, unsigned i);
170 void offset_crossings(Crossings &cr, double a, double b);
172 Crossings reverse_ta(Crossings const &cr, std::vector<double> max);
173 Crossings reverse_tb(Crossings const &cr, unsigned split, std::vector<double> max);
174 CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double> max);
175 CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max);
177 void clean(Crossings &cr_a, Crossings &cr_b);
179 }
181 #endif
182 /*
183 Local Variables:
184 mode:c++
185 c-file-style:"stroustrup"
186 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
187 indent-tabs-mode:nil
188 fill-column:99
189 End:
190 */
191 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :