Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 231 lines (210 sloc) 8.781 kb
c864070 @aewallin start on offset
authored
1 /*
2 * Copyright 2012 Anders Wallin (anders.e.e.wallin "at" gmail.com)
3 *
4 * This file is part of OpenVoronoi.
5 *
6 * OpenVoronoi is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * OpenVoronoi is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with OpenVoronoi. If not, see <http://www.gnu.org/licenses/>.
18 */
19 #pragma once
20
21 #include <string>
22 #include <iostream>
23
24 #include "graph.hpp"
42ede05 @aewallin more progress on offset
authored
25 #include "site.hpp"
c864070 @aewallin start on offset
authored
26
27 namespace ovd
28 {
29
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
30 /// \brief Line- or arc-vertex of an offset curve.
16314ca @aewallin add documentation so the doxygen class list looks ok (mostly \brief d…
authored
31 ///
32 /// \todo this duplicates the idea of the Ofs class. Remove this or Ofs!
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
33 struct OffsetVertex {
34 Point p;
35 // line-vertex is indicated by radius of -1, and c and cw are then ignored.
36 // otherwise this is an arc-vertex.
37 double r; // arc radius
38 Point c; // arc center
39 bool cw; // clockwise (or not)
40
41 OffsetVertex(Point pi, double ri, Point ci, bool cwi): p(pi), r(ri), c(ci), cw(cwi) {}
189cfcf Oops, missing "set_flags() in Offset::offset() to initialize list of …
Kaben Nanlohy authored
42 OffsetVertex(Point pi): p(pi), r(-1.), cw(false) {}
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
43 };
44 typedef std::list<OffsetVertex> OffsetLoop;
45 typedef std::list<OffsetLoop> OffsetLoops;
46
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
47 /// \brief From a voronoi-diagram, generate offsets.
48 /// an offset is allways a closed loop.
49 /// the loop consists of offset-elements from each face that the loop visits.
50 /// each face is associated with a Site, and the offset element from
51 /// - a point-site is a circular arc
52 /// - a line-site is a line
53 /// - an arc is a circular arc
54 ///
55 /// This class produces offsets at the given offset-distance on the entire
56 /// voronoi-diagram. To produce offsets only inside or outside a given geometry,
57 /// use a filter first. The filter sets the valid-property of edges, so that offsets
58 /// are not produced on faces with one or more invalid edge.
c864070 @aewallin start on offset
authored
59 class Offset {
60 public:
61 Offset(HEGraph& gi): g(gi) {
62 face_done.clear();
63 face_done.assign( g.num_faces(), 1 );
64 }
65 void print() {
66 std::cout << "Offset: verts: " << g.num_vertices() << "\n";
67 std::cout << "Offset: edges: " << g.num_edges() << "\n";
68 std::cout << "Offset: faces: " << g.num_faces() << "\n";
69 }
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
70 OffsetLoops offset(double t) {
71 offset_list = OffsetLoops();
189cfcf Oops, missing "set_flags() in Offset::offset() to initialize list of …
Kaben Nanlohy authored
72 set_flags(t);
42d7147 @aewallin figure out how to draw cw/ccw offset-arcs.
authored
73 HEFace start;
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
74 while (find_start_face(start)) { // while there are faces that still require offsets
75 offset_walk(start,t); // start on the face, and do an offset loop
c864070 @aewallin start on offset
authored
76 }
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
77 return offset_list;
42ede05 @aewallin more progress on offset
authored
78 }
79 bool find_start_face(HEFace& start) {
80 for(HEFace f=0; f<g.num_faces() ; f++) {
81 if (face_done[f]==0 ) {
82 start=f;
83 return true;
84 }
85 }
86 return false;
87 }
9f8ee61 @aewallin move the rest of the printing functions to halfedgediagram.
authored
88
42ede05 @aewallin more progress on offset
authored
89 void offset_walk(HEFace start,double t) {
251d540 @aewallin python example for emc2
authored
90 //std::cout << " offset_walk() starting on face " << start << "\n";
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
91 bool out_in_mode= false;
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
92 HEEdge start_edge = find_next_offset_edge( g[start].edge , t, out_in_mode); // the first edge on the start-face
c864070 @aewallin start on offset
authored
93 HEEdge current_edge = start_edge;
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
94
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
95 OffsetLoop loop; // store the output in this loop
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
96
97 // add the first point to the loop.
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
98 OffsetVertex pt( g[current_edge].point(t) );
99 loop.push_back( pt );
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
100
c864070 @aewallin start on offset
authored
101 do {
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
102 out_in_mode = edge_mode(current_edge, t);
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
103 // find the next edge
104 HEEdge next_edge = find_next_offset_edge( g[current_edge].next, t, out_in_mode);
42ede05 @aewallin more progress on offset
authored
105 //std::cout << "offset-output: "; print_edge(current_edge); std::cout << " to "; print_edge(next_edge); std::cout << "\n";
106 HEFace current_face = g[current_edge].face;
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
107 { // append the offset-element of current_face to the output
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
108 Site* s = g[current_face].site;
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
109 Ofs* o = s->offset( g[current_edge].point(t), g[next_edge].point(t) ); // ask the Site for offset-geometry here.
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
110 bool cw(true);
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
111 if (!s->isLine() ) // point and arc-sites produce arc-offsets, for which cw must be set.
112 cw = find_cw( o->start(), o->center(), o->end() ); // figure out cw or ccw arcs?
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
113 // add offset to output
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
114 OffsetVertex lpt( g[next_edge].point(t), o->radius(), o->center(), cw );
115 loop.push_back( lpt );
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
116 }
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
117 face_done[current_face]=1; // although we may revisit current_face (if it is non-convex), it seems safe to mark it "done" here.
c864070 @aewallin start on offset
authored
118 current_edge = g[next_edge].twin;
119 } while (current_edge != start_edge);
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
120 offset_list.push_back( loop ); // append the created loop to the output
42ede05 @aewallin more progress on offset
authored
121 }
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
122 bool edge_mode(HEEdge e, double t) {
123 HEVertex src = g.source(e);
124 HEVertex trg = g.target(e);
125 double src_r = g[src].dist();
126 double trg_r = g[trg].dist();
127 if ( (src_r<t) && (t<trg_r) ) {
128 return true;
129 } else if ((trg_r<t) && (t<src_r) ) {
130 return false;
131 } else {
132 assert(0);
133 return false;
134 }
135 }
42d7147 @aewallin figure out how to draw cw/ccw offset-arcs.
authored
136 // figure out cw or ccw for an arc
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
137 bool find_cw(Point start, Point center, Point end) {
42d7147 @aewallin figure out how to draw cw/ccw offset-arcs.
authored
138 // arc from current to next edge
139 // center at
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
140 return center.is_right(start,end); // this only works for arcs smaller than a half-circle !
c864070 @aewallin start on offset
authored
141 }
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
142
143 // starting at e, find the next edge on the face that brackets t
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
144 // we can be in one of two modes.
145 // if mode=false then we are looking for an edge where src_t<t<trg_t
146 // if mode=true we are looning for an edge where trg_t<t<src_t
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
147 HEEdge find_next_offset_edge(HEEdge e, double t, bool mode) {
c864070 @aewallin start on offset
authored
148 // find the first edge that has an offset
149 HEEdge start=e;
150 HEEdge current=start;
42d7147 @aewallin figure out how to draw cw/ccw offset-arcs.
authored
151 HEEdge ofs_edge=e;
c864070 @aewallin start on offset
authored
152 do {
153 HEVertex src = g.source(current);
154 HEVertex trg = g.target(current);
155 double src_r = g[src].dist();
156 double trg_r = g[trg].dist();
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
157 if ( !mode && (src_r<t) && (t<trg_r) ) {
158 ofs_edge = current;
159 break;
160 } else if (mode && (trg_r<t) && (t<src_r) ) {
c864070 @aewallin start on offset
authored
161 ofs_edge = current;
162 break;
163 }
164 current =g[current].next;
165 } while( current!=start );
a0c3d0b @aewallin try to fix offset of nonconvex faces. (in/out alternating mode for fi…
authored
166 //std::cout << "offset_edge = "; g.print_edge(ofs_edge);
c864070 @aewallin start on offset
authored
167 return ofs_edge;
168 }
169
170
171 void set_flags(double t) {
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
172
173 // go through all faces and set flag=0 if the face requires an offset.
c864070 @aewallin start on offset
authored
174 for(HEFace f=0; f<g.num_faces() ; f++) {
175 HEEdge start = g[f].edge;
176 HEEdge current = start;
177 do {
178 HEVertex src = g.source(current);
179 HEVertex trg = g.target(current);
180 double src_r = g[src].dist();
181 double trg_r = g[trg].dist();
182 if (t_bracket(src_r,trg_r,t)) {
37b4adb @aewallin filtering to get vd inside/outside a polygon.
authored
183 if ( face_done[f] ) // if 1
184 face_done[f] = 0; // , set to 0. this is a face that requires an offset!
c864070 @aewallin start on offset
authored
185 }
186 current = g[current].next;
187 } while ( current!=start );
188 }
37b4adb @aewallin filtering to get vd inside/outside a polygon.
authored
189
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
190 // again go through faces again, and set flag=1 in any edge on the face is invalid
191 // this is required because an upstream filter will set valid=false on some edges, but not all, on a face where we do not want offsets.
37b4adb @aewallin filtering to get vd inside/outside a polygon.
authored
192 for(HEFace f=0; f<g.num_faces() ; f++) {
193 HEEdge start = g[f].edge;
194 HEEdge current = start;
195 do {
196 if ( !g[current].valid ) {
197 face_done[f] = 1; // don't offset faces with invalid edges
198 }
199 current = g[current].next;
200 } while ( current!=start );
201 }
202
203
204
ce2b4cb @aewallin another offset example
authored
205 //print_status();
c864070 @aewallin start on offset
authored
206 }
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
207 // is t in (a,b) ?
c864070 @aewallin start on offset
authored
208 bool t_bracket(double a, double b, double t) {
209 double min_t = std::min(a,b);
210 double max_t = std::max(a,b);
211 return ( (min_t<t) && (t<max_t) );
212 }
42ede05 @aewallin more progress on offset
authored
213 void print_status() {
214 for(HEFace f=0; f<g.num_faces() ; f++) {
215 std::cout << (int)face_done[f];
216 }
217 std::cout << "\n";
218 }
49a756d C++ access to class Offset, sans Boost::Python.
Kaben Nanlohy authored
219 protected:
220 OffsetLoops offset_list;
c864070 @aewallin start on offset
authored
221 private:
222 Offset(); // don't use.
223 HEGraph& g;
4242d6c @aewallin copy deb-source package work from opencamlib.
authored
224 // hold a 0/1 flag for each face, indicating if an offset for this face has been produced or not.
c864070 @aewallin start on offset
authored
225 std::vector<unsigned char> face_done;
226 };
227
228
ca2b4fc @aewallin some cleanup
authored
229 } // end ovd namespace
c864070 @aewallin start on offset
authored
230 // end file offset.hpp
Something went wrong with that request. Please try again.