1 ////////////////////////////////////////////////////////////////////////////////////////////////
2 // 2d geometry classes - implements 2d kurve offset for use in dll
3 //
4 // g.j.hawkesford August 2003
5 //
6 // This program is released under the BSD license. See the file COPYING for details.
7 //
8 ////////////////////////////////////////////////////////////////////////////////////////////////
9 #include "geometry.h"
10 using namespace geoff_geometry;
11
12 namespace geoff_geometry {
13 static Kurve eliminateLoops(const Kurve& k , const Kurve& originalk, double offset, int& ret);
14 static bool DoesIntersInterfere(const Point& pInt, const Kurve& k, double offset);
15
Offset(vector<Kurve * > & OffsetKurves,double offset,int direction,int method,int & ret) const16 int Kurve::Offset(vector<Kurve*>&OffsetKurves, double offset, int direction, int method, int& ret)const {
17
18 switch(method) {
19 case NO_ELIMINATION:
20 case BASIC_OFFSET:
21 {
22 Kurve* ko = new Kurve;
23 int n = OffsetMethod1(*ko, offset, direction, method, ret);
24 OffsetKurves.push_back(ko);
25 return n;
26 }
27
28 default:
29 FAILURE(L"Requested Offsetting Method not available");
30 }
31 return 0;
32 }
33
OffsetMethod1(Kurve & kOffset,double off,int direction,int method,int & ret) const34 int Kurve::OffsetMethod1(Kurve& kOffset, double off, int direction, int method, int& ret)const
35 {
36 // offset kurve with simple span elimination
37 // direction 1 = left, -1 = right
38
39 // ret = 0 - kurve offset ok
40 // = 1 - kurve has differential scale (not allowed)
41 // = 2 - offset failed
42 // = 3 - offset too large
43 if(this == &kOffset) FAILURE(L"Illegal Call - 'this' must not be kOffset");
44 double offset = (direction == GEOFF_LEFT)?off : -off;
45
46 if(fabs(offset) < geoff_geometry::TOLERANCE || m_nVertices < 2) {
47 kOffset = *this;
48 ret = 0;
49 return 1;
50 }
51
52 Span curSpan, curSpanOff; // current & offset spans
53 Span prevSpanOff; // previous offset span
54 Point p0, p1; // Offset span intersections
55
56 // offset Kurve
57 kOffset = Matrix(*this);
58
59 if(m_mirrored) offset = -offset;
60 int RollDir = ( off < 0 ) ? direction : - direction; // Roll arc direction
61
62 double scalex;
63 if(!GetScale(scalex)) {
64 ret = 1;
65 return 0; // differential scale
66 }
67 offset /= scalex;
68
69 bool bClosed = Closed();
70 int nspans = nSpans();
71 if(bClosed) {
72 Get(nspans, curSpan, true); // assign previus span for closed
73
74 prevSpanOff = curSpan.Offset(offset);
75 nspans++; // read first again
76 }
77
78 for(int spannumber = 1; spannumber <= nspans; spannumber++) {
79 if(spannumber > nSpans())
80 Get(1, curSpan, true); // closed kurve - read first span again
81 else
82 Get(spannumber, curSpan, true);
83
84 if(!curSpan.NullSpan) {
85 int numint = 0;
86 curSpanOff = curSpan.Offset(offset);
87 curSpanOff.ID = 0;
88 if(!kOffset.m_started) {
89 kOffset.Start(curSpanOff.p0);
90 kOffset.AddSpanID(0);
91 }
92
93 if(spannumber > 1) {
94 // see if tangent
95 double d = curSpanOff.p0.Dist(prevSpanOff.p1);
96 if((d > geoff_geometry::TOLERANCE) && (curSpanOff.NullSpan == false && prevSpanOff.NullSpan == false)) {
97 // see if offset spans intersect
98
99 double cp = prevSpanOff.ve ^ curSpanOff.vs;
100 bool inters = (cp > 0 && direction == GEOFF_LEFT) || (cp < 0 && direction == GEOFF_RIGHT);
101
102 if(inters) {
103 double t[4];
104 numint = prevSpanOff.Intof(curSpanOff, p0, p1, t);
105 }
106
107 if(numint == 1) {
108 // intersection - modify previous endpoint
109 kOffset.Replace(kOffset.m_nVertices-1, prevSpanOff.dir, p0, prevSpanOff.pc, prevSpanOff.ID);
110 }
111 else {
112 // 0 or 2 intersections, add roll around (remove -ve loops in elimination function)
113 if(kOffset.Add(RollDir, curSpanOff.p0, curSpan.p0, false)) kOffset.AddSpanID(ROLL_AROUND);
114 }
115 }
116 }
117
118 // add span
119 if(spannumber < m_nVertices) {
120 curSpanOff.ID = spannumber;
121 kOffset.Add(curSpanOff, false);
122 }
123 else if(numint == 1) // or replace the closed first span
124 kOffset.Replace(0, 0, p0, Point(0, 0), 0);
125
126 }
127 if(!curSpanOff.NullSpan)prevSpanOff = curSpanOff;
128 } // end of main pre-offsetting loop
129
130
131 #ifdef _DEBUG
132 //testDraw->AddKurve("", &kOffset, 0, GREEN);
133 // outXML oxml(L"c:\\temp\\eliminateLoops.xml");
134 // oxml.startElement(L"eliminateLoops");
135 // oxml.Write(kOffset, L"kOffset");
136 // oxml.endElement();
137 #endif
138 // eliminate loops
139 if(method == NO_ELIMINATION) {
140 ret = 0;
141 return 1;
142 }
143 kOffset = eliminateLoops(kOffset, *this, offset, ret);
144
145 if(ret == 0 && bClosed) {
146 // check for inverted offsets of closed kurves
147 if(kOffset.Closed()) {
148 double a = Area();
149 int dir = (a < 0);
150 double ao = kOffset.Area();
151 int dirOffset = ao < 0;
152
153 if(dir != dirOffset)
154 ret = 3;
155 else {
156 // check area change compatible with offset direction - catastrophic failure
157 bool bigger = (a > 0 && offset > 0) || (a < 0 && offset < 0);
158 if(bigger && fabs(ao) < fabs(a)) ret = 2;
159 }
160 }
161 else
162 ret = 2; // started closed but now open??
163 }
164 return (ret == 0)?1 : 0;
165 }
166
167
eliminateLoops(const Kurve & k,const Kurve & originalk,double offset,int & ret)168 static Kurve eliminateLoops(const Kurve& k , const Kurve& originalk, double offset, int& ret) {
169 // a simple loop elimination routine based on first offset ideas in Peps
170 // this needs extensive work for future
171 // start point musn't disappear & only one valid offset is determined
172 //
173 // ret = 0 for ok
174 // ret = 2 for impossible geometry
175
176 Span sp0, sp1;
177 Point pInt, pIntOther;
178
179 Kurve ko; // eliminated output
180 ko = Matrix(k);
181 int kinVertex = 0;
182
183 while(kinVertex <= k.nSpans()) {
184 bool clipped = false ; // not in a clipped section (assumption with this simple method)
185
186 sp0.dir = k.Get(kinVertex, sp0.p0, sp0.pc);
187 sp0.ID = k.GetSpanID(kinVertex++);
188 if (kinVertex == 1) {
189 ko.Start(sp0.p0); // start point mustn't dissappear for this simple method
190 ko.AddSpanID(sp0.ID);
191 }
192 if (kinVertex <= k.nSpans()) { // any more?
193 int ksaveVertex = kinVertex ;
194 sp0.dir = k.Get(kinVertex, sp0.p1, sp0.pc); // first span
195 sp0.ID = k.GetSpanID(kinVertex++);
196
197 sp0.SetProperties(true);
198
199 int ksaveVertex1 = kinVertex; // mark position AA
200 if (kinVertex <= k.nSpans()) { // get the next but one span
201 sp1.dir = k.Get(kinVertex, sp1.p0, sp1.pc);
202 sp1.ID = k.GetSpanID(kinVertex++);
203 int ksaveVertex2 = kinVertex; // mark position BB
204
205 int fwdCount = 0;
206 while(kinVertex <= k.nSpans()) {
207 sp1.dir = k.Get(kinVertex, sp1.p1, sp1.pc); // check span
208 sp1.ID = k.GetSpanID(kinVertex++);
209 sp1.SetProperties(true);
210
211 double t[4];
212 int numint = sp0.Intof(sp1, pInt, pIntOther, t); // find span intersections
213 if(numint && sp0.p0.Dist(pInt) < geoff_geometry::TOLERANCE ) numint=0; // check that intersection is not at the start of the check span
214 if(numint ) {
215
216 if(numint == 2) {
217 // choose first intercept on sp0
218 Span spd = sp0;
219 spd.p1 = pInt;
220 spd.SetProperties(true);
221 double dd = spd.length;
222
223 spd.p1 = pIntOther;
224 spd.SetProperties(true);
225 if(dd > spd.length) pInt = pIntOther;
226 numint = 1;
227
228 }
229 ksaveVertex = ksaveVertex1 ;
230
231 clipped = true ; // in a clipped section
232 if(DoesIntersInterfere(pInt, originalk, offset) == false) {
233 sp0.p1 = pInt; // ok so truncate this span to the intersection
234 clipped = false; // end of clipped section
235 break;
236 }
237 // no valid intersection found so carry on
238 }
239 sp1.p0 = sp1.p1 ; // next
240 ksaveVertex1 = ksaveVertex2 ; // pos AA = BB
241 ksaveVertex2 = kinVertex; // mark
242
243 if((kinVertex > k.nSpans() || fwdCount++ > 25) && clipped == false) break;
244 }
245 }
246
247 if(clipped) {
248 ret = 2; // still in a clipped section - error
249
250 return ko;
251 }
252
253 ko.Add(sp0, false);
254
255 kinVertex = ksaveVertex;
256 }
257 }
258 ret = 0;
259
260 return ko; // no more spans - seems ok
261 }
262
263
DoesIntersInterfere(const Point & pInt,const Kurve & k,double offset)264 static bool DoesIntersInterfere(const Point& pInt, const Kurve& k, double offset) {
265 // check that intersections don't interfere with the original kurve
266 Span sp;
267 Point dummy;
268 int kCheckVertex = 0;
269 k.Get(kCheckVertex++, sp.p0, sp.pc);
270
271 offset = fabs(offset) - geoff_geometry::TOLERANCE;
272 while(kCheckVertex <= k.nSpans()) {
273 sp.dir = k.Get(kCheckVertex++, sp.p1, sp.pc);
274 sp.SetProperties(true);
275 // check for interference
276 if(Dist(sp, pInt, dummy) < offset) return true;
277 sp.p0 = sp.p1;
278 }
279 return false; // intersection is ok
280 }
281 }
282
283
284 static struct iso {
285 Span sp;
286 Span off;
287 } isodata;
288 static void isoRadius(Span& before, Span& blend, Span& after, double radius);
289
OffsetISOMethod(Kurve & kOut,double off,int direction,bool BlendAll) const290 int Kurve::OffsetISOMethod(Kurve& kOut, double off, int direction, bool BlendAll)const {
291 // produces a special offset Kurve - observing so-called ISO radii
292 // eg line/arc/line tangent - keep arc radius constant
293 // this method also considers arc/arc/arc etc.
294 // interior radius must be smallest of triplet for above.
295
296 // parameters:-
297 // Output kOut resulting kurve
298 // Input off offset amount
299 // Input direction offset direction (LEFT or RIGHT)
300 // Input BlendAall if false only consider ISO radius for LINE/ARC/LINE
301 // if true consider all blended radii (ARC/ARC/ARC etc.)
302 double offset = (direction == GEOFF_LEFT)?off : -off;
303 if(FEQZ(off) || nSpans() < 1) {
304 kOut = *this;
305 return 1;
306 }
307 double cptol = 1.0e-05;
308 std::vector<iso> spans;
309 for(int i = 0; i < nSpans(); i++) { // store all spans and offsets
310 Get(i+1, isodata.sp, true, true);
311 isodata.off = isodata.sp.Offset(offset);
312 spans.push_back(isodata);
313 }
314
315 for(int i = 0; i < nSpans() - 1; i++) // calculate intersections for none tangent spans
316 if(fabs(spans[i].off.ve ^ spans[i+1].off.vs) > cptol) spans[i].off.JoinSeparateSpans(spans[i+1].off);
317
318 for(int i = 1; i < nSpans() - 1; i++) { // deal with isoradii
319 if(spans[i].off.dir) {
320 if(BlendAll) { // interior radius should be smaller than neighbours
321 if(spans[i-1].sp.dir)
322 if(spans[i-1].sp.radius < spans[i].sp.radius) continue;
323 if(spans[i+1].sp.dir)
324 if(spans[i+1].sp.radius < spans[i].sp.radius) continue;
325 }
326 else {
327 if((spans[i-1].off.dir || spans[i+1].off.dir)) continue; // linear neighbours only
328 }
329
330 if((fabs(spans[i-1].sp.ve ^ spans[i].sp.vs) < cptol) && (fabs(spans[i].sp.ve ^ spans[i+1].sp.vs) < cptol)) {
331 // isoradius - calculate the new offset radius and modify neighbouring spans
332 isoRadius(spans[i-1].off, spans[i].off, spans[i+1].off, spans[i].sp.radius);
333 }
334 }
335 }
336
337 kOut.Start(spans[0].off.p0); // start point
338 for(int i = 0; i < nSpans(); i++)
339 kOut.Add(spans[i].off.dir, spans[i].off.p1, spans[i].off.pc); // output all spans
340 return 1;
341 }
342
isoRadius(Span & before,Span & blend,Span & after,double radius)343 static void isoRadius(Span& before, Span& blend, Span& after, double radius) {
344 // calculate the new offset radius and modify neighbouring spans
345 int direction = ((before.ve ^ after.vs) > 0)? 1 : -1; // offset direction
346 Span beforeOff = before.Offset(direction * radius);
347 Span afterOff = after.Offset(direction * radius);
348 int turnLeft = ((before.ve ^ after.vs) > 0)? 1 : -1;
349 if(before.dir == LINEAR) {
350 CLine b(beforeOff);
351 if(after.dir == LINEAR) {
352 CLine a(afterOff);
353 blend.pc = b.Intof(a);
354 }
355 else {
356 Circle a(afterOff);
357 b.Intof(turnLeft * after.dir, a, blend.pc);
358 }
359 }
360 else {
361 Circle b(beforeOff);
362
363 if(after.dir == LINEAR) {
364 CLine a(afterOff);
365 a.Intof(-turnLeft * before.dir, b, blend.pc);
366 }
367 else {
368 // arc arc
369 Circle a(afterOff);
370 int leftright = ((Vector2d(b.pc, blend.pc) ^ Vector2d(b.pc, a.pc)) < 0)? 1 : -1;
371 b.Intof(leftright, a, blend.pc);
372 }
373 }
374 before.p1 = blend.p0 = before.Near(blend.pc);
375 after.p0 = blend.p1 = after.Near(blend.pc);
376 }
377