← Back to branch summary

~ubuntu-branches/debian/experimental/inkscape/experimental

« back to all changes in this revision

Viewing changes to src/2geom/shape.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Viehmann
  • Date: 2008-09-09 23:29:02 UTC
  • mfrom: (1.1.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20080909232902-c50iujhk1w79u8e7
Tags: 0.46-2.1
http://bugs.debian.org/487623
* Non-maintainer upload.
* Add upstream patch fixing a crash in the open dialog
  in the zh_CN.utf8 locale. Closes: #487623.
  Thanks to Luca Bruno for the patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/2geom/shape.cpp
 
1
#include "shape.h"
 
2
#include "utils.h"
 
3
#include "sweep.h"
 
4
#include "ord.h"
 
5
 
 
6
#include <iostream>
 
7
#include <algorithm>
 
8
#include <cstdlib>
 
9
 
 
10
namespace Geom {
 
11
 
 
12
// A little sugar for appending a list to another
 
13
template<typename T>
 
14
void append(T &a, T const &b) {
 
15
    a.insert(a.end(), b.begin(), b.end());
 
16
}
 
17
 
 
18
//Orders a list of indices according to their containment within eachother.
 
19
struct ContainmentOrder {
 
20
    std::vector<Region> const *rs;
 
21
    explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {}
 
22
    bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); }
 
23
};
 
24
 
 
25
//Returns the list of regions containing a particular point.  Useful in tandem with ContainmentOrder
 
26
std::vector<unsigned> Shape::containment_list(Point p) const {
 
27
    std::vector<Rect> pnt;
 
28
    pnt.push_back(Rect(p, p));
 
29
    std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this));
 
30
    std::vector<unsigned> containers;
 
31
    if(cull[0].size() == 0) return containers;
 
32
    for(unsigned i = 0; i < cull[0].size(); i++)
 
33
        if(content[cull[0][i]].contains(p)) containers.push_back(cull[0][i]);
 
34
    return containers;
 
35
}
 
36
 
 
37
/* Used within shape_boolean and related functions, as the name describes, finds the
 
38
 * first false within the list of lists of booleans.
 
39
 */
 
40
void first_false(std::vector<std::vector<bool> > visited, unsigned &i, unsigned &j) {
 
41
    for(i = 0, j = 0; i < visited.size(); i++) {
 
42
        std::vector<bool>::iterator unvisited = std::find(visited[i].begin(), visited[i].end(), false);
 
43
        if(unvisited != visited[i].end()) {
 
44
            j = unvisited - visited[i].begin();
 
45
            break;
 
46
        }
 
47
    }
 
48
}
 
49
 
 
50
// Finds a crossing in a list of them, given the sorting index.
 
51
unsigned find_crossing(Crossings const &cr, Crossing x, unsigned i) {
 
52
    return std::lower_bound(cr.begin(), cr.end(), x, CrossingOrder(i)) - cr.begin();
 
53
}
 
54
 
 
55
/* This function handles boolean ops on shapes.  The first parameter is a bool
 
56
 * which determines its behavior in each combination of cases.  For proper
 
57
 * fill information and noncrossing behavior, the fill data of the regions
 
58
 * must be correct.  The boolean parameter determines whether the operation
 
59
 * is a union or a subtraction.  Reversed paths represent inverse regions,
 
60
 * where everything is included in the fill except for the insides.
 
61
 *
 
62
 * Here is a chart of the behavior under various circumstances:
 
63
 * 
 
64
 * rev = false (union)
 
65
 *            A
 
66
 *        F         H
 
67
 * F  A+B -> F  A-B -> H
 
68
 *B
 
69
 * H  B-A -> H  AxB -> H
 
70
 *
 
71
 * rev = true (intersect)
 
72
 *            A
 
73
 *        F         H
 
74
 * F  AxB -> F  B-A -> F
 
75
 *B
 
76
 * H  A-B -> F  A+B -> H
 
77
 *
 
78
 * F/H = Fill outer / Hole outer
 
79
 * A/B specify operands
 
80
 * + = union, - = subtraction, x = intersection
 
81
 * -> read as "produces"
 
82
 *
 
83
 * This is the main function of boolops, yet its operation isn't very complicated.
 
84
 * It traverses the crossings, and uses the crossing direction to decide whether
 
85
 * the next segment should be taken from A or from B.  The second half of the
 
86
 * function deals with figuring out what to do with bits that have no intersection.
 
87
 */
 
