dxfngc

1) /* drawing (DXF) to G-code (NGC) converter
2)  * Copyright 2013 Stefan Schuermans <stefan@schuermans.info>
3)  * Copyleft: CC-BY-SA http://creativecommons.org/licenses/by-sa/3.0/
4)  */
5) 
6) #include <boost/shared_ptr.hpp>
7) #include <iostream>
8) #include <vector>
9) 

10) #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

11) #include <CGAL/Polygon_2.h>
12) #include <CGAL/Polygon_with_holes_2.h>
13) #include <CGAL/Boolean_set_operations_2.h>

14) #include <CGAL/create_offset_polygons_from_polygon_with_holes_2.h>

15) #include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>

16) 
17) #include "layer.h"
18) #include "path.h"
19) #include "point.h"
20) #include "polygons.h"
21) 
22) /**
23)  * @brief clear all polygons
24)  */
25) void Polygons::clear()
26) {
27)   mPolys.clear();
28) }
29) 
30) /**
31)  * @brief add polygons from layer
32)  * @param[in] layer layer to obtain the polygons from
33)  * @param[in] eqDist maximum distance of two points to be considered equal
34)  * @return if the layer could be converted to polygons and imported
35)  */
36) bool Polygons::addLayer(const Layer &layer, double eqDist)
37) {
38)   // convert all paths to simple polygons
39)   CgPolyVec simples;
40)   Layer::Paths::const_iterator path;
41)   for (path = layer.mPaths.begin(); path != layer.mPaths.end(); ++path) {
42)     // skip empty paths
43)     if (path->mPoints.empty())
44)       continue;
45)     // check that path is closed
46)     if (!path->mPoints.front().equals(path->mPoints.back(), eqDist)) {
47)       std::cerr << "path not closed" << std::endl;
48)       return false;
49)     }
50)     // create simple polygon from path
51)     //   - do not add last point to polygon, as it is the same as the first one
52)     CgPoly simple;
53)     Path::Points::const_iterator pt;
54)     for (pt = path->mPoints.begin(); pt + 1 != path->mPoints.end(); ++pt)
55)       simple.push_back(CgPoint(pt->mX, pt->mY));
56)     // check that polygon is simple
57)     if (!simple.is_simple()) {
58)       std::cerr << "path is not simple (maybe self-itersecting?)" << std::endl;
59)       return false;
60)     }
61)     // ensure orientation is clockwise (must be the same for all polygons)
62)     if (simple.is_clockwise_oriented())
63)       simple.reverse_orientation();
64)     // collect polygons
65)     simples.push_back(simple);
66)   } // for path
67) 
68)   // check that no partly overlaps are present
69)   // deterine which polygon is contained in which one
70)   std::vector<ssize_t> contained_in; // idx: contained poly, val: containing poly
71)   ssize_t ia, ib;
72)   CgPolyVec::const_iterator a, b;
73)   for (a = simples.begin(); a != simples.end(); ++a)
74)     contained_in.push_back(-1); // not contained in any polygon
75)   for (a = simples.begin(), ia = 0; a != simples.end(); ++a, ++ia) {
76)     b = a;
77)     ib = ia;
78)     for (++b, ++ib; b != simples.end(); ++b, ++ib) {
79)       // A and B intersect each other
80)       if (CGAL::do_intersect(*a, *b)) {
81)         // compute differences A - B and B - A
82)         CgPolyHolesVec a_b, b_a;
83)         CGAL::difference(*a, *b, std::back_inserter(a_b));
84)         CGAL::difference(*b, *a, std::back_inserter(b_a));
85)         if (a_b.empty()) {
86)           // A and B are identical
87)           if (b_a.empty()) {
88)             std::cerr << "duplicate polygons found - meaning is undefined"
89)                       << std::endl;
90)             return false;
91)           }
92)           // B contains A (A is hole in B)
93)           else {
94)             if (contained_in.at(ia) >= 0) {
95)               std::cerr << "polygon contained in multiple polygons"
96)                            " - meaning is undefined" << std::endl;
97)               return false;
98)             }
99)             contained_in.at(ia) = ib;
100)           }
101)         } else {
102)           // A contains B (B is hole in A)
103)           if (b_a.empty()) {
104)             if (contained_in.at(ib) >= 0) {
105)               std::cerr << "polygon contained in multiple polygons"
106)                            " - meaning is undefined" << std::endl;
107)               return false;
108)             }
109)             contained_in.at(ib) = ia;
110)           }
111)           // A and B overlap partly
112)           else {
113)             std::cerr << "polygons overlap partly - meaning is undefined"
114)                       << std::endl;
115)             return false;
116)           }
117)         }
118)       }
119)     } // for b
120)   } // for a
121) 
122)   // add found polygons to member variable
123)   for (ia = 0; (size_t)ia < contained_in.size(); ++ia) {
124)     // outer polygon
125)     if (contained_in.at(ia) < 0) {
126)       CgPolyHoles poly(simples.at(ia));
127)       // find and add holes

