dxfngc

1) /* drawing (DXF) to G-code (NGC) converter
2)  * Copyright 2013 Stefan Schuermans <stefan@schuermans.info>

3)  * Copyleft: GNU public license - http://www.gnu.org/copyleft/gpl.html

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 and paths with just one point
43)     if (path->mPoints.size() <= 1)

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)       Path::Points::const_iterator pt;
49)       for (pt = path->mPoints.begin(); pt != path->mPoints.end(); ++pt)
50)         std::cerr << "  " << pt->mX << "," << pt->mY << std::endl;

51)       return false;
52)     }
53)     // create simple polygon from path
54)     //   - do not add last point to polygon, as it is the same as the first one
55)     CgPoly simple;
56)     Path::Points::const_iterator pt;
57)     for (pt = path->mPoints.begin(); pt + 1 != path->mPoints.end(); ++pt)
58)       simple.push_back(CgPoint(pt->mX, pt->mY));
59)     // check that polygon is simple
60)     if (!simple.is_simple()) {
61)       std::cerr << "path is not simple (maybe self-itersecting?)" << std::endl;

62)       Path::Points::const_iterator pt;
63)       for (pt = path->mPoints.begin(); pt != path->mPoints.end(); ++pt)
64)         std::cerr << "  " << pt->mX << "," << pt->mY << std::endl;

65)       return false;
66)     }
67)     // ensure orientation is clockwise (must be the same for all polygons)
68)     if (simple.is_clockwise_oriented())
69)       simple.reverse_orientation();
70)     // collect polygons
71)     simples.push_back(simple);
72)   } // for path
73) 
74)   // check that no partly overlaps are present
75)   // deterine which polygon is contained in which one
76)   std::vector<ssize_t> contained_in; // idx: contained poly, val: containing poly
77)   ssize_t ia, ib;
78)   CgPolyVec::const_iterator a, b;
79)   for (a = simples.begin(); a != simples.end(); ++a)
80)     contained_in.push_back(-1); // not contained in any polygon
81)   for (a = simples.begin(), ia = 0; a != simples.end(); ++a, ++ia) {
82)     b = a;
83)     ib = ia;
84)     for (++b, ++ib; b != simples.end(); ++b, ++ib) {
85)       // A and B intersect each other
86)       if (CGAL::do_intersect(*a, *b)) {
87)         // compute differences A - B and B - A
88)         CgPolyHolesVec a_b, b_a;
89)         CGAL::difference(*a, *b, std::back_inserter(a_b));
90)         CGAL::difference(*b, *a, std::back_inserter(b_a));
91)         if (a_b.empty()) {
92)           // A and B are identical
93)           if (b_a.empty()) {
94)             std::cerr << "duplicate polygons found - meaning is undefined"
95)                       << std::endl;
96)             return false;
97)           }
98)           // B contains A (A is hole in B)
99)           else {
100)             if (contained_in.at(ia) >= 0) {
101)               std::cerr << "polygon contained in multiple polygons"
102)                            " - meaning is undefined" << std::endl;
103)               return false;
104)             }
105)             contained_in.at(ia) = ib;
106)           }
107)         } else {
108)           // A contains B (B is hole in A)
109)           if (b_a.empty()) {
110)             if (contained_in.at(ib) >= 0) {
111)               std::cerr << "polygon contained in multiple polygons"
112)                            " - meaning is undefined" << std::endl;
113)               return false;
114)             }
115)             contained_in.at(ib) = ia;
116)           }
117)           // A and B overlap partly
118)           else {
119)             std::cerr << "polygons overlap partly - meaning is undefined"
120)                       << std::endl;
121)             return false;
122)           }
123)         }
124)       }
125)     } // for b
126)   } // for a
127) 
128)   // add found polygons to member variable
129)   for (ia = 0; (size_t)ia < contained_in.size(); ++ia) {
130)     // outer polygon
131)     if (contained_in.at(ia) < 0) {
132)       CgPolyHoles poly(simples.at(ia));
133)       // find and add holes

134)       for (ib = 0; (size_t)ib < contained_in.size(); ++ib) {
135)         if (contained_in.at(ib) == ia) {
136)           // holes must be counter-clockwise
137)           simples.at(ib).reverse_orientation();

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

139)         }
140)       }

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

161) /**
162)  * @brief create inner offset polygons
163)  * @param[in] offset offset, > 0.0
164)  * @param[out] offsetPolys offset polygons (!= *this)

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

166)  */

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

168) {
169)   // clear output polygons
170)   offsetPolys.mPolys.clear();

171)   // leave if offset size is invalid

172)   if (offset <= 0.0) {
173)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
174)     return false;
175)   }

176) 
177)   // process all polygons
178)   CgPolyHolesVec::const_iterator poly;
179)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
180) 
181)     // create inner offset polygons
182)     CgPolyHolesPtrVec offPolys =
183)       CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2(
184)         offset, *poly);
185) 
186)     // add offset polygons to output polygons
187)     CgPolyHolesPtrVec::const_iterator offPoly;
188)     for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
189)       offsetPolys.mPolys.push_back(**offPoly);
190) 
191)   } // for poly

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

206)   // leave if offset size is invalid

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

220) }
221) 

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

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

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