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_exact_constructions_kernel.h>

11) #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

12) #include <CGAL/Gmpq.h>

13) #include <CGAL/Polygon_2.h>
14) #include <CGAL/Polygon_with_holes_2.h>
15) #include <CGAL/Boolean_set_operations_2.h>

16) #include <CGAL/create_offset_polygons_from_polygon_with_holes_2.h>

17) #include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>

18) 
19) #include "layer.h"
20) #include "path.h"
21) #include "point.h"
22) #include "polygons.h"
23) 
24) /**
25)  * @brief clear all polygons
26)  */
27) void Polygons::clear()
28) {
29)   mPolys.clear();
30) }
31) 
32) /**
33)  * @brief add polygons from layer
34)  * @param[in] layer layer to obtain the polygons from
35)  * @param[in] eqDist maximum distance of two points to be considered equal
36)  * @return if the layer could be converted to polygons and imported
37)  */
38) bool Polygons::addLayer(const Layer &layer, double eqDist)
39) {
40)   // convert all paths to simple polygons

41)   // once using exact construction kernel (needed by intersection, difference)
42)   // once using inexact construction kernel (faster offsetting)
43)   CgExPolyVec simplesEx;

44)   CgPolyVec simples;
45)   Layer::Paths::const_iterator path;
46)   for (path = layer.mPaths.begin(); path != layer.mPaths.end(); ++path) {

47)     // skip empty paths and paths with just one point
48)     if (path->mPoints.size() <= 1)

49)       continue;
50)     // check that path is closed
51)     if (!path->mPoints.front().equals(path->mPoints.back(), eqDist)) {
52)       std::cerr << "path not closed" << std::endl;

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

56)       return false;
57)     }
58)     // create simple polygon from path
59)     //   - do not add last point to polygon, as it is the same as the first one

60)     CgExPoly simpleEx;

61)     CgPoly simple;
62)     Path::Points::const_iterator pt;

63)     for (pt = path->mPoints.begin(); pt + 1 != path->mPoints.end(); ++pt) {
64)       simpleEx.push_back(CgExPoint(pt->mX, pt->mY));

65)       simple.push_back(CgPoint(pt->mX, pt->mY));

66)     }

67)     // check that polygon is simple

68)     if (!simpleEx.is_simple()) {

69)       std::cerr << "path is not simple (maybe self-itersecting?)" << std::endl;

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

73)       return false;
74)     }
75)     // ensure orientation is clockwise (must be the same for all polygons)

76)     if (simpleEx.is_clockwise_oriented()) {
77)       simpleEx.reverse_orientation();

78)       simple.reverse_orientation();

79)     }

80)     // collect polygons

81)     simplesEx.push_back(simpleEx);

82)     simples.push_back(simple);
83)   } // for path
84) 
85)   // check that no partly overlaps are present
86)   // deterine which polygon is contained in which one
87)   std::vector<ssize_t> contained_in; // idx: contained poly, val: containing poly
88)   ssize_t ia, ib;

89)   CgExPolyVec::const_iterator a, b;
90)   for (a = simplesEx.begin(); a != simplesEx.end(); ++a)

91)     contained_in.push_back(-1); // not contained in any polygon

92)   for (a = simplesEx.begin(), ia = 0; a != simplesEx.end(); ++a, ++ia) {

93)     b = a;
94)     ib = ia;

95)     for (++b, ++ib; b != simplesEx.end(); ++b, ++ib) {

96)       // A and B intersect each other
97)       if (CGAL::do_intersect(*a, *b)) {
98)         // compute differences A - B and B - A

99)         CgExPolyHolesVec a_b, b_a;