88
Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet const & crs) {
 
89
    const Regions ac = a.content, bc = b.content;
 
90
 
 
91
    //Keep track of which crossings we've hit.
 
92
    std::vector<std::vector<bool> > visited;
 
93
    for(unsigned i = 0; i < crs.size(); i++)
 
94
        visited.push_back(std::vector<bool>(crs[i].size(), false));
 
95
    
 
96
    //Traverse the crossings, creating chunks
 
97
    Regions chunks;
 
98
    while(true) {
 
99
        unsigned i, j;
 
100
        first_false(visited, i, j);
 
101
        if(i == visited.size()) break;
 
102
        
 
103
        Path res;
 
104
        do {
 
105
            Crossing cur = crs[i][j];
 
106
            visited[i][j] = true;
 
107
            
 
108
            //get indices of the dual:
 
109
            unsigned io = cur.getOther(i), jo = find_crossing(crs[io], cur, io);
 
110
            if(jo < visited[io].size()) visited[io][jo] = true;
 
111
            
 
112
            //main driving logic
 
113
            if(logical_xor(cur.dir, rev)) {
 
114
                if(i >= ac.size()) { i = io; j = jo; }
 
115
                j++;
 
116
                if(j >= crs[i].size()) j = 0;
 
117
                Crossing next = crs[i][j];
 
118
                ac[next.a].boundary.appendPortionTo(res, cur.ta, next.ta);
 
119
            } else {
 
120
                if(i < ac.size()) { i = io; j = jo; }
 
121
                j++;
 
122
                if(j >= crs[i].size()) j = 0;
 
123
                Crossing next = crs[i][j];
 
124
                bc[next.b - ac.size()].boundary.appendPortionTo(res, cur.tb, next.tb);
 
125
            }
 
126
        } while (!visited[i][j]);
 
127
        if(res.size() > 0) chunks.push_back(Region(res));
 
128
    }
 
129
    
 
130
    //If true, then we are on the 'subtraction diagonal'
 
131
    bool const on_sub = logical_xor(a.fill, b.fill);
 
132
    //If true, outer paths are filled
 
133
    bool const res_fill = rev ? (on_sub || (a.fill && b.fill)) : (a.fill && b.fill);
 
134
    
 
135
    //Handle unintersecting portions
 
136
    for(unsigned i = 0; i < crs.size(); i++) {
 
137
        if(crs[i].size() == 0) {
 
138
            bool env;
 
139
            bool on_a = i < ac.size();
 
140
            Region const & r(on_a ? ac[i] : bc[i - ac.size()]);
 
141
            Shape const & other(on_a ? b : a);
 
142
            
 
143
            std::vector<unsigned> containers = other.containment_list(r.boundary.initialPoint());
 
144
            if(containers.empty()) {
 
145
                //not included in any container, the environment fill is the opposite of the outer fill
 
146
                env = !res_fill;
 
147
                if(on_sub && logical_xor(other.fill, res_fill)) env = !env;  //If on the subtractor, invert the environment fill
 
148
            } else {
 
149
                //environment fill is the same as the inner-most container
 
150
                std::vector<unsigned>::iterator cit = std::min_element(containers.begin(), containers.end(), ContainmentOrder(&other.content));
 
151
                env = other[*cit].isFill();
 
152
            }
 
153
            if(!logical_xor(rev, env)) chunks.push_back(r); //When unioning, environment must be hole for inclusion, when intersecting, it must be filled
 
154
        }
 
155
    }
 
156
    
 
157
    return Shape(chunks, res_fill);
 
158
}
 
