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/Gmpq.h>
12) #include <CGAL/number_utils.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)   CgPolyVec simples;
42)   Layer::Paths::const_iterator path;
43)   for (path = layer.mPaths.begin(); path != layer.mPaths.end(); ++path) {

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

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

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

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

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

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

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

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

141)         }
142)       }

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

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

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

168)  */

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

170) {
171)   // clear output polygons
172)   offsetPolys.mPolys.clear();

173)   // leave if offset size is invalid

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

178) 
179)   // process all polygons
180)   CgPolyHolesVec::const_iterator poly;
181)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
182) 
183)     // create inner offset polygons

184)     CGAL::Lazy_exact_nt<CGAL::Gmpq> offs(offset);

185)     CgPolyHolesPtrVec offPolys =
186)       CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2(

187)         offs, *poly);

188) 
189)     // add offset polygons to output polygons
190)     CgPolyHolesPtrVec::const_iterator offPoly;
191)     for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
192)       offsetPolys.mPolys.push_back(**offPoly);
193) 
194)   } // for poly

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

209)   // leave if offset size is invalid

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

223) }
224) 

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

253)       CGAL::Lazy_exact_nt<CGAL::Gmpq> offs_i(offset * i);

254)       CgPolyPtrVec offPolys =

255)         CGAL::create_offset_polygons_2<CgPoly>(offs_i, *skel);

256) 
257)       // no offset polygons -> done
258)       if (offPolys.empty())
259)         break;
260) 
261)       // add offset polygons to output polygons
262)       CgPolyPtrVec::const_iterator offPoly;
263)       for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
264)         offsetPolys.mPolys.push_back(CgPolyHoles(**offPoly));
265) 
266)     } // for i
267) 
268)   } // for poly
269) 
270)   return true;
271) }
272) 

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

294) /**
295)  * @brief create outer offset polygon
296)  * @param[in] poly polygon to create outer offset of
297)  * @param[in] offset offset, > 0.0
298)  * @param[out] offsetPoly offset polygon (!= *this)
299)  * @return if outer offset polygon could be constructed
300)  */
301) bool Polygons::createOuterOffsetPoly(const CgPolyHoles &poly, double offset,
302)                                      CgPolyHoles &offsetPoly)
303) {
304)   // calculate outer offset of outer bondary

305)   CGAL::Lazy_exact_nt<CGAL::Gmpq> offs(offset);

306)   const CgPoly &outer = poly.outer_boundary();

307)   CgKern kern;

308)   CgPolyPtrVec outOffPolys =

309)     CGAL::create_exterior_skeleton_and_offset_polygons_2(
310)       offs, outer, kern, kern);

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

325)       CGAL::create_interior_skeleton_and_offset_polygons_2(
326)         offs, holeRev, kern, kern);

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

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

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

354)   // add first point again to close path

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