100)         CGAL::difference(*a, *b, std::back_inserter(a_b));
101)         CGAL::difference(*b, *a, std::back_inserter(b_a));
102)         if (a_b.empty()) {
103)           // A and B are identical
104)           if (b_a.empty()) {
105)             std::cerr << "duplicate polygons found - meaning is undefined"
106)                       << std::endl;
107)             return false;
108)           }
109)           // B contains A (A is hole in B)
110)           else {
111)             if (contained_in.at(ia) >= 0) {
112)               std::cerr << "polygon contained in multiple polygons"
113)                            " - meaning is undefined" << std::endl;
114)               return false;
115)             }
116)             contained_in.at(ia) = ib;
117)           }
118)         } else {
119)           // A contains B (B is hole in A)
120)           if (b_a.empty()) {
121)             if (contained_in.at(ib) >= 0) {
122)               std::cerr << "polygon contained in multiple polygons"
123)                            " - meaning is undefined" << std::endl;
124)               return false;
125)             }
126)             contained_in.at(ib) = ia;
127)           }
128)           // A and B overlap partly
129)           else {
130)             std::cerr << "polygons overlap partly - meaning is undefined"
131)                       << std::endl;
132)             return false;
133)           }
134)         }
135)       }
136)     } // for b
137)   } // for a
138) 
139)   // add found polygons to member variable
140)   for (ia = 0; (size_t)ia < contained_in.size(); ++ia) {
141)     // outer polygon
142)     if (contained_in.at(ia) < 0) {
143)       CgPolyHoles poly(simples.at(ia));
144)       // find and add holes

145)       for (ib = 0; (size_t)ib < contained_in.size(); ++ib) {
146)         if (contained_in.at(ib) == ia) {
147)           // holes must be counter-clockwise
148)           simples.at(ib).reverse_orientation();

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

150)         }
151)       }

152)       // add polygon to member variable
153)       mPolys.push_back(poly);
154)     }
155)   }
156) 
157)   return true;
158) }
159) 
160) /**
161)  * @brief load polygons from layer
162)  * @param[in] layer layer to obtain the polygons from
163)  * @param[in] eqDist maximum distance of two points to be considered equal
164)  * @return if the layer could be converted to polygons and imported
165)  */
166) bool Polygons::loadLayer(const Layer &layer, double eqDist)
167) {
168)   clear();
169)   return addLayer(layer, eqDist);
170) }
171) 

172) /**
173)  * @brief create inner offset polygons
174)  * @param[in] offset offset, > 0.0
175)  * @param[out] offsetPolys offset polygons (!= *this)

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

177)  */

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

179) {
180)   // clear output polygons
181)   offsetPolys.mPolys.clear();

182)   // leave if offset size is invalid

183)   if (offset <= 0.0) {
184)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
185)     return false;
186)   }

187) 
188)   // process all polygons
189)   CgPolyHolesVec::const_iterator poly;
190)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
191) 
192)     // create inner offset polygons
193)     CgPolyHolesPtrVec offPolys =
194)       CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2(

195)         offset, *poly);

196) 
197)     // add offset polygons to output polygons
198)     CgPolyHolesPtrVec::const_iterator offPoly;
199)     for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
200)       offsetPolys.mPolys.push_back(**offPoly);
201) 
202)   } // for poly

203) 
204)   return true;
205) }
206) 
207) /**
208)  * @brief create outer offset polygons
209)  * @param[in] offset offset, > 0.0
210)  * @param[out] offsetPolys offset polygons (!= *this)
211)  * @return if outer offset polygons could be constructed
212)  */
213) bool Polygons::createOuterOffset(double offset, Polygons &offsetPolys) const
214) {
215)   // clear output polygons
216)   offsetPolys.mPolys.clear();

217)   // leave if offset size is invalid

218)   if (offset <= 0.0) {
219)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
220)     return false;
221)   }
222) 
223)   // process all polygons
224)   CgPolyHolesVec::const_iterator poly;
225)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
226)     offsetPolys.mPolys.push_back(CgPolyHoles());
227)     createOuterOffsetPoly(*poly, offset, offsetPolys.mPolys.back());
228)   }
229) 
230)   return true;

231) }
232) 

233) /**
234)  * @brief fill insides of polygons by creating inner offset polygons
235)  * @param[in] offset offset, > 0.0
236)  * @param[out] offsetPolys offset polygons (!= *this)
237)  * @return if insides of polygons could be filles with inner offset polygons
238)  */
239) bool Polygons::fillInnerOffset(double offset, Polygons &offsetPolys) const
240) {
241)   // clear output polygons
242)   offsetPolys.mPolys.clear();
243)   // leave if offset size is invalid
244)   if (offset <= 0.0) {
245)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
246)     return false;
247)   }
248) 
249)   // process all polygons
250)   CgPolyHolesVec::const_iterator poly;
251)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
252) 
253)     // create interior straight skeleton
254)     CgSsPtr skel = CGAL::create_interior_straight_skeleton_2(*poly);
255) 
256)     // create inner offset polygons with increasing offset
257)     size_t i;
258)     for (i = 1; ; ++i) {
259) 
260)       // create inner offset polygons
261)       CgPolyPtrVec offPolys =