159
 
 
160
// Just a convenience wrapper for shape_boolean, which handles the crossings
 
161
Shape shape_boolean(bool rev, Shape const & a, Shape const & b) {
 
162
    CrossingSet crs = crossings_between(a, b);
 
163
    
 
164
    return shape_boolean(rev, a, b, crs);
 
165
}
 
166
 
 
167
 
 
168
// Some utility functions for boolop:
 
169
 
 
170
std::vector<double> region_sizes(Shape const &a) {
 
171
    std::vector<double> ret;
 
172
    for(unsigned i = 0; i < a.size(); i++) {
 
173
        ret.push_back(double(a[i].size()));
 
174
    }
 
175
    return ret;
 
176
}
 
177
 
 
178
Shape shape_boolean_ra(bool rev, Shape const &a, Shape const &b, CrossingSet const &crs) {
 
179
    return shape_boolean(rev, a.inverse(), b, reverse_ta(crs, a.size(), region_sizes(a)));
 
180
}
 
181
 
 
182
Shape shape_boolean_rb(bool rev, Shape const &a, Shape const &b, CrossingSet const &crs) {
 
183
    return shape_boolean(rev, a, b.inverse(), reverse_tb(crs, a.size(), region_sizes(b)));
 
184
}
 
185
 
 
186
/* This is a function based on shape_boolean which allows boolean operations
 
187
 * to be specified as a logic table.  This logic table is 4 bit-flags, which
 
188
 * correspond to the elements of the 'truth table' for a particular operation.
 
189
 * These flags are defined with the enums starting with BOOLOP_ .
 
190
 *
 
191
 * NOTE: currently doesn't work, as the CrossingSet reversal functions crash
 
192
 */
 
193
Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &crs) {
 
194
    throwNotImplemented();
 
195
    flags &= 15;
 
196
    if(flags <= BOOLOP_UNION) {
 
197
        switch(flags) {
 
198
            case BOOLOP_INTERSECT:    return shape_boolean(true, a, b, crs);
 
199
            case BOOLOP_SUBTRACT_A_B: return shape_boolean_rb(true, a, b, crs);
 
200
            case BOOLOP_IDENTITY_A:   return a;
 
201
            case BOOLOP_SUBTRACT_B_A: return shape_boolean_ra(true, a, b, crs);
 
202
            case BOOLOP_IDENTITY_B:   return b;
 
203
            case BOOLOP_EXCLUSION: {
 
204
                Shape res = shape_boolean_rb(true, a, b, crs);
 
205
                append(res.content, shape_boolean_ra(true, a, b, crs).content);
 
206
                return res;
 
207
            }
 
208
            case BOOLOP_UNION:        return shape_boolean(false, a, b);
 
209
        }
 
210
    } else {
 
211
        flags = ~flags & 15;
 
212
        switch(flags - BOOLOP_NEITHER) {
 
213
            case BOOLOP_SUBTRACT_A_B: return shape_boolean_ra(false, a, b, crs);
 
214
            case BOOLOP_SUBTRACT_B_A: return shape_boolean_rb(false, a, b, crs);
 
215
            case BOOLOP_EXCLUSION: {
 
216
                Shape res = shape_boolean_ra(false, a, b, CrossingSet(crs));
 
217
                append(res.content, shape_boolean_rb(false, a, b, CrossingSet(crs)).content);
 
218
                return res;
 
219
            }
 
220
        }
 
221
        return boolop(a, b, flags, crs).inverse();
 
222
    }
 
223
    return Shape();
 
224
}
 
225
 
 
226
/* This version of the boolop function doesn't require a set of crossings, as
 
227
 * it computes them for you.  This is more efficient in some cases, as the
 
228
 * shape can be inverted before finding crossings.  In the special case of
 
229
 * exclusion it uses the other version of boolop.
 
230
 */
 