128)       for (ib = 0; (size_t)ib < contained_in.size(); ++ib) {
129)         if (contained_in.at(ib) == ia) {
130)           // holes must be counter-clockwise
131)           simples.at(ib).reverse_orientation();

132)           poly.add_hole(simples.at(ib));

133)         }
134)       }

135)       // add polygon to member variable
136)       mPolys.push_back(poly);
137)     }
138)   }
139) 
140)   return true;
141) }
142) 
143) /**
144)  * @brief load polygons from layer
145)  * @param[in] layer layer to obtain the polygons from
146)  * @param[in] eqDist maximum distance of two points to be considered equal
147)  * @return if the layer could be converted to polygons and imported
148)  */
149) bool Polygons::loadLayer(const Layer &layer, double eqDist)
150) {
151)   clear();
152)   return addLayer(layer, eqDist);
153) }
154) 

155) /**
156)  * @brief create inner offset polygons
157)  * @param[in] offset offset, > 0.0
158)  * @param[out] offsetPolys offset polygons (!= *this)

159)  * @return if inner offset polygons could be constructed

160)  */

161) bool Polygons::createInnerOffset(double offset, Polygons &offsetPolys) const

162) {
163)   // clear output polygons
164)   offsetPolys.mPolys.clear();

165)   // leave if offset size is invalid

166)   if (offset <= 0.0) {
167)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
168)     return false;
169)   }

170) 
171)   // process all polygons
172)   CgPolyHolesVec::const_iterator poly;
173)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
174) 
175)     // create inner offset polygons
176)     CgPolyHolesPtrVec offPolys =
177)       CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2(
178)         offset, *poly);
179) 
180)     // add offset polygons to output polygons
181)     CgPolyHolesPtrVec::const_iterator offPoly;
182)     for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
183)       offsetPolys.mPolys.push_back(**offPoly);
184) 
185)   } // for poly

186) 
187)   return true;
188) }
189) 
190) /**
191)  * @brief create outer offset polygons
192)  * @param[in] offset offset, > 0.0
193)  * @param[out] offsetPolys offset polygons (!= *this)
194)  * @return if outer offset polygons could be constructed
195)  */
196) bool Polygons::createOuterOffset(double offset, Polygons &offsetPolys) const
197) {
198)   // clear output polygons
199)   offsetPolys.mPolys.clear();

200)   // leave if offset size is invalid

201)   if (offset <= 0.0) {
202)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
203)     return false;
204)   }
205) 
206)   // process all polygons
207)   CgPolyHolesVec::const_iterator poly;
208)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
209)     offsetPolys.mPolys.push_back(CgPolyHoles());
210)     createOuterOffsetPoly(*poly, offset, offsetPolys.mPolys.back());
211)   }
212) 
213)   return true;

214) }
215) 