262)         CGAL::create_offset_polygons_2<CgPoly>(offset * i, *skel);

263) 
264)       // no offset polygons -> done
265)       if (offPolys.empty())
266)         break;
267) 
268)       // add offset polygons to output polygons
269)       CgPolyPtrVec::const_iterator offPoly;
270)       for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
271)         offsetPolys.mPolys.push_back(CgPolyHoles(**offPoly));
272) 
273)     } // for i
274) 
275)   } // for poly
276) 
277)   return true;
278) }
279) 

280) /**
281)  * @brief add all polygons with holes as multiple paths to a layer
282)  * @param[in,out] layer layer to add paths to
283)  */
284) void Polygons::addToLayer(Layer &layer) const
285) {
286)   CgPolyHolesVec::const_iterator poly;
287)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly)
288)     PolyHolesToLayer(*poly, layer);
289) }
290) 
291) /**
292)  * @brief write all polygons with holes as multiple paths to a layer
293)  * @param[in,out] layer layer to write paths to
294)  */
295) void Polygons::writeToLayer(Layer &layer) const
296) {
297)   layer.mPaths.clear();
298)   addToLayer(layer);
299) }
300) 

301) /**
302)  * @brief create outer offset polygon
303)  * @param[in] poly polygon to create outer offset of
304)  * @param[in] offset offset, > 0.0
305)  * @param[out] offsetPoly offset polygon (!= *this)
306)  * @return if outer offset polygon could be constructed
307)  */
308) bool Polygons::createOuterOffsetPoly(const CgPolyHoles &poly, double offset,
309)                                      CgPolyHoles &offsetPoly)
310) {
311)   // calculate outer offset of outer bondary
312)   const CgPoly &outer = poly.outer_boundary();
313)   CgPolyPtrVec outOffPolys =

314)     CGAL::create_exterior_skeleton_and_offset_polygons_2(

315)       offset, outer);

316)   /* outer Offset should now contain 2 polygons,
317)      the artificially added very outer boundary and the offset polygon */
318)   if (outOffPolys.size() != 2) {
319)     std::cerr << "internal error during outer offset computation" << std::endl;
320)     return false;
321)   }
322)   offsetPoly = CgPolyHoles(*outOffPolys.at(1)); // use offset polygon
323) 
324)   // calculate inner offset of holes
325)   CgPolyHoles::Hole_const_iterator hole;
326)   for (hole = poly.holes_begin(); hole != poly.holes_end(); ++hole) {
327)     CgPoly holeRev = *hole; // reverse orientation (make hole a normal poly)
328)     holeRev.reverse_orientation();
329)     CgPolyPtrVec inOffPolys =

330)       CGAL::create_interior_skeleton_and_offset_polygons_2(

331)         offset, holeRev);

332)     CgPolyPtrVec::iterator inOff; // add inner offset polys as new holes
333)     for (inOff = inOffPolys.begin(); inOff != inOffPolys.end(); ++inOff) {
334)       (*inOff)->reverse_orientation(); // re-reverse (make poly a hole again)
335)       offsetPoly.add_hole(**inOff);
336)     }
337)   }
338) 
339)   return true;
340) }
341) 

342) /**
343)  * @brief add a polygon as path to a layer
344)  * @param[in] poly polygon to add to layer
345)  * @param[in,out] layer layer to add path to
346)  */
347) void Polygons::PolyToLayer(const CgPoly &poly, Layer &layer)
348) {
349)   // ignore empty polygons
350)   if (poly.vertices_begin() == poly.vertices_end())
351)     return;
352)   // create new path
353)   layer.mPaths.push_back(Path());
354)   Path &path = layer.mPaths.back();
355)   // add all points
356)   CgPoly::Vertex_const_iterator v;
357)   for (v = poly.vertices_begin(); v != poly.vertices_end(); ++v)

358)     path.addPoint(CGAL::to_double(v->x()), CGAL::to_double(v->y()));

359)   // add first point again to close path

360)   path.addPoint(path.mPoints.front());