231
Shape boolop(Shape const &a, Shape const &b, unsigned flags) {
 
232
    flags &= 15;
 
233
    if(flags <= BOOLOP_UNION) {
 
234
        switch(flags) {
 
235
            case BOOLOP_INTERSECT:    return shape_boolean(true, a, b);
 
236
            case BOOLOP_SUBTRACT_A_B: return shape_boolean(true, a, b.inverse());
 
237
            case BOOLOP_IDENTITY_A:   return a;
 
238
            case BOOLOP_SUBTRACT_B_A: return shape_boolean(true, b, a.inverse());
 
239
            case BOOLOP_IDENTITY_B:   return b;
 
240
            case BOOLOP_EXCLUSION: {
 
241
                Shape res = shape_boolean(true, a, b.inverse());
 
242
                append(res.content, shape_boolean(true, b, a.inverse()).content);
 
243
                return res;
 
244
            } //return boolop(a, b, flags,  crossings_between(a, b));
 
245
            case BOOLOP_UNION:        return shape_boolean(false, a, b);
 
246
        }
 
247
    } else {
 
248
        flags = ~flags & 15;
 
249
        switch(flags) {
 
250
            case BOOLOP_SUBTRACT_A_B: return shape_boolean(false, b, a.inverse());
 
251
            case BOOLOP_SUBTRACT_B_A: return shape_boolean(false, a, b.inverse());
 
252
            case BOOLOP_EXCLUSION: {
 
253
                Shape res = shape_boolean(false, a, b.inverse());
 
254
                append(res.content, shape_boolean(false, b, a.inverse()).content);
 
255
                return res;
 
256
            } //return boolop(a, b, flags, crossings_between(a, b));
 
257
        }
 
258
        return boolop(a, b, flags).inverse();
 
259
    }
 
260
    return Shape();
 
261
}
 
262
 
 
263
int paths_winding(std::vector<Path> const &ps, Point p) {
 
264
    int ret = 0;
 
265
    for(unsigned i = 0; i < ps.size(); i++)
 
266
        ret += winding(ps[i], p);
 
267
    return ret;
 
268
}
 
269
 
 
270
void add_to_shape(Shape &s, Path const &p, bool fill) {
 
271
    if(fill)
 
272
        s.content.push_back(Region(p).asFill());
 
273
    else
 
274
        s.content.push_back(Region(p).asHole());
 
275
}
 
276
 
 
277
int inner_winding(Path const & p, std::vector<Path> const &ps) {
 
278
    Point pnt = p.initialPoint();
 
279
    return paths_winding(ps, pnt) - winding(p, pnt) + 1;
 
280
}
 
281
 
 
282
double fudgerize(double d, bool rev) {
 
283
    double ret = rev ? d - 0.01 : d + 0.01;
 
284
    if(ret < 0) ret = 0;
 
285
    return ret;
 
286
}
 
287
 
 
288
unsigned pick_coincident(unsigned ix, unsigned jx, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
 
289
    unsigned ex_jx = jx;
 
290
    unsigned oix = crs[ix][jx].getOther(ix);
 
291
    double otime = crs[ix][jx].getTime(oix);
 
292
    Point cross_point = ps[oix].pointAt(otime),
 
293
          along = ps[oix].pointAt(fudgerize(otime, rev)) - cross_point,
 
294
          prev = -along;
 
295
    bool ex_dir = rev;
 
296
    for(unsigned k = jx; k < crs[ix].size(); k++) {
 
297
        unsigned koix = crs[ix][k].getOther(ix);
 
298
        if(koix == oix) {
 
299
            if(!are_near(otime, crs[ix][k].getTime(oix))) break;
 
300
            for(unsigned dir = 0; dir < 2; dir++) {
 
301
                Point val = ps[ix].pointAt(fudgerize(crs[ix][k].getTime(ix), dir)) - cross_point;
 
302
                Cmp to_prev = cmp(cross(val, prev), 0);
 
303
                Cmp from_along = cmp(cross(along, val), 0);
 
304
                Cmp c = cmp(from_along, to_prev);
 
305
                if(c == EQUAL_TO && from_along == LESS_THAN) {
 
306
                    ex_jx = k;
 
307
                    prev = val;
 
308
                    ex_dir = dir;
 
309
                }
 
310
            }
 
311
        }
 
312
    }
 
313
    rev = ex_dir;
 
314
    return ex_jx;
 
315
}
 
