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

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

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

132)         }
133)       }

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

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

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

159)  */

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

161) {
162)   // clear output polygons
163)   offsetPolys.mPolys.clear();
164)   // leave if tool diameter is invalid

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

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

185) 
186)   return true;
187) }
188) 
189) /**
190)  * @brief create outer offset polygons
191)  * @param[in] offset offset, > 0.0
192)  * @param[out] offsetPolys offset polygons (!= *this)
193)  * @return if outer offset polygons could be constructed
194)  */
195) bool Polygons::createOuterOffset(double offset, Polygons &offsetPolys) const
196) {
197)   // clear output polygons
198)   offsetPolys.mPolys.clear();
199)   // leave if tool diameter is invalid
200)   if (offset <= 0.0) {
201)     std::cerr << "invalid polygon offset distance " << offset << std::endl;
202)     return false;
203)   }
204) 
205)   // process all polygons
206)   CgPolyHolesVec::const_iterator poly;
207)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
208)     offsetPolys.mPolys.push_back(CgPolyHoles());
209)     createOuterOffsetPoly(*poly, offset, offsetPolys.mPolys.back());
210)   }
211) 
212)   return true;

213) }
214) 

215) /**
216)  * @brief add all polygons with holes as multiple paths to a layer
217)  * @param[in,out] layer layer to add paths to
218)  */
219) void Polygons::addToLayer(Layer &layer) const
220) {
221)   CgPolyHolesVec::const_iterator poly;
222)   for (poly = mPolys.begin(); poly != mPolys.end(); ++poly)
223)     PolyHolesToLayer(*poly, layer);
224) }
225) 
226) /**
227)  * @brief write all polygons with holes as multiple paths to a layer
228)  * @param[in,out] layer layer to write paths to
229)  */
230) void Polygons::writeToLayer(Layer &layer) const
231) {
232)   layer.mPaths.clear();
233)   addToLayer(layer);
234) }
235) 

236) /**
237)  * @brief create outer offset polygon
238)  * @param[in] poly polygon to create outer offset of
239)  * @param[in] offset offset, > 0.0
240)  * @param[out] offsetPoly offset polygon (!= *this)
241)  * @return if outer offset polygon could be constructed
242)  */
243) bool Polygons::createOuterOffsetPoly(const CgPolyHoles &poly, double offset,
244)                                      CgPolyHoles &offsetPoly)
245) {
246)   // calculate outer offset of outer bondary
247)   const CgPoly &outer = poly.outer_boundary();
248)   CgPolyPtrVec outOffPolys =
249)     CGAL::create_exterior_skeleton_and_offset_polygons_2(offset, outer);
250)   /* outer Offset should now contain 2 polygons,
251)      the artificially added very outer boundary and the offset polygon */
252)   if (outOffPolys.size() != 2) {
253)     std::cerr << "internal error during outer offset computation" << std::endl;
254)     return false;
255)   }
256)   offsetPoly = CgPolyHoles(*outOffPolys.at(1)); // use offset polygon
257) 
258)   // calculate inner offset of holes
259)   CgPolyHoles::Hole_const_iterator hole;
260)   for (hole = poly.holes_begin(); hole != poly.holes_end(); ++hole) {
261)     CgPoly holeRev = *hole; // reverse orientation (make hole a normal poly)
262)     holeRev.reverse_orientation();
263)     CgPolyPtrVec inOffPolys =
264)       CGAL::create_interior_skeleton_and_offset_polygons_2(offset, holeRev);
265)     CgPolyPtrVec::iterator inOff; // add inner offset polys as new holes
266)     for (inOff = inOffPolys.begin(); inOff != inOffPolys.end(); ++inOff) {
267)       (*inOff)->reverse_orientation(); // re-reverse (make poly a hole again)
268)       offsetPoly.add_hole(**inOff);
269)     }
270)   }
271) 
272)   return true;
273) }
274)