diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
commit | 35a96bde514a8897f6f0fcc41c5833bf63df2e2a (patch) | |
tree | 657d15a03cc46bd099fc2c6546a7a4ad43815d9f /src/livarot/ShapeMisc.cpp | |
parent | Initial commit. (diff) | |
download | inkscape-35a96bde514a8897f6f0fcc41c5833bf63df2e2a.tar.xz inkscape-35a96bde514a8897f6f0fcc41c5833bf63df2e2a.zip |
Adding upstream version 1.0.2.upstream/1.0.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/livarot/ShapeMisc.cpp')
-rw-r--r-- | src/livarot/ShapeMisc.cpp | 1457 |
1 files changed, 1457 insertions, 0 deletions
diff --git a/src/livarot/ShapeMisc.cpp b/src/livarot/ShapeMisc.cpp new file mode 100644 index 0000000..b76ea58 --- /dev/null +++ b/src/livarot/ShapeMisc.cpp @@ -0,0 +1,1457 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** @file + * TODO: insert short description here + *//* + * Authors: + * see git history + * Fred + * + * Copyright (C) 2018 Authors + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#include "livarot/Shape.h" +#include "livarot/Path.h" +#include "livarot/path-description.h" +#include <glib.h> +#include <cstdio> +#include <cstdlib> +#include <cstring> +#include <2geom/point.h> +#include <2geom/affine.h> + +/* + * polygon offset and polyline to path reassembling (when using back data) + */ + +// until i find something better +#define MiscNormalize(v) {\ + double _l=sqrt(dot(v,v)); \ + if ( _l < 0.0000001 ) { \ + v[0]=v[1]=0; \ + } else { \ + v/=_l; \ + }\ +} + +// extracting the contour of an uncrossed polygon: a mere depth first search +// more precisely that's extracting an eulerian path from a graph, but here we want to split +// the polygon into contours and avoid holes. so we take a "next counter-clockwise edge first" approach +// (make a checkboard and extract its contours to see the difference) +void +Shape::ConvertToForme (Path * dest) +{ + if (numberOfPoints() <= 1 || numberOfEdges() <= 1) + return; + + // prepare + dest->Reset (); + + MakePointData (true); + MakeEdgeData (true); + MakeSweepDestData (true); + + for (int i = 0; i < numberOfPoints(); i++) + { + pData[i].rx[0] = Round (getPoint(i).x[0]); + pData[i].rx[1] = Round (getPoint(i).x[1]); + } + for (int i = 0; i < numberOfEdges(); i++) + { + eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx; + } + + // sort edge clockwise, with the closest after midnight being first in the doubly-linked list + // that's vital to the algorithm... + SortEdges (); + + // depth-first search implies: we make a stack of edges traversed. + // precParc: previous in the stack + // suivParc: next in the stack + for (int i = 0; i < numberOfEdges(); i++) + { + swdData[i].misc = nullptr; + swdData[i].precParc = swdData[i].suivParc = -1; + } + + int searchInd = 0; + + int lastPtUsed = 0; + do + { + // first get a starting point, and a starting edge + // -> take the upper left point, and take its first edge + // points traversed have swdData[].misc != 0, so it's easy + int startBord = -1; + { + int fi = 0; + for (fi = lastPtUsed; fi < numberOfPoints(); fi++) + { + if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == nullptr) + break; + } + lastPtUsed = fi + 1; + if (fi < numberOfPoints()) + { + int bestB = getPoint(fi).incidentEdge[FIRST]; + while (bestB >= 0 && getEdge(bestB).st != fi) + bestB = NextAt (fi, bestB); + if (bestB >= 0) + { + startBord = bestB; + dest->MoveTo (getPoint(getEdge(startBord).en).x); + } + } + } + // and walk the graph, doing contours when needed + if (startBord >= 0) + { + // parcours en profondeur pour mettre les leF et riF a leurs valeurs + swdData[startBord].misc = (void *) 1; + // printf("part de %d\n",startBord); + int curBord = startBord; + bool back = false; + swdData[curBord].precParc = -1; + swdData[curBord].suivParc = -1; + do + { + int cPt = getEdge(curBord).en; + int nb = curBord; + // printf("de curBord= %d au point %i -> ",curBord,cPt); + // get next edge + do + { + int nnb = CycleNextAt (cPt, nb); + if (nnb == nb) + { + // cul-de-sac + nb = -1; + break; + } + nb = nnb; + if (nb < 0 || nb == curBord) + break; + } + while (swdData[nb].misc != nullptr || getEdge(nb).st != cPt); + + if (nb < 0 || nb == curBord) + { + // no next edge: end of this contour, we get back + if (back == false) + dest->Close (); + back = true; + // retour en arriere + curBord = swdData[curBord].precParc; + // printf("retour vers %d\n",curBord); + if (curBord < 0) + break; + } + else + { + // new edge, maybe for a new contour + if (back) + { + // we were backtracking, so if we have a new edge, that means we're creating a new contour + dest->MoveTo (getPoint(cPt).x); + back = false; + } + swdData[nb].misc = (void *) 1; + swdData[nb].ind = searchInd++; + swdData[nb].precParc = curBord; + swdData[curBord].suivParc = nb; + curBord = nb; + // printf("suite %d\n",curBord); + { + // add that edge + dest->LineTo (getPoint(getEdge(nb).en).x); + } + } + } + while (true /*swdData[curBord].precParc >= 0 */ ); + // fin du cas non-oriente + } + } + while (lastPtUsed < numberOfPoints()); + + MakePointData (false); + MakeEdgeData (false); + MakeSweepDestData (false); +} + +// same as before, but each time we have a contour, try to reassemble the segments on it to make chunks of +// the original(s) path(s) +// originals are in the orig array, whose size is nbP +void +Shape::ConvertToForme (Path * dest, int nbP, Path * *orig, bool splitWhenForced) +{ + if (numberOfPoints() <= 1 || numberOfEdges() <= 1) + return; +// if (Eulerian (true) == false) +// return; + + if (_has_back_data == false) + { + ConvertToForme (dest); + return; + } + + dest->Reset (); + + MakePointData (true); + MakeEdgeData (true); + MakeSweepDestData (true); + + for (int i = 0; i < numberOfPoints(); i++) + { + pData[i].rx[0] = Round (getPoint(i).x[0]); + pData[i].rx[1] = Round (getPoint(i).x[1]); + } + for (int i = 0; i < numberOfEdges(); i++) + { + eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx; + } + + SortEdges (); + + for (int i = 0; i < numberOfEdges(); i++) + { + swdData[i].misc = nullptr; + swdData[i].precParc = swdData[i].suivParc = -1; + } + + int searchInd = 0; + + int lastPtUsed = 0; + do + { + int startBord = -1; + { + int fi = 0; + for (fi = lastPtUsed; fi < numberOfPoints(); fi++) + { + if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == nullptr) + break; + } + lastPtUsed = fi + 1; + if (fi < numberOfPoints()) + { + int bestB = getPoint(fi).incidentEdge[FIRST]; + while (bestB >= 0 && getEdge(bestB).st != fi) + bestB = NextAt (fi, bestB); + if (bestB >= 0) + { + startBord = bestB; + } + } + } + if (startBord >= 0) + { + // parcours en profondeur pour mettre les leF et riF a leurs valeurs + swdData[startBord].misc = (void *) 1; + //printf("part de %d\n",startBord); + int curBord = startBord; + bool back = false; + swdData[curBord].precParc = -1; + swdData[curBord].suivParc = -1; + int curStartPt=getEdge(curBord).st; + do + { + int cPt = getEdge(curBord).en; + int nb = curBord; + //printf("de curBord= %d au point %i -> ",curBord,cPt); + do + { + int nnb = CycleNextAt (cPt, nb); + if (nnb == nb) + { + // cul-de-sac + nb = -1; + break; + } + nb = nnb; + if (nb < 0 || nb == curBord) + break; + } + while (swdData[nb].misc != nullptr || getEdge(nb).st != cPt); + + if (nb < 0 || nb == curBord) + { + if (back == false) + { + if (curBord == startBord || curBord < 0) + { + // probleme -> on vire le moveto + // dest->descr_nb--; + } + else + { + swdData[curBord].suivParc = -1; + AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced); + } + // dest->Close(); + } + back = true; + // retour en arriere + curBord = swdData[curBord].precParc; + //printf("retour vers %d\n",curBord); + if (curBord < 0) + break; + } + else + { + if (back) + { + back = false; + startBord = nb; + curStartPt=getEdge(nb).st; + } else { + if ( getEdge(curBord).en == curStartPt ) { + //printf("contour %i ",curStartPt); + swdData[curBord].suivParc = -1; + AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced); + startBord=nb; + } + } + swdData[nb].misc = (void *) 1; + swdData[nb].ind = searchInd++; + swdData[nb].precParc = curBord; + swdData[curBord].suivParc = nb; + curBord = nb; + //printf("suite %d\n",curBord); + } + } + while (true /*swdData[curBord].precParc >= 0 */ ); + // fin du cas non-oriente + } + } + while (lastPtUsed < numberOfPoints()); + + MakePointData (false); + MakeEdgeData (false); + MakeSweepDestData (false); +} +void +Shape::ConvertToFormeNested (Path * dest, int nbP, Path * *orig, int /*wildPath*/,int &nbNest,int *&nesting,int *&contStart,bool splitWhenForced) +{ + nesting=nullptr; + contStart=nullptr; + nbNest=0; + + if (numberOfPoints() <= 1 || numberOfEdges() <= 1) + return; + // if (Eulerian (true) == false) + // return; + + if (_has_back_data == false) + { + ConvertToForme (dest); + return; + } + + dest->Reset (); + +// MakePointData (true); + MakeEdgeData (true); + MakeSweepDestData (true); + + for (int i = 0; i < numberOfPoints(); i++) + { + pData[i].rx[0] = Round (getPoint(i).x[0]); + pData[i].rx[1] = Round (getPoint(i).x[1]); + } + for (int i = 0; i < numberOfEdges(); i++) + { + eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx; + } + + SortEdges (); + + for (int i = 0; i < numberOfEdges(); i++) + { + swdData[i].misc = nullptr; + swdData[i].precParc = swdData[i].suivParc = -1; + } + + int searchInd = 0; + + int lastPtUsed = 0; + int parentContour=-1; + do + { + int childEdge = -1; + bool foundChild = false; + int startBord = -1; + { + int fi = 0; + for (fi = lastPtUsed; fi < numberOfPoints(); fi++) + { + if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == nullptr) + break; + } + { + int askTo = pData[fi].askForWindingB; + if (askTo < 0 || askTo >= numberOfEdges() ) { + parentContour=-1; + } else { + if (getEdge(askTo).prevS >= 0) { + parentContour = GPOINTER_TO_INT(swdData[askTo].misc); + parentContour-=1; // pour compenser le decalage + } + childEdge = getPoint(fi % numberOfPoints()).incidentEdge[FIRST]; + } + } + lastPtUsed = fi + 1; + if (fi < numberOfPoints()) + { + int bestB = getPoint(fi).incidentEdge[FIRST]; + while (bestB >= 0 && getEdge(bestB).st != fi) + bestB = NextAt (fi, bestB); + if (bestB >= 0) + { + startBord = bestB; + } + } + } + if (startBord >= 0) + { + // parcours en profondeur pour mettre les leF et riF a leurs valeurs + swdData[startBord].misc = (void *)(intptr_t)(1 + nbNest); + if (startBord == childEdge) { + foundChild = true; + } + //printf("part de %d\n",startBord); + int curBord = startBord; + bool back = false; + swdData[curBord].precParc = -1; + swdData[curBord].suivParc = -1; + int curStartPt=getEdge(curBord).st; + do + { + int cPt = getEdge(curBord).en; + int nb = curBord; + //printf("de curBord= %d au point %i -> ",curBord,cPt); + do + { + int nnb = CycleNextAt (cPt, nb); + if (nnb == nb) + { + // cul-de-sac + nb = -1; + break; + } + nb = nnb; + if (nb < 0 || nb == curBord) + break; + } + while (swdData[nb].misc != nullptr || getEdge(nb).st != cPt); + + if (nb < 0 || nb == curBord) + { + if (back == false) + { + if (curBord == startBord || curBord < 0) + { + // probleme -> on vire le moveto + // dest->descr_nb--; + } + else + { +// bool escapePath=false; +// int tb=curBord; +// while ( tb >= 0 && tb < numberOfEdges() ) { +// if ( ebData[tb].pathID == wildPath ) { +// escapePath=true; +// break; +// } +// tb=swdData[tb].precParc; +// } + nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int)); + contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int)); + contStart[nbNest]=dest->descr_cmd.size(); + if (foundChild) { + nesting[nbNest++]=parentContour; + foundChild = false; + } else { + nesting[nbNest++]=-1; // contient des bouts de coupure -> a part + } + swdData[curBord].suivParc = -1; + AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced); + } + // dest->Close(); + } + back = true; + // retour en arriere + curBord = swdData[curBord].precParc; + //printf("retour vers %d\n",curBord); + if (curBord < 0) + break; + } + else + { + if (back) + { + back = false; + startBord = nb; + curStartPt=getEdge(nb).st; + } else { + if ( getEdge(curBord).en == curStartPt ) { + //printf("contour %i ",curStartPt); + +// bool escapePath=false; +// int tb=curBord; +// while ( tb >= 0 && tb < numberOfEdges() ) { +// if ( ebData[tb].pathID == wildPath ) { +// escapePath=true; +// break; +// } +// tb=swdData[tb].precParc; +// } + nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int)); + contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int)); + contStart[nbNest]=dest->descr_cmd.size(); + if (foundChild) { + nesting[nbNest++]=parentContour; + foundChild = false; + } else { + nesting[nbNest++]=-1; // contient des bouts de coupure -> a part + } + swdData[curBord].suivParc = -1; + AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced); + startBord=nb; + } + } + swdData[nb].misc = (void *)(intptr_t)(1 + nbNest); + swdData[nb].ind = searchInd++; + swdData[nb].precParc = curBord; + swdData[curBord].suivParc = nb; + curBord = nb; + if (nb == childEdge) { + foundChild = true; + } + //printf("suite %d\n",curBord); + } + } + while (true /*swdData[curBord].precParc >= 0 */ ); + // fin du cas non-oriente + } + } + while (lastPtUsed < numberOfPoints()); + + MakePointData (false); + MakeEdgeData (false); + MakeSweepDestData (false); +} + + +int +Shape::MakeTweak (int mode, Shape *a, double power, JoinType join, double miter, bool do_profile, Geom::Point c, Geom::Point vector, double radius, Geom::Affine *i2doc) +{ + Reset (0, 0); + MakeBackData(a->_has_back_data); + + bool done_something = false; + + if (power == 0) + { + _pts = a->_pts; + if (numberOfPoints() > maxPt) + { + maxPt = numberOfPoints(); + if (_has_points_data) { + pData.resize(maxPt); + _point_data_initialised = false; + _bbox_up_to_date = false; + } + } + + _aretes = a->_aretes; + if (numberOfEdges() > maxAr) + { + maxAr = numberOfEdges(); + if (_has_edges_data) + eData.resize(maxAr); + if (_has_sweep_src_data) + swsData.resize(maxAr); + if (_has_sweep_dest_data) + swdData.resize(maxAr); + if (_has_raster_data) + swrData.resize(maxAr); + if (_has_back_data) + ebData.resize(maxAr); + } + return 0; + } + if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon) + return shape_input_err; + + a->SortEdges (); + + a->MakeSweepDestData (true); + a->MakeSweepSrcData (true); + + for (int i = 0; i < a->numberOfEdges(); i++) + { + int stB = -1, enB = -1; + if (power <= 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen) { + stB = a->CyclePrevAt (a->getEdge(i).st, i); + enB = a->CycleNextAt (a->getEdge(i).en, i); + } else { + stB = a->CycleNextAt (a->getEdge(i).st, i); + enB = a->CyclePrevAt (a->getEdge(i).en, i); + } + + Geom::Point stD = a->getEdge(stB).dx; + Geom::Point seD = a->getEdge(i).dx; + Geom::Point enD = a->getEdge(enB).dx; + + double stL = sqrt (dot(stD,stD)); + double seL = sqrt (dot(seD,seD)); + //double enL = sqrt (dot(enD,enD)); + MiscNormalize (stD); + MiscNormalize (enD); + MiscNormalize (seD); + + Geom::Point ptP; + int stNo, enNo; + ptP = a->getPoint(a->getEdge(i).st).x; + + Geom::Point to_center = ptP * (*i2doc) - c; + Geom::Point to_center_normalized = (1/Geom::L2(to_center)) * to_center; + + double this_power; + if (do_profile && i2doc) { + double alpha = 1; + double x; + if (mode == tweak_mode_repel) { + x = (Geom::L2(to_center)/radius); + } else { + x = (Geom::L2(ptP * (*i2doc) - c)/radius); + } + if (x > 1) { + this_power = 0; + } else if (x <= 0) { + if (mode == tweak_mode_repel) { + this_power = 0; + } else { + this_power = power; + } + } else { + this_power = power * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5); + } + } else { + if (mode == tweak_mode_repel) { + this_power = 0; + } else { + this_power = power; + } + } + + if (this_power != 0) + done_something = true; + + double scaler = 1 / (*i2doc).descrim(); + + Geom::Point this_vec(0,0); + if (mode == tweak_mode_push) { + Geom::Affine tovec (*i2doc); + tovec[4] = tovec[5] = 0; + tovec = tovec.inverse(); + this_vec = this_power * (vector * tovec) ; + } else if (mode == tweak_mode_repel) { + this_vec = this_power * scaler * to_center_normalized; + } else if (mode == tweak_mode_roughen) { + double angle = g_random_double_range(0, 2*M_PI); + this_vec = g_random_double_range(0, 1) * this_power * scaler * Geom::Point(sin(angle), cos(angle)); + } + + int usePathID=-1; + int usePieceID=0; + double useT=0.0; + if ( a->_has_back_data ) { + if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID + && a->ebData[stB].tEn == a->ebData[i].tSt ) { + usePathID=a->ebData[i].pathID; + usePieceID=a->ebData[i].pieceID; + useT=a->ebData[i].tSt; + } else { + usePathID=a->ebData[i].pathID; + usePieceID=0; + useT=0; + } + } + + if (mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen) { + Path::DoLeftJoin (this, 0, join, ptP+this_vec, stD+this_vec, seD+this_vec, miter, stL, seL, + stNo, enNo,usePathID,usePieceID,useT); + a->swsData[i].stPt = enNo; + a->swsData[stB].enPt = stNo; + } else { + if (power > 0) { + Path::DoRightJoin (this, this_power * scaler, join, ptP, stD, seD, miter, stL, seL, + stNo, enNo,usePathID,usePieceID,useT); + a->swsData[i].stPt = enNo; + a->swsData[stB].enPt = stNo; + } else { + Path::DoLeftJoin (this, -this_power * scaler, join, ptP, stD, seD, miter, stL, seL, + stNo, enNo,usePathID,usePieceID,useT); + a->swsData[i].stPt = enNo; + a->swsData[stB].enPt = stNo; + } + } + } + + if (power < 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen) + { + for (int i = 0; i < numberOfEdges(); i++) + Inverse (i); + } + + if ( _has_back_data ) { + for (int i = 0; i < a->numberOfEdges(); i++) + { + int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt); + ebData[nEd]=a->ebData[i]; + } + } else { + for (int i = 0; i < a->numberOfEdges(); i++) + { + AddEdge (a->swsData[i].stPt, a->swsData[i].enPt); + } + } + + a->MakeSweepSrcData (false); + a->MakeSweepDestData (false); + + return (done_something? 0 : shape_nothing_to_do); +} + + +// offsets +// take each edge, offset it, and make joins with previous at edge start and next at edge end (previous and +// next being with respect to the clockwise order) +// you gotta be very careful with the join, as anything but the right one will fuck everything up +// see PathStroke.cpp for the "right" joins +int +Shape::MakeOffset (Shape * a, double dec, JoinType join, double miter, bool do_profile, double cx, double cy, double radius, Geom::Affine *i2doc) +{ + Reset (0, 0); + MakeBackData(a->_has_back_data); + + bool done_something = false; + + if (dec == 0) + { + _pts = a->_pts; + if (numberOfPoints() > maxPt) + { + maxPt = numberOfPoints(); + if (_has_points_data) { + pData.resize(maxPt); + _point_data_initialised = false; + _bbox_up_to_date = false; + } + } + + _aretes = a->_aretes; + if (numberOfEdges() > maxAr) + { + maxAr = numberOfEdges(); + if (_has_edges_data) + eData.resize(maxAr); + if (_has_sweep_src_data) + swsData.resize(maxAr); + if (_has_sweep_dest_data) + swdData.resize(maxAr); + if (_has_raster_data) + swrData.resize(maxAr); + if (_has_back_data) + ebData.resize(maxAr); + } + return 0; + } + if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon) + return shape_input_err; + + a->SortEdges (); + + a->MakeSweepDestData (true); + a->MakeSweepSrcData (true); + + for (int i = 0; i < a->numberOfEdges(); i++) + { + // int stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/; + int stB = -1, enB = -1; + if (dec > 0) + { + stB = a->CycleNextAt (a->getEdge(i).st, i); + enB = a->CyclePrevAt (a->getEdge(i).en, i); + } + else + { + stB = a->CyclePrevAt (a->getEdge(i).st, i); + enB = a->CycleNextAt (a->getEdge(i).en, i); + } + + Geom::Point stD = a->getEdge(stB).dx; + Geom::Point seD = a->getEdge(i).dx; + Geom::Point enD = a->getEdge(enB).dx; + + double stL = sqrt (dot(stD,stD)); + double seL = sqrt (dot(seD,seD)); + //double enL = sqrt (dot(enD,enD)); + MiscNormalize (stD); + MiscNormalize (enD); + MiscNormalize (seD); + + Geom::Point ptP; + int stNo, enNo; + ptP = a->getPoint(a->getEdge(i).st).x; + + double this_dec; + if (do_profile && i2doc) { + double alpha = 1; + double x = (Geom::L2(ptP * (*i2doc) - Geom::Point(cx,cy))/radius); + if (x > 1) { + this_dec = 0; + } else if (x <= 0) { + this_dec = dec; + } else { + this_dec = dec * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5); + } + } else { + this_dec = dec; + } + + if (this_dec != 0) + done_something = true; + + int usePathID=-1; + int usePieceID=0; + double useT=0.0; + if ( a->_has_back_data ) { + if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID + && a->ebData[stB].tEn == a->ebData[i].tSt ) { + usePathID=a->ebData[i].pathID; + usePieceID=a->ebData[i].pieceID; + useT=a->ebData[i].tSt; + } else { + usePathID=a->ebData[i].pathID; + usePieceID=0; + useT=0; + } + } + if (dec > 0) + { + Path::DoRightJoin (this, this_dec, join, ptP, stD, seD, miter, stL, seL, + stNo, enNo,usePathID,usePieceID,useT); + a->swsData[i].stPt = enNo; + a->swsData[stB].enPt = stNo; + } + else + { + Path::DoLeftJoin (this, -this_dec, join, ptP, stD, seD, miter, stL, seL, + stNo, enNo,usePathID,usePieceID,useT); + a->swsData[i].stPt = enNo; + a->swsData[stB].enPt = stNo; + } + } + + if (dec < 0) + { + for (int i = 0; i < numberOfEdges(); i++) + Inverse (i); + } + + if ( _has_back_data ) { + for (int i = 0; i < a->numberOfEdges(); i++) + { + int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt); + ebData[nEd]=a->ebData[i]; + } + } else { + for (int i = 0; i < a->numberOfEdges(); i++) + { + AddEdge (a->swsData[i].stPt, a->swsData[i].enPt); + } + } + + a->MakeSweepSrcData (false); + a->MakeSweepDestData (false); + + return (done_something? 0 : shape_nothing_to_do); +} + + + +// we found a contour, now reassemble the edges on it, instead of dumping them in the Path "dest" as a +// polyline. since it was a DFS, the precParc and suivParc make a nice doubly-linked list of the edges in +// the contour. the first and last edges of the contour are startBord and curBord +void +Shape::AddContour (Path * dest, int nbP, Path * *orig, int startBord, int curBord, bool splitWhenForced) +{ + int bord = startBord; + + { + dest->MoveTo (getPoint(getEdge(bord).st).x); + } + + while (bord >= 0) + { + int nPiece = ebData[bord].pieceID; + int nPath = ebData[bord].pathID; + + if (nPath < 0 || nPath >= nbP || orig[nPath] == nullptr) + { + // segment batard + dest->LineTo (getPoint(getEdge(bord).en).x); + bord = swdData[bord].suivParc; + } + else + { + Path *from = orig[nPath]; + if (nPiece < 0 || nPiece >= int(from->descr_cmd.size())) + { + // segment batard + dest->LineTo (getPoint(getEdge(bord).en).x); + bord = swdData[bord].suivParc; + } + else + { + int nType = from->descr_cmd[nPiece]->getType(); + if (nType == descr_close || nType == descr_moveto + || nType == descr_forced) + { + // devrait pas arriver + dest->LineTo (getPoint(getEdge(bord).en).x); + bord = swdData[bord].suivParc; + } + else if (nType == descr_lineto) + { + bord = ReFormeLineTo (bord, curBord, dest, from); + } + else if (nType == descr_arcto) + { + bord = ReFormeArcTo (bord, curBord, dest, from); + } + else if (nType == descr_cubicto) + { + bord = ReFormeCubicTo (bord, curBord, dest, from); + } + else if (nType == descr_bezierto) + { + PathDescrBezierTo* nBData = + dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]); + + if (nBData->nb == 0) + { + bord = ReFormeLineTo (bord, curBord, dest, from); + } + else + { + bord = ReFormeBezierTo (bord, curBord, dest, from); + } + } + else if (nType == descr_interm_bezier) + { + bord = ReFormeBezierTo (bord, curBord, dest, from); + } + else + { + // devrait pas arriver non plus + dest->LineTo (getPoint(getEdge(bord).en).x); + bord = swdData[bord].suivParc; + } + if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) { + dest->ForcePoint (); + } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2) { + if ( splitWhenForced ) { + // pour les coupures + dest->ForcePoint (); + } else { + if ( _has_back_data ) { + int prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST]; + int nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST]; + if ( getEdge(prevEdge).en != getEdge(bord).st ) { + int swai=prevEdge;prevEdge=nextEdge;nextEdge=swai; + } + if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) { + if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) { + } else { + dest->ForcePoint (); + } + } else { + dest->ForcePoint (); + } + } else { + dest->ForcePoint (); + } + } + } + } + } + } + dest->Close (); +} + +int +Shape::ReFormeLineTo (int bord, int /*curBord*/, Path * dest, Path * /*orig*/) +{ + int nPiece = ebData[bord].pieceID; + int nPath = ebData[bord].pathID; + double /*ts=ebData[bord].tSt, */ te = ebData[bord].tEn; + Geom::Point nx = getPoint(getEdge(bord).en).x; + bord = swdData[bord].suivParc; + while (bord >= 0) + { + if (getPoint(getEdge(bord).st).totalDegree() > 2 + || getPoint(getEdge(bord).st).oldDegree > 2) + { + break; + } + if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath) + { + if (fabs (te - ebData[bord].tSt) > 0.0001) + break; + nx = getPoint(getEdge(bord).en).x; + te = ebData[bord].tEn; + } + else + { + break; + } + bord = swdData[bord].suivParc; + } + { + dest->LineTo (nx); + } + return bord; +} + +int +Shape::ReFormeArcTo (int bord, int /*curBord*/, Path * dest, Path * from) +{ + int nPiece = ebData[bord].pieceID; + int nPath = ebData[bord].pathID; + double ts = ebData[bord].tSt, te = ebData[bord].tEn; + // double px=pts[getEdge(bord).st].x,py=pts[getEdge(bord).st].y; + Geom::Point nx = getPoint(getEdge(bord).en).x; + bord = swdData[bord].suivParc; + while (bord >= 0) + { + if (getPoint(getEdge(bord).st).totalDegree() > 2 + || getPoint(getEdge(bord).st).oldDegree > 2) + { + break; + } + if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath) + { + if (fabs (te - ebData[bord].tSt) > 0.0001) + { + break; + } + nx = getPoint(getEdge(bord).en).x; + te = ebData[bord].tEn; + } + else + { + break; + } + bord = swdData[bord].suivParc; + } + double sang, eang; + PathDescrArcTo* nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]); + bool nLarge = nData->large; + bool nClockwise = nData->clockwise; + Path::ArcAngles (from->PrevPoint (nPiece - 1), nData->p,nData->rx,nData->ry,nData->angle*M_PI/180.0, nLarge, nClockwise, sang, eang); + if (nClockwise) + { + if (sang < eang) + sang += 2 * M_PI; + } + else + { + if (sang > eang) + sang -= 2 * M_PI; + } + double delta = eang - sang; + double ndelta = delta * (te - ts); + if (ts > te) + nClockwise = !nClockwise; + if (ndelta < 0) + ndelta = -ndelta; + if (ndelta > M_PI) + nLarge = true; + else + nLarge = false; + /* if ( delta < 0 ) delta=-delta; + if ( ndelta < 0 ) ndelta=-ndelta; + if ( ( delta < M_PI && ndelta < M_PI ) || ( delta >= M_PI && ndelta >= M_PI ) ) { + if ( ts < te ) { + } else { + nClockwise=!(nClockwise); + } + } else { + // nLarge=!(nLarge); + nLarge=false; // c'est un sous-segment -> l'arc ne peut que etre plus petit + if ( ts < te ) { + } else { + nClockwise=!(nClockwise); + } + }*/ + { + PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]); + dest->ArcTo (nx, nData->rx,nData->ry,nData->angle, nLarge, nClockwise); + } + return bord; +} + +int +Shape::ReFormeCubicTo (int bord, int /*curBord*/, Path * dest, Path * from) +{ + int nPiece = ebData[bord].pieceID; + int nPath = ebData[bord].pathID; + double ts = ebData[bord].tSt, te = ebData[bord].tEn; + Geom::Point nx = getPoint(getEdge(bord).en).x; + bord = swdData[bord].suivParc; + while (bord >= 0) + { + if (getPoint(getEdge(bord).st).totalDegree() > 2 + || getPoint(getEdge(bord).st).oldDegree > 2) + { + break; + } + if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath) + { + if (fabs (te - ebData[bord].tSt) > 0.0001) + { + break; + } + nx = getPoint(getEdge(bord).en).x; + te = ebData[bord].tEn; + } + else + { + break; + } + bord = swdData[bord].suivParc; + } + Geom::Point prevx = from->PrevPoint (nPiece - 1); + + Geom::Point sDx, eDx; + { + PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(from->descr_cmd[nPiece]); + Path::CubicTangent (ts, sDx, prevx,nData->start,nData->p,nData->end); + Path::CubicTangent (te, eDx, prevx,nData->start,nData->p,nData->end); + } + sDx *= (te - ts); + eDx *= (te - ts); + { + dest->CubicTo (nx,sDx,eDx); + } + return bord; +} + +int +Shape::ReFormeBezierTo (int bord, int /*curBord*/, Path * dest, Path * from) +{ + int nPiece = ebData[bord].pieceID; + int nPath = ebData[bord].pathID; + double ts = ebData[bord].tSt, te = ebData[bord].tEn; + int ps = nPiece, pe = nPiece; + Geom::Point px = getPoint(getEdge(bord).st).x; + Geom::Point nx = getPoint(getEdge(bord).en).x; + int inBezier = -1, nbInterm = -1; + int typ; + typ = from->descr_cmd[nPiece]->getType(); + PathDescrBezierTo *nBData = nullptr; + if (typ == descr_bezierto) + { + nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]); + inBezier = nPiece; + nbInterm = nBData->nb; + } + else + { + int n = nPiece - 1; + while (n > 0) + { + typ = from->descr_cmd[n]->getType(); + if (typ == descr_bezierto) + { + inBezier = n; + nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[n]); + nbInterm = nBData->nb; + break; + } + n--; + } + if (inBezier < 0) + { + bord = swdData[bord].suivParc; + dest->LineTo (nx); + return bord; + } + } + bord = swdData[bord].suivParc; + while (bord >= 0) + { + if (getPoint(getEdge(bord).st).totalDegree() > 2 + || getPoint(getEdge(bord).st).oldDegree > 2) + { + break; + } + if (ebData[bord].pathID == nPath) + { + if (ebData[bord].pieceID < inBezier + || ebData[bord].pieceID >= inBezier + nbInterm) + break; + if (ebData[bord].pieceID == pe + && fabs (te - ebData[bord].tSt) > 0.0001) + break; + if (ebData[bord].pieceID != pe + && (ebData[bord].tSt > 0.0001 && ebData[bord].tSt < 0.9999)) + break; + if (ebData[bord].pieceID != pe && (te > 0.0001 && te < 0.9999)) + break; + nx = getPoint(getEdge(bord).en).x; + te = ebData[bord].tEn; + pe = ebData[bord].pieceID; + } + else + { + break; + } + bord = swdData[bord].suivParc; + } + + g_return_val_if_fail(nBData != nullptr, 0); + + if (pe == ps) + { + ReFormeBezierChunk (px, nx, dest, inBezier, nbInterm, from, ps, + ts, te); + } + else if (ps < pe) + { + if (ts < 0.0001) + { + if (te > 0.9999) + { + dest->BezierTo (nx); + for (int i = ps; i <= pe; i++) + { + PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + } + else + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]); + tx = (pnData->p + psData->p) / 2; + } + dest->BezierTo (tx); + for (int i = ps; i < pe; i++) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm, + from, pe, 0.0, te); + } + } + else + { + if (te > 0.9999) + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]); + tx = (psData->p + pnData->p) / 2; + } + ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm, + from, ps, ts, 1.0); + dest->BezierTo (nx); + for (int i = ps + 1; i <= pe; i++) + { + PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + } + else + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]); + tx = (pnData->p + psData->p) / 2; + } + ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm, + from, ps, ts, 1.0); + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]); + tx = (pnData->p + psData->p) / 2; + } + dest->BezierTo (tx); + for (int i = ps + 1; i <= pe; i++) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm, + from, pe, 0.0, te); + } + } + } + else + { + if (ts > 0.9999) + { + if (te < 0.0001) + { + dest->BezierTo (nx); + for (int i = ps; i >= pe; i--) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + } + else + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]); + tx = (pnData->p + psData->p) / 2; + } + dest->BezierTo (tx); + for (int i = ps; i > pe; i--) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm, + from, pe, 1.0, te); + } + } + else + { + if (te < 0.0001) + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]); + tx = (pnData->p + psData->p) / 2; + } + ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm, + from, ps, ts, 0.0); + dest->BezierTo (nx); + for (int i = ps + 1; i >= pe; i--) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + } + else + { + Geom::Point tx; + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]); + tx = (pnData->p + psData->p) / 2; + } + ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm, + from, ps, ts, 0.0); + { + PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]); + PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]); + tx = (pnData->p + psData->p) / 2; + } + dest->BezierTo (tx); + for (int i = ps + 1; i > pe; i--) + { + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]); + dest->IntermBezierTo (nData->p); + } + dest->EndBezierTo (); + ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm, + from, pe, 1.0, te); + } + } + } + return bord; +} + +void +Shape::ReFormeBezierChunk (Geom::Point px, Geom::Point nx, + Path * dest, int inBezier, int nbInterm, + Path * from, int p, double ts, double te) +{ + PathDescrBezierTo* nBData = dynamic_cast<PathDescrBezierTo*>(from->descr_cmd[inBezier]); + Geom::Point bstx = from->PrevPoint (inBezier - 1); + Geom::Point benx = nBData->p; + + Geom::Point mx; + if (p == inBezier) + { + // premier bout + if (nbInterm <= 1) + { + // seul bout de la spline + PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]); + mx = nData->p; + } + else + { + // premier bout d'une spline qui en contient plusieurs + PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]); + mx = nData->p; + nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+2]); + benx = (nData->p + mx) / 2; + } + } + else if (p == inBezier + nbInterm - 1) + { + // dernier bout + // si nbInterm == 1, le cas a deja ete traite + // donc dernier bout d'une spline qui en contient plusieurs + PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm]); + mx = nData->p; + nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm-1]); + bstx = (nData->p + mx) / 2; + } + else + { + // la spline contient forcément plusieurs bouts, et ce n'est ni le premier ni le dernier + PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+1]); + mx = nData->p; + nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p]); + bstx = (nData->p + mx) / 2; + nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+2]); + benx = (nData->p + mx) / 2; + } + Geom::Point cx; + { + Path::QuadraticPoint ((ts + te) / 2, cx, bstx, mx, benx); + } + cx = 2 * cx - (px + nx) / 2; + { + dest->BezierTo (nx); + dest->IntermBezierTo (cx); + dest->EndBezierTo (); + } +} + +#undef MiscNormalize |