316
 
 
317
unsigned crossing_along(double t, unsigned ix, unsigned jx, bool dir, Crossings const & crs) {
 
318
    Crossing cur = Crossing(t, t, ix, ix, false);
 
319
    if(jx < crs.size()) {
 
320
        double ct = crs[jx].getTime(ix);
 
321
        if(t == ct) {
 
322
            cur = crs[jx];
 
323
            if(cur.a == cur.b) {
 
324
                if(jx+1 <= crs.size() && crs[jx+1].getOther(ix) == ix) return jx+1;
 
325
                if(jx > 0 && crs[jx-1].getOther(ix) == ix) return jx-1;
 
326
            }
 
327
        }
 
328
    }
 
329
    if(!dir) {
 
330
        jx = std::upper_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
 
331
    } else {
 
332
        jx = std::lower_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
 
333
        if(jx == 0) jx = crs.size() - 1; else jx--;
 
334
        jx = std::lower_bound(crs.begin(), crs.end(), crs[jx], CrossingOrder(ix)) - crs.begin();
 
335
    }
 
336
    if(jx >= crs.size()) jx = 0;
 
337
    return jx;
 
338
}
 
339
 
 
340
void crossing_dual(unsigned &i, unsigned &j, CrossingSet const & crs) {
 
341
    Crossing cur = crs[i][j];
 
342
    i = cur.getOther(i);
 
343
    std::cout << i << "\n";
 
344
    if(crs[i].empty())
 
345
        j = 0;
 
346
    else
 
347
        j = std::lower_bound(crs[i].begin(), crs[i].end(), cur, CrossingOrder(i)) - crs[i].begin();
 
348
}
 
349
 
 
350
//locate a crossing on the outside, by casting a ray through the middle of the bbox
 
351
void outer_crossing(unsigned &ix, unsigned &jx, bool & dir, std::vector<Path> const & ps, CrossingSet const & crs) {
 
352
    Rect bounds = ps[ix].boundsFast();
 
353
    double ry = bounds[Y].middle();
 
354
    double max_val = bounds.left(), max_t = 0;
 
355
    ix = ps.size();
 
356
    for(unsigned i = 0; i < ps.size(); i++) {
 
357
        if(!crs[i].empty()) {
 
358
            std::vector<double> rts = ps[i].roots(ry, Y);
 
359
            for(unsigned j = 0; j < rts.size(); j++) {
 
360
                double val = ps[i].valueAt(rts[j], X);
 
361
                if(val > max_val) {
 
362
                    ix = i;
 
363
                    max_val = val;
 
364
                    max_t = rts[j];
 
365
                }
 
366
            }
 
367
        }
 
368
    }
 
369
    if(ix != ps.size()) {
 
370
        dir = ps[ix].valueAt(max_t + 0.01, Y) >
 
371
              ps[ix].valueAt(max_t - 0.01, Y);
 
372
        jx = crossing_along(max_t, ix, jx, dir, crs[ix]);
 
373
    }
 
374
}
 