216) /**
217)  * @brief fill insides of polygons by creating inner offset polygons
218)  * @param[in] offset offset, > 0.0
219)  * @param[out] offsetPolys offset polygons (!= *this)
220)  * @return if insides of polygons could be filles with inner offset polygons
221)  */
222) bool Polygons::fillInnerOffset(double offset, Polygons &offsetPolys) const
223) {
224)   // clear output polygons
225)   offsetPolys.mPolys.clear();
226)   // leave if offset size is invalid
227)   if (offset <= 0.0) {
228)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
229)     return false;
230)   }
231) 
232)   // process all polygons
233)   CgPolyHolesVec::const_iterator poly;
234)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
235) 
236)     // create interior straight skeleton
237)     CgSsPtr skel = CGAL::create_interior_straight_skeleton_2(*poly);
238) 
239)     // create inner offset polygons with increasing offset
240)     size_t i;
241)     for (i = 1; ; ++i) {
242) 
243)       // create inner offset polygons
244)       CgPolyPtrVec offPolys =
245)         CGAL::create_offset_polygons_2<CgPoly>(offset * i, *skel);
246) 
247)       // no offset polygons -> done
248)       if (offPolys.empty())
249)         break;
250) 
251)       // add offset polygons to output polygons
252)       CgPolyPtrVec::const_iterator offPoly;
253)       for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
254)         offsetPolys.mPolys.push_back(CgPolyHoles(**offPoly));
255) 
256)     } // for i
257) 
258)   } // for poly
259) 
260)   return true;
261) }
262) 

263) /**
264)  * @brief add all polygons with holes as multiple paths to a layer
265)  * @param[in,out] layer layer to add paths to
266)  */
267) void Polygons::addToLayer(Layer &layer) const
268) {
269)   CgPolyHolesVec::const_iterator poly;
270)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly)
271)     PolyHolesToLayer(*poly, layer);
272) }
273) 
274) /**
275)  * @brief write all polygons with holes as multiple paths to a layer
276)  * @param[in,out] layer layer to write paths to
277)  */
278) void Polygons::writeToLayer(Layer &layer) const
279) {
280)   layer.mPaths.clear();
281)   addToLayer(layer);
282) }
283) 

284) /**
285)  * @brief create outer offset polygon
286)  * @param[in] poly polygon to create outer offset of
287)  * @param[in] offset offset, > 0.0
288)  * @param[out] offsetPoly offset polygon (!= *this)
289)  * @return if outer offset polygon could be constructed
290)  */
291) bool Polygons::createOuterOffsetPoly(const CgPolyHoles &poly, double offset,
292)                                      CgPolyHoles &offsetPoly)
293) {
294)   // calculate outer offset of outer bondary
295)   const CgPoly &outer = poly.outer_boundary();
296)   CgPolyPtrVec outOffPolys =
297)     CGAL::create_exterior_skeleton_and_offset_polygons_2(offset, outer);
298)   /* outer Offset should now contain 2 polygons,
299)      the artificially added very outer boundary and the offset polygon */
300)   if (outOffPolys.size() != 2) {
301)     std::cerr << "internal error during outer offset computation" << std::endl;
302)     return false;
303)   }
304)   offsetPoly = CgPolyHoles(*outOffPolys.at(1)); // use offset polygon
305) 
306)   // calculate inner offset of holes
307)   CgPolyHoles::Hole_const_iterator hole;
308)   for (hole = poly.holes_begin(); hole != poly.holes_end(); ++hole) {
309)     CgPoly holeRev = *hole; // reverse orientation (make hole a normal poly)
310)     holeRev.reverse_orientation();
311)     CgPolyPtrVec inOffPolys =
312)       CGAL::create_interior_skeleton_and_offset_polygons_2(offset, holeRev);
313)     CgPolyPtrVec::iterator inOff; // add inner offset polys as new holes
314)     for (inOff = inOffPolys.begin(); inOff != inOffPolys.end(); ++inOff) {
315)       (*inOff)->reverse_orientation(); // re-reverse (make poly a hole again)
316)       offsetPoly.add_hole(**inOff);
317)     }
318)   }
319) 
320)   return true;
321) }
322)