1 /*
2 * Digraph.h
3 * nlivarot
4 *
5 * Created by fred on Thu Jun 12 2003.
6 *
7 */
9 #ifndef my_shape
10 #define my_shape
12 #include <cmath>
13 #include <cstdio>
14 #include <cstdlib>
15 #include <cstring>
16 #include <vector>
18 #include "libnr/nr-point.h"
19 #include "livarot/livarot-forward.h"
20 #include "livarot/LivarotDefs.h"
22 struct SweepTree;
23 struct SweepTreeList;
24 struct SweepEventQueue;
26 enum {
27 tweak_mode_grow,
28 tweak_mode_push,
29 tweak_mode_repel,
30 tweak_mode_roughen
31 };
33 /*
34 * the Shape class (was the Digraph class, as the header says) stores digraphs (no kidding!) of which
35 * a very interesting kind are polygons.
36 * the main use of this class is the ConvertToShape() (or Booleen(), quite the same) function, which
37 * removes all problems a polygon can present: duplicate points or edges, self-intersection. you end up with a
38 * full-fledged polygon
39 */
41 // possible values for the "type" field in the Shape class:
42 enum
43 {
44 shape_graph = 0, // it's just a graph; a bunch of edges, maybe intersections
45 shape_polygon = 1, // a polygon: intersection-free, edges oriented so that the inside is on their left
46 shape_polypatch = 2 // a graph without intersection; each face is a polygon (not yet used)
47 };
49 class IntLigne;
50 class BitLigne;
51 class AlphaLigne;
53 class Shape
54 {
55 public:
57 struct back_data
58 {
59 int pathID, pieceID;
60 double tSt, tEn;
61 };
63 struct voronoi_point
64 { // info for points treated as points of a voronoi diagram (obtained by MakeShape())
65 double value; // distance to source
66 int winding; // winding relatively to source
67 };
69 struct voronoi_edge
70 { // info for edges, treated as approximation of edges of the voronoi diagram
71 int leF, riF; // left and right site
72 double leStX, leStY, riStX, riStY; // on the left side: (leStX,leStY) is the smallest vector from the source to st
73 // etc...
74 double leEnX, leEnY, riEnX, riEnY;
75 };
77 struct quick_raster_data
78 {
79 double x; // x-position on the sweepline
80 int bord; // index of the edge
81 int ind; // index of qrsData elem for edge (ie inverse of the bord)
82 int next,prev; // dbl linkage
83 };
85 enum sTreeChangeType
86 {
87 EDGE_INSERTED = 0,
88 EDGE_REMOVED = 1,
89 INTERSECTION = 2
90 };
92 struct sTreeChange
93 {
94 sTreeChangeType type; // type of modification to the sweepline:
95 int ptNo; // point at which the modification takes place
97 Shape *src; // left edge (or unique edge if not an intersection) involved in the event
98 int bord;
99 Shape *osrc; // right edge (if intersection)
100 int obord;
101 Shape *lSrc; // edge directly on the left in the sweepline at the moment of the event
102 int lBrd;
103 Shape *rSrc; // edge directly on the right
104 int rBrd;
105 };
107 struct incidenceData
108 {
109 int nextInc; // next incidence in the linked list
110 int pt; // point incident to the edge (there is one list per edge)
111 double theta; // coordinate of the incidence on the edge
112 };
114 Shape();
115 virtual ~Shape();
117 void MakeBackData(bool nVal);
118 void MakeVoronoiData(bool nVal);
120 void Affiche();
122 // insertion/deletion/movement of elements in the graph
123 void Copy(Shape *a);
124 // -reset the graph, and ensure there's room for n points and m edges
125 void Reset(int n = 0, int m = 0);
126 // -points:
127 int AddPoint(const Geom::Point x); // as the function name says
128 // returns the index at which the point has been added in the array
129 void SubPoint(int p); // removes the point at index p
130 // nota: this function relocates the last point to the index p
131 // so don't trust point indices if you use SubPoint
132 void SwapPoints(int a, int b); // swaps 2 points at indices a and b
133 void SwapPoints(int a, int b, int c); // swaps 3 points: c <- a <- b <- c
134 void SortPoints(); // sorts the points if needed (checks the need_points_sorting flag)
136 // -edges:
137 // add an edge between points of indices st and en
138 int AddEdge(int st, int en);
139 // return the edge index in the array
141 // add an edge between points of indices st and en
142 int AddEdge(int st, int en, int leF, int riF);
143 // return the edge index in the array
145 // version for the voronoi (with faces IDs)
146 void SubEdge(int e); // removes the edge at index e (same remarks as for SubPoint)
147 void SwapEdges(int a, int b); // swaps 2 edges
148 void SwapEdges(int a, int b, int c); // swaps 3 edges
149 void SortEdges(); // sort the edges if needed (checks the need_edges_sorting falg)
151 // primitives for topological manipulations
153 // endpoint of edge at index b that is different from the point p
154 inline int Other(int p, int b) const
155 {
156 if (getEdge(b).st == p) {
157 return getEdge(b).en;
158 }
159 return getEdge(b).st;
160 }
162 // next edge (after edge b) in the double-linked list at point p
163 inline int NextAt(int p, int b) const
164 {
165 if (p == getEdge(b).st) {
166 return getEdge(b).nextS;
167 }
168 else if (p == getEdge(b).en) {
169 return getEdge(b).nextE;
170 }
172 return -1;
173 }
175 // previous edge
176 inline int PrevAt(int p, int b) const
177 {
178 if (p == getEdge(b).st) {
179 return getEdge(b).prevS;
180 }
181 else if (p == getEdge(b).en) {
182 return getEdge(b).prevE;
183 }
185 return -1;
186 }
188 // same as NextAt, but the list is considered circular
189 inline int CycleNextAt(int p, int b) const
190 {
191 if (p == getEdge(b).st) {
192 if (getEdge(b).nextS < 0) {
193 return getPoint(p).incidentEdge[FIRST];
194 }
195 return getEdge(b).nextS;
196 } else if (p == getEdge(b).en) {
197 if (getEdge(b).nextE < 0) {
198 return getPoint(p).incidentEdge[FIRST];
199 }
201 return getEdge(b).nextE;
202 }
204 return -1;
205 }
207 // same as PrevAt, but the list is considered circular
208 inline int CyclePrevAt(int p, int b) const
209 {
210 if (p == getEdge(b).st) {
211 if (getEdge(b).prevS < 0) {
212 return getPoint(p).incidentEdge[LAST];
213 }
214 return getEdge(b).prevS;
215 } else if (p == getEdge(b).en) {
216 if (getEdge(b).prevE < 0) {
217 return getPoint(p).incidentEdge[LAST];
218 }
219 return getEdge(b).prevE;
220 }
222 return -1;
223 }
225 void ConnectStart(int p, int b); // set the point p as the start of edge b
226 void ConnectEnd(int p, int b); // set the point p as the end of edge b
227 void DisconnectStart(int b); // disconnect edge b from its start point
228 void DisconnectEnd(int b); // disconnect edge b from its end point
230 // reverses edge b (start <-> end)
231 void Inverse(int b);
232 // calc bounding box and sets leftX,rightX,topY and bottomY to their values
233 void CalcBBox(bool strict_degree = false);
235 // debug function: plots the graph (mac only)
236 void Plot(double ix, double iy, double ir, double mx, double my, bool doPoint,
237 bool edgesNo, bool pointNo, bool doDir, char *fileName);
239 // transforms a polygon in a "forme" structure, ie a set of contours, which can be holes (see ShapeUtils.h)
240 // return NULL in case it's not possible
241 void ConvertToForme(Path *dest);
243 // version to use when conversion was done with ConvertWithBackData(): will attempt to merge segment belonging to
244 // the same curve
245 // nota: apparently the function doesn't like very small segments of arc
246 void ConvertToForme(Path *dest, int nbP, Path **orig, bool splitWhenForced = false);
247 // version trying to recover the nesting of subpaths (ie: holes)
248 void ConvertToFormeNested(Path *dest, int nbP, Path **orig, int wildPath, int &nbNest,
249 int *&nesting, int *&contStart, bool splitWhenForced = false);
251 // sweeping a digraph to produce a intersection-free polygon
252 // return 0 if everything is ok and a return code otherwise (see LivarotDefs.h)
253 // the input is the Shape "a"
254 // directed=true <=> non-zero fill rule
255 int ConvertToShape(Shape *a, FillRule directed = fill_nonZero, bool invert = false);
256 // directed=false <=> even-odd fill rule
257 // invert=true: make as if you inverted all edges in the source
258 int Reoriente(Shape *a); // subcase of ConvertToShape: the input a is already intersection-free
259 // all that's missing are the correct directions of the edges
260 // Reoriented is equivalent to ConvertToShape(a,false,false) , but faster sicne
261 // it doesn't computes interections nor adjacencies
262 void ForceToPolygon(); // force the Shape to believe it's a polygon (eulerian+intersection-free+no
263 // duplicate edges+no duplicate points)
264 // be careful when using this function
266 // the coordinate rounding function
267 inline static double Round(double x)
268 {
269 return ldexp(rint(ldexp(x, 5)), -5);
270 }
272 // 2 miscannellous variations on it, to scale to and back the rounding grid
273 inline static double HalfRound(double x)
274 {
275 return ldexp(x, -5);
276 }
278 inline static double IHalfRound(double x)
279 {
280 return ldexp(x, 5);
281 }
283 // boolean operations on polygons (requests intersection-free poylygons)
284 // boolean operation types are defined in LivarotDefs.h
285 // same return code as ConvertToShape
286 int Booleen(Shape *a, Shape *b, BooleanOp mod, int cutPathID = -1);
288 // create a graph that is an offseted version of the graph "of"
289 // the offset is dec, with joins between edges of type "join" (see LivarotDefs.h)
290 // the result is NOT a polygon; you need a subsequent call to ConvertToShape to get a real polygon
291 int MakeOffset(Shape *of, double dec, JoinType join, double miter, bool do_profile=false, double cx = 0, double cy = 0, double radius = 0, Geom::Matrix *i2doc = NULL);
293 int MakeTweak (int mode, Shape *a, double dec, JoinType join, double miter, bool do_profile, Geom::Point c, Geom::Point vector, double radius, Geom::Matrix *i2doc);
295 int PtWinding(const Geom::Point px) const; // plus rapide
296 int Winding(const Geom::Point px) const;
298 // rasterization
299 void BeginRaster(float &pos, int &curPt);
300 void EndRaster();
301 void BeginQuickRaster(float &pos, int &curPt);
302 void EndQuickRaster();
304 void Scan(float &pos, int &curP, float to, float step);
305 void QuickScan(float &pos, int &curP, float to, bool doSort, float step);
306 void DirectScan(float &pos, int &curP, float to, float step);
307 void DirectQuickScan(float &pos, int &curP, float to, bool doSort, float step);
309 void Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step);
310 void Scan(float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step);
311 void Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step);
313 void QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step);
314 void QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step);
315 void QuickScan(float &pos, int &curP, float to, AlphaLigne* line, float step);
317 void Transform(Geom::Matrix const &tr)
318 {for(std::vector<dg_point>::iterator it=_pts.begin();it!=_pts.end();it++) it->x*=tr;}
320 std::vector<back_data> ebData;
321 std::vector<voronoi_point> vorpData;
322 std::vector<voronoi_edge> voreData;
324 int nbQRas;
325 int firstQRas;
326 int lastQRas;
327 quick_raster_data *qrsData;
329 std::vector<sTreeChange> chgts;
330 int nbInc;
331 int maxInc;
333 incidenceData *iData;
334 // these ones are allocated at the beginning of each sweep and freed at the end of the sweep
335 SweepTreeList *sTree;
336 SweepEventQueue *sEvts;
338 // bounding box stuff
339 double leftX, topY, rightX, bottomY;
341 // topological information: who links who?
342 struct dg_point
343 {
344 Geom::Point x; // position
345 int dI, dO; // indegree and outdegree
346 int incidentEdge[2]; // first and last incident edge
347 int oldDegree;
349 int totalDegree() const { return dI + dO; }
350 };
352 struct dg_arete
353 {
354 Geom::Point dx; // edge vector
355 int st, en; // start and end points of the edge
356 int nextS, prevS; // next and previous edge in the double-linked list at the start point
357 int nextE, prevE; // next and previous edge in the double-linked list at the end point
358 };
360 // lists of the nodes and edges
361 int maxPt; // [FIXME: remove this]
362 int maxAr; // [FIXME: remove this]
364 // flags
365 int type;
367 inline int numberOfPoints() const { return _pts.size(); }
368 inline bool hasPoints() const { return (_pts.empty() == false); }
369 inline int numberOfEdges() const { return _aretes.size(); }
370 inline bool hasEdges() const { return (_aretes.empty() == false); }
372 inline void needPointsSorting() { _need_points_sorting = true; }
373 inline void needEdgesSorting() { _need_edges_sorting = true; }
375 inline bool hasBackData() const { return _has_back_data; }
377 inline dg_point const &getPoint(int n) const { return _pts[n]; }
378 inline dg_arete const &getEdge(int n) const { return _aretes[n]; }
380 private:
382 friend class SweepTree;
383 friend class SweepEvent;
384 friend class SweepEventQueue;
386 // temporary data for the various algorithms
387 struct edge_data
388 {
389 int weight; // weight of the edge (to handle multiple edges)
390 Geom::Point rdx; // rounded edge vector
391 double length, sqlength, ilength, isqlength; // length^2, length, 1/length^2, 1/length
392 double siEd, coEd; // siEd=abs(rdy/length) and coEd=rdx/length
393 edge_data() : weight(0), length(0.0), sqlength(0.0), ilength(0.0), isqlength(0.0), siEd(0.0), coEd(0.0) {}
394 // used to determine the "most horizontal" edge between 2 edges
395 };
397 struct sweep_src_data
398 {
399 void *misc; // pointer to the SweepTree* in the sweepline
400 int firstLinkedPoint; // not used
401 int stPt, enPt; // start- end end- points for this edge in the resulting polygon
402 int ind; // for the GetAdjacencies function: index in the sliceSegs array (for quick deletions)
403 int leftRnd, rightRnd; // leftmost and rightmost points (in the result polygon) that are incident to
404 // the edge, for the current sweep position
405 // not set if the edge doesn't start/end or intersect at the current sweep position
406 Shape *nextSh; // nextSh and nextBo identify the next edge in the list
407 int nextBo; // they are used to maintain a linked list of edge that start/end or intersect at
408 // the current sweep position
409 int curPoint, doneTo;
410 double curT;
411 };
413 struct sweep_dest_data
414 {
415 void *misc; // used to check if an edge has already been seen during the depth-first search
416 int suivParc, precParc; // previous and current next edge in the depth-first search
417 int leW, riW; // left and right winding numbers for this edge
418 int ind; // order of the edges during the depth-first search
419 };
421 struct raster_data
422 {
423 SweepTree *misc; // pointer to the associated SweepTree* in the sweepline
424 double lastX, lastY, curX, curY; // curX;curY is the current intersection of the edge with the sweepline
425 // lastX;lastY is the intersection with the previous sweepline
426 bool sens; // true if the edge goes down, false otherwise
427 double calcX; // horizontal position of the intersection of the edge with the
428 // previous sweepline
429 double dxdy, dydx; // horizontal change per unit vertical move of the intersection with the sweepline
430 int guess;
431 };
433 struct point_data
434 {
435 int oldInd, newInd; // back and forth indices used when sorting the points, to know where they have
436 // been relocated in the array
437 int pending; // number of intersection attached to this edge, and also used when sorting arrays
438 int edgeOnLeft; // not used (should help speeding up winding calculations)
439 int nextLinkedPoint; // not used
440 Shape *askForWindingS;
441 int askForWindingB;
442 Geom::Point rx; // rounded coordinates of the point
443 };
446 struct edge_list
447 { // temporary array of edges for easier sorting
448 int no;
449 bool starting;
450 Geom::Point x;
451 };
453 void initialisePointData();
454 void initialiseEdgeData();
455 void clearIncidenceData();
457 void _countUpDown(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const;
458 void _countUpDownTotalDegree2(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const;
459 void _updateIntersection(int e, int p);
461 // activation/deactivation of the temporary data arrays
462 void MakePointData(bool nVal);
463 void MakeEdgeData(bool nVal);
464 void MakeSweepSrcData(bool nVal);
465 void MakeSweepDestData(bool nVal);
466 void MakeRasterData(bool nVal);
467 void MakeQuickRasterData(bool nVal);
469 void SortPoints(int s, int e);
470 void SortPointsByOldInd(int s, int e);
472 // fonctions annexes pour ConvertToShape et Booleen
473 void ResetSweep(); // allocates sweep structures
474 void CleanupSweep(); // deallocates them
476 // edge sorting function
477 void SortEdgesList(edge_list *edges, int s, int e);
479 void TesteIntersection(SweepTree *t, Side s, bool onlyDiff); // test if there is an intersection
480 bool TesteIntersection(SweepTree *iL, SweepTree *iR, Geom::Point &atx, double &atL, double &atR, bool onlyDiff);
481 bool TesteIntersection(Shape *iL, Shape *iR, int ilb, int irb,
482 Geom::Point &atx, double &atL, double &atR,
483 bool onlyDiff);
484 bool TesteAdjacency(Shape *iL, int ilb, const Geom::Point atx, int nPt,
485 bool push);
486 int PushIncidence(Shape *a, int cb, int pt, double theta);
487 int CreateIncidence(Shape *a, int cb, int pt);
488 void AssemblePoints(Shape *a);
489 int AssemblePoints(int st, int en);
490 void AssembleAretes(FillRule directed = fill_nonZero);
491 void AddChgt(int lastPointNo, int lastChgtPt, Shape *&shapeHead,
492 int &edgeHead, sTreeChangeType type, Shape *lS, int lB, Shape *rS,
493 int rB);
494 void CheckAdjacencies(int lastPointNo, int lastChgtPt, Shape *shapeHead, int edgeHead);
495 void CheckEdges(int lastPointNo, int lastChgtPt, Shape *a, Shape *b, BooleanOp mod);
496 void Avance(int lastPointNo, int lastChgtPt, Shape *iS, int iB, Shape *a, Shape *b, BooleanOp mod);
497 void DoEdgeTo(Shape *iS, int iB, int iTo, bool direct, bool sens);
498 void GetWindings(Shape *a, Shape *b = NULL, BooleanOp mod = bool_op_union, bool brutal = false);
500 void Validate();
502 int Winding(int nPt) const;
503 void SortPointsRounded();
504 void SortPointsRounded(int s, int e);
506 void CreateEdge(int no, float to, float step);
507 void AvanceEdge(int no, float to, bool exact, float step);
508 void DestroyEdge(int no, float to, FloatLigne *line);
509 void AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step);
510 void DestroyEdge(int no, BitLigne *line);
511 void AvanceEdge(int no, float to, BitLigne *line, bool exact, float step);
512 void DestroyEdge(int no, AlphaLigne *line);
513 void AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step);
515 void AddContour(Path * dest, int nbP, Path **orig, int startBord,
516 int curBord, bool splitWhenForced);
517 int ReFormeLineTo(int bord, int curBord, Path *dest, Path *orig);
518 int ReFormeArcTo(int bord, int curBord, Path *dest, Path *orig);
519 int ReFormeCubicTo(int bord, int curBord, Path *dest, Path *orig);
520 int ReFormeBezierTo(int bord, int curBord, Path *dest, Path *orig);
521 void ReFormeBezierChunk(const Geom::Point px, const Geom::Point nx,
522 Path *dest, int inBezier, int nbInterm,
523 Path *from, int p, double ts, double te);
525 int QuickRasterChgEdge(int oBord, int nbord, double x);
526 int QuickRasterAddEdge(int bord, double x, int guess);
527 void QuickRasterSubEdge(int bord);
528 void QuickRasterSwapEdge(int a, int b);
529 void QuickRasterSort();
531 bool _need_points_sorting; ///< points have been added or removed: we need to sort the points again
532 bool _need_edges_sorting; ///< edges have been added: maybe they are not ordered clockwise
533 ///< nota: if you remove an edge, the clockwise order still holds
534 bool _has_points_data; ///< the pData array is allocated
535 bool _point_data_initialised;///< the pData array is up to date
536 bool _has_edges_data; ///< the eData array is allocated
537 bool _has_sweep_src_data; ///< the swsData array is allocated
538 bool _has_sweep_dest_data; ///< the swdData array is allocated
539 bool _has_raster_data; ///< the swrData array is allocated
540 bool _has_quick_raster_data;///< the swrData array is allocated
541 bool _has_back_data; //< the ebData array is allocated
542 bool _has_voronoi_data;
543 bool _bbox_up_to_date; ///< the leftX/rightX/topY/bottomY are up to date
545 std::vector<dg_point> _pts;
546 std::vector<dg_arete> _aretes;
548 // the arrays of temporary data
549 // these ones are dynamically kept at a length of maxPt or maxAr
550 std::vector<edge_data> eData;
551 std::vector<sweep_src_data> swsData;
552 std::vector<sweep_dest_data> swdData;
553 std::vector<raster_data> swrData;
554 std::vector<point_data> pData;
556 static int CmpQRs(const quick_raster_data &p1, const quick_raster_data &p2) {
557 if ( fabs(p1.x - p2.x) < 0.00001 ) {
558 return 0;
559 }
561 return ( ( p1.x < p2.x ) ? -1 : 1 );
562 };
564 // edge direction comparison function
565 static int CmpToVert(const Geom::Point ax, const Geom::Point bx, bool as, bool bs);
566 };
568 bool directedEulerian(Shape const *s);
569 double distance(Shape const *s, Geom::Point const &p);
570 bool distanceLessThanOrEqual(Shape const *s, Geom::Point const &p, double const max_l2);
572 #endif