375
 
 
376
std::vector<Path> inner_sanitize(std::vector<Path> const & ps) {
 
377
    CrossingSet crs(crossings_among(ps));
 
378
    
 
379
    Regions chunks;
 
380
    
 
381
    std::vector<bool> used_path(ps.size(), false);
 
382
    std::vector<std::vector<bool> > visited;
 
383
    for(unsigned i = 0; i < crs.size(); i++)
 
384
        visited.push_back(std::vector<bool>(crs[i].size(), false));
 
385
    
 
386
    std::vector<Path> result_paths;
 
387
    
 
388
    while(true) {
 
389
        unsigned ix = 0, jx = 0;
 
390
        bool dir = false;
 
391
 
 
392
        //find an outer crossing by trying various paths and checking if the crossings are used
 
393
        for(; ix < crs.size(); ix++) {
 
394
            //TODO: optimize so it doesn't unecessarily check stuff
 
395
            bool cont = true;
 
396
            for(unsigned j = 0; j < crs[ix].size(); j++) {
 
397
                if(!visited[ix][j]) { cont = false; break; }
 
398
            }
 
399
            if(cont) continue;
 
400
            unsigned rix = ix, rjx = jx;
 
401
            outer_crossing(rix, rjx, dir, ps, crs);
 
402
            if(rix >= crs.size() || visited[rix][rjx]) continue;
 
403
            ix = rix; jx = rjx;
 
404
            break;
 
405
        }
 
406
        if(ix == crs.size()) break;
 
407
        crossing_dual(ix, jx, crs);
 
408
 
 
409
        dir = !dir;
 
410
 
 
411
        Path res;
 
412
        do {
 
413
            visited[ix][jx] = true;
 
414
            //unsigned nix = ix, njx = jx;
 
415
            //crossing_dual(nix, njx, crs);
 
416
            //visited[nix][njx] = true;
 
417
            unsigned fix = ix, fjx = jx;
 
418
            
 
419
            bool new_dir = dir;
 
420
            
 
421
            jx = crossing_along(crs[ix][jx].getTime(ix), ix, jx, dir, crs[ix]);
 
422
            if(crs[ix][jx].a != crs[ix][jx].b) crossing_dual(ix, jx, crs); else new_dir = !new_dir;
 
423
            jx = pick_coincident(ix, jx, new_dir, ps, crs);
 
424
            
 
425
            //unsigned nix = ix, njx = jx;
 
426
            //crossing_dual(nix, njx, crs);
 
427
            
 
428
            Crossing from = crs[fix][fjx],
 
429
                     to = crs[ix][jx];
 
430
            if(dir) {
 
431
                // backwards
 
432
                std::cout << "r" << ix << "[" << from.getTime(ix)  << ", " << to.getTime(ix) << "]\n";
 
433
                Path p = ps[ix].portion(from.getTime(ix), to.getTime(ix)).reverse();
 
434
                for(unsigned i = 0; i < p.size(); i++)
 
435
                    res.append(p[i]);
 
436
            } else {
 
437
                // forwards
 
438
                std::cout << "f" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n";
 
439
                ps[ix].appendPortionTo(res, from.getTime(ix), to.getTime(ix));
 
440
            }
 
441
            dir = new_dir;
 
442
        } while(!visited[ix][jx]);
 
443
        std::cout << "added " << res.size() << "\n";
 
444
        result_paths.push_back(res);
 
445
    }
 
446
    for(unsigned i = 0; i < crs.size(); i++) {
 
447
        if(crs[i].empty() && !used_path[i])
 
448
            result_paths.push_back(ps[i]);
 
449
    }
 
450
    return result_paths;
 
451
}
 
452
 
 
453
Shape sanitize(std::vector<Path> const & ps) {
 
454
    std::vector<Path> res;
 
455
    for(unsigned i = 0; i < ps.size(); i++) {
 
456
        append(res, inner_sanitize(std::vector<Path>(1, ps[i])));
 
457
    }
 
458
    return stopgap_cleaner(res);
 
459
}
 
460
 
 
461
/*  WIP sanitizer:
 
462
unsigned pick_coincident(unsigned ix, unsigned jx, bool pref, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
 
463
    unsigned ex_jx = jx;
 
464
    unsigned oix = crs[ix][jx].getOther(ix);
 
465
    double otime = crs[ix][jx].getTime(oix);
 
466
    Point cross_point = ps[oix].pointAt(otime),
 
467
          along = ps[oix].pointAt(otime + (rev ? -0.01 : 0.01)) - cross_point,
 
468
          prev = -along;
 
469
    bool ex_dir = rev;
 
470
    for(unsigned k = jx; k < crs[ix].size(); k++) {
 
471
        unsigned koix = crs[ix][k].getOther(ix);
 
472
        if(koix == oix) {
 
473
            if(!are_near(otime, crs[ix][k].getTime(oix))) break;
 
474
            for(unsigned dir = 0; dir < 2; dir++) {
 
475
                Point val = ps[ix].pointAt(crs[ix][k].getTime(ix) + (dir ? -0.01 : 0.01)) - cross_point;
 
476
                Cmp to_prev = cmp(cross(val, prev), 0);
 
477
                Cmp from_along = cmp(cross(along, val), 0);
 
478
                Cmp c = cmp(from_along, to_prev);
 
479
                if(c == EQUAL_TO && (from_along == LESS_THAN) == pref) {
 
480
                    ex_jx = k;
 
481
                    prev = val;
 
482
                    ex_dir = dir;
 
483
                }
 
484
            }
 
485
        }
 
486
    }
 
487
    rev = ex_dir;
 
488
    return ex_jx;
 
489
}
 
490
 
 
491
unsigned corner_index(unsigned &i) {
 
492
    div_t div_res = div(i, 4);
 
493
    i = div_res.quot;
 
494
    return div_res.rem;
 
495
}
 
496
 
 
497
bool corner_direction(unsigned ix, unsigned jc, unsigned corner, CrossingSet const &crs) {
 
498
    if(crs[ix][jc].a == ix) return corner > 1; else return corner %2 == 1;
 
499
}
 
500
 
 
501
Shape sanitize(std::vector<Path> const & ps) {
 
502
    CrossingSet crs = crossings_among(ps);
 
503
    
 
504
    //Keep track of which CORNERS we've hit.
 
505
    // FF FR RF RR, first is A dir, second B dir
 
506
    std::vector<std::vector<bool> > visited;
 
507
    for(unsigned i = 0; i < crs.size(); i++)
 
508
        visited.push_back(std::vector<bool>(crs[i].size()*4, false));
 
509
    
 
510
    Regions chunks;
 
511
    while(true) {
 
512
        unsigned i, j;
 
513
        first_false(visited, i, j);
 
514
        unsigned corner = corner_index(j);
 
515
        
 
516
        if(i == visited.size()) break;
 
517
        
 
518
        bool dir = corner_direction(i, j, corner, crs);
 
519
        
 
520
        //Figure out whether we hug the path cw or ccw, based on the orientation of the initial corner:        
 
521
        unsigned oix = crs[i][j].getOther(i);
 
522
        double otime = crs[i][j].getTime(oix);
 
523
        bool odir = (oix == crs[i][j].a) ? corner > 1 : corner % 2 == 1;
 
524
        Point cross_point = ps[oix].pointAt(otime),
 
525
              along = ps[oix].pointAt(otime + (odir ? -0.01 : 0.01)) - cross_point,
 
526
                val = ps[i].pointAt(crs[i][j].getTime(i) + (dir ? -0.01 : 0.01)) - cross_point;
 
527
        
 
528
        Cmp from_along = cmp(cross(along, val), 0);
 
529
        bool cw = from_along == LESS_THAN;
 
530
        std::cout << "cw = " << cw << "\n";
 
531
        Path res;
 
532
        do {
 
533
            Crossing cur = crs[i][j];
 
534
            visited[i][j*4+corner] = true;
 
535
            
 
536
            unsigned fix = i, fjx = j;
 
537
            crossing_dual(i, j, crs);
 
538
            visited[i][j*4+corner] = true;
 
539
            i = fix; j = fjx;
 
540
            
 
541
            j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]);
 
542
            
 
543
            crossing_dual(i, j, crs);
 
544
            
 
545
            bool new_dir = dir;
 
546
            pick_coincident(i, j, cw, new_dir, ps, crs);
 
547
            
 
548
            Crossing from = crs[fix][fjx],
 
549
                     to = crs[i][j];
 
550
            if(dir) {
 
551
                // backwards
 
552
                std::cout << "r" << i << "[" << to.getTime(i)  << ", " << from.getTime(i) << "]\n";
 
553
                Path p = ps[i].portion(to.getTime(i) + 0.001, from.getTime(i)).reverse();
 
554
                for(unsigned k = 0; k < p.size(); k++)
 
555
                    res.append(p[k]);
 
556
            } else {
 
557
                // forwards
 
558
                std::cout << "f" << i << "[" << from.getTime(i) << ", " << to.getTime(i) << "]\n";
 
559
                ps[i].appendPortionTo(res, from.getTime(i) + 0.001, to.getTime(i));
 
560
            }
 
561
            if(i == to.a)
 
562
                corner = (new_dir ? 2 : 0) + (dir ? 1 : 0);
 
563
            else
 
564
                corner = (new_dir ? 1 : 0) + (dir ? 2 : 0);
 
565
            dir = new_dir;
 
566
        } while(!visited[i][j*4+corner]);
 
567
        chunks.push_back(Region(res));
 
568
//        if(use) {
 
569
//            chunks.push_back(Region(res, true));
 
570
//        }
 
571
    }
 
572
    return Shape(chunks);
 
573
//    return ret;
 
574
} */
 
575
 
 
576
/* This transforms a shape by a matrix.  In the case that the matrix flips
 
577
 * the shape, it reverses the paths in order to preserve the fill.
 
578
 */
 
579
Shape Shape::operator*(Matrix const &m) const {
 
580
    Shape ret;
 
581
    for(unsigned i = 0; i < size(); i++)
 
582
        ret.content.push_back(content[i] * m);
 
583
    ret.fill = fill;
 
584
    return ret;
 
585
}
 
586
 
 
587
// Inverse is a boolean not, and simply reverses all the paths & fill flags
 
588
Shape Shape::inverse() const {
 
589
    Shape ret;
 
590
    for(unsigned i = 0; i < size(); i++)
 
591
        ret.content.push_back(content[i].inverse());
 
592
    ret.fill = !fill;
 
593
    return ret;
 
594
}
 
595
 
 
596
bool Shape::contains(Point const &p) const {
 
597
    std::vector<unsigned> containers = containment_list(p);
 
598
    if(containers.empty()) return !isFill();
 
599
    unsigned ix = *min_element(containers.begin(), containers.end(), ContainmentOrder(&content));
 
600
    return content[ix].isFill();
 
601
}
 
602
 
 
603
Shape stopgap_cleaner(std::vector<Path> const &ps) {
 
604
    if(ps.empty()) return Shape(false);
 
605
    Shape ret;
 
606
    for(unsigned i = 0; i < ps.size(); i++)
 
607
        add_to_shape(ret, ps[i], inner_winding(ps[i], ps) % 2 != 0);
 
608
    return ret;
 
609
}
 
610
 
 
611
bool Shape::inside_invariants() const {  //semi-slow & easy to violate
 
612
    for(unsigned i = 0; i < size(); i++)
 
613
        if( logical_xor(content[i].isFill(), contains(content[i].boundary.initialPoint())) ) return false;
 
614
    return true;
 
615
}
 
616
bool Shape::region_invariants() const { //semi-slow
 
617
    for(unsigned i = 0; i < size(); i++)
 
618
        if(!content[i].invariants()) return false;
 
619
    return true;
 
620
}
 
621
bool Shape::cross_invariants() const { //slow
 
622
    CrossingSet crs; // = crossings_among(paths_from_regions(content));
 
623
    for(unsigned i = 0; i < crs.size(); i++)
 
624
        if(!crs[i].empty()) return false;
 
625
    return true;
 
626
}
 
627
 
 
628
bool Shape::invariants() const {
 
629
    return inside_invariants() && region_invariants() && cross_invariants();
 
630
}
 
631
 
 
632
}