Shape Class Reference

#include <Shape.h>

Collaboration diagram for Shape:
Collaboration graph
[legend]

List of all members.

Classes

struct  back_data
struct  dg_arete
struct  dg_point
struct  edge_data
struct  edge_list
struct  incidenceData
struct  point_data
struct  quick_raster_data
struct  raster_data
struct  sTreeChange
struct  sweep_dest_data
struct  sweep_src_data
struct  voronoi_edge
struct  voronoi_point

Public Types

enum  sTreeChangeType { EDGE_INSERTED = 0, EDGE_REMOVED = 1, INTERSECTION = 2 }

Public Member Functions

 Shape ()
virtual ~Shape ()
void MakeBackData (bool nVal)
void MakeVoronoiData (bool nVal)
void Affiche ()
void Copy (Shape *a)
 Copy point and edge data from `who' into this object, discarding any cached data that we have.
void Reset (int n=0, int m=0)
 Clear points and edges and prepare internal data using new size.
int AddPoint (const Geom::Point x)
void SubPoint (int p)
void SwapPoints (int a, int b)
void SwapPoints (int a, int b, int c)
void SortPoints ()
int AddEdge (int st, int en)
int AddEdge (int st, int en, int leF, int riF)
void SubEdge (int e)
void SwapEdges (int a, int b)
void SwapEdges (int a, int b, int c)
void SortEdges ()
int Other (int p, int b) const
int NextAt (int p, int b) const
int PrevAt (int p, int b) const
int CycleNextAt (int p, int b) const
int CyclePrevAt (int p, int b) const
void ConnectStart (int p, int b)
void ConnectEnd (int p, int b)
void DisconnectStart (int b)
void DisconnectEnd (int b)
void Inverse (int b)
void CalcBBox (bool strict_degree=false)
void Plot (double ix, double iy, double ir, double mx, double my, bool doPoint, bool edgesNo, bool pointNo, bool doDir, char *fileName)
void ConvertToForme (Path *dest)
void ConvertToForme (Path *dest, int nbP, Path **orig, bool splitWhenForced=false)
void ConvertToFormeNested (Path *dest, int nbP, Path **orig, int wildPath, int &nbNest, int *&nesting, int *&contStart, bool splitWhenForced=false)
int ConvertToShape (Shape *a, FillRule directed=fill_nonZero, bool invert=false)
int Reoriente (Shape *a)
void ForceToPolygon ()
int Booleen (Shape *a, Shape *b, BooleanOp mod, int cutPathID=-1)
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)
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)
int PtWinding (const Geom::Point px) const
int Winding (const Geom::Point px) const
void BeginRaster (float &pos, int &curPt)
void EndRaster ()
void BeginQuickRaster (float &pos, int &curPt)
void EndQuickRaster ()
void Scan (float &pos, int &curP, float to, float step)
void QuickScan (float &pos, int &curP, float to, bool doSort, float step)
void DirectScan (float &pos, int &curP, float to, float step)
void DirectQuickScan (float &pos, int &curP, float to, bool doSort, float step)
void Scan (float &pos, int &curP, float to, FloatLigne *line, bool exact, float step)
void Scan (float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step)
void Scan (float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step)
void QuickScan (float &pos, int &curP, float to, FloatLigne *line, float step)
void QuickScan (float &pos, int &curP, float to, FillRule directed, BitLigne *line, float step)
void QuickScan (float &pos, int &curP, float to, AlphaLigne *line, float step)
void Transform (Geom::Matrix const &tr)
int numberOfPoints () const
bool hasPoints () const
int numberOfEdges () const
bool hasEdges () const
void needPointsSorting ()
void needEdgesSorting ()
bool hasBackData () const
dg_point const & getPoint (int n) const
dg_arete const & getEdge (int n) const

Static Public Member Functions

static double Round (double x)
static double HalfRound (double x)
static double IHalfRound (double x)

Public Attributes

std::vector< back_data > ebData
std::vector< voronoi_point > vorpData
std::vector< voronoi_edge > voreData
int nbQRas
int firstQRas
int lastQRas
quick_raster_data * qrsData
std::vector< sTreeChange > chgts
int nbInc
int maxInc
incidenceData * iData
SweepTreeList * sTree
SweepEventQueue * sEvts
double leftX
double topY
double rightX
double bottomY
int maxPt
int maxAr
int type

Private Member Functions

void initialisePointData ()
void initialiseEdgeData ()
void clearIncidenceData ()
void _countUpDown (int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
void _countUpDownTotalDegree2 (int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
 Version of Shape::_countUpDown optimised for the case when getPoint(P).totalDegree() == 2.
void _updateIntersection (int e, int p)
void MakePointData (bool nVal)
 Allocates space for point cache or clears the cache.
void MakeEdgeData (bool nVal)
void MakeSweepSrcData (bool nVal)
void MakeSweepDestData (bool nVal)
void MakeRasterData (bool nVal)
void MakeQuickRasterData (bool nVal)
void SortPoints (int s, int e)
void SortPointsByOldInd (int s, int e)
void ResetSweep ()
void CleanupSweep ()
void SortEdgesList (edge_list *edges, int s, int e)
void TesteIntersection (SweepTree *t, Side s, bool onlyDiff)
bool TesteIntersection (SweepTree *iL, SweepTree *iR, Geom::Point &atx, double &atL, double &atR, bool onlyDiff)
bool TesteIntersection (Shape *iL, Shape *iR, int ilb, int irb, Geom::Point &atx, double &atL, double &atR, bool onlyDiff)
bool TesteAdjacency (Shape *iL, int ilb, const Geom::Point atx, int nPt, bool push)
int PushIncidence (Shape *a, int cb, int pt, double theta)
int CreateIncidence (Shape *a, int cb, int pt)
void AssemblePoints (Shape *a)
int AssemblePoints (int st, int en)
void AssembleAretes (FillRule directed=fill_nonZero)
void AddChgt (int lastPointNo, int lastChgtPt, Shape *&shapeHead, int &edgeHead, sTreeChangeType type, Shape *lS, int lB, Shape *rS, int rB)
void CheckAdjacencies (int lastPointNo, int lastChgtPt, Shape *shapeHead, int edgeHead)
void CheckEdges (int lastPointNo, int lastChgtPt, Shape *a, Shape *b, BooleanOp mod)
void Avance (int lastPointNo, int lastChgtPt, Shape *iS, int iB, Shape *a, Shape *b, BooleanOp mod)
void DoEdgeTo (Shape *iS, int iB, int iTo, bool direct, bool sens)
void GetWindings (Shape *a, Shape *b=NULL, BooleanOp mod=bool_op_union, bool brutal=false)
void Validate ()
int Winding (int nPt) const
void SortPointsRounded ()
void SortPointsRounded (int s, int e)
void CreateEdge (int no, float to, float step)
void AvanceEdge (int no, float to, bool exact, float step)
void DestroyEdge (int no, float to, FloatLigne *line)
void AvanceEdge (int no, float to, FloatLigne *line, bool exact, float step)
void DestroyEdge (int no, BitLigne *line)
void AvanceEdge (int no, float to, BitLigne *line, bool exact, float step)
void DestroyEdge (int no, AlphaLigne *line)
void AvanceEdge (int no, float to, AlphaLigne *line, bool exact, float step)
void AddContour (Path *dest, int nbP, Path **orig, int startBord, int curBord, bool splitWhenForced)
int ReFormeLineTo (int bord, int curBord, Path *dest, Path *orig)
int ReFormeArcTo (int bord, int curBord, Path *dest, Path *orig)
int ReFormeCubicTo (int bord, int curBord, Path *dest, Path *orig)
int ReFormeBezierTo (int bord, int curBord, Path *dest, Path *orig)
void ReFormeBezierChunk (const Geom::Point px, const Geom::Point nx, Path *dest, int inBezier, int nbInterm, Path *from, int p, double ts, double te)
int QuickRasterChgEdge (int oBord, int nbord, double x)
int QuickRasterAddEdge (int bord, double x, int guess)
void QuickRasterSubEdge (int bord)
void QuickRasterSwapEdge (int a, int b)
void QuickRasterSort ()

Static Private Member Functions

static int CmpQRs (const quick_raster_data &p1, const quick_raster_data &p2)
static int CmpToVert (const Geom::Point ax, const Geom::Point bx, bool as, bool bs)

Private Attributes

bool _need_points_sorting
 points have been added or removed: we need to sort the points again
bool _need_edges_sorting
 edges have been added: maybe they are not ordered clockwise
bool _has_points_data
 the pData array is allocated
bool _point_data_initialised
 the pData array is up to date
bool _has_edges_data
 the eData array is allocated
bool _has_sweep_src_data
 the swsData array is allocated
bool _has_sweep_dest_data
 the swdData array is allocated
bool _has_raster_data
 the swrData array is allocated
bool _has_quick_raster_data
 the swrData array is allocated
bool _has_back_data
bool _has_voronoi_data
bool _bbox_up_to_date
 the leftX/rightX/topY/bottomY are up to date
std::vector< dg_point > _pts
std::vector< dg_arete > _aretes
std::vector< edge_data > eData
std::vector< sweep_src_data > swsData
std::vector< sweep_dest_data > swdData
std::vector< raster_data > swrData
std::vector< point_data > pData

Friends

class SweepTree
class SweepEvent
class SweepEventQueue

Detailed Description

Definition at line 53 of file Shape.h.

Member Enumeration Documentation

enum Shape::sTreeChangeType
Enumerator:
EDGE_INSERTED 
EDGE_REMOVED 
INTERSECTION 

Definition at line 85 of file Shape.h.

00086     {
00087         EDGE_INSERTED = 0,
00088         EDGE_REMOVED = 1,
00089         INTERSECTION = 2
00090     };

Constructor & Destructor Documentation

Shape::Shape (  ) 

Definition at line 23 of file Shape.cpp.

References bottomY, leftX, maxAr, maxPt, rightX, shape_polygon, topY, and type.

00024   : qrsData(NULL),
00025     iData(NULL),
00026     sTree(NULL),
00027     sEvts(NULL),
00028     _need_points_sorting(false),
00029     _need_edges_sorting(false),
00030     _has_points_data(false),
00031     _point_data_initialised(false),
00032     _has_edges_data(false),
00033     _has_sweep_src_data(false),
00034     _has_sweep_dest_data(false),
00035     _has_raster_data(false),
00036     _has_quick_raster_data(false),
00037     _has_back_data(false),
00038     _has_voronoi_data(false),
00039     _bbox_up_to_date(false)
00040 {
00041   leftX = topY = rightX = bottomY = 0;
00042   maxPt = 0;
00043   maxAr = 0;
00044 
00045   type = shape_polygon;
00046 }

Shape::~Shape ( void   )  [virtual]

Definition at line 47 of file Shape.cpp.

References maxAr, maxPt, and qrsData.

00048 {
00049   maxPt = 0;
00050   maxAr = 0;
00051   free(qrsData);
00052 }

Member Function Documentation

void Shape::_countUpDown ( int  P,
int *  numberUp,
int *  numberDown,
int *  upEdge,
int *  downEdge 
) const [private]
Parameters:
P point index.
numberUp Filled in with the number of edges coming into P from above.
numberDown Filled in with the number of edges coming exiting P to go below.
upEdge One of the numberUp edges, or -1.
downEdge One of the numberDown edges, or -1.

Definition at line 1937 of file ShapeRaster.cpp.

References addnodes::e, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, max, min, NextAt(), numberOfEdges(), and Shape::dg_arete::st.

Referenced by QuickScan(), and Scan().

01938 {
01939     *numberUp = 0;
01940     *numberDown = 0;
01941     *upEdge = -1;
01942     *downEdge = -1;
01943     
01944     int i = getPoint(P).incidentEdge[FIRST];
01945     
01946     while ( i >= 0 && i < numberOfEdges() ) {
01947         Shape::dg_arete const &e = getEdge(i);
01948         if ( P == std::max(e.st, e.en) ) {
01949             *upEdge = i;
01950             (*numberUp)++;
01951         }
01952         if ( P == std::min(e.st, e.en) ) {
01953             *downEdge = i;
01954             (*numberDown)++;
01955         }
01956         i = NextAt(P, i);
01957     }
01958     
01959 }

void Shape::_countUpDownTotalDegree2 ( int  P,
int *  numberUp,
int *  numberDown,
int *  upEdge,
int *  downEdge 
) const [private]

Version of Shape::_countUpDown optimised for the case when getPoint(P).totalDegree() == 2.

Definition at line 1967 of file ShapeRaster.cpp.

References addnodes::e, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, max, min, and Shape::dg_arete::st.

Referenced by QuickScan(), and Scan().

01969 {
01970     *numberUp = 0;
01971     *numberDown = 0;
01972     *upEdge = -1;
01973     *downEdge = -1;
01974     
01975     for (int i = 0; i < 2; i++) {
01976         int const j = getPoint(P).incidentEdge[i];
01977         Shape::dg_arete const &e = getEdge(j);
01978         if ( P == std::max(e.st, e.en) ) {
01979             *upEdge = j;
01980             (*numberUp)++;
01981         }
01982         if ( P == std::min(e.st, e.en) ) {
01983             *downEdge = j;
01984             (*numberDown)++;
01985         }
01986     }
01987 }

void Shape::_updateIntersection ( int  e,
int  p 
) [private]

Definition at line 1990 of file ShapeRaster.cpp.

References getPoint(), NULL, swrData, and Shape::dg_point::x.

Referenced by QuickScan(), and Scan().

01991 {
01992     swrData[e].lastX = swrData[e].curX;
01993     swrData[e].lastY = swrData[e].curY;
01994     swrData[e].curX = getPoint(p).x[0];
01995     swrData[e].curY = getPoint(p).x[1];
01996     swrData[e].misc = NULL;
01997 }

void Shape::AddChgt ( int  lastPointNo,
int  lastChgtPt,
Shape *&  shapeHead,
int &  edgeHead,
sTreeChangeType  type,
Shape *  lS,
int  lB,
Shape *  rS,
int  rB 
) [private]

Definition at line 2922 of file ShapeSweep.cpp.

References SweepTree::bord, Shape::sTreeChange::bord, c, chgts, AVLTree::elem, getPoint(), LEFT, NULL, Shape::sTreeChange::obord, Shape::sTreeChange::osrc, Shape::sTreeChange::ptNo, RIGHT, SweepTree::src, Shape::sTreeChange::src, swsData, Shape::sTreeChange::type, and Shape::dg_point::x.

Referenced by Booleen(), and ConvertToShape().

02925 {
02926     sTreeChange c;
02927     c.ptNo = lastPointNo;
02928     c.type = type;
02929     c.src = lS;
02930     c.bord = lB;
02931     c.osrc = rS;
02932     c.obord = rB;
02933     chgts.push_back(c);
02934     const int nCh = chgts.size() - 1;
02935 
02936     /* FIXME: this looks like a cut and paste job */
02937 
02938     if (lS) {
02939     SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
02940     if (lE && lE->elem[LEFT]) {
02941         SweepTree *llE = static_cast < SweepTree * >(lE->elem[LEFT]);
02942         chgts[nCh].lSrc = llE->src;
02943         chgts[nCh].lBrd = llE->bord;
02944     } else {
02945         chgts[nCh].lSrc = NULL;
02946         chgts[nCh].lBrd = -1;
02947     }
02948 
02949     if (lS->swsData[lB].leftRnd < lastChgtPt) {
02950         lS->swsData[lB].leftRnd = lastPointNo;
02951         lS->swsData[lB].nextSh = shapeHead;
02952         lS->swsData[lB].nextBo = edgeHead;
02953         edgeHead = lB;
02954         shapeHead = lS;
02955     } else {
02956         int old = lS->swsData[lB].leftRnd;
02957         if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
02958         lS->swsData[lB].leftRnd = lastPointNo;
02959         }
02960     }
02961     if (lS->swsData[lB].rightRnd < lastChgtPt) {
02962         lS->swsData[lB].rightRnd = lastPointNo;
02963     } else {
02964         int old = lS->swsData[lB].rightRnd;
02965         if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
02966         lS->swsData[lB].rightRnd = lastPointNo;
02967     }
02968     }
02969 
02970     if (rS) {
02971     SweepTree *rE = static_cast < SweepTree * >(rS->swsData[rB].misc);
02972     if (rE->elem[RIGHT]) {
02973         SweepTree *rrE = static_cast < SweepTree * >(rE->elem[RIGHT]);
02974         chgts[nCh].rSrc = rrE->src;
02975         chgts[nCh].rBrd = rrE->bord;
02976     } else {
02977         chgts[nCh].rSrc = NULL;
02978         chgts[nCh].rBrd = -1;
02979     }
02980     
02981     if (rS->swsData[rB].leftRnd < lastChgtPt) {
02982         rS->swsData[rB].leftRnd = lastPointNo;
02983         rS->swsData[rB].nextSh = shapeHead;
02984         rS->swsData[rB].nextBo = edgeHead;
02985         edgeHead = rB;
02986         shapeHead = rS;
02987     } else {
02988         int old = rS->swsData[rB].leftRnd;
02989         if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
02990         rS->swsData[rB].leftRnd = lastPointNo;
02991         }
02992     }
02993     if (rS->swsData[rB].rightRnd < lastChgtPt) {
02994         rS->swsData[rB].rightRnd = lastPointNo;
02995     } else {
02996         int old = rS->swsData[rB].rightRnd;
02997         if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
02998         rS->swsData[rB].rightRnd = lastPointNo;
02999     }
03000     } else {
03001     SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
03002     if (lE && lE->elem[RIGHT]) {
03003         SweepTree *rlE = static_cast < SweepTree * >(lE->elem[RIGHT]);
03004         chgts[nCh].rSrc = rlE->src;
03005         chgts[nCh].rBrd = rlE->bord;
03006     } else {
03007         chgts[nCh].rSrc = NULL;
03008         chgts[nCh].rBrd = -1;
03009     }
03010     }
03011 }

void Shape::AddContour ( Path *  dest,
int  nbP,
Path **  orig,
int  startBord,
int  curBord,
bool  splitWhenForced 
) [private]

Definition at line 878 of file ShapeMisc.cpp.

References _has_back_data, Path::Close(), descr_arcto, descr_bezierto, descr_close, Path::descr_cmd, descr_cubicto, descr_forced, descr_interm_bezier, descr_lineto, descr_moveto, ebData, FIRST, Path::ForcePoint(), getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, Path::LineTo(), Path::MoveTo(), PathDescrBezierTo::nb, NULL, ReFormeArcTo(), ReFormeBezierTo(), ReFormeCubicTo(), ReFormeLineTo(), swdData, and voronoi::x.

Referenced by ConvertToForme(), and ConvertToFormeNested().

00879 {
00880   int bord = startBord;
00881   
00882   {
00883     dest->MoveTo (getPoint(getEdge(bord).st).x);
00884   }
00885   
00886   while (bord >= 0)
00887   {
00888     int nPiece = ebData[bord].pieceID;
00889     int nPath = ebData[bord].pathID;
00890     
00891     if (nPath < 0 || nPath >= nbP || orig[nPath] == NULL)
00892     {
00893       // segment batard
00894       dest->LineTo (getPoint(getEdge(bord).en).x);
00895       bord = swdData[bord].suivParc;
00896     }
00897     else
00898     {
00899       Path *from = orig[nPath];
00900       if (nPiece < 0 || nPiece >= int(from->descr_cmd.size()))
00901         {
00902           // segment batard
00903           dest->LineTo (getPoint(getEdge(bord).en).x);
00904           bord = swdData[bord].suivParc;
00905         }
00906       else
00907         {
00908           int nType = from->descr_cmd[nPiece]->getType();
00909           if (nType == descr_close || nType == descr_moveto
00910             || nType == descr_forced)
00911         {
00912           // devrait pas arriver
00913           dest->LineTo (getPoint(getEdge(bord).en).x);
00914           bord = swdData[bord].suivParc;
00915         }
00916           else if (nType == descr_lineto)
00917         {
00918           bord = ReFormeLineTo (bord, curBord, dest, from);
00919         }
00920           else if (nType == descr_arcto)
00921         {
00922           bord = ReFormeArcTo (bord, curBord, dest, from);
00923         }
00924           else if (nType == descr_cubicto)
00925         {
00926           bord = ReFormeCubicTo (bord, curBord, dest, from);
00927         }
00928           else if (nType == descr_bezierto)
00929         {
00930           PathDescrBezierTo* nBData =
00931         dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
00932       
00933           if (nBData->nb == 0)
00934           {
00935             bord = ReFormeLineTo (bord, curBord, dest, from);
00936           }
00937           else
00938           {
00939             bord = ReFormeBezierTo (bord, curBord, dest, from);
00940           }
00941         }
00942           else if (nType == descr_interm_bezier)
00943         {
00944           bord = ReFormeBezierTo (bord, curBord, dest, from);
00945         }
00946           else
00947         {
00948           // devrait pas arriver non plus
00949           dest->LineTo (getPoint(getEdge(bord).en).x);
00950           bord = swdData[bord].suivParc;
00951         }
00952           if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) {
00953           dest->ForcePoint ();
00954         } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2)  {
00955           if ( splitWhenForced ) {
00956             // pour les coupures
00957             dest->ForcePoint ();
00958          } else {
00959             if ( _has_back_data ) {
00960               int   prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST];
00961               int   nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST];
00962               if ( getEdge(prevEdge).en != getEdge(bord).st ) {
00963                 int  swai=prevEdge;prevEdge=nextEdge;nextEdge=swai;
00964               }
00965               if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID  && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) {
00966                 if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) {
00967                 } else {
00968                   dest->ForcePoint ();
00969                 }
00970               } else {
00971                 dest->ForcePoint ();
00972               }
00973             } else {
00974               dest->ForcePoint ();
00975             }    
00976           }
00977         }
00978       }
00979     }
00980   }
00981   dest->Close ();
00982 }

int Shape::AddEdge ( int  st,
int  en,
int  leF,
int  riF 
)

Definition at line 1176 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _has_voronoi_data, _need_edges_sorting, org::w3c::dom::svg::a, ConnectEnd(), ConnectStart(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, maxAr, n, NextAt(), Shape::dg_arete::nextE, Shape::dg_arete::nextS, NULL, numberOfEdges(), Point, Shape::dg_arete::prevE, Shape::dg_arete::prevS, shape_graph, Shape::dg_arete::st, swdData, swrData, swsData, type, voreData, and Shape::dg_point::x.

01177 {
01178   if (st == en)
01179     return -1;
01180   if (st < 0 || en < 0)
01181     return -1;
01182   {
01183     int cb = getPoint(st).incidentEdge[FIRST];
01184     while (cb >= 0)
01185       {
01186         if (getEdge(cb).st == st && getEdge(cb).en == en)
01187           return -1;        // doublon
01188         if (getEdge(cb).st == en && getEdge(cb).en == st)
01189           return -1;        // doublon
01190         cb = NextAt (st, cb);
01191       }
01192   }
01193   type = shape_graph;
01194   if (numberOfEdges() >= maxAr)
01195     {
01196       maxAr = 2 * numberOfEdges() + 1;
01197       if (_has_edges_data)
01198         eData.resize(maxAr);
01199       if (_has_sweep_src_data)
01200         swsData.resize(maxAr);
01201       if (_has_sweep_dest_data)
01202         swdData.resize(maxAr);
01203       if (_has_raster_data)
01204         swrData.resize(maxAr);
01205       if (_has_back_data)
01206         ebData.resize(maxAr);
01207       if (_has_voronoi_data)
01208         voreData.resize(maxAr);
01209     }
01210 
01211   dg_arete a;
01212   a.dx = Geom::Point(0, 0);
01213   a.st = a.en = -1;
01214   a.prevS = a.nextS = -1;
01215   a.prevE = a.nextE = -1;
01216   if (st >= 0 && en >= 0) {
01217     a.dx = getPoint(en).x - getPoint(st).x;
01218   }
01219   
01220   _aretes.push_back(a);
01221   int const n = numberOfEdges() - 1;
01222 
01223   ConnectStart (st, n);
01224   ConnectEnd (en, n);
01225   if (_has_edges_data)
01226     {
01227       eData[n].weight = 1;
01228       eData[n].rdx = getEdge(n).dx;
01229     }
01230   if (_has_sweep_src_data)
01231     {
01232       swsData[n].misc = NULL;
01233       swsData[n].firstLinkedPoint = -1;
01234     }
01235   if (_has_back_data)
01236     {
01237       ebData[n].pathID = -1;
01238       ebData[n].pieceID = -1;
01239       ebData[n].tSt = ebData[n].tEn = 0;
01240     }
01241   if (_has_voronoi_data)
01242     {
01243       voreData[n].leF = leF;
01244       voreData[n].riF = riF;
01245     }
01246   _need_edges_sorting = true;
01247   return n;
01248 }

int Shape::AddEdge ( int  st,
int  en 
)

Definition at line 1112 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _has_voronoi_data, _need_edges_sorting, org::w3c::dom::svg::a, ConnectEnd(), ConnectStart(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), getPoint(), maxAr, n, Shape::dg_arete::nextE, Shape::dg_arete::nextS, NULL, numberOfEdges(), Point, Shape::dg_arete::prevE, Shape::dg_arete::prevS, shape_graph, Shape::dg_arete::st, swdData, swrData, swsData, type, voreData, and Shape::dg_point::x.

Referenced by Booleen(), Path::DoButt(), DoEdgeTo(), Path::DoJoin(), Path::DoLeftJoin(), Path::DoRightJoin(), Path::DoStroke(), Path::Fill(), MakeOffset(), MakeTweak(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Path::RecRound(), and Path::Stroke().

01113 {
01114   if (st == en)
01115     return -1;
01116   if (st < 0 || en < 0)
01117     return -1;
01118   type = shape_graph;
01119   if (numberOfEdges() >= maxAr)
01120     {
01121       maxAr = 2 * numberOfEdges() + 1;
01122       if (_has_edges_data)
01123         eData.resize(maxAr);
01124       if (_has_sweep_src_data)
01125         swsData.resize(maxAr);
01126       if (_has_sweep_dest_data)
01127         swdData.resize(maxAr);
01128       if (_has_raster_data)
01129         swrData.resize(maxAr);
01130       if (_has_back_data)
01131         ebData.resize(maxAr);
01132       if (_has_voronoi_data)
01133         voreData.resize(maxAr);
01134     }
01135 
01136   dg_arete a;
01137   a.dx = Geom::Point(0, 0);
01138   a.st = a.en = -1;
01139   a.prevS = a.nextS = -1;
01140   a.prevE = a.nextE = -1;
01141   if (st >= 0 && en >= 0) {
01142     a.dx = getPoint(en).x - getPoint(st).x;
01143   }
01144 
01145   _aretes.push_back(a);
01146   int const n = numberOfEdges() - 1;
01147   
01148   ConnectStart (st, n);
01149   ConnectEnd (en, n);
01150   if (_has_edges_data)
01151     {
01152       eData[n].weight = 1;
01153       eData[n].rdx = getEdge(n).dx;
01154     }
01155   if (_has_sweep_src_data)
01156     {
01157       swsData[n].misc = NULL;
01158       swsData[n].firstLinkedPoint = -1;
01159     }
01160   if (_has_back_data)
01161     {
01162       ebData[n].pathID = -1;
01163       ebData[n].pieceID = -1;
01164       ebData[n].tSt = ebData[n].tEn = 0;
01165     }
01166   if (_has_voronoi_data)
01167     {
01168       voreData[n].leF = -1;
01169       voreData[n].riF = -1;
01170     }
01171   _need_edges_sorting = true;
01172   return n;
01173 }

int Shape::AddPoint ( const Geom::Point  x  ) 

Definition at line 312 of file Shape.cpp.

References _has_points_data, _has_voronoi_data, _need_points_sorting, _pts, Shape::dg_point::dI, Shape::dg_point::dO, FIRST, Shape::dg_point::incidentEdge, LAST, maxPt, n, NULL, numberOfPoints(), Shape::dg_point::oldDegree, uniconv-ext::p, pData, Round(), vorpData, and Shape::dg_point::x.

Referenced by Booleen(), ConvertToShape(), Path::DoButt(), Path::DoJoin(), Path::DoLeftJoin(), Path::DoRightJoin(), Path::Fill(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), and Path::RecRound().

00313 {
00314   if (numberOfPoints() >= maxPt)
00315     {
00316       maxPt = 2 * numberOfPoints() + 1;
00317       if (_has_points_data)
00318         pData.resize(maxPt);
00319       if (_has_voronoi_data)
00320         vorpData.resize(maxPt);
00321     }
00322 
00323   dg_point p;
00324   p.x = x;
00325   p.dI = p.dO = 0;
00326   p.incidentEdge[FIRST] = p.incidentEdge[LAST] = -1;
00327   p.oldDegree = -1;
00328   _pts.push_back(p);
00329   int const n = _pts.size() - 1;
00330 
00331   if (_has_points_data)
00332     {
00333       pData[n].pending = 0;
00334       pData[n].edgeOnLeft = -1;
00335       pData[n].nextLinkedPoint = -1;
00336       pData[n].askForWindingS = NULL;
00337       pData[n].askForWindingB = -1;
00338       pData[n].rx[0] = Round(p.x[0]);
00339       pData[n].rx[1] = Round(p.x[1]);
00340     }
00341   if (_has_voronoi_data)
00342     {
00343       vorpData[n].value = 0.0;
00344       vorpData[n].winding = -2;
00345     }
00346   _need_points_sorting = true;
00347 
00348   return n;
00349 }

void Shape::Affiche ( void   ) 

Definition at line 54 of file Shape.cpp.

References _aretes, _pts, Barcode::Code39Ext::i, and voronoi::x.

00055 {
00056   printf("sh=%p nbPt=%i nbAr=%i\n", this, static_cast<int>(_pts.size()), static_cast<int>(_aretes.size())); // localizing ok
00057   for (unsigned int i=0; i<_pts.size(); i++) {
00058     printf("pt %i : x=(%f %f) dI=%i dO=%i\n",i, _pts[i].x[0], _pts[i].x[1], _pts[i].dI, _pts[i].dO); // localizing ok
00059   }
00060   for (unsigned int i=0; i<_aretes.size(); i++) {
00061     printf("ar %i : dx=(%f %f) st=%i en=%i\n",i, _aretes[i].dx[0], _aretes[i].dx[1], _aretes[i].st, _aretes[i].en); // localizing ok
00062   }
00063 }

void Shape::AssembleAretes ( FillRule  directed = fill_nonZero  )  [private]

Definition at line 2180 of file ShapeSweep.cpp.

References _aretes, _has_back_data, DisconnectEnd(), DisconnectStart(), ebData, eData, fill_justDont, fill_nonZero, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, Inverse(), LAST, NextAt(), numberOfEdges(), numberOfPoints(), Other(), pData, SwapEdges(), swsData, and Shape::dg_point::totalDegree().

Referenced by Booleen(), and ConvertToShape().

02181 {
02182   if ( directed == fill_justDont && _has_back_data == false ) {
02183     directed=fill_nonZero;
02184   }
02185   
02186   for (int i = 0; i < numberOfPoints(); i++) {
02187     if (getPoint(i).totalDegree() == 2) {
02188       int cb, cc;
02189       cb = getPoint(i).incidentEdge[FIRST];
02190       cc = getPoint(i).incidentEdge[LAST];
02191       bool  doublon=false;
02192       if ((getEdge(cb).st == getEdge(cc).st && getEdge(cb).en == getEdge(cc).en)
02193           || (getEdge(cb).st == getEdge(cc).en && getEdge(cb).en == getEdge(cc).en)) doublon=true;
02194       if ( directed == fill_justDont ) {
02195         if ( doublon ) {
02196           if ( ebData[cb].pathID > ebData[cc].pathID ) {
02197             cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
02198             cb = getPoint(i).incidentEdge[LAST];
02199           } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
02200             if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
02201               cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
02202               cb = getPoint(i).incidentEdge[LAST];
02203             } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) { 
02204               if ( ebData[cb].tSt > ebData[cc].tSt ) {
02205                 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
02206                 cb = getPoint(i).incidentEdge[LAST];
02207               }
02208             }
02209           }
02210         }
02211         if ( doublon ) eData[cc].weight = 0;
02212       } else {
02213       }
02214       if ( doublon ) {
02215         if (getEdge(cb).st == getEdge(cc).st) {
02216           eData[cb].weight += eData[cc].weight;
02217         } else {
02218           eData[cb].weight -= eData[cc].weight;
02219         }
02220           eData[cc].weight = 0;
02221         
02222           if (swsData[cc].firstLinkedPoint >= 0) {
02223           int cp = swsData[cc].firstLinkedPoint;
02224           while (cp >= 0) {
02225             pData[cp].askForWindingB = cb;
02226             cp = pData[cp].nextLinkedPoint;
02227           }
02228           if (swsData[cb].firstLinkedPoint < 0) {
02229             swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
02230           } else {
02231             int ncp = swsData[cb].firstLinkedPoint;
02232             while (pData[ncp].nextLinkedPoint >= 0) {
02233               ncp = pData[ncp].nextLinkedPoint;
02234             }
02235             pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
02236           }
02237         }
02238         
02239           DisconnectStart (cc);
02240           DisconnectEnd (cc);
02241           if (numberOfEdges() > 1) {
02242           int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
02243           while (cp >= 0) {
02244             pData[cp].askForWindingB = cc;
02245             cp = pData[cp].nextLinkedPoint;
02246           }
02247         }
02248           SwapEdges (cc, numberOfEdges() - 1);
02249           if (cb == numberOfEdges() - 1) {
02250           cb = cc;
02251         }
02252           _aretes.pop_back();
02253         }
02254     } else {
02255       int cb;
02256       cb = getPoint(i).incidentEdge[FIRST];
02257       while (cb >= 0 && cb < numberOfEdges()) {
02258           int other = Other (i, cb);
02259           int cc;
02260           cc = getPoint(i).incidentEdge[FIRST];
02261           while (cc >= 0 && cc < numberOfEdges()) {
02262           int ncc = NextAt (i, cc);
02263           bool  doublon=false;
02264           if (cc != cb && Other (i, cc) == other ) doublon=true;
02265           if ( directed == fill_justDont ) {
02266             if ( doublon ) {
02267               if ( ebData[cb].pathID > ebData[cc].pathID ) {
02268                 doublon=false;
02269               } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
02270                 if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
02271                   doublon=false;
02272                 } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) { 
02273                   if ( ebData[cb].tSt > ebData[cc].tSt ) {
02274                     doublon=false;
02275                   }
02276                 }
02277               }
02278             }
02279             if ( doublon ) eData[cc].weight = 0;
02280           } else {
02281           }
02282           if ( doublon ) {
02283 //            if (cc != cb && Other (i, cc) == other) {
02284             // doublon
02285             if (getEdge(cb).st == getEdge(cc).st) {
02286               eData[cb].weight += eData[cc].weight;
02287             } else {
02288               eData[cb].weight -= eData[cc].weight;
02289             }
02290             eData[cc].weight = 0;
02291             
02292             if (swsData[cc].firstLinkedPoint >= 0) {
02293               int cp = swsData[cc].firstLinkedPoint;
02294               while (cp >= 0) {
02295                 pData[cp].askForWindingB = cb;
02296                 cp = pData[cp].nextLinkedPoint;
02297               }
02298               if (swsData[cb].firstLinkedPoint < 0) {
02299                 swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
02300               } else {
02301                 int ncp = swsData[cb].firstLinkedPoint;
02302                 while (pData[ncp].nextLinkedPoint >= 0) {
02303                   ncp = pData[ncp].nextLinkedPoint;
02304                 }
02305                 pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
02306               }
02307             }
02308             
02309             DisconnectStart (cc);
02310             DisconnectEnd (cc);
02311             if (numberOfEdges() > 1) {
02312               int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
02313               while (cp >= 0) {
02314                 pData[cp].askForWindingB = cc;
02315                 cp = pData[cp].nextLinkedPoint;
02316               }
02317             }
02318             SwapEdges (cc, numberOfEdges() - 1);
02319             if (cb == numberOfEdges() - 1) {
02320               cb = cc;
02321             }
02322             if (ncc == numberOfEdges() - 1) {
02323               ncc = cc;
02324             }
02325         _aretes.pop_back();
02326           }
02327           cc = ncc;
02328         }
02329           cb = NextAt (i, cb);
02330         }
02331     }
02332   }
02333   
02334   if ( directed == fill_justDont ) {
02335     for (int i = 0; i < numberOfEdges(); i++)  {
02336       if (eData[i].weight == 0) {
02337 //        SubEdge(i);
02338  //       i--;
02339       } else {
02340         if (eData[i].weight < 0) Inverse (i);
02341       }
02342     }
02343   } else {
02344     for (int i = 0; i < numberOfEdges(); i++)  {
02345       if (eData[i].weight == 0) {
02346         //                      SubEdge(i);
02347         //                      i--;
02348       } else {
02349         if (eData[i].weight < 0) Inverse (i);
02350       }
02351     }
02352   }
02353 }

int Shape::AssemblePoints ( int  st,
int  en 
) [private]

Definition at line 2114 of file ShapeSweep.cpp.

References _pts, getPoint(), Barcode::Code39Ext::i, NULL, pData, SortPointsByOldInd(), Shape::dg_point::x, and voronoi::x.

02115 {
02116   if (en > st) {
02117    for (int i = st; i < en; i++) pData[i].oldInd = i;
02118 //              SortPoints(st,en-1);
02119     SortPointsByOldInd (st, en - 1); // SortPointsByOldInd() is required here, because of the edges we have
02120                                        // associated with the point for later computation of winding numbers.
02121                                        // specifically, we need the first point we treated, it's the only one with a valid
02122                                        // associated edge (man, that was a nice bug).
02123      for (int i = st; i < en; i++) pData[pData[i].oldInd].newInd = i;
02124 
02125      int lastI = st;
02126      for (int i = st; i < en; i++) {
02127           pData[i].pending = lastI++;
02128           if (i > st && getPoint(i - 1).x[0] == getPoint(i).x[0] && getPoint(i - 1).x[1] == getPoint(i).x[1]) {
02129             pData[i].pending = pData[i - 1].pending;
02130             if (pData[pData[i].pending].askForWindingS == NULL) {
02131                 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
02132                 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
02133               } else {
02134                 if (pData[pData[i].pending].askForWindingS == pData[i].askForWindingS
02135               && pData[pData[i].pending].askForWindingB == pData[i].askForWindingB) {
02136               // meme bord, c bon
02137                 } else {
02138               // meme point, mais pas le meme bord: ouille!
02139               // il faut prendre le bord le plus a gauche
02140               // en pratique, n'arrive que si 2 maxima sont dans la meme case -> le mauvais choix prend une arete incidente 
02141               // au bon choix
02142 //                                              printf("doh");
02143                 }
02144               }
02145             lastI--;
02146           } else {
02147             if (i > pData[i].pending) {
02148                 _pts[pData[i].pending].x = getPoint(i).x;
02149                 pData[pData[i].pending].rx = getPoint(i).x;
02150                 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
02151                 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
02152               }
02153           }
02154         }
02155       for (int i = st; i < en; i++) pData[i].newInd = pData[pData[i].newInd].pending;
02156       return lastI;
02157   }
02158   return en;
02159 }

void Shape::AssemblePoints ( Shape *  a  )  [private]

Definition at line 2162 of file ShapeSweep.cpp.

References _pts, hasPoints(), Barcode::Code39Ext::i, iData, nbInc, numberOfEdges(), numberOfPoints(), pData, and swsData.

Referenced by Booleen(), and ConvertToShape().

02163 {
02164   if (hasPoints())
02165     {
02166       int lastI = AssemblePoints (0, numberOfPoints());
02167 
02168       for (int i = 0; i < a->numberOfEdges(); i++)
02169     {
02170       a->swsData[i].stPt = pData[a->swsData[i].stPt].newInd;
02171       a->swsData[i].enPt = pData[a->swsData[i].enPt].newInd;
02172     }
02173       for (int i = 0; i < nbInc; i++)
02174     iData[i].pt = pData[iData[i].pt].newInd;
02175 
02176       _pts.resize(lastI);
02177     }
02178 }

void Shape::Avance ( int  lastPointNo,
int  lastChgtPt,
Shape *  iS,
int  iB,
Shape *  a,
Shape *  b,
BooleanOp  mod 
) [private]

Definition at line 3114 of file ShapeSweep.cpp.

References bool_op_diff, bool_op_symdiff, DoEdgeTo(), eData, getPoint(), HalfRound(), numberOfPoints(), uniconv-ext::p, swsData, and voronoi::x.

Referenced by CheckEdges().

03116 {
03117   double dd = HalfRound (1);
03118   bool avoidDiag = false;
03119 //      if ( lastChgtPt > 0 && pts[lastChgtPt-1].y+dd == pts[lastChgtPt].y ) avoidDiag=true;
03120 
03121   bool direct = true;
03122   if (lS == b && (mod == bool_op_diff || mod == bool_op_symdiff))
03123     direct = false;
03124   int lftN = lS->swsData[lB].leftRnd;
03125   int rgtN = lS->swsData[lB].rightRnd;
03126   if (lS->swsData[lB].doneTo < lastChgtPt)
03127     {
03128       int lp = lS->swsData[lB].curPoint;
03129       if (lp >= 0 && getPoint(lp).x[1] + dd == getPoint(lastChgtPt).x[1])
03130     avoidDiag = true;
03131       if (lS->eData[lB].rdx[1] == 0)
03132     {
03133       // tjs de gauche a droite et pas de diagonale
03134       if (lS->eData[lB].rdx[0] >= 0)
03135         {
03136           for (int p = lftN; p <= rgtN; p++)
03137         {
03138           DoEdgeTo (lS, lB, p, direct, true);
03139           lp = p;
03140         }
03141         }
03142       else
03143         {
03144           for (int p = lftN; p <= rgtN; p++)
03145         {
03146           DoEdgeTo (lS, lB, p, direct, false);
03147           lp = p;
03148         }
03149         }
03150     }
03151       else if (lS->eData[lB].rdx[1] > 0)
03152     {
03153       if (lS->eData[lB].rdx[0] >= 0)
03154         {
03155 
03156           for (int p = lftN; p <= rgtN; p++)
03157         {
03158           if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
03159             {
03160               if (lftN > 0 && lftN - 1 >= lastChgtPt
03161               && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
03162             {
03163               DoEdgeTo (lS, lB, lftN - 1, direct, true);
03164               DoEdgeTo (lS, lB, lftN, direct, true);
03165             }
03166               else
03167             {
03168               DoEdgeTo (lS, lB, lftN, direct, true);
03169             }
03170             }
03171           else
03172             {
03173               DoEdgeTo (lS, lB, p, direct, true);
03174             }
03175           lp = p;
03176         }
03177         }
03178       else
03179         {
03180 
03181           for (int p = rgtN; p >= lftN; p--)
03182         {
03183           if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
03184             {
03185               if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
03186               && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
03187             {
03188               DoEdgeTo (lS, lB, rgtN + 1, direct, true);
03189               DoEdgeTo (lS, lB, rgtN, direct, true);
03190             }
03191               else
03192             {
03193               DoEdgeTo (lS, lB, rgtN, direct, true);
03194             }
03195             }
03196           else
03197             {
03198               DoEdgeTo (lS, lB, p, direct, true);
03199             }
03200           lp = p;
03201         }
03202         }
03203     }
03204       else
03205     {
03206       if (lS->eData[lB].rdx[0] >= 0)
03207         {
03208 
03209           for (int p = rgtN; p >= lftN; p--)
03210         {
03211           if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
03212             {
03213               if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
03214               && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
03215             {
03216               DoEdgeTo (lS, lB, rgtN + 1, direct, false);
03217               DoEdgeTo (lS, lB, rgtN, direct, false);
03218             }
03219               else
03220             {
03221               DoEdgeTo (lS, lB, rgtN, direct, false);
03222             }
03223             }
03224           else
03225             {
03226               DoEdgeTo (lS, lB, p, direct, false);
03227             }
03228           lp = p;
03229         }
03230         }
03231       else
03232         {
03233 
03234           for (int p = lftN; p <= rgtN; p++)
03235         {
03236           if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
03237             {
03238               if (lftN > 0 && lftN - 1 >= lastChgtPt
03239               && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
03240             {
03241               DoEdgeTo (lS, lB, lftN - 1, direct, false);
03242               DoEdgeTo (lS, lB, lftN, direct, false);
03243             }
03244               else
03245             {
03246               DoEdgeTo (lS, lB, lftN, direct, false);
03247             }
03248             }
03249           else
03250             {
03251               DoEdgeTo (lS, lB, p, direct, false);
03252             }
03253           lp = p;
03254         }
03255         }
03256     }
03257       lS->swsData[lB].curPoint = lp;
03258     }
03259   lS->swsData[lB].doneTo = lastPointNo - 1;
03260 }

void Shape::AvanceEdge ( int  no,
float  to,
AlphaLigne *  line,
bool  exact,
float  step 
) [private]

Definition at line 1885 of file ShapeRaster.cpp.

References AlphaLigne::AddBord(), AvanceEdge(), and swrData.

01886 {
01887     AvanceEdge(no,to,exact,step);
01888 
01889     if ( swrData[no].sens ) {
01890         
01891         if ( swrData[no].curX <= swrData[no].lastX ) {
01892             
01893             line->AddBord(swrData[no].curX,
01894                           0,
01895                           swrData[no].lastX,
01896                           swrData[no].curY - swrData[no].lastY,
01897                           -swrData[no].dydx);
01898             
01899         } else if ( swrData[no].curX > swrData[no].lastX ) {
01900             
01901             line->AddBord(swrData[no].lastX,
01902                           0,
01903                           swrData[no].curX,
01904                           swrData[no].curY - swrData[no].lastY,
01905                           swrData[no].dydx);
01906         }
01907         
01908     } else {
01909         
01910         if ( swrData[no].curX <= swrData[no].lastX ) {
01911             
01912             line->AddBord(swrData[no].curX,
01913                           0,
01914                           swrData[no].lastX,
01915                           swrData[no].lastY - swrData[no].curY,
01916                           swrData[no].dydx);
01917             
01918         } else if ( swrData[no].curX > swrData[no].lastX ) {
01919             
01920             line->AddBord(swrData[no].lastX,
01921                           0,
01922                           swrData[no].curX,
01923                           swrData[no].lastY - swrData[no].curY,
01924                           -swrData[no].dydx);
01925         }
01926     }
01927 }

void Shape::AvanceEdge ( int  no,
float  to,
BitLigne *  line,
bool  exact,
float  step 
) [private]

Definition at line 1813 of file ShapeRaster.cpp.

References BitLigne::AddBord(), AvanceEdge(), and swrData.

01814 {
01815     AvanceEdge(no, to, exact, step);
01816 
01817     if ( swrData[no].sens ) {
01818         
01819         if ( swrData[no].curX < swrData[no].lastX ) {
01820             
01821             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
01822             
01823         } else if ( swrData[no].curX > swrData[no].lastX ) {
01824             
01825             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
01826         }
01827 
01828     } else {
01829         
01830         if ( swrData[no].curX < swrData[no].lastX ) {
01831             
01832             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
01833             
01834         } else if ( swrData[no].curX > swrData[no].lastX ) {
01835             
01836             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
01837         }
01838     }
01839 }

void Shape::AvanceEdge ( int  no,
float  to,
FloatLigne *  line,
bool  exact,
float  step 
) [private]

Definition at line 1736 of file ShapeRaster.cpp.

References FloatLigne::AddBord(), FloatLigne::AddBordR(), AvanceEdge(), and swrData.

01737 {
01738     AvanceEdge(no,to,exact,step);
01739 
01740     if ( swrData[no].sens ) {
01741         
01742         if ( swrData[no].curX < swrData[no].lastX ) {
01743             
01744             swrData[no].guess = line->AddBordR(swrData[no].curX,
01745                                                to - swrData[no].curY,
01746                                                swrData[no].lastX,
01747                                                to - swrData[no].lastY,
01748                                                -swrData[no].dydx,
01749                                                swrData[no].guess);
01750             
01751         } else if ( swrData[no].curX > swrData[no].lastX ) {
01752             
01753             swrData[no].guess = line->AddBord(swrData[no].lastX,
01754                                               -(to - swrData[no].lastY),
01755                                               swrData[no].curX,
01756                                               -(to - swrData[no].curY),
01757                                               swrData[no].dydx,
01758                                               swrData[no].guess);
01759         }
01760         
01761     } else {
01762 
01763         if ( swrData[no].curX < swrData[no].lastX ) {
01764 
01765             swrData[no].guess = line->AddBordR(swrData[no].curX,
01766                                                -(to - swrData[no].curY),
01767                                                swrData[no].lastX,
01768                                                -(to - swrData[no].lastY),
01769                                                swrData[no].dydx,
01770                                                swrData[no].guess);
01771             
01772         } else if ( swrData[no].curX > swrData[no].lastX ) {
01773             
01774             swrData[no].guess = line->AddBord(swrData[no].lastX,
01775                                               to - swrData[no].lastY,
01776                                               swrData[no].curX,
01777                                               to - swrData[no].curY,
01778                                               -swrData[no].dydx,
01779                                               swrData[no].guess);
01780         }
01781     }
01782 }

void Shape::AvanceEdge ( int  no,
float  to,
bool  exact,
float  step 
) [private]

Definition at line 1656 of file ShapeRaster.cpp.

References Shape::dg_arete::dx, getEdge(), getPoint(), swrData, and Shape::dg_point::x.

Referenced by AvanceEdge(), DirectQuickScan(), DirectScan(), QuickScan(), and Scan().

01657 {
01658     if ( exact ) {
01659         Geom::Point dir;
01660         Geom::Point stp;
01661         if ( swrData[no].sens ) {
01662             stp = getPoint(getEdge(no).st).x;
01663             dir = getEdge(no).dx;
01664         } else {
01665             stp = getPoint(getEdge(no).en).x;
01666             dir = -getEdge(no).dx;
01667         }
01668         
01669         if ( fabs(dir[1]) < 0.000001 ) {
01670             swrData[no].calcX = stp[0] + dir[0];
01671         } else {
01672             swrData[no].calcX = stp[0] + ((to - stp[1]) * dir[0]) / dir[1];
01673         }
01674     } else {
01675         swrData[no].calcX += step * swrData[no].dxdy;
01676     }
01677     
01678     swrData[no].lastX = swrData[no].curX;
01679     swrData[no].lastY = swrData[no].curY;
01680     swrData[no].curX = swrData[no].calcX;
01681     swrData[no].curY = to;
01682 }

void Shape::BeginQuickRaster ( float &  pos,
int &  curPt 
)

Definition at line 78 of file ShapeRaster.cpp.

References eData, Shape::dg_arete::en, firstQRas, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::quick_raster_data::ind, initialisePointData(), lastQRas, MakeEdgeData(), MakePointData(), MakeQuickRasterData(), MakeRasterData(), nbQRas, NULL, numberOfEdges(), numberOfPoints(), pData, qrsData, SortPoints(), Shape::dg_arete::st, swrData, and Shape::dg_point::x.

Referenced by raster_glyph::LoadSubPixelPosition(), and nr_pixblock_render_shape_mask_or().

00079 {
00080     if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
00081         curPt = 0;
00082         pos = 0;
00083         return;
00084     }
00085     
00086     MakeRasterData(true);
00087     MakeQuickRasterData(true);
00088     nbQRas = 0;
00089     firstQRas = lastQRas = -1;
00090     MakePointData(true);
00091     MakeEdgeData(true);
00092 
00093     curPt = 0;
00094     pos = getPoint(0).x[1] - 1.0;
00095 
00096     initialisePointData();
00097     
00098     for (int i=0;i<numberOfEdges();i++) {
00099         swrData[i].misc = NULL;
00100         qrsData[i].ind = -1;
00101         eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
00102     }
00103     
00104     SortPoints();
00105 //  SortPointsRounded();
00106 }

void Shape::BeginRaster ( float &  pos,
int &  curPt 
)

Definition at line 26 of file ShapeRaster.cpp.

References eData, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, MakeEdgeData(), MakePointData(), MakeRasterData(), NULL, numberOfEdges(), numberOfPoints(), pData, sEvts, SortPoints(), Shape::dg_arete::st, sTree, SweepEventQueue, swrData, and Shape::dg_point::x.

Referenced by Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker().

00027 {
00028     if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
00029         curPt = 0;
00030         pos = 0;
00031         return;
00032     }
00033     
00034     MakeRasterData(true);
00035     MakePointData(true);
00036     MakeEdgeData(true);
00037 
00038     if (sTree == NULL) {
00039         sTree = new SweepTreeList(numberOfEdges());
00040     }
00041     if (sEvts == NULL) {
00042         sEvts = new SweepEventQueue(numberOfEdges());
00043     }
00044 
00045     SortPoints();
00046 
00047     curPt = 0;
00048     pos = getPoint(0).x[1] - 1.0;
00049 
00050     for (int i = 0; i < numberOfPoints(); i++) {
00051         pData[i].pending = 0;
00052         pData[i].edgeOnLeft = -1;
00053         pData[i].nextLinkedPoint = -1;
00054         pData[i].rx[0] = /*Round(*/getPoint(i).x[0]/*)*/;
00055         pData[i].rx[1] = /*Round(*/getPoint(i).x[1]/*)*/;
00056     }
00057 
00058     for (int i = 0;i < numberOfEdges(); i++) {
00059         swrData[i].misc = NULL;
00060         eData[i].rdx=pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
00061     }
00062 }

int Shape::Booleen ( Shape *  a,
Shape *  b,
BooleanOp  mod,
int  cutPathID = -1 
)

Definition at line 840 of file ShapeSweep.cpp.

References _aretes, _need_edges_sorting, _pts, SweepTreeList::add(), AddChgt(), AddEdge(), AddPoint(), AssembleAretes(), AssemblePoints(), bool_op_cut, bool_op_diff, bool_op_inters, bool_op_slice, bool_op_symdiff, bool_op_union, SweepTree::bord, CheckAdjacencies(), CheckEdges(), chgts, CleanupSweep(), clearIncidenceData(), SweepTree::ConvertTo(), Shape::dg_point::dI, directedEulerian(), Shape::dg_point::dO, ebData, eData, EDGE_INSERTED, EDGE_REMOVED, AVLTree::elem, Shape::dg_arete::en, SweepEventQueue::extract(), fill_justDont, FIRST, getEdge(), getPoint(), GetWindings(), hasBackData(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, initialiseEdgeData(), initialisePointData(), SweepTree::Insert(), SweepTree::InsertAt(), INTERSECTION, Inverse(), LEFT, MakeBackData(), MakeEdgeData(), MakePointData(), MakeSweepDestData(), MakeSweepSrcData(), NextAt(), NULL, numberOfEdges(), numberOfPoints(), pData, SweepEventQueue::peek(), SweepTree::Remove(), SweepTree::RemoveEvent(), SweepTree::RemoveEvents(), Reset(), ResetSweep(), RIGHT, Round(), sEvts, shape_euler_err, shape_input_err, shape_polygon, SweepEventQueue::size(), SortPointsRounded(), SweepTree::src, Shape::dg_arete::st, sTree, SubEdge(), SwapEdges(), SweepTree::SwapWithRight(), swdData, SweepEventQueue, swsData, TesteIntersection(), Shape::dg_point::totalDegree(), and type.

Referenced by SPFlowtext::_buildExclusionShape(), sp_selected_path_boolop(), and UnionShape().

00841 {
00842   if (a == b || a == NULL || b == NULL)
00843     return shape_input_err;
00844   Reset (0, 0);
00845   if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
00846     return 0;
00847   if (b->numberOfPoints() <= 1 || b->numberOfEdges() <= 1)
00848     return 0;
00849   if ( mod == bool_op_cut ) {
00850   } else if ( mod == bool_op_slice ) {
00851   } else {
00852     if (a->type != shape_polygon)
00853       return shape_input_err;
00854     if (b->type != shape_polygon)
00855       return shape_input_err;
00856   }
00857 
00858   a->ResetSweep ();
00859   b->ResetSweep ();
00860 
00861   if (sTree == NULL) {
00862       sTree = new SweepTreeList(a->numberOfEdges() + b->numberOfEdges());
00863   }
00864   if (sEvts == NULL) {
00865       sEvts = new SweepEventQueue(a->numberOfEdges() + b->numberOfEdges());
00866   }
00867   
00868   MakePointData (true);
00869   MakeEdgeData (true);
00870   MakeSweepSrcData (true);
00871   MakeSweepDestData (true);
00872   if (a->hasBackData () && b->hasBackData ())
00873     {
00874       MakeBackData (true);
00875     }
00876   else
00877     {
00878       MakeBackData (false);
00879     }
00880 
00881   a->initialisePointData();
00882   b->initialisePointData();
00883 
00884   a->initialiseEdgeData();
00885   b->initialiseEdgeData();
00886 
00887   a->SortPointsRounded ();
00888   b->SortPointsRounded ();
00889 
00890   chgts.clear();
00891 
00892   double lastChange =
00893     (a->pData[0].rx[1] <
00894      b->pData[0].rx[1]) ? a->pData[0].rx[1] - 1.0 : b->pData[0].rx[1] - 1.0;
00895   int lastChgtPt = 0;
00896   int edgeHead = -1;
00897   Shape *shapeHead = NULL;
00898 
00899   clearIncidenceData();
00900 
00901   int curAPt = 0;
00902   int curBPt = 0;
00903 
00904   while (curAPt < a->numberOfPoints() || curBPt < b->numberOfPoints() || sEvts->size() > 0)
00905     {
00906 /*      for (int i=0;i<sEvts.nbEvt;i++) {
00907             printf("%f %f %i %i\n",sEvts.events[i].posx,sEvts.events[i].posy,sEvts.events[i].leftSweep->bord,sEvts.events[i].rightSweep->bord); // localizing ok
00908         }
00909         //      cout << endl;
00910         if ( sTree.racine ) {
00911             SweepTree*  ct=static_cast <SweepTree*> (sTree.racine->Leftmost());
00912             while ( ct ) {
00913                 printf("%i %i [%i\n",ct->bord,ct->startPoint,(ct->src==a)?1:0);
00914                 ct=static_cast <SweepTree*> (ct->elem[RIGHT]);
00915             }
00916         }
00917         printf("\n");*/
00918 
00919     Geom::Point ptX;
00920       double ptL, ptR;
00921       SweepTree *intersL = NULL;
00922       SweepTree *intersR = NULL;
00923       int nPt = -1;
00924       Shape *ptSh = NULL;
00925       bool isIntersection = false;
00926 
00927       if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
00928     {
00929       if (curAPt < a->numberOfPoints())
00930         {
00931           if (curBPt < b->numberOfPoints())
00932         {
00933           if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
00934               || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
00935               && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
00936             {
00937               if (a->pData[curAPt].pending > 0
00938               || (a->pData[curAPt].rx[1] > ptX[1]
00939                   || (a->pData[curAPt].rx[1] == ptX[1]
00940                   && a->pData[curAPt].rx[0] > ptX[0])))
00941             {
00942               /* FIXME: could be pop? */
00943               sEvts->extract(intersL, intersR, ptX, ptL, ptR);
00944               isIntersection = true;
00945             }
00946               else
00947             {
00948               nPt = curAPt++;
00949               ptSh = a;
00950               ptX = ptSh->pData[nPt].rx;
00951               isIntersection = false;
00952             }
00953             }
00954           else
00955             {
00956               if (b->pData[curBPt].pending > 0
00957               || (b->pData[curBPt].rx[1] > ptX[1]
00958                   || (b->pData[curBPt].rx[1] == ptX[1]
00959                   && b->pData[curBPt].rx[0] > ptX[0])))
00960             {
00961               /* FIXME: could be pop? */
00962               sEvts->extract(intersL, intersR, ptX, ptL, ptR);
00963               isIntersection = true;
00964             }
00965               else
00966             {
00967               nPt = curBPt++;
00968               ptSh = b;
00969               ptX = ptSh->pData[nPt].rx;
00970               isIntersection = false;
00971             }
00972             }
00973         }
00974           else
00975         {
00976           if (a->pData[curAPt].pending > 0
00977               || (a->pData[curAPt].rx[1] > ptX[1]
00978               || (a->pData[curAPt].rx[1] == ptX[1]
00979                   && a->pData[curAPt].rx[0] > ptX[0])))
00980             {
00981               /* FIXME: could be pop? */
00982               sEvts->extract(intersL, intersR, ptX, ptL, ptR);
00983               isIntersection = true;
00984             }
00985           else
00986             {
00987               nPt = curAPt++;
00988               ptSh = a;
00989               ptX = ptSh->pData[nPt].rx;
00990               isIntersection = false;
00991             }
00992         }
00993         }
00994       else
00995         {
00996           if (b->pData[curBPt].pending > 0
00997           || (b->pData[curBPt].rx[1] > ptX[1]
00998               || (b->pData[curBPt].rx[1] == ptX[1]
00999               && b->pData[curBPt].rx[0] > ptX[0])))
01000         {
01001           /* FIXME: could be pop? */
01002           sEvts->extract(intersL, intersR, ptX,  ptL, ptR);
01003           isIntersection = true;
01004         }
01005           else
01006         {
01007           nPt = curBPt++;
01008           ptSh = b;
01009           ptX = ptSh->pData[nPt].rx;
01010           isIntersection = false;
01011         }
01012         }
01013     }
01014       else
01015     {
01016       if (curAPt < a->numberOfPoints())
01017         {
01018           if (curBPt < b->numberOfPoints())
01019         {
01020           if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
01021               || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
01022               && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
01023             {
01024               nPt = curAPt++;
01025               ptSh = a;
01026             }
01027           else
01028             {
01029               nPt = curBPt++;
01030               ptSh = b;
01031             }
01032         }
01033           else
01034         {
01035           nPt = curAPt++;
01036           ptSh = a;
01037         }
01038         }
01039       else
01040         {
01041           nPt = curBPt++;
01042           ptSh = b;
01043         }
01044       ptX = ptSh->pData[nPt].rx;
01045       isIntersection = false;
01046     }
01047 
01048       if (isIntersection == false)
01049     {
01050       if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
01051         continue;
01052     }
01053 
01054       Geom::Point rPtX;
01055       rPtX[0]= Round (ptX[0]);
01056       rPtX[1]= Round (ptX[1]);
01057       int lastPointNo = -1;
01058       lastPointNo = AddPoint (rPtX);
01059       pData[lastPointNo].rx = rPtX;
01060 
01061       if (rPtX[1] > lastChange)
01062     {
01063       int lastI = AssemblePoints (lastChgtPt, lastPointNo);
01064 
01065 
01066       Shape *curSh = shapeHead;
01067       int curBo = edgeHead;
01068       while (curSh)
01069         {
01070           curSh->swsData[curBo].leftRnd =
01071         pData[curSh->swsData[curBo].leftRnd].newInd;
01072           curSh->swsData[curBo].rightRnd =
01073         pData[curSh->swsData[curBo].rightRnd].newInd;
01074 
01075           Shape *neSh = curSh->swsData[curBo].nextSh;
01076           curBo = curSh->swsData[curBo].nextBo;
01077           curSh = neSh;
01078         }
01079 
01080       for (unsigned int i = 0; i < chgts.size(); i++)
01081         {
01082           chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
01083           if (chgts[i].type == 0)
01084         {
01085           if (chgts[i].src->getEdge(chgts[i].bord).st <
01086               chgts[i].src->getEdge(chgts[i].bord).en)
01087             {
01088               chgts[i].src->swsData[chgts[i].bord].stPt =
01089             chgts[i].ptNo;
01090             }
01091           else
01092             {
01093               chgts[i].src->swsData[chgts[i].bord].enPt =
01094             chgts[i].ptNo;
01095             }
01096         }
01097           else if (chgts[i].type == 1)
01098         {
01099           if (chgts[i].src->getEdge(chgts[i].bord).st >
01100               chgts[i].src->getEdge(chgts[i].bord).en)
01101             {
01102               chgts[i].src->swsData[chgts[i].bord].stPt =
01103             chgts[i].ptNo;
01104             }
01105           else
01106             {
01107               chgts[i].src->swsData[chgts[i].bord].enPt =
01108             chgts[i].ptNo;
01109             }
01110         }
01111         }
01112 
01113       CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
01114 
01115       CheckEdges (lastI, lastChgtPt, a, b, mod);
01116 
01117       for (int i = lastChgtPt; i < lastI; i++)
01118         {
01119           if (pData[i].askForWindingS)
01120         {
01121           Shape *windS = pData[i].askForWindingS;
01122           int windB = pData[i].askForWindingB;
01123           pData[i].nextLinkedPoint =
01124             windS->swsData[windB].firstLinkedPoint;
01125           windS->swsData[windB].firstLinkedPoint = i;
01126         }
01127         }
01128 
01129     if (lastI < lastPointNo)
01130         {
01131           _pts[lastI] = getPoint(lastPointNo);
01132           pData[lastI] = pData[lastPointNo];
01133         }
01134       lastPointNo = lastI;
01135       _pts.resize(lastI + 1);
01136 
01137       lastChgtPt = lastPointNo;
01138       lastChange = rPtX[1];
01139       chgts.clear();
01140       edgeHead = -1;
01141       shapeHead = NULL;
01142     }
01143 
01144 
01145       if (isIntersection)
01146     {
01147       // les 2 events de part et d'autre de l'intersection
01148       // (celui de l'intersection a deja ete depile)
01149       intersL->RemoveEvent (*sEvts, LEFT);
01150       intersR->RemoveEvent (*sEvts, RIGHT);
01151 
01152       AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
01153            intersL->src, intersL->bord, intersR->src, intersR->bord);
01154 
01155       intersL->SwapWithRight (*sTree, *sEvts);
01156 
01157       TesteIntersection (intersL, LEFT, true);
01158       TesteIntersection (intersR, RIGHT, true);
01159     }
01160       else
01161     {
01162       int cb;
01163 
01164       int nbUp = 0, nbDn = 0;
01165       int upNo = -1, dnNo = -1;
01166       cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
01167       while (cb >= 0 && cb < ptSh->numberOfEdges())
01168         {
01169           if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
01170            && nPt == ptSh->getEdge(cb).en)
01171           || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
01172               && nPt == ptSh->getEdge(cb).st))
01173         {
01174           upNo = cb;
01175           nbUp++;
01176         }
01177           if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
01178            && nPt == ptSh->getEdge(cb).en)
01179           || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
01180               && nPt == ptSh->getEdge(cb).st))
01181         {
01182           dnNo = cb;
01183           nbDn++;
01184         }
01185           cb = ptSh->NextAt (nPt, cb);
01186         }
01187 
01188       if (nbDn <= 0)
01189         {
01190           upNo = -1;
01191         }
01192       if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == NULL)
01193         {
01194           upNo = -1;
01195         }
01196 
01197 //                      upNo=-1;
01198 
01199       bool doWinding = true;
01200 
01201       if (nbUp > 0)
01202         {
01203           cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
01204           while (cb >= 0 && cb < ptSh->numberOfEdges())
01205         {
01206           if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
01207                && nPt == ptSh->getEdge(cb).en)
01208               || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
01209               && nPt == ptSh->getEdge(cb).st))
01210             {
01211               if (cb != upNo)
01212             {
01213               SweepTree *node =
01214                 (SweepTree *) ptSh->swsData[cb].misc;
01215               if (node == NULL)
01216                 {
01217                 }
01218               else
01219                 {
01220                   AddChgt (lastPointNo, lastChgtPt, shapeHead,
01221                        edgeHead, EDGE_REMOVED, node->src, node->bord,
01222                        NULL, -1);
01223                   ptSh->swsData[cb].misc = NULL;
01224 
01225                   int onLeftB = -1, onRightB = -1;
01226                   Shape *onLeftS = NULL;
01227                   Shape *onRightS = NULL;
01228                   if (node->elem[LEFT])
01229                 {
01230                   onLeftB =
01231                     (static_cast <
01232                      SweepTree * >(node->elem[LEFT]))->bord;
01233                   onLeftS =
01234                     (static_cast <
01235                      SweepTree * >(node->elem[LEFT]))->src;
01236                 }
01237                   if (node->elem[RIGHT])
01238                 {
01239                   onRightB =
01240                     (static_cast <
01241                      SweepTree * >(node->elem[RIGHT]))->bord;
01242                   onRightS =
01243                     (static_cast <
01244                      SweepTree * >(node->elem[RIGHT]))->src;
01245                 }
01246 
01247                   node->Remove (*sTree, *sEvts, true);
01248                   if (onLeftS && onRightS)
01249                 {
01250                   SweepTree *onLeft =
01251                     (SweepTree *) onLeftS->swsData[onLeftB].
01252                     misc;
01253 //                                                                      SweepTree* onRight=(SweepTree*)onRightS->swsData[onRightB].misc;
01254                   if (onLeftS == ptSh
01255                       && (onLeftS->getEdge(onLeftB).en == nPt
01256                       || onLeftS->getEdge(onLeftB).st ==
01257                       nPt))
01258                     {
01259                     }
01260                   else
01261                     {
01262                       if (onRightS == ptSh
01263                       && (onRightS->getEdge(onRightB).en ==
01264                           nPt
01265                           || onRightS->getEdge(onRightB).
01266                           st == nPt))
01267                     {
01268                     }
01269                       else
01270                     {
01271                       TesteIntersection (onLeft, RIGHT, true);
01272                     }
01273                     }
01274                 }
01275                 }
01276             }
01277             }
01278           cb = ptSh->NextAt (nPt, cb);
01279         }
01280         }
01281 
01282       // traitement du "upNo devient dnNo"
01283       SweepTree *insertionNode = NULL;
01284       if (dnNo >= 0)
01285         {
01286           if (upNo >= 0)
01287         {
01288           SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
01289 
01290           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
01291                node->src, node->bord, NULL, -1);
01292 
01293           ptSh->swsData[upNo].misc = NULL;
01294 
01295           node->RemoveEvents (*sEvts);
01296           node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
01297           ptSh->swsData[dnNo].misc = node;
01298           TesteIntersection (node, RIGHT, true);
01299           TesteIntersection (node, LEFT, true);
01300           insertionNode = node;
01301 
01302           ptSh->swsData[dnNo].curPoint = lastPointNo;
01303 
01304           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
01305                node->src, node->bord, NULL, -1);
01306         }
01307           else
01308         {
01309           SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
01310           ptSh->swsData[dnNo].misc = node;
01311           node->Insert (*sTree, *sEvts, this, lastPointNo, true);
01312 
01313           if (doWinding)
01314             {
01315               SweepTree *myLeft =
01316             static_cast < SweepTree * >(node->elem[LEFT]);
01317               if (myLeft)
01318             {
01319               pData[lastPointNo].askForWindingS = myLeft->src;
01320               pData[lastPointNo].askForWindingB = myLeft->bord;
01321             }
01322               else
01323             {
01324               pData[lastPointNo].askForWindingB = -1;
01325             }
01326               doWinding = false;
01327             }
01328 
01329           TesteIntersection (node, RIGHT, true);
01330           TesteIntersection (node, LEFT, true);
01331           insertionNode = node;
01332 
01333           ptSh->swsData[dnNo].curPoint = lastPointNo;
01334 
01335           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
01336                node->src, node->bord, NULL, -1);
01337         }
01338         }
01339 
01340       if (nbDn > 1)
01341         {           // si nbDn == 1 , alors dnNo a deja ete traite
01342           cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
01343           while (cb >= 0 && cb < ptSh->numberOfEdges())
01344         {
01345           if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
01346                && nPt == ptSh->getEdge(cb).en)
01347               || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
01348               && nPt == ptSh->getEdge(cb).st))
01349             {
01350               if (cb != dnNo)
01351             {
01352               SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
01353               ptSh->swsData[cb].misc = node;
01354 //                                                      node->Insert(sTree,*sEvts,this,lastPointNo,true);
01355               node->InsertAt (*sTree, *sEvts, this, insertionNode,
01356                       nPt, true);
01357 
01358               if (doWinding)
01359                 {
01360                   SweepTree *myLeft =
01361                 static_cast < SweepTree * >(node->elem[LEFT]);
01362                   if (myLeft)
01363                 {
01364                   pData[lastPointNo].askForWindingS =
01365                     myLeft->src;
01366                   pData[lastPointNo].askForWindingB =
01367                     myLeft->bord;
01368                 }
01369                   else
01370                 {
01371                   pData[lastPointNo].askForWindingB = -1;
01372                 }
01373                   doWinding = false;
01374                 }
01375 
01376               TesteIntersection (node, RIGHT, true);
01377               TesteIntersection (node, LEFT, true);
01378 
01379               ptSh->swsData[cb].curPoint = lastPointNo;
01380 
01381               AddChgt (lastPointNo, lastChgtPt, shapeHead,
01382                    edgeHead, EDGE_INSERTED, node->src, node->bord, NULL,
01383                    -1);
01384             }
01385             }
01386           cb = ptSh->NextAt (nPt, cb);
01387         }
01388         }
01389     }
01390     }
01391   {
01392     int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
01393 
01394 
01395     Shape *curSh = shapeHead;
01396     int curBo = edgeHead;
01397     while (curSh)
01398       {
01399     curSh->swsData[curBo].leftRnd =
01400       pData[curSh->swsData[curBo].leftRnd].newInd;
01401     curSh->swsData[curBo].rightRnd =
01402       pData[curSh->swsData[curBo].rightRnd].newInd;
01403 
01404     Shape *neSh = curSh->swsData[curBo].nextSh;
01405     curBo = curSh->swsData[curBo].nextBo;
01406     curSh = neSh;
01407       }
01408 
01409     /* FIXME: this kind of code seems to appear frequently */
01410     for (unsigned int i = 0; i < chgts.size(); i++)
01411       {
01412     chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
01413     if (chgts[i].type == 0)
01414       {
01415         if (chgts[i].src->getEdge(chgts[i].bord).st <
01416         chgts[i].src->getEdge(chgts[i].bord).en)
01417           {
01418         chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
01419           }
01420         else
01421           {
01422         chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
01423           }
01424       }
01425     else if (chgts[i].type == 1)
01426       {
01427         if (chgts[i].src->getEdge(chgts[i].bord).st >
01428         chgts[i].src->getEdge(chgts[i].bord).en)
01429           {
01430         chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
01431           }
01432         else
01433           {
01434         chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
01435           }
01436       }
01437       }
01438 
01439     CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
01440 
01441     CheckEdges (lastI, lastChgtPt, a, b, mod);
01442 
01443     for (int i = lastChgtPt; i < lastI; i++)
01444       {
01445     if (pData[i].askForWindingS)
01446       {
01447         Shape *windS = pData[i].askForWindingS;
01448         int windB = pData[i].askForWindingB;
01449         pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
01450         windS->swsData[windB].firstLinkedPoint = i;
01451       }
01452       }
01453 
01454     _pts.resize(lastI);
01455 
01456     edgeHead = -1;
01457     shapeHead = NULL;
01458   }
01459 
01460   chgts.clear();
01461   clearIncidenceData();
01462 
01463 //      Plot(190,70,6,400,400,true,false,true,true);
01464 
01465   if ( mod == bool_op_cut ) {
01466     AssembleAretes (fill_justDont);
01467     // dupliquer les aretes de la coupure
01468     int i=numberOfEdges()-1;
01469     for (;i>=0;i--) {
01470       if ( ebData[i].pathID == cutPathID ) {
01471         // on duplique
01472         int nEd=AddEdge(getEdge(i).en,getEdge(i).st);
01473         ebData[nEd].pathID=cutPathID;
01474         ebData[nEd].pieceID=ebData[i].pieceID;
01475         ebData[nEd].tSt=ebData[i].tEn;
01476         ebData[nEd].tEn=ebData[i].tSt;
01477         eData[nEd].weight=eData[i].weight;
01478         // lui donner les firstlinkedpoitn si besoin
01479         if ( getEdge(i).en >= getEdge(i).st ) {
01480           int cp = swsData[i].firstLinkedPoint;
01481           while (cp >= 0) {
01482             pData[cp].askForWindingB = nEd;
01483             cp = pData[cp].nextLinkedPoint;
01484           }
01485           swsData[nEd].firstLinkedPoint = swsData[i].firstLinkedPoint;
01486           swsData[i].firstLinkedPoint=-1;
01487         }
01488       }
01489     }
01490   } else if ( mod == bool_op_slice ) {
01491   } else {
01492     AssembleAretes ();
01493   }
01494   
01495   for (int i = 0; i < numberOfPoints(); i++)
01496     {
01497       _pts[i].oldDegree = getPoint(i).totalDegree();
01498     }
01499 
01500   _need_edges_sorting = true;
01501   if ( mod == bool_op_slice ) {
01502   } else {
01503     GetWindings (a, b, mod, false);
01504   }
01505 //      Plot(190,70,6,400,400,true,true,true,true);
01506 
01507   if (mod == bool_op_symdiff)
01508   {
01509     for (int i = 0; i < numberOfEdges(); i++)
01510     {
01511       swdData[i].leW = swdData[i].leW % 2;
01512       if (swdData[i].leW < 0)
01513         swdData[i].leW = -swdData[i].leW;
01514       swdData[i].riW = swdData[i].riW;
01515       if (swdData[i].riW < 0)
01516         swdData[i].riW = -swdData[i].riW;
01517       
01518       if (swdData[i].leW > 0 && swdData[i].riW <= 0)
01519         {
01520           eData[i].weight = 1;
01521         }
01522       else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
01523         {
01524           Inverse (i);
01525           eData[i].weight = 1;
01526         }
01527       else
01528         {
01529           eData[i].weight = 0;
01530           SubEdge (i);
01531           i--;
01532         }
01533     }
01534   }
01535   else if (mod == bool_op_union || mod == bool_op_diff)
01536   {
01537     for (int i = 0; i < numberOfEdges(); i++)
01538     {
01539       if (swdData[i].leW > 0 && swdData[i].riW <= 0)
01540         {
01541           eData[i].weight = 1;
01542         }
01543       else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
01544         {
01545           Inverse (i);
01546           eData[i].weight = 1;
01547         }
01548       else
01549         {
01550           eData[i].weight = 0;
01551           SubEdge (i);
01552           i--;
01553         }
01554     }
01555   }
01556   else if (mod == bool_op_inters)
01557   {
01558     for (int i = 0; i < numberOfEdges(); i++)
01559     {
01560       if (swdData[i].leW > 1 && swdData[i].riW <= 1)
01561         {
01562           eData[i].weight = 1;
01563         }
01564       else if (swdData[i].leW <= 1 && swdData[i].riW > 1)
01565         {
01566           Inverse (i);
01567           eData[i].weight = 1;
01568         }
01569       else
01570         {
01571           eData[i].weight = 0;
01572           SubEdge (i);
01573           i--;
01574         }
01575     }
01576   } else if ( mod == bool_op_cut ) {
01577     // inverser les aretes de la coupe au besoin
01578     for (int i=0;i<numberOfEdges();i++) {
01579       if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
01580         if ( i < numberOfEdges()-1 ) {
01581           // decaler les askForWinding
01582           int cp = swsData[numberOfEdges()-1].firstLinkedPoint;
01583           while (cp >= 0) {
01584             pData[cp].askForWindingB = i;
01585             cp = pData[cp].nextLinkedPoint;
01586           }
01587         }
01588         SwapEdges(i,numberOfEdges()-1);
01589         SubEdge(numberOfEdges()-1);
01590 //        SubEdge(i);
01591         i--;
01592       } else if ( ebData[i].pathID == cutPathID ) {
01593         swdData[i].leW=swdData[i].leW%2;
01594         swdData[i].riW=swdData[i].riW%2;
01595         if ( swdData[i].leW < swdData[i].riW ) {
01596           Inverse(i);
01597         }
01598       }
01599     }
01600   } else if ( mod == bool_op_slice ) {
01601     // supprimer les aretes de la coupe
01602     int i=numberOfEdges()-1;
01603     for (;i>=0;i--) {
01604       if ( ebData[i].pathID == cutPathID || getEdge(i).st < 0 || getEdge(i).en < 0 ) {
01605         SubEdge(i);
01606       }
01607     }
01608   }
01609   else
01610   {
01611     for (int i = 0; i < numberOfEdges(); i++)
01612     {
01613       if (swdData[i].leW > 0 && swdData[i].riW <= 0)
01614         {
01615           eData[i].weight = 1;
01616         }
01617       else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
01618         {
01619           Inverse (i);
01620           eData[i].weight = 1;
01621         }
01622       else
01623         {
01624           eData[i].weight = 0;
01625           SubEdge (i);
01626           i--;
01627         }
01628     }
01629   }
01630   
01631   delete sTree;
01632   sTree = NULL;
01633   delete sEvts;
01634   sEvts = NULL;
01635   
01636   if ( mod == bool_op_cut ) {
01637     // on garde le askForWinding
01638   } else {
01639     MakePointData (false);
01640   }
01641   MakeEdgeData (false);
01642   MakeSweepSrcData (false);
01643   MakeSweepDestData (false);
01644   a->CleanupSweep ();
01645   b->CleanupSweep ();
01646 
01647   if (directedEulerian(this) == false)
01648     {
01649 //              printf( "pas euclidian2");
01650       _pts.clear();
01651       _aretes.clear();
01652       return shape_euler_err;
01653     }
01654   type = shape_polygon;
01655   return 0;
01656 }

void Shape::CalcBBox ( bool  strict_degree = false  ) 

Definition at line 2019 of file Shape.cpp.

References _bbox_up_to_date, bottomY, Shape::dg_point::dI, Shape::dg_point::dO, getPoint(), hasPoints(), Barcode::Code39Ext::i, leftX, numberOfPoints(), rightX, topY, voronoi::x, and Shape::dg_point::x.

Referenced by raster_glyph::LoadSubPixelPosition(), nr_arena_shape_add_bboxes(), nr_pixblock_render_shape_mask_or(), Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker(), and sp_offset_set_shape().

02020 {
02021   if (_bbox_up_to_date)
02022     return;
02023   if (hasPoints() == false)
02024   {
02025     leftX = rightX = topY = bottomY = 0;
02026     _bbox_up_to_date = true;
02027     return;
02028   }
02029   leftX = rightX = getPoint(0).x[0];
02030   topY = bottomY = getPoint(0).x[1];
02031   bool not_set=true;
02032   for (int i = 0; i < numberOfPoints(); i++)
02033   {
02034     if ( strict_degree == false || getPoint(i).dI > 0 || getPoint(i).dO > 0 ) {
02035       if ( not_set ) {
02036         leftX = rightX = getPoint(i).x[0];
02037         topY = bottomY = getPoint(i).x[1];
02038         not_set=false;
02039       } else {
02040         if (  getPoint(i).x[0] < leftX) leftX = getPoint(i).x[0];
02041         if (  getPoint(i).x[0] > rightX) rightX = getPoint(i).x[0];
02042         if (  getPoint(i).x[1] < topY) topY = getPoint(i).x[1];
02043         if (  getPoint(i).x[1] > bottomY) bottomY = getPoint(i).x[1];
02044       }
02045     }
02046   }
02047 
02048   _bbox_up_to_date = true;
02049 }

void Shape::CheckAdjacencies ( int  lastPointNo,
int  lastChgtPt,
Shape *  shapeHead,
int  edgeHead 
) [private]

Definition at line 2723 of file ShapeSweep.cpp.

References SweepTree::bord, chgts, AVLTree::elem, getPoint(), LEFT, n, NULL, RIGHT, SweepTree::src, swsData, TesteAdjacency(), Shape::dg_point::x, and voronoi::x.

Referenced by Booleen(), and ConvertToShape().

02725 {
02726   for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
02727     {
02728       int chLeN = chgts[cCh].ptNo;
02729       int chRiN = chgts[cCh].ptNo;
02730       if (chgts[cCh].src)
02731     {
02732       Shape *lS = chgts[cCh].src;
02733       int lB = chgts[cCh].bord;
02734       int lftN = lS->swsData[lB].leftRnd;
02735       int rgtN = lS->swsData[lB].rightRnd;
02736       if (lftN < chLeN)
02737         chLeN = lftN;
02738       if (rgtN > chRiN)
02739         chRiN = rgtN;
02740 //                      for (int n=lftN;n<=rgtN;n++) CreateIncidence(lS,lB,n);
02741       for (int n = lftN - 1; n >= lastChgtPt; n--)
02742         {
02743           if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
02744           false)
02745         break;
02746           lS->swsData[lB].leftRnd = n;
02747         }
02748       for (int n = rgtN + 1; n < lastPointNo; n++)
02749         {
02750           if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
02751           false)
02752         break;
02753           lS->swsData[lB].rightRnd = n;
02754         }
02755     }
02756       if (chgts[cCh].osrc)
02757     {
02758       Shape *rS = chgts[cCh].osrc;
02759       int rB = chgts[cCh].obord;
02760       int lftN = rS->swsData[rB].leftRnd;
02761       int rgtN = rS->swsData[rB].rightRnd;
02762       if (lftN < chLeN)
02763         chLeN = lftN;
02764       if (rgtN > chRiN)
02765         chRiN = rgtN;
02766 //                      for (int n=lftN;n<=rgtN;n++) CreateIncidence(rS,rB,n);
02767       for (int n = lftN - 1; n >= lastChgtPt; n--)
02768         {
02769           if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
02770           false)
02771         break;
02772           rS->swsData[rB].leftRnd = n;
02773         }
02774       for (int n = rgtN + 1; n < lastPointNo; n++)
02775         {
02776           if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
02777           false)
02778         break;
02779           rS->swsData[rB].rightRnd = n;
02780         }
02781     }
02782       if (chgts[cCh].lSrc)
02783     {
02784       if (chgts[cCh].lSrc->swsData[chgts[cCh].lBrd].leftRnd < lastChgtPt)
02785         {
02786           Shape *nSrc = chgts[cCh].lSrc;
02787           int nBrd = chgts[cCh].lBrd /*,nNo=chgts[cCh].ptNo */ ;
02788           bool hit;
02789 
02790           do
02791         {
02792           hit = false;
02793           for (int n = chRiN; n >= chLeN; n--)
02794             {
02795               if (TesteAdjacency
02796               (nSrc, nBrd, getPoint(n).x, n, false))
02797             {
02798               if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
02799                 {
02800                   nSrc->swsData[nBrd].leftRnd = n;
02801                   nSrc->swsData[nBrd].rightRnd = n;
02802                 }
02803               else
02804                 {
02805                   if (n < nSrc->swsData[nBrd].leftRnd)
02806                 nSrc->swsData[nBrd].leftRnd = n;
02807                   if (n > nSrc->swsData[nBrd].rightRnd)
02808                 nSrc->swsData[nBrd].rightRnd = n;
02809                 }
02810               hit = true;
02811             }
02812             }
02813           for (int n = chLeN - 1; n >= lastChgtPt; n--)
02814             {
02815               if (TesteAdjacency
02816               (nSrc, nBrd, getPoint(n).x, n, false) == false)
02817             break;
02818               if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
02819             {
02820               nSrc->swsData[nBrd].leftRnd = n;
02821               nSrc->swsData[nBrd].rightRnd = n;
02822             }
02823               else
02824             {
02825               if (n < nSrc->swsData[nBrd].leftRnd)
02826                 nSrc->swsData[nBrd].leftRnd = n;
02827               if (n > nSrc->swsData[nBrd].rightRnd)
02828                 nSrc->swsData[nBrd].rightRnd = n;
02829             }
02830               hit = true;
02831             }
02832           if (hit)
02833             {
02834               SweepTree *node =
02835             static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
02836               if (node == NULL)
02837             break;
02838               node = static_cast < SweepTree * >(node->elem[LEFT]);
02839               if (node == NULL)
02840             break;
02841               nSrc = node->src;
02842               nBrd = node->bord;
02843               if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
02844             break;
02845             }
02846         }
02847           while (hit);
02848 
02849         }
02850     }
02851       if (chgts[cCh].rSrc)
02852     {
02853       if (chgts[cCh].rSrc->swsData[chgts[cCh].rBrd].leftRnd < lastChgtPt)
02854         {
02855           Shape *nSrc = chgts[cCh].rSrc;
02856           int nBrd = chgts[cCh].rBrd /*,nNo=chgts[cCh].ptNo */ ;
02857           bool hit;
02858           do
02859         {
02860           hit = false;
02861           for (int n = chLeN; n <= chRiN; n++)
02862             {
02863               if (TesteAdjacency
02864               (nSrc, nBrd, getPoint(n).x, n, false))
02865             {
02866               if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
02867                 {
02868                   nSrc->swsData[nBrd].leftRnd = n;
02869                   nSrc->swsData[nBrd].rightRnd = n;
02870                 }
02871               else
02872                 {
02873                   if (n < nSrc->swsData[nBrd].leftRnd)
02874                 nSrc->swsData[nBrd].leftRnd = n;
02875                   if (n > nSrc->swsData[nBrd].rightRnd)
02876                 nSrc->swsData[nBrd].rightRnd = n;
02877                 }
02878               hit = true;
02879             }
02880             }
02881           for (int n = chRiN + 1; n < lastPointNo; n++)
02882             {
02883               if (TesteAdjacency
02884               (nSrc, nBrd, getPoint(n).x, n, false) == false)
02885             break;
02886               if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
02887             {
02888               nSrc->swsData[nBrd].leftRnd = n;
02889               nSrc->swsData[nBrd].rightRnd = n;
02890             }
02891               else
02892             {
02893               if (n < nSrc->swsData[nBrd].leftRnd)
02894                 nSrc->swsData[nBrd].leftRnd = n;
02895               if (n > nSrc->swsData[nBrd].rightRnd)
02896                 nSrc->swsData[nBrd].rightRnd = n;
02897             }
02898               hit = true;
02899             }
02900           if (hit)
02901             {
02902               SweepTree *node =
02903             static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
02904               if (node == NULL)
02905             break;
02906               node = static_cast < SweepTree * >(node->elem[RIGHT]);
02907               if (node == NULL)
02908             break;
02909               nSrc = node->src;
02910               nBrd = node->bord;
02911               if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
02912             break;
02913             }
02914         }
02915           while (hit);
02916         }
02917     }
02918     }
02919 }

void Shape::CheckEdges ( int  lastPointNo,
int  lastChgtPt,
Shape *  a,
Shape *  b,
BooleanOp  mod 
) [private]

Definition at line 3041 of file ShapeSweep.cpp.

References Avance(), SweepTree::bord, chgts, AVLTree::elem, LEFT, NULL, RIGHT, SweepTree::src, swsData, and type.

Referenced by Booleen(), and ConvertToShape().

03043 {
03044 
03045   for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
03046     {
03047       if (chgts[cCh].type == 0)
03048     {
03049       Shape *lS = chgts[cCh].src;
03050       int lB = chgts[cCh].bord;
03051       lS->swsData[lB].curPoint = chgts[cCh].ptNo;
03052     }
03053     }
03054   for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
03055     {
03056 //              int   chLeN=chgts[cCh].ptNo;
03057 //              int   chRiN=chgts[cCh].ptNo;
03058       if (chgts[cCh].src)
03059     {
03060       Shape *lS = chgts[cCh].src;
03061       int lB = chgts[cCh].bord;
03062       Avance (lastPointNo, lastChgtPt, lS, lB, a, b, mod);
03063     }
03064       if (chgts[cCh].osrc)
03065     {
03066       Shape *rS = chgts[cCh].osrc;
03067       int rB = chgts[cCh].obord;
03068       Avance (lastPointNo, lastChgtPt, rS, rB, a, b, mod);
03069     }
03070       if (chgts[cCh].lSrc)
03071     {
03072       Shape *nSrc = chgts[cCh].lSrc;
03073       int nBrd = chgts[cCh].lBrd;
03074       while (nSrc->swsData[nBrd].leftRnd >=
03075          lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
03076         {
03077           Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
03078 
03079           SweepTree *node =
03080         static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
03081           if (node == NULL)
03082         break;
03083           node = static_cast < SweepTree * >(node->elem[LEFT]);
03084           if (node == NULL)
03085         break;
03086           nSrc = node->src;
03087           nBrd = node->bord;
03088         }
03089     }
03090       if (chgts[cCh].rSrc)
03091     {
03092       Shape *nSrc = chgts[cCh].rSrc;
03093       int nBrd = chgts[cCh].rBrd;
03094       while (nSrc->swsData[nBrd].rightRnd >=
03095          lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
03096         {
03097           Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
03098 
03099           SweepTree *node =
03100         static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
03101           if (node == NULL)
03102         break;
03103           node = static_cast < SweepTree * >(node->elem[RIGHT]);
03104           if (node == NULL)
03105         break;
03106           nSrc = node->src;
03107           nBrd = node->bord;
03108         }
03109     }
03110     }
03111 }

void Shape::CleanupSweep ( void   )  [private]

Definition at line 55 of file ShapeSweep.cpp.

References MakeEdgeData(), MakePointData(), and MakeSweepSrcData().

Referenced by Booleen(), and ConvertToShape().

00056 {
00057   MakePointData (false);
00058   MakeEdgeData (false);
00059   MakeSweepSrcData (false);
00060 }

void Shape::clearIncidenceData (  )  [private]

Definition at line 2157 of file Shape.cpp.

References iData, maxInc, nbInc, and NULL.

Referenced by Booleen(), and ConvertToShape().

02158 {
02159     g_free(iData);
02160     iData = NULL;
02161     nbInc = maxInc = 0;
02162 }

static int Shape::CmpQRs ( const quick_raster_data &  p1,
const quick_raster_data &  p2 
) [inline, static, private]

Definition at line 556 of file Shape.h.

References Shape::quick_raster_data::x.

Referenced by QuickRasterAddEdge(), and QuickRasterSort().

00556                                                                                 {
00557         if ( fabs(p1.x - p2.x) < 0.00001 ) {
00558             return 0;
00559         }
00560 
00561         return ( ( p1.x < p2.x ) ? -1 : 1 );
00562     };

int Shape::CmpToVert ( const Geom::Point  ax,
const Geom::Point  bx,
bool  as,
bool  bs 
) [static, private]

Definition at line 1555 of file Shape.cpp.

References Geom::cross().

Referenced by SortEdgesList().

01556 {
01557   int tstAX = 0;
01558   int tstAY = 0;
01559   int tstBX = 0;
01560   int tstBY = 0;
01561   if (ax[0] > 0)
01562     tstAX = 1;
01563   if (ax[0] < 0)
01564     tstAX = -1;
01565   if (ax[1] > 0)
01566     tstAY = 1;
01567   if (ax[1] < 0)
01568     tstAY = -1;
01569   if (bx[0] > 0)
01570     tstBX = 1;
01571   if (bx[0] < 0)
01572     tstBX = -1;
01573   if (bx[1] > 0)
01574     tstBY = 1;
01575   if (bx[1] < 0)
01576     tstBY = -1;
01577 
01578   int quadA = 0, quadB = 0;
01579   if (tstAX < 0)
01580     {
01581       if (tstAY < 0)
01582         {
01583           quadA = 7;
01584         }
01585       else if (tstAY == 0)
01586         {
01587           quadA = 6;
01588         }
01589       else if (tstAY > 0)
01590         {
01591           quadA = 5;
01592         }
01593     }
01594   else if (tstAX == 0)
01595     {
01596       if (tstAY < 0)
01597         {
01598           quadA = 0;
01599         }
01600       else if (tstAY == 0)
01601         {
01602           quadA = -1;
01603         }
01604       else if (tstAY > 0)
01605         {
01606           quadA = 4;
01607         }
01608     }
01609   else if (tstAX > 0)
01610     {
01611       if (tstAY < 0)
01612         {
01613           quadA = 1;
01614         }
01615       else if (tstAY == 0)
01616         {
01617           quadA = 2;
01618         }
01619       else if (tstAY > 0)
01620         {
01621           quadA = 3;
01622         }
01623     }
01624   if (tstBX < 0)
01625     {
01626       if (tstBY < 0)
01627         {
01628           quadB = 7;
01629         }
01630       else if (tstBY == 0)
01631         {
01632           quadB = 6;
01633         }
01634       else if (tstBY > 0)
01635         {
01636           quadB = 5;
01637         }
01638     }
01639   else if (tstBX == 0)
01640     {
01641       if (tstBY < 0)
01642         {
01643           quadB = 0;
01644         }
01645       else if (tstBY == 0)
01646         {
01647           quadB = -1;
01648         }
01649       else if (tstBY > 0)
01650         {
01651           quadB = 4;
01652         }
01653     }
01654   else if (tstBX > 0)
01655     {
01656       if (tstBY < 0)
01657         {
01658           quadB = 1;
01659         }
01660       else if (tstBY == 0)
01661         {
01662           quadB = 2;
01663         }
01664       else if (tstBY > 0)
01665         {
01666           quadB = 3;
01667         }
01668     }
01669   if (quadA < quadB)
01670     return 1;
01671   if (quadA > quadB)
01672     return -1;
01673 
01674   Geom::Point av, bv;
01675   av = ax;
01676   bv = bx;
01677   double si = cross (bv, av);
01678   int tstSi = 0;
01679   if (si > 0.000001) tstSi = 1;
01680   if (si < -0.000001) tstSi = -1;
01681   if ( tstSi == 0 ) {
01682     if ( as == true && bs == false ) return -1;
01683     if ( as == false && bs == true ) return 1;
01684   }
01685   return tstSi;
01686 }

void Shape::ConnectEnd ( int  p,
int  b 
)

Definition at line 1878 of file Shape.cpp.

References _aretes, _pts, DisconnectEnd(), FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, and LAST.

Referenced by AddEdge(), and Path::Fill().

01879 {
01880   if (getEdge(b).en >= 0)
01881     DisconnectEnd (b);
01882   _aretes[b].en = p;
01883   _pts[p].dI++;
01884   _aretes[b].nextE = -1;
01885   _aretes[b].prevE = getPoint(p).incidentEdge[LAST];
01886   if (getPoint(p).incidentEdge[LAST] >= 0)
01887     {
01888       if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
01889         {
01890           _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
01891         }
01892       else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
01893         {
01894           _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
01895         }
01896     }
01897   _pts[p].incidentEdge[LAST] = b;
01898   if (getPoint(p).incidentEdge[FIRST] < 0)
01899     _pts[p].incidentEdge[FIRST] = b;
01900 }

void Shape::ConnectStart ( int  p,
int  b 
)

Definition at line 1852 of file Shape.cpp.

References _aretes, _pts, DisconnectStart(), FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, and LAST.

Referenced by AddEdge(), and Path::Fill().

01853 {
01854   if (getEdge(b).st >= 0)
01855     DisconnectStart (b);
01856   
01857   _aretes[b].st = p;
01858   _pts[p].dO++;
01859   _aretes[b].nextS = -1;
01860   _aretes[b].prevS = getPoint(p).incidentEdge[LAST];
01861   if (getPoint(p).incidentEdge[LAST] >= 0)
01862     {
01863       if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
01864         {
01865           _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
01866         }
01867       else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
01868         {
01869           _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
01870         }
01871     }
01872   _pts[p].incidentEdge[LAST] = b;
01873   if (getPoint(p).incidentEdge[FIRST] < 0)
01874     _pts[p].incidentEdge[FIRST] = b;
01875 }

void Shape::ConvertToForme ( Path *  dest,
int  nbP,
Path **  orig,
bool  splitWhenForced = false 
)

Definition at line 181 of file ShapeMisc.cpp.

References _has_back_data, AddContour(), ConvertToForme(), CycleNextAt(), eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, MakeEdgeData(), MakePointData(), MakeSweepDestData(), NextAt(), numberOfEdges(), numberOfPoints(), pData, Path::Reset(), Round(), SortEdges(), Shape::dg_arete::st, swdData, and voronoi::x.

00182 {
00183   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
00184     return;
00185 //  if (Eulerian (true) == false)
00186 //    return;
00187   
00188   if (_has_back_data == false)
00189   {
00190     ConvertToForme (dest);
00191     return;
00192   }
00193   
00194   dest->Reset ();
00195   
00196   MakePointData (true);
00197   MakeEdgeData (true);
00198   MakeSweepDestData (true);
00199   
00200   for (int i = 0; i < numberOfPoints(); i++)
00201   {
00202     pData[i].rx[0] = Round (getPoint(i).x[0]);
00203     pData[i].rx[1] = Round (getPoint(i).x[1]);
00204   }
00205   for (int i = 0; i < numberOfEdges(); i++)
00206   {
00207     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
00208   }
00209   
00210   SortEdges ();
00211   
00212   for (int i = 0; i < numberOfEdges(); i++)
00213   {
00214     swdData[i].misc = 0;
00215     swdData[i].precParc = swdData[i].suivParc = -1;
00216   }
00217   
00218   int searchInd = 0;
00219   
00220   int lastPtUsed = 0;
00221   do
00222   {
00223     int startBord = -1;
00224     {
00225       int fi = 0;
00226       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
00227       {
00228         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
00229           break;
00230       }
00231       lastPtUsed = fi + 1;
00232       if (fi < numberOfPoints())
00233       {
00234         int bestB = getPoint(fi).incidentEdge[FIRST];
00235         while (bestB >= 0 && getEdge(bestB).st != fi)
00236           bestB = NextAt (fi, bestB);
00237         if (bestB >= 0)
00238           {
00239           startBord = bestB;
00240           }
00241       }
00242     }
00243     if (startBord >= 0)
00244     {
00245       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
00246       swdData[startBord].misc = (void *) 1;
00247       //printf("part de %d\n",startBord);
00248       int curBord = startBord;
00249       bool back = false;
00250       swdData[curBord].precParc = -1;
00251       swdData[curBord].suivParc = -1;
00252       int curStartPt=getEdge(curBord).st;
00253       do
00254         {
00255           int cPt = getEdge(curBord).en;
00256           int nb = curBord;
00257         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
00258           do
00259         {
00260           int nnb = CycleNextAt (cPt, nb);
00261           if (nnb == nb)
00262           {
00263             // cul-de-sac
00264             nb = -1;
00265             break;
00266           }
00267           nb = nnb;
00268           if (nb < 0 || nb == curBord)
00269             break;
00270         }
00271           while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
00272         
00273           if (nb < 0 || nb == curBord)
00274         {
00275           if (back == false)
00276           {
00277             if (curBord == startBord || curBord < 0)
00278             {
00279               // probleme -> on vire le moveto
00280               //                                                      dest->descr_nb--;
00281             }
00282             else
00283             {
00284               swdData[curBord].suivParc = -1;
00285               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
00286             }
00287             //                                              dest->Close();
00288           }
00289           back = true;
00290           // retour en arriere
00291           curBord = swdData[curBord].precParc;
00292           //printf("retour vers %d\n",curBord);
00293           if (curBord < 0)
00294             break;
00295         }
00296           else
00297         {
00298           if (back)
00299           {
00300             back = false;
00301             startBord = nb;
00302             curStartPt=getEdge(nb).st;
00303           } else {
00304             if ( getEdge(curBord).en == curStartPt ) {
00305               //printf("contour %i ",curStartPt);
00306               swdData[curBord].suivParc = -1;
00307               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
00308               startBord=nb;
00309             }
00310           }
00311           swdData[nb].misc = (void *) 1;
00312           swdData[nb].ind = searchInd++;
00313           swdData[nb].precParc = curBord;
00314           swdData[curBord].suivParc = nb;
00315           curBord = nb;
00316           //printf("suite %d\n",curBord);
00317         }
00318         }
00319       while (1 /*swdData[curBord].precParc >= 0 */ );
00320       // fin du cas non-oriente
00321     }
00322   }
00323   while (lastPtUsed < numberOfPoints());
00324   
00325   MakePointData (false);
00326   MakeEdgeData (false);
00327   MakeSweepDestData (false);
00328 }

void Shape::ConvertToForme ( Path *  dest  ) 

Definition at line 38 of file ShapeMisc.cpp.

References Path::Close(), CycleNextAt(), eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, Path::LineTo(), MakeEdgeData(), MakePointData(), MakeSweepDestData(), Path::MoveTo(), NextAt(), numberOfEdges(), numberOfPoints(), pData, Path::Reset(), Round(), SortEdges(), Shape::dg_arete::st, swdData, and voronoi::x.

Referenced by ConvertToForme(), ConvertToFormeNested(), do_trace(), refresh_offset_source(), sp_offset_set_shape(), sp_selected_path_boolop(), sp_selected_path_create_offset_object(), sp_selected_path_do_offset(), sp_selected_path_outline(), and sp_tweak_dilate_recursive().

00039 {
00040   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
00041     return;
00042   
00043   // prepare
00044   dest->Reset ();
00045   
00046   MakePointData (true);
00047   MakeEdgeData (true);
00048   MakeSweepDestData (true);
00049   
00050   for (int i = 0; i < numberOfPoints(); i++)
00051   {
00052     pData[i].rx[0] = Round (getPoint(i).x[0]);
00053     pData[i].rx[1] = Round (getPoint(i).x[1]);
00054   }
00055   for (int i = 0; i < numberOfEdges(); i++)
00056   {
00057     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
00058   }
00059   
00060   // sort edge clockwise, with the closest after midnight being first in the doubly-linked list
00061   // that's vital to the algorithm...
00062   SortEdges ();
00063   
00064   // depth-first search implies: we make a stack of edges traversed.
00065   // precParc: previous in the stack
00066   // suivParc: next in the stack
00067   for (int i = 0; i < numberOfEdges(); i++)
00068   {
00069     swdData[i].misc = 0;
00070     swdData[i].precParc = swdData[i].suivParc = -1;
00071   }
00072   
00073   int searchInd = 0;
00074   
00075   int lastPtUsed = 0;
00076   do
00077   {
00078     // first get a starting point, and a starting edge
00079     // -> take the upper left point, and take its first edge
00080     // points traversed have swdData[].misc != 0, so it's easy
00081     int startBord = -1;
00082     {
00083       int fi = 0;
00084       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
00085       {
00086         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
00087           break;
00088       }
00089       lastPtUsed = fi + 1;
00090       if (fi < numberOfPoints())
00091       {
00092         int bestB = getPoint(fi).incidentEdge[FIRST];
00093         while (bestB >= 0 && getEdge(bestB).st != fi)
00094           bestB = NextAt (fi, bestB);
00095         if (bestB >= 0)
00096           {
00097           startBord = bestB;
00098           dest->MoveTo (getPoint(getEdge(startBord).en).x);
00099           }
00100       }
00101     }
00102     // and walk the graph, doing contours when needed
00103     if (startBord >= 0)
00104     {
00105       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
00106       swdData[startBord].misc = (void *) 1;
00107       //                      printf("part de %d\n",startBord);
00108       int curBord = startBord;
00109       bool back = false;
00110       swdData[curBord].precParc = -1;
00111       swdData[curBord].suivParc = -1;
00112       do
00113         {
00114           int cPt = getEdge(curBord).en;
00115           int nb = curBord;
00116         //                              printf("de curBord= %d au point %i  -> ",curBord,cPt);
00117         // get next edge
00118           do
00119         {
00120           int nnb = CycleNextAt (cPt, nb);
00121           if (nnb == nb)
00122           {
00123             // cul-de-sac
00124             nb = -1;
00125             break;
00126           }
00127           nb = nnb;
00128           if (nb < 0 || nb == curBord)
00129             break;
00130         }
00131           while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
00132         
00133           if (nb < 0 || nb == curBord)
00134         {
00135           // no next edge: end of this contour, we get back
00136           if (back == false)
00137             dest->Close ();
00138           back = true;
00139           // retour en arriere
00140           curBord = swdData[curBord].precParc;
00141           //                                      printf("retour vers %d\n",curBord);
00142           if (curBord < 0)
00143             break;
00144         }
00145           else
00146         {
00147           // new edge, maybe for a new contour
00148           if (back)
00149           {
00150             // we were backtracking, so if we have a new edge, that means we're creating a new contour
00151             dest->MoveTo (getPoint(cPt).x);
00152             back = false;
00153           }
00154           swdData[nb].misc = (void *) 1;
00155           swdData[nb].ind = searchInd++;
00156           swdData[nb].precParc = curBord;
00157           swdData[curBord].suivParc = nb;
00158           curBord = nb;
00159           //                                      printf("suite %d\n",curBord);
00160           {
00161             // add that edge
00162             dest->LineTo (getPoint(getEdge(nb).en).x);
00163           }
00164         }
00165         }
00166       while (1 /*swdData[curBord].precParc >= 0 */ );
00167       // fin du cas non-oriente
00168     }
00169   }
00170   while (lastPtUsed < numberOfPoints());
00171   
00172   MakePointData (false);
00173   MakeEdgeData (false);
00174   MakeSweepDestData (false);
00175 }

void Shape::ConvertToFormeNested ( Path *  dest,
int  nbP,
Path **  orig,
int  wildPath,
int &  nbNest,
int *&  nesting,
int *&  contStart,
bool  splitWhenForced = false 
)

Definition at line 330 of file ShapeMisc.cpp.

References _has_back_data, AddContour(), ConvertToForme(), CycleNextAt(), Path::descr_cmd, ebData, eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, MakeEdgeData(), MakePointData(), MakeSweepDestData(), NextAt(), NULL, numberOfEdges(), numberOfPoints(), pData, Path::Reset(), Round(), SortEdges(), Shape::dg_arete::st, swdData, and voronoi::x.

Referenced by sp_selected_path_boolop().

00331 {
00332   nesting=NULL;
00333   contStart=NULL;
00334   nbNest=0;
00335 
00336   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
00337     return;
00338   //  if (Eulerian (true) == false)
00339   //    return;
00340   
00341   if (_has_back_data == false)
00342   {
00343     ConvertToForme (dest);
00344     return;
00345   }
00346   
00347   dest->Reset ();
00348   
00349 //  MakePointData (true);
00350   MakeEdgeData (true);
00351   MakeSweepDestData (true);
00352   
00353   for (int i = 0; i < numberOfPoints(); i++)
00354   {
00355     pData[i].rx[0] = Round (getPoint(i).x[0]);
00356     pData[i].rx[1] = Round (getPoint(i).x[1]);
00357   }
00358   for (int i = 0; i < numberOfEdges(); i++)
00359   {
00360     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
00361   }
00362   
00363   SortEdges ();
00364   
00365   for (int i = 0; i < numberOfEdges(); i++)
00366   {
00367     swdData[i].misc = 0;
00368     swdData[i].precParc = swdData[i].suivParc = -1;
00369   }
00370   
00371   int searchInd = 0;
00372   
00373   int lastPtUsed = 0;
00374   do
00375   {
00376     int dadContour=-1;
00377     int startBord = -1;
00378     {
00379       int fi = 0;
00380       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
00381       {
00382         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
00383           break;
00384       }
00385       {
00386         int askTo = pData[fi].askForWindingB;
00387         if (askTo < 0 || askTo >= numberOfEdges() ) {
00388           dadContour=-1;
00389         } else {
00390           dadContour = GPOINTER_TO_INT(swdData[askTo].misc);
00391           dadContour-=1; // pour compenser le decalage
00392         }
00393       }
00394       lastPtUsed = fi + 1;
00395       if (fi < numberOfPoints())
00396       {
00397         int bestB = getPoint(fi).incidentEdge[FIRST];
00398         while (bestB >= 0 && getEdge(bestB).st != fi)
00399           bestB = NextAt (fi, bestB);
00400         if (bestB >= 0)
00401           {
00402           startBord = bestB;
00403           }
00404       }
00405     }
00406     if (startBord >= 0)
00407     {
00408       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
00409       swdData[startBord].misc = (void *) (1+nbNest);
00410       //printf("part de %d\n",startBord);
00411       int curBord = startBord;
00412       bool back = false;
00413       swdData[curBord].precParc = -1;
00414       swdData[curBord].suivParc = -1;
00415       int curStartPt=getEdge(curBord).st;
00416       do
00417         {
00418           int cPt = getEdge(curBord).en;
00419           int nb = curBord;
00420         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
00421           do
00422         {
00423           int nnb = CycleNextAt (cPt, nb);
00424           if (nnb == nb)
00425           {
00426             // cul-de-sac
00427             nb = -1;
00428             break;
00429           }
00430           nb = nnb;
00431           if (nb < 0 || nb == curBord)
00432             break;
00433         }
00434           while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
00435         
00436           if (nb < 0 || nb == curBord)
00437         {
00438           if (back == false)
00439           {
00440             if (curBord == startBord || curBord < 0)
00441             {
00442               // probleme -> on vire le moveto
00443               //                                                      dest->descr_nb--;
00444             }
00445             else
00446             {
00447               bool escapePath=false;
00448               int tb=curBord;
00449               while ( tb >= 0 && tb < numberOfEdges() ) {
00450                 if ( ebData[tb].pathID == wildPath ) {
00451                   escapePath=true;
00452                   break;
00453                 }
00454                 tb=swdData[tb].precParc;
00455               }
00456               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
00457               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
00458               contStart[nbNest]=dest->descr_cmd.size();
00459               if ( escapePath ) {
00460                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
00461               } else {
00462                 nesting[nbNest++]=dadContour;
00463               }
00464               swdData[curBord].suivParc = -1;
00465               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
00466             }
00467             //                                              dest->Close();
00468           }
00469           back = true;
00470           // retour en arriere
00471           curBord = swdData[curBord].precParc;
00472           //printf("retour vers %d\n",curBord);
00473           if (curBord < 0)
00474             break;
00475         }
00476           else
00477         {
00478           if (back)
00479           {
00480             back = false;
00481             startBord = nb;
00482             curStartPt=getEdge(nb).st;
00483           } else {
00484             if ( getEdge(curBord).en == curStartPt ) {
00485               //printf("contour %i ",curStartPt);
00486               
00487               bool escapePath=false;
00488               int tb=curBord;
00489               while ( tb >= 0 && tb < numberOfEdges() ) {
00490                 if ( ebData[tb].pathID == wildPath ) {
00491                   escapePath=true;
00492                   break;
00493                 }
00494                 tb=swdData[tb].precParc;
00495               }
00496               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
00497               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
00498               contStart[nbNest]=dest->descr_cmd.size();
00499               if ( escapePath ) {
00500                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
00501               } else {
00502                 nesting[nbNest++]=dadContour;
00503               }
00504 
00505               swdData[curBord].suivParc = -1;
00506               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
00507               startBord=nb;
00508             }
00509           }
00510           swdData[nb].misc = (void *) (1+nbNest);
00511           swdData[nb].ind = searchInd++;
00512           swdData[nb].precParc = curBord;
00513           swdData[curBord].suivParc = nb;
00514           curBord = nb;
00515           //printf("suite %d\n",curBord);
00516         }
00517         }
00518       while (1 /*swdData[curBord].precParc >= 0 */ );
00519       // fin du cas non-oriente
00520     }
00521   }
00522   while (lastPtUsed < numberOfPoints());
00523   
00524   MakePointData (false);
00525   MakeEdgeData (false);
00526   MakeSweepDestData (false);
00527 }

int Shape::ConvertToShape ( Shape *  a,
FillRule  directed = fill_nonZero,
bool  invert = false 
)

Definition at line 168 of file ShapeSweep.cpp.

References _has_back_data, _need_edges_sorting, _pts, SweepTreeList::add(), AddChgt(), AddPoint(), AssembleAretes(), AssemblePoints(), bool_op_union, SweepTree::bord, CheckAdjacencies(), CheckEdges(), chgts, CleanupSweep(), clearIncidenceData(), SweepTree::ConvertTo(), Shape::dg_point::dI, directedEulerian(), Shape::dg_point::dO, eData, EDGE_INSERTED, EDGE_REMOVED, AVLTree::elem, Shape::dg_arete::en, SweepEventQueue::extract(), fill_justDont, fill_nonZero, fill_oddEven, fill_positive, FIRST, getEdge(), getPoint(), GetWindings(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, initialiseEdgeData(), initialisePointData(), SweepTree::Insert(), SweepTree::InsertAt(), INTERSECTION, Inverse(), LEFT, MakeBackData(), MakeEdgeData(), MakePointData(), MakeSweepDestData(), MakeSweepSrcData(), NextAt(), NULL, numberOfEdges(), numberOfPoints(), pData, SweepEventQueue::peek(), SweepTree::Remove(), SweepTree::RemoveEvent(), SweepTree::RemoveEvents(), Reset(), ResetSweep(), RIGHT, Round(), sEvts, shape_input_err, shape_polygon, SweepEventQueue::size(), SortEdges(), SortPointsRounded(), SweepTree::src, Shape::dg_arete::st, sTree, SubEdge(), SweepTree::SwapWithRight(), swdData, SweepEventQueue, swsData, TesteIntersection(), Shape::dg_point::totalDegree(), and type.

Referenced by do_trace(), GetDest(), raster_font::LoadRasterGlyph(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), refresh_offset_source(), Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker(), sp_offset_distance_to_original(), sp_offset_set_shape(), sp_selected_path_boolop(), sp_selected_path_create_offset_object(), sp_selected_path_do_offset(), sp_selected_path_outline(), and sp_tweak_dilate_recursive().

00169 {
00170     Reset (0, 0);
00171 
00172     if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1) {
00173     return 0;
00174     }
00175     
00176     if ( directed != fill_justDont && directedEulerian(a) == false ) {
00177             g_warning ("Shape error in ConvertToShape: directedEulerian(a) == false\n");
00178                 return shape_input_err;
00179     }
00180   
00181     a->ResetSweep();
00182 
00183     if (sTree == NULL) {
00184     sTree = new SweepTreeList(a->numberOfEdges());
00185     }
00186     if (sEvts == NULL) {
00187     sEvts = new SweepEventQueue(a->numberOfEdges());
00188     }
00189   
00190     MakePointData(true);
00191     MakeEdgeData(true);
00192     MakeSweepSrcData(true);
00193     MakeSweepDestData(true);
00194     MakeBackData(a->_has_back_data);
00195 
00196     a->initialisePointData();
00197     a->initialiseEdgeData();
00198 
00199     a->SortPointsRounded();
00200 
00201     chgts.clear();
00202 
00203     double lastChange = a->pData[0].rx[1] - 1.0;
00204     int lastChgtPt = 0;
00205     int edgeHead = -1;
00206     Shape *shapeHead = NULL;
00207 
00208     clearIncidenceData();
00209     
00210     int curAPt = 0;
00211 
00212     while (curAPt < a->numberOfPoints() || sEvts->size() > 0) {
00213     Geom::Point ptX;
00214       double ptL, ptR;
00215       SweepTree *intersL = NULL;
00216       SweepTree *intersR = NULL;
00217       int nPt = -1;
00218       Shape *ptSh = NULL;
00219       bool isIntersection = false;
00220       if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
00221     {
00222       if (a->pData[curAPt].pending > 0
00223           || (a->pData[curAPt].rx[1] > ptX[1]
00224           || (a->pData[curAPt].rx[1] == ptX[1]
00225               && a->pData[curAPt].rx[0] > ptX[0])))
00226         {
00227           /* FIXME: could just be pop? */
00228           sEvts->extract(intersL, intersR, ptX, ptL, ptR);
00229           isIntersection = true;
00230         }
00231       else
00232         {
00233           nPt = curAPt++;
00234           ptSh = a;
00235           ptX = ptSh->pData[nPt].rx;
00236           isIntersection = false;
00237         }
00238     }
00239       else
00240     {
00241       nPt = curAPt++;
00242       ptSh = a;
00243       ptX = ptSh->pData[nPt].rx;
00244       isIntersection = false;
00245     }
00246 
00247       if (isIntersection == false)
00248     {
00249       if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
00250         continue;
00251     }
00252 
00253       Geom::Point rPtX;
00254       rPtX[0]= Round (ptX[0]);
00255       rPtX[1]= Round (ptX[1]);
00256       int lastPointNo = -1;
00257       lastPointNo = AddPoint (rPtX);
00258       pData[lastPointNo].rx = rPtX;
00259 
00260       if (rPtX[1] > lastChange)
00261     {
00262       int lastI = AssemblePoints (lastChgtPt, lastPointNo);
00263 
00264       Shape *curSh = shapeHead;
00265       int curBo = edgeHead;
00266       while (curSh)
00267         {
00268           curSh->swsData[curBo].leftRnd =
00269         pData[curSh->swsData[curBo].leftRnd].newInd;
00270           curSh->swsData[curBo].rightRnd =
00271         pData[curSh->swsData[curBo].rightRnd].newInd;
00272 
00273           Shape *neSh = curSh->swsData[curBo].nextSh;
00274           curBo = curSh->swsData[curBo].nextBo;
00275           curSh = neSh;
00276         }
00277 
00278       for (unsigned int i = 0; i < chgts.size(); i++)
00279         {
00280           chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
00281           if (chgts[i].type == 0)
00282         {
00283           if (chgts[i].src->getEdge(chgts[i].bord).st <
00284               chgts[i].src->getEdge(chgts[i].bord).en)
00285             {
00286               chgts[i].src->swsData[chgts[i].bord].stPt =
00287             chgts[i].ptNo;
00288             }
00289           else
00290             {
00291               chgts[i].src->swsData[chgts[i].bord].enPt =
00292             chgts[i].ptNo;
00293             }
00294         }
00295           else if (chgts[i].type == 1)
00296         {
00297           if (chgts[i].src->getEdge(chgts[i].bord).st >
00298               chgts[i].src->getEdge(chgts[i].bord).en)
00299             {
00300               chgts[i].src->swsData[chgts[i].bord].stPt =
00301             chgts[i].ptNo;
00302             }
00303           else
00304             {
00305               chgts[i].src->swsData[chgts[i].bord].enPt =
00306             chgts[i].ptNo;
00307             }
00308         }
00309         }
00310 
00311       CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
00312 
00313       CheckEdges (lastI, lastChgtPt, a, NULL, bool_op_union);
00314 
00315       for (int i = lastChgtPt; i < lastI; i++) {
00316         if (pData[i].askForWindingS) {
00317             Shape *windS = pData[i].askForWindingS;
00318             int windB = pData[i].askForWindingB;
00319             pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
00320             windS->swsData[windB].firstLinkedPoint = i;
00321           }
00322        }
00323 
00324     if (lastI < lastPointNo) {
00325           _pts[lastI] = getPoint(lastPointNo);
00326        pData[lastI] = pData[lastPointNo];
00327       }
00328       lastPointNo = lastI;
00329       _pts.resize(lastI + 1);
00330 
00331       lastChgtPt = lastPointNo;
00332       lastChange = rPtX[1];
00333       chgts.clear();
00334       edgeHead = -1;
00335       shapeHead = NULL;
00336     }
00337 
00338 
00339       if (isIntersection)
00340     {
00341 //                      printf("(%i %i [%i %i]) ",intersL->bord,intersR->bord,intersL->startPoint,intersR->startPoint);
00342       intersL->RemoveEvent (*sEvts, LEFT);
00343       intersR->RemoveEvent (*sEvts, RIGHT);
00344 
00345       AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
00346            intersL->src, intersL->bord, intersR->src, intersR->bord);
00347 
00348       intersL->SwapWithRight (*sTree, *sEvts);
00349 
00350       TesteIntersection (intersL, LEFT, false);
00351       TesteIntersection (intersR, RIGHT, false);
00352     }
00353       else
00354     {
00355       int cb;
00356 
00357       int nbUp = 0, nbDn = 0;
00358       int upNo = -1, dnNo = -1;
00359       cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
00360       while (cb >= 0 && cb < ptSh->numberOfEdges())
00361         {
00362           if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
00363            && nPt == ptSh->getEdge(cb).en)
00364           || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
00365               && nPt == ptSh->getEdge(cb).st))
00366         {
00367           upNo = cb;
00368           nbUp++;
00369         }
00370           if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
00371            && nPt == ptSh->getEdge(cb).en)
00372           || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
00373               && nPt == ptSh->getEdge(cb).st))
00374         {
00375           dnNo = cb;
00376           nbDn++;
00377         }
00378           cb = ptSh->NextAt (nPt, cb);
00379         }
00380 
00381       if (nbDn <= 0)
00382         {
00383           upNo = -1;
00384         }
00385       if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == NULL)
00386         {
00387           upNo = -1;
00388         }
00389 
00390       bool doWinding = true;
00391 
00392       if (nbUp > 0)
00393         {
00394           cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
00395           while (cb >= 0 && cb < ptSh->numberOfEdges())
00396         {
00397           if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
00398                && nPt == ptSh->getEdge(cb).en)
00399               || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
00400               && nPt == ptSh->getEdge(cb).st))
00401             {
00402               if (cb != upNo)
00403             {
00404               SweepTree *node =
00405                 (SweepTree *) ptSh->swsData[cb].misc;
00406               if (node == NULL)
00407                 {
00408                 }
00409               else
00410                 {
00411                   AddChgt (lastPointNo, lastChgtPt, shapeHead,
00412                        edgeHead, EDGE_REMOVED, node->src, node->bord,
00413                        NULL, -1);
00414                   ptSh->swsData[cb].misc = NULL;
00415 
00416                   int onLeftB = -1, onRightB = -1;
00417                   Shape *onLeftS = NULL;
00418                   Shape *onRightS = NULL;
00419                   if (node->elem[LEFT])
00420                 {
00421                   onLeftB =
00422                     (static_cast <
00423                      SweepTree * >(node->elem[LEFT]))->bord;
00424                   onLeftS =
00425                     (static_cast <
00426                      SweepTree * >(node->elem[LEFT]))->src;
00427                 }
00428                   if (node->elem[RIGHT])
00429                 {
00430                   onRightB =
00431                     (static_cast <
00432                      SweepTree * >(node->elem[RIGHT]))->bord;
00433                   onRightS =
00434                     (static_cast <
00435                      SweepTree * >(node->elem[RIGHT]))->src;
00436                 }
00437 
00438                   node->Remove (*sTree, *sEvts, true);
00439                   if (onLeftS && onRightS)
00440                 {
00441                   SweepTree *onLeft =
00442                     (SweepTree *) onLeftS->swsData[onLeftB].
00443                     misc;
00444                   if (onLeftS == ptSh
00445                       && (onLeftS->getEdge(onLeftB).en == nPt
00446                       || onLeftS->getEdge(onLeftB).st ==
00447                       nPt))
00448                     {
00449                     }
00450                   else
00451                     {
00452                       if (onRightS == ptSh
00453                       && (onRightS->getEdge(onRightB).en ==
00454                           nPt
00455                           || onRightS->getEdge(onRightB).
00456                           st == nPt))
00457                     {
00458                     }
00459                       else
00460                     {
00461                       TesteIntersection (onLeft, RIGHT, false);
00462                     }
00463                     }
00464                 }
00465                 }
00466             }
00467             }
00468           cb = ptSh->NextAt (nPt, cb);
00469         }
00470         }
00471 
00472       // traitement du "upNo devient dnNo"
00473       SweepTree *insertionNode = NULL;
00474       if (dnNo >= 0)
00475         {
00476           if (upNo >= 0)
00477         {
00478           SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
00479 
00480           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
00481                node->src, node->bord, NULL, -1);
00482 
00483           ptSh->swsData[upNo].misc = NULL;
00484 
00485           node->RemoveEvents (*sEvts);
00486           node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
00487           ptSh->swsData[dnNo].misc = node;
00488           TesteIntersection (node, RIGHT, false);
00489           TesteIntersection (node, LEFT, false);
00490           insertionNode = node;
00491 
00492           ptSh->swsData[dnNo].curPoint = lastPointNo;
00493           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
00494                node->src, node->bord, NULL, -1);
00495         }
00496           else
00497         {
00498           SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
00499           ptSh->swsData[dnNo].misc = node;
00500           node->Insert (*sTree, *sEvts, this, lastPointNo, true);
00501           if (doWinding)
00502             {
00503               SweepTree *myLeft =
00504             static_cast < SweepTree * >(node->elem[LEFT]);
00505               if (myLeft)
00506             {
00507               pData[lastPointNo].askForWindingS = myLeft->src;
00508               pData[lastPointNo].askForWindingB = myLeft->bord;
00509             }
00510               else
00511             {
00512               pData[lastPointNo].askForWindingB = -1;
00513             }
00514               doWinding = false;
00515             }
00516           TesteIntersection (node, RIGHT, false);
00517           TesteIntersection (node, LEFT, false);
00518           insertionNode = node;
00519 
00520           ptSh->swsData[dnNo].curPoint = lastPointNo;
00521           AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
00522                node->src, node->bord, NULL, -1);
00523         }
00524         }
00525 
00526       if (nbDn > 1)
00527         {           // si nbDn == 1 , alors dnNo a deja ete traite
00528           cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
00529           while (cb >= 0 && cb < ptSh->numberOfEdges())
00530         {
00531           if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
00532                && nPt == ptSh->getEdge(cb).en)
00533               || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
00534               && nPt == ptSh->getEdge(cb).st))
00535             {
00536               if (cb != dnNo)
00537             {
00538               SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
00539               ptSh->swsData[cb].misc = node;
00540               node->InsertAt (*sTree, *sEvts, this, insertionNode,
00541                       nPt, true);
00542               if (doWinding)
00543                 {
00544                   SweepTree *myLeft =
00545                 static_cast < SweepTree * >(node->elem[LEFT]);
00546                   if (myLeft)
00547                 {
00548                   pData[lastPointNo].askForWindingS =
00549                     myLeft->src;
00550                   pData[lastPointNo].askForWindingB =
00551                     myLeft->bord;
00552                 }
00553                   else
00554                 {
00555                   pData[lastPointNo].askForWindingB = -1;
00556                 }
00557                   doWinding = false;
00558                 }
00559               TesteIntersection (node, RIGHT, false);
00560               TesteIntersection (node, LEFT, false);
00561 
00562               ptSh->swsData[cb].curPoint = lastPointNo;
00563               AddChgt (lastPointNo, lastChgtPt, shapeHead,
00564                    edgeHead, EDGE_INSERTED, node->src, node->bord, NULL,
00565                    -1);
00566             }
00567             }
00568           cb = ptSh->NextAt (nPt, cb);
00569         }
00570         }
00571     }
00572     }
00573   {
00574     int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
00575 
00576 
00577     Shape *curSh = shapeHead;
00578     int curBo = edgeHead;
00579     while (curSh)
00580       {
00581     curSh->swsData[curBo].leftRnd =
00582       pData[curSh->swsData[curBo].leftRnd].newInd;
00583     curSh->swsData[curBo].rightRnd =
00584       pData[curSh->swsData[curBo].rightRnd].newInd;
00585 
00586     Shape *neSh = curSh->swsData[curBo].nextSh;
00587     curBo = curSh->swsData[curBo].nextBo;
00588     curSh = neSh;
00589       }
00590 
00591     for (unsigned int i = 0; i < chgts.size(); i++)
00592       {
00593     chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
00594     if (chgts[i].type == 0)
00595       {
00596         if (chgts[i].src->getEdge(chgts[i].bord).st <
00597         chgts[i].src->getEdge(chgts[i].bord).en)
00598           {
00599         chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
00600           }
00601         else
00602           {
00603         chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
00604           }
00605       }
00606     else if (chgts[i].type == 1)
00607       {
00608         if (chgts[i].src->getEdge(chgts[i].bord).st >
00609         chgts[i].src->getEdge(chgts[i].bord).en)
00610           {
00611         chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
00612           }
00613         else
00614           {
00615         chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
00616           }
00617       }
00618       }
00619 
00620     CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
00621 
00622     CheckEdges (lastI, lastChgtPt, a, NULL, bool_op_union);
00623 
00624     for (int i = lastChgtPt; i < lastI; i++)
00625       {
00626     if (pData[i].askForWindingS)
00627       {
00628         Shape *windS = pData[i].askForWindingS;
00629         int windB = pData[i].askForWindingB;
00630         pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
00631         windS->swsData[windB].firstLinkedPoint = i;
00632       }
00633       }
00634 
00635     _pts.resize(lastI);
00636 
00637     edgeHead = -1;
00638     shapeHead = NULL;
00639   }
00640 
00641     chgts.clear();
00642 
00643 //  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
00644 //      Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
00645 
00646   //      AssemblePoints(a);
00647 
00648 //      GetAdjacencies(a);
00649 
00650 //      MakeAretes(a);
00651     clearIncidenceData();
00652 
00653   AssembleAretes (directed);
00654 
00655 //  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
00656 
00657   for (int i = 0; i < numberOfPoints(); i++)
00658     {
00659       _pts[i].oldDegree = getPoint(i).totalDegree();
00660     }
00661 //      Validate();
00662 
00663   _need_edges_sorting = true;
00664   if ( directed == fill_justDont ) {
00665     SortEdges();
00666   } else {
00667     GetWindings (a);
00668   }
00669 //  Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
00670 //   if ( doDebug ) {
00671 //   a->CalcBBox();
00672 //     a->Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"orig.svg");
00673 //     Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"winded.svg");
00674 //   }
00675   if (directed == fill_positive)
00676   {
00677     if (invert)
00678     {
00679       for (int i = 0; i < numberOfEdges(); i++)
00680         {
00681           if (swdData[i].leW < 0 && swdData[i].riW >= 0)
00682         {
00683           eData[i].weight = 1;
00684         }
00685           else if (swdData[i].leW >= 0 && swdData[i].riW < 0)
00686         {
00687           Inverse (i);
00688           eData[i].weight = 1;
00689         }
00690           else
00691         {
00692           eData[i].weight = 0;
00693           SubEdge (i);
00694           i--;
00695         }
00696         }
00697     }
00698     else
00699     {
00700       for (int i = 0; i < numberOfEdges(); i++)
00701         {
00702           if (swdData[i].leW > 0 && swdData[i].riW <= 0)
00703         {
00704           eData[i].weight = 1;
00705         }
00706           else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
00707         {
00708           Inverse (i);
00709           eData[i].weight = 1;
00710         }
00711           else
00712         {
00713            eData[i].weight = 0;
00714           SubEdge (i);
00715           i--;
00716         }
00717         }
00718     }
00719   }
00720   else if (directed == fill_nonZero)
00721   {
00722     if (invert)
00723     {
00724       for (int i = 0; i < numberOfEdges(); i++)
00725         {
00726           if (swdData[i].leW < 0 && swdData[i].riW == 0)
00727         {
00728           eData[i].weight = 1;
00729         }
00730           else if (swdData[i].leW > 0 && swdData[i].riW == 0)
00731         {
00732           eData[i].weight = 1;
00733         }
00734           else if (swdData[i].leW == 0 && swdData[i].riW < 0)
00735         {
00736           Inverse (i);
00737           eData[i].weight = 1;
00738         }
00739           else if (swdData[i].leW == 0 && swdData[i].riW > 0)
00740         {
00741           Inverse (i);
00742           eData[i].weight = 1;
00743         }
00744           else
00745         {
00746           eData[i].weight = 0;
00747           SubEdge (i);
00748           i--;
00749         }
00750         }
00751     }
00752     else
00753     {
00754       for (int i = 0; i < numberOfEdges(); i++)
00755         {
00756           if (swdData[i].leW > 0 && swdData[i].riW == 0)
00757         {
00758           eData[i].weight = 1;
00759         }
00760           else if (swdData[i].leW < 0 && swdData[i].riW == 0)
00761         {
00762           eData[i].weight = 1;
00763         }
00764           else if (swdData[i].leW == 0 && swdData[i].riW > 0)
00765         {
00766           Inverse (i);
00767           eData[i].weight = 1;
00768         }
00769           else if (swdData[i].leW == 0 && swdData[i].riW < 0)
00770         {
00771           Inverse (i);
00772           eData[i].weight = 1;
00773         }
00774           else
00775         {
00776           eData[i].weight = 0;
00777           SubEdge (i);
00778           i--;
00779         }
00780         }
00781     }
00782   }
00783   else if (directed == fill_oddEven)
00784   {
00785     for (int i = 0; i < numberOfEdges(); i++)
00786     {
00787       swdData[i].leW %= 2;
00788       swdData[i].riW %= 2;
00789       if (swdData[i].leW < 0)
00790         swdData[i].leW = -swdData[i].leW;
00791       if (swdData[i].riW < 0)
00792         swdData[i].riW = -swdData[i].riW;
00793       if (swdData[i].leW > 0 && swdData[i].riW <= 0)
00794         {
00795           eData[i].weight = 1;
00796         }
00797       else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
00798         {
00799           Inverse (i);
00800           eData[i].weight = 1;
00801         }
00802       else
00803         {
00804           eData[i].weight = 0;
00805           SubEdge (i);
00806           i--;
00807         }
00808     }
00809   } else if ( directed == fill_justDont ) {
00810     for (int i=0;i<numberOfEdges();i++) {
00811       if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
00812         SubEdge(i);
00813         i--;
00814       } else {
00815           eData[i].weight = 0;
00816       }
00817     }
00818   }
00819   
00820 //      Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
00821 
00822   delete sTree;
00823   sTree = NULL;
00824   delete sEvts;
00825   sEvts = NULL;
00826 
00827   MakePointData (false);
00828   MakeEdgeData (false);
00829   MakeSweepSrcData (false);
00830   MakeSweepDestData (false);
00831   a->CleanupSweep ();
00832   type = shape_polygon;
00833   return 0;
00834 }

void Shape::Copy ( Shape *  a  ) 

Copy point and edge data from `who' into this object, discarding any cached data that we have.

Definition at line 234 of file Shape.cpp.

References _aretes, _bbox_up_to_date, _has_back_data, _has_edges_data, _has_points_data, _has_quick_raster_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _has_voronoi_data, _need_edges_sorting, _need_points_sorting, _point_data_initialised, _pts, MakeBackData(), MakeEdgeData(), MakePointData(), MakeQuickRasterData(), MakeRasterData(), MakeSweepDestData(), MakeSweepSrcData(), NULL, numberOfEdges(), numberOfPoints(), Reset(), sEvts, sTree, and type.

Referenced by SPFlowtext::_buildExclusionShape(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker(), and UnionShape().

00235 {
00236   if (who == NULL)
00237     {
00238       Reset (0, 0);
00239       return;
00240     }
00241   MakePointData (false);
00242   MakeEdgeData (false);
00243   MakeSweepSrcData (false);
00244   MakeSweepDestData (false);
00245   MakeRasterData (false);
00246   MakeQuickRasterData (false);
00247   MakeBackData (false);
00248 
00249   delete sTree;
00250   sTree = NULL;
00251   delete sEvts;
00252   sEvts = NULL;
00253 
00254   Reset (who->numberOfPoints(), who->numberOfEdges());
00255   type = who->type;
00256   _need_points_sorting = who->_need_points_sorting;
00257   _need_edges_sorting = who->_need_edges_sorting;
00258   _has_points_data = false;
00259   _point_data_initialised = false;
00260   _has_edges_data = false;
00261   _has_sweep_src_data = false;
00262   _has_sweep_dest_data = false;
00263   _has_raster_data = false;
00264   _has_quick_raster_data = false;
00265   _has_back_data = false;
00266   _has_voronoi_data = false;
00267   _bbox_up_to_date = false;
00268 
00269   _pts = who->_pts;
00270   _aretes = who->_aretes;
00271 }

void Shape::CreateEdge ( int  no,
float  to,
float  step 
) [private]

Definition at line 1622 of file ShapeRaster.cpp.

References Shape::dg_arete::dx, Shape::dg_arete::en, getEdge(), getPoint(), Shape::dg_arete::st, swrData, and Shape::dg_point::x.

Referenced by DirectQuickScan(), DirectScan(), QuickScan(), and Scan().

01623 {
01624     int cPt;
01625     Geom::Point dir;
01626     if ( getEdge(no).st < getEdge(no).en ) {
01627         cPt = getEdge(no).st;
01628         swrData[no].sens = true;
01629         dir = getEdge(no).dx;
01630     } else {
01631         cPt = getEdge(no).en;
01632         swrData[no].sens = false;
01633         dir = -getEdge(no).dx;
01634     }
01635 
01636     swrData[no].lastX = swrData[no].curX = getPoint(cPt).x[0];
01637     swrData[no].lastY = swrData[no].curY = getPoint(cPt).x[1];
01638     
01639     if ( fabs(dir[1]) < 0.000001 ) {
01640         swrData[no].dxdy = 0;
01641     } else {
01642         swrData[no].dxdy = dir[0]/dir[1];
01643     }
01644     
01645     if ( fabs(dir[0]) < 0.000001 ) {
01646         swrData[no].dydx = 0;
01647     } else {
01648         swrData[no].dydx = dir[1]/dir[0];
01649     }
01650     
01651     swrData[no].calcX = swrData[no].curX + (to - step - swrData[no].curY) * swrData[no].dxdy;
01652     swrData[no].guess = -1;
01653 }

int Shape::CreateIncidence ( Shape *  a,
int  cb,
int  pt 
) [private]

Definition at line 2002 of file ShapeSweep.cpp.

References ffgeom::dot(), eData, getEdge(), getPoint(), pData, PushIncidence(), Shape::dg_arete::st, and Shape::dg_point::x.

02003 {
02004   Geom::Point adir, diff;
02005   adir = a->eData[no].rdx;
02006   diff = getPoint(nPt).x - a->pData[a->getEdge(no).st].rx;
02007   double t = dot (diff, adir);
02008   t *= a->eData[no].ilength;
02009   return PushIncidence (a, no, nPt, t);
02010 }

int Shape::CycleNextAt ( int  p,
int  b 
) const [inline]

Definition at line 189 of file Shape.h.

References FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, Shape::dg_arete::nextE, and Shape::dg_arete::nextS.

Referenced by ConvertToForme(), ConvertToFormeNested(), MakeOffset(), and MakeTweak().

00190     {
00191         if (p == getEdge(b).st) {
00192             if (getEdge(b).nextS < 0) {
00193                 return getPoint(p).incidentEdge[FIRST];
00194             }
00195             return getEdge(b).nextS;
00196         } else if (p == getEdge(b).en) {
00197             if (getEdge(b).nextE < 0) {
00198                 return getPoint(p).incidentEdge[FIRST];
00199             }
00200 
00201             return getEdge(b).nextE;
00202         }
00203 
00204         return -1;
00205     }

int Shape::CyclePrevAt ( int  p,
int  b 
) const [inline]

Definition at line 208 of file Shape.h.

References getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, Shape::dg_arete::prevE, and Shape::dg_arete::prevS.

Referenced by GetWindings(), MakeOffset(), and MakeTweak().

00209     {
00210         if (p == getEdge(b).st) {
00211             if (getEdge(b).prevS < 0) {
00212                 return getPoint(p).incidentEdge[LAST];
00213             }
00214             return getEdge(b).prevS;
00215         } else if (p == getEdge(b).en) {
00216             if (getEdge(b).prevE < 0) {
00217                 return getPoint(p).incidentEdge[LAST];
00218             }
00219             return getEdge(b).prevE;
00220         }
00221 
00222         return -1;
00223     }

void Shape::DestroyEdge ( int  no,
AlphaLigne *  line 
) [private]

Definition at line 1842 of file ShapeRaster.cpp.

References AlphaLigne::AddBord(), and swrData.

01843 {
01844     if ( swrData[no].sens ) {
01845         
01846         if ( swrData[no].curX <= swrData[no].lastX ) {
01847 
01848             line->AddBord(swrData[no].curX,
01849                           0,
01850                           swrData[no].lastX,
01851                           swrData[no].curY - swrData[no].lastY,
01852                           -swrData[no].dydx);
01853             
01854         } else if ( swrData[no].curX > swrData[no].lastX ) {
01855             
01856             line->AddBord(swrData[no].lastX,
01857                           0,
01858                           swrData[no].curX,
01859                           swrData[no].curY - swrData[no].lastY,
01860                           swrData[no].dydx);
01861         }
01862         
01863     } else {
01864         
01865         if ( swrData[no].curX <= swrData[no].lastX ) {
01866 
01867             line->AddBord(swrData[no].curX,
01868                           0,
01869                           swrData[no].lastX,
01870                           swrData[no].lastY - swrData[no].curY,
01871                           swrData[no].dydx);
01872 
01873         } else if ( swrData[no].curX > swrData[no].lastX ) {
01874 
01875             line->AddBord(swrData[no].lastX,
01876                           0,
01877                           swrData[no].curX,
01878                           swrData[no].lastY - swrData[no].curY,
01879                           -swrData[no].dydx);
01880         }
01881     }
01882 }

void Shape::DestroyEdge ( int  no,
BitLigne *  line 
) [private]

Definition at line 1785 of file ShapeRaster.cpp.

References BitLigne::AddBord(), and swrData.

01786 {
01787     if ( swrData[no].sens ) {
01788         
01789         if ( swrData[no].curX < swrData[no].lastX ) {
01790             
01791             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
01792             
01793         } else if ( swrData[no].curX > swrData[no].lastX ) {
01794             
01795             line->AddBord(swrData[no].lastX,swrData[no].curX,false);
01796         }
01797         
01798     } else {
01799 
01800     if ( swrData[no].curX < swrData[no].lastX ) {
01801             
01802             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
01803             
01804         } else if ( swrData[no].curX > swrData[no].lastX ) {
01805             
01806             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
01807             
01808         }
01809     }
01810 }

void Shape::DestroyEdge ( int  no,
float  to,
FloatLigne *  line 
) [private]

Definition at line 1688 of file ShapeRaster.cpp.

References FloatLigne::AddBord(), FloatLigne::AddBordR(), and swrData.

Referenced by QuickScan(), and Scan().

01689 {
01690     if ( swrData[no].sens ) {
01691 
01692         if ( swrData[no].curX < swrData[no].lastX ) {
01693 
01694             swrData[no].guess = line->AddBordR(swrData[no].curX,
01695                                                to - swrData[no].curY,
01696                                                swrData[no].lastX,
01697                                                to - swrData[no].lastY,
01698                                                -swrData[no].dydx,
01699                                                swrData[no].guess);
01700             
01701         } else if ( swrData[no].curX > swrData[no].lastX ) {
01702             
01703             swrData[no].guess = line->AddBord(swrData[no].lastX,
01704                                               -(to - swrData[no].lastY),
01705                                               swrData[no].curX,
01706                                               -(to - swrData[no].curY),
01707                                               swrData[no].dydx,
01708                                               swrData[no].guess);
01709         }
01710         
01711     } else {
01712         
01713         if ( swrData[no].curX < swrData[no].lastX ) {
01714 
01715             swrData[no].guess = line->AddBordR(swrData[no].curX,
01716                                                -(to - swrData[no].curY),
01717                                                swrData[no].lastX,
01718                                                -(to - swrData[no].lastY),
01719                                                swrData[no].dydx,
01720                                                swrData[no].guess);
01721             
01722         } else if ( swrData[no].curX > swrData[no].lastX ) {
01723             
01724             swrData[no].guess = line->AddBord(swrData[no].lastX,
01725                                               to - swrData[no].lastY,
01726                                               swrData[no].curX,
01727                                               to - swrData[no].curY,
01728                                               -swrData[no].dydx,
01729                                               swrData[no].guess);
01730         }
01731     }
01732 }

void Shape::DirectQuickScan ( float &  pos,
int &  curP,
float  to,
bool  doSort,
float  step 
)

Definition at line 709 of file ShapeRaster.cpp.

References AvanceEdge(), Shape::quick_raster_data::bord, CreateEdge(), addnodes::e, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, nbQRas, numberOfEdges(), numberOfPoints(), qrsData, QuickRasterAddEdge(), QuickRasterSort(), QuickRasterSubEdge(), Shape::dg_arete::st, swrData, Shape::quick_raster_data::x, Shape::dg_point::x, and voronoi::x.

Referenced by raster_glyph::LoadSubPixelPosition(), and nr_pixblock_render_shape_mask_or().

00710 {
00711     if ( numberOfEdges() <= 1 ) {
00712         return;
00713     }
00714 
00715     if ( pos == to ) {
00716         return;
00717     }
00718     
00719     if ( pos < to ) {
00720         // we're moving downwards
00721         // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
00722         // until we reach the wanted position to.
00723         // don't forget to update curP and pos when we're done
00724         int curPt=curP;
00725         while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
00726             curPt++;
00727         }
00728         
00729         for (int i = 0; i < numberOfEdges(); i++) {
00730             if ( qrsData[i].ind < 0 ) {
00731                 QuickRasterSubEdge(i);
00732             }
00733         }
00734         
00735         for (int i = 0; i < numberOfEdges(); i++) {
00736             Shape::dg_arete const &e = getEdge(i);
00737             if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
00738                 // crosses sweepline
00739                 int nPt = (e.st < e.en) ? e.st : e.en;
00740                 QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
00741                 CreateEdge(i, to, step);
00742             }
00743         }
00744     
00745         curP = curPt;
00746         if ( curPt > 0 ) {
00747             pos=getPoint(curPt-1).x[1];
00748         } else {
00749             pos = to;
00750         }
00751         
00752     } else {
00753 
00754         // same thing, but going up. so the sweepSens is inverted for the Find() function
00755         int curPt=curP;
00756         while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
00757             curPt--;
00758         }
00759     
00760         for (int i = 0; i < numberOfEdges(); i++) {
00761             if ( qrsData[i].ind < 0 ) {
00762                 QuickRasterSubEdge(i);
00763             }
00764         }
00765         
00766         for (int i=0;i<numberOfEdges();i++) {
00767             Shape::dg_arete const &e = getEdge(i);
00768             if ( ( e.st < curPt-1 && e.en >= curPt-1 ) || ( e.en < curPt-1 && e.st >= curPt-1 )) {
00769                 // crosses sweepline
00770                 int nPt = (e.st > e.en) ? e.st : e.en;
00771                 QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
00772                 CreateEdge(i, to, step);
00773             }
00774         }
00775         
00776         curP = curPt;
00777         if ( curPt > 0 ) {
00778             pos = getPoint(curPt-1).x[1];
00779         } else {
00780             pos = to;
00781         }
00782         
00783     }
00784     
00785     pos = to;
00786     for (int i = 0; i < nbQRas; i++) {
00787         int cb = qrsData[i].bord;
00788         AvanceEdge(cb, to, true, step);
00789         qrsData[i].x = swrData[cb].curX;
00790     }
00791     
00792     QuickRasterSort();
00793 }

void Shape::DirectScan ( float &  pos,
int &  curP,
float  to,
float  step 
)

Definition at line 610 of file ShapeRaster.cpp.

References SweepTreeList::add(), AvanceEdge(), SweepTree::bord, CreateEdge(), addnodes::e, AVLTree::elem, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, AVLTree::Leftmost(), NULL, numberOfEdges(), numberOfPoints(), Other(), SweepTreeList::racine, SweepTree::Remove(), RIGHT, sEvts, Shape::dg_arete::st, sTree, swrData, Shape::dg_point::x, and voronoi::x.

00611 {
00612     if ( numberOfEdges() <= 1 ) {
00613         return;
00614     }
00615     
00616     if ( pos == to ) {
00617         return;
00618     }
00619     
00620     if ( pos < to ) {
00621         // we're moving downwards
00622         // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
00623         // until we reach the wanted position to.
00624         // don't forget to update curP and pos when we're done
00625         int curPt = curP;
00626         while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
00627             curPt++;
00628         }
00629         
00630         for (int i=0;i<numberOfEdges();i++) {
00631             if ( swrData[i].misc ) {
00632                 SweepTree* node = swrData[i].misc;
00633                 swrData[i].misc = NULL;
00634                 node->Remove(*sTree, *sEvts, true);
00635             }
00636         }
00637 
00638         for (int i=0; i < numberOfEdges(); i++) {
00639             Shape::dg_arete const &e = getEdge(i);
00640             if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
00641                 // crosses sweepline
00642                 int nPt = (e.st < curPt) ? e.st : e.en;
00643                 SweepTree* node = sTree->add(this, i, 1, nPt, this);
00644                 swrData[i].misc = node;
00645                 node->Insert(*sTree, *sEvts, this, nPt, true);
00646                 CreateEdge(i, to, step);
00647             }
00648         }
00649         
00650         curP = curPt;
00651         if ( curPt > 0 ) {
00652             pos = getPoint(curPt - 1).x[1];
00653         } else {
00654             pos = to;
00655         }
00656         
00657     } else {
00658         
00659         // same thing, but going up. so the sweepSens is inverted for the Find() function
00660         int curPt=curP;
00661         while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
00662             curPt--;
00663         }
00664 
00665         for (int i = 0; i < numberOfEdges(); i++) {
00666             if ( swrData[i].misc ) {
00667                 SweepTree* node = swrData[i].misc;
00668                 swrData[i].misc = NULL;
00669                 node->Remove(*sTree, *sEvts, true);
00670             }
00671         }
00672         
00673         for (int i=0;i<numberOfEdges();i++) {
00674             Shape::dg_arete const &e = getEdge(i);
00675             if ( ( e.st > curPt - 1 && e.en <= curPt - 1 ) || ( e.en > curPt - 1 && e.st <= curPt - 1 )) {
00676                 // crosses sweepline
00677                 int nPt = (e.st > curPt) ? e.st : e.en;
00678                 SweepTree* node = sTree->add(this, i, 1, nPt, this);
00679                 swrData[i].misc = node;
00680                 node->Insert(*sTree, *sEvts, this, nPt, false);
00681                 node->startPoint = Other(nPt, i);
00682                 CreateEdge(i, to, step);
00683             }
00684         }
00685         
00686         curP = curPt;
00687         if ( curPt > 0 ) {
00688             pos = getPoint(curPt - 1).x[1];
00689         } else {
00690             pos = to;
00691         }
00692     }
00693         
00694     // the final touch: edges intersecting the sweepline must be update so that their intersection with
00695     // said sweepline is correct.
00696     pos = to;
00697     if ( sTree->racine ) {
00698         SweepTree* curS=static_cast<SweepTree*>(sTree->racine->Leftmost());
00699         while ( curS ) {
00700             int cb = curS->bord;
00701             AvanceEdge(cb, to, true, step);
00702             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
00703         }
00704     }
00705 }

void Shape::DisconnectEnd ( int  b  ) 

Definition at line 1938 of file Shape.cpp.

References _aretes, _pts, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), LAST, Shape::dg_arete::nextE, and Shape::dg_arete::prevE.

Referenced by AssembleAretes(), ConnectEnd(), Path::Fill(), and SubEdge().

01939 {
01940   if (getEdge(b).en < 0)
01941     return;
01942   _pts[getEdge(b).en].dI--;
01943   if (getEdge(b).prevE >= 0)
01944     {
01945       if (getEdge(getEdge(b).prevE).st == getEdge(b).en)
01946         {
01947           _aretes[getEdge(b).prevE].nextS = getEdge(b).nextE;
01948         }
01949       else if (getEdge(getEdge(b).prevE).en == getEdge(b).en)
01950         {
01951           _aretes[getEdge(b).prevE].nextE = getEdge(b).nextE;
01952         }
01953     }
01954   if (getEdge(b).nextE >= 0)
01955     {
01956       if (getEdge(getEdge(b).nextE).st == getEdge(b).en)
01957         {
01958           _aretes[getEdge(b).nextE].prevS = getEdge(b).prevE;
01959         }
01960       else if (getEdge(getEdge(b).nextE).en == getEdge(b).en)
01961         {
01962           _aretes[getEdge(b).nextE].prevE = getEdge(b).prevE;
01963         }
01964     }
01965   if (getPoint(getEdge(b).en).incidentEdge[FIRST] == b)
01966     _pts[getEdge(b).en].incidentEdge[FIRST] = getEdge(b).nextE;
01967   if (getPoint(getEdge(b).en).incidentEdge[LAST] == b)
01968     _pts[getEdge(b).en].incidentEdge[LAST] = getEdge(b).prevE;
01969   _aretes[b].en = -1;
01970 }

void Shape::DisconnectStart ( int  b  ) 

Definition at line 1903 of file Shape.cpp.

References _aretes, _pts, FIRST, getEdge(), getPoint(), LAST, Shape::dg_arete::nextS, Shape::dg_arete::prevS, and Shape::dg_arete::st.

Referenced by AssembleAretes(), ConnectStart(), Path::Fill(), and SubEdge().

01904 {
01905   if (getEdge(b).st < 0)
01906     return;
01907   _pts[getEdge(b).st].dO--;
01908   if (getEdge(b).prevS >= 0)
01909     {
01910       if (getEdge(getEdge(b).prevS).st == getEdge(b).st)
01911         {
01912           _aretes[getEdge(b).prevS].nextS = getEdge(b).nextS;
01913         }
01914       else if (getEdge(getEdge(b).prevS).en == getEdge(b).st)
01915         {
01916           _aretes[getEdge(b).prevS].nextE = getEdge(b).nextS;
01917         }
01918     }
01919   if (getEdge(b).nextS >= 0)
01920     {
01921       if (getEdge(getEdge(b).nextS).st == getEdge(b).st)
01922         {
01923           _aretes[getEdge(b).nextS].prevS = getEdge(b).prevS;
01924         }
01925       else if (getEdge(getEdge(b).nextS).en == getEdge(b).st)
01926         {
01927           _aretes[getEdge(b).nextS].prevE = getEdge(b).prevS;
01928         }
01929     }
01930   if (getPoint(getEdge(b).st).incidentEdge[FIRST] == b)
01931     _pts[getEdge(b).st].incidentEdge[FIRST] = getEdge(b).nextS;
01932   if (getPoint(getEdge(b).st).incidentEdge[LAST] == b)
01933     _pts[getEdge(b).st].incidentEdge[LAST] = getEdge(b).prevS;
01934   _aretes[b].st = -1;
01935 }

void Shape::DoEdgeTo ( Shape *  iS,
int  iB,
int  iTo,
bool  direct,
bool  sens 
) [private]

Definition at line 3263 of file ShapeSweep.cpp.

References _has_back_data, AddEdge(), ffgeom::dot(), ebData, eData, getEdge(), getPoint(), pData, Shape::dg_arete::st, swsData, and Shape::dg_point::x.

Referenced by Avance().

03264 {
03265   int lp = iS->swsData[iB].curPoint;
03266   int ne = -1;
03267   if (sens)
03268     {
03269       if (direct)
03270     ne = AddEdge (lp, iTo);
03271       else
03272     ne = AddEdge (iTo, lp);
03273     }
03274   else
03275     {
03276       if (direct)
03277     ne = AddEdge (iTo, lp);
03278       else
03279     ne = AddEdge (lp, iTo);
03280     }
03281   if (ne >= 0 && _has_back_data)
03282     {
03283       ebData[ne].pathID = iS->ebData[iB].pathID;
03284       ebData[ne].pieceID = iS->ebData[iB].pieceID;
03285       if (iS->eData[iB].length < 0.00001)
03286     {
03287       ebData[ne].tSt = ebData[ne].tEn = iS->ebData[iB].tSt;
03288     }
03289       else
03290     {
03291       double bdl = iS->eData[iB].ilength;
03292     Geom::Point bpx = iS->pData[iS->getEdge(iB).st].rx;
03293       Geom::Point bdx = iS->eData[iB].rdx;
03294       Geom::Point psx = getPoint(getEdge(ne).st).x;
03295       Geom::Point pex = getPoint(getEdge(ne).en).x;
03296         Geom::Point psbx=psx-bpx;
03297         Geom::Point pebx=pex-bpx;
03298       double pst = dot(psbx,bdx) * bdl;
03299       double pet = dot(pebx,bdx) * bdl;
03300       pst = iS->ebData[iB].tSt * (1 - pst) + iS->ebData[iB].tEn * pst;
03301       pet = iS->ebData[iB].tSt * (1 - pet) + iS->ebData[iB].tEn * pet;
03302       ebData[ne].tEn = pet;
03303       ebData[ne].tSt = pst;
03304     }
03305     }
03306   iS->swsData[iB].curPoint = iTo;
03307   if (ne >= 0)
03308     {
03309       int cp = iS->swsData[iB].firstLinkedPoint;
03310       swsData[ne].firstLinkedPoint = iS->swsData[iB].firstLinkedPoint;
03311       while (cp >= 0)
03312     {
03313       pData[cp].askForWindingB = ne;
03314       cp = pData[cp].nextLinkedPoint;
03315     }
03316       iS->swsData[iB].firstLinkedPoint = -1;
03317     }
03318 }

void Shape::EndQuickRaster (  ) 

Definition at line 109 of file ShapeRaster.cpp.

References MakeEdgeData(), MakePointData(), MakeQuickRasterData(), and MakeRasterData().

Referenced by raster_glyph::LoadSubPixelPosition(), and nr_pixblock_render_shape_mask_or().

00110 {
00111     MakePointData(false);
00112     MakeEdgeData(false);
00113     MakeRasterData(false);
00114     MakeQuickRasterData(false);
00115 }

void Shape::EndRaster (  ) 

Definition at line 65 of file ShapeRaster.cpp.

References MakeEdgeData(), MakePointData(), MakeRasterData(), NULL, sEvts, and sTree.

Referenced by Inkscape::Text::Layout::ShapeScanlineMaker::~ShapeScanlineMaker().

00066 {
00067     delete sTree;
00068     sTree = NULL;
00069     delete sEvts;
00070     sEvts = NULL;
00071     
00072     MakePointData(false);
00073     MakeEdgeData(false);
00074     MakeRasterData(false);
00075 }

void Shape::ForceToPolygon ( void   ) 

Definition at line 63 of file ShapeSweep.cpp.

References shape_polygon, and type.

Referenced by nr_arena_shape_update_fill(), and nr_arena_shape_update_stroke().

00064 {
00065   type = shape_polygon;
00066 }

dg_arete const& Shape::getEdge ( int  n  )  const [inline]

Definition at line 378 of file Shape.h.

References _aretes.

Referenced by _countUpDown(), _countUpDownTotalDegree2(), SweepEventQueue::add(), AddContour(), AddEdge(), AssembleAretes(), AvanceEdge(), BeginQuickRaster(), BeginRaster(), Booleen(), ConnectEnd(), ConnectStart(), SweepTree::ConvertTo(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), CreateEdge(), CreateIncidence(), CycleNextAt(), CyclePrevAt(), DirectQuickScan(), DirectScan(), DisconnectEnd(), DisconnectStart(), distance(), distanceLessThanOrEqual(), DoEdgeTo(), SweepTree::Find(), GetWindings(), initialiseEdgeData(), SweepTree::InsertAt(), Inverse(), SweepEvent::MakeDelete(), MakeOffset(), MakeTweak(), NextAt(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Other(), Plot(), PrevAt(), PtWinding(), QuickScan(), ReFormeArcTo(), ReFormeBezierTo(), ReFormeCubicTo(), ReFormeLineTo(), Reoriente(), Scan(), SortEdges(), sp_offset_distance_to_original(), sp_selected_path_boolop(), SubPoint(), SwapEdges(), SwapPoints(), TesteAdjacency(), TesteIntersection(), Validate(), and Winding().

00378 { return _aretes[n]; }

dg_point const& Shape::getPoint ( int  n  )  const [inline]

Definition at line 377 of file Shape.h.

References _pts.

Referenced by _countUpDown(), _countUpDownTotalDegree2(), _updateIntersection(), AddChgt(), AddContour(), AddEdge(), AssembleAretes(), AssemblePoints(), Avance(), AvanceEdge(), BeginQuickRaster(), BeginRaster(), Booleen(), CalcBBox(), CheckAdjacencies(), ConnectEnd(), ConnectStart(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), CreateEdge(), CreateIncidence(), CycleNextAt(), CyclePrevAt(), directedEulerian(), DirectQuickScan(), DirectScan(), DisconnectEnd(), DisconnectStart(), distance(), distanceLessThanOrEqual(), DoEdgeTo(), GetWindings(), initialisePointData(), SweepTree::Insert(), MakeOffset(), MakeTweak(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Plot(), PtWinding(), QuickScan(), ReFormeArcTo(), ReFormeBezierTo(), ReFormeCubicTo(), ReFormeLineTo(), Reoriente(), Scan(), SortEdges(), SortPoints(), SortPointsByOldInd(), sp_offset_distance_to_original(), sp_offset_top_point(), sp_selected_path_boolop(), SubPoint(), SwapEdges(), SwapPoints(), and Validate().

00377 { return _pts[n]; }

void Shape::GetWindings ( Shape *  a,
Shape *  b = NULL,
BooleanOp  mod = bool_op_union,
bool  brutal = false 
) [private]

Definition at line 2355 of file ShapeSweep.cpp.

References CyclePrevAt(), eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, Inverse(), numberOfEdges(), numberOfPoints(), pData, SortEdges(), Shape::dg_arete::st, swdData, Winding(), and voronoi::x.

Referenced by Booleen(), ConvertToShape(), and Reoriente().

02356 {
02357   // preparation du parcours
02358   for (int i = 0; i < numberOfEdges(); i++)
02359     {
02360       swdData[i].misc = 0;
02361       swdData[i].precParc = swdData[i].suivParc = -1;
02362     }
02363 
02364   // chainage
02365   SortEdges ();
02366 
02367   int searchInd = 0;
02368 
02369   int lastPtUsed = 0;
02370   do
02371     {
02372       int startBord = -1;
02373       int outsideW = 0;
02374       {
02375     int fi = 0;
02376     for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
02377       {
02378         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
02379           break;
02380       }
02381     lastPtUsed = fi + 1;
02382     if (fi < numberOfPoints())
02383       {
02384         int bestB = getPoint(fi).incidentEdge[FIRST];
02385         if (bestB >= 0)
02386           {
02387         startBord = bestB;
02388         if (fi == 0)
02389           {
02390             outsideW = 0;
02391           }
02392         else
02393           {
02394             if (brutal)
02395               {
02396             outsideW = Winding (getPoint(fi).x);
02397               }
02398             else
02399               {
02400             outsideW = Winding (fi);
02401               }
02402           }
02403     if ( getPoint(fi).totalDegree() == 1 ) {
02404       if ( fi == getEdge(startBord).en ) {
02405         if ( eData[startBord].weight == 0 ) {
02406           // on se contente d'inverser
02407           Inverse(startBord);
02408         } else {
02409           // on passe le askForWinding (sinon ca va rester startBord)
02410           pData[getEdge(startBord).st].askForWindingB=pData[getEdge(startBord).en].askForWindingB;
02411         }
02412       }
02413     }
02414         if (getEdge(startBord).en == fi)
02415           outsideW += eData[startBord].weight;
02416           }
02417       }
02418       }
02419       if (startBord >= 0)
02420     {
02421       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
02422       swdData[startBord].misc = (void *) 1;
02423       swdData[startBord].leW = outsideW;
02424       swdData[startBord].riW = outsideW - eData[startBord].weight;
02425 //    if ( doDebug ) printf("part de %d\n",startBord);
02426       int curBord = startBord;
02427       bool curDir = true;
02428       swdData[curBord].precParc = -1;
02429       swdData[curBord].suivParc = -1;
02430       do
02431         {
02432           int cPt;
02433           if (curDir)
02434         cPt = getEdge(curBord).en;
02435           else
02436         cPt = getEdge(curBord).st;
02437           int nb = curBord;
02438 //        if ( doDebug ) printf("de curBord= %d avec leF= %d et riF= %d  -> ",curBord,swdData[curBord].leW,swdData[curBord].riW);
02439           do
02440         {
02441           int nnb = -1;
02442           if (getEdge(nb).en == cPt)
02443             {
02444               outsideW = swdData[nb].riW;
02445               nnb = CyclePrevAt (cPt, nb);
02446             }
02447           else
02448             {
02449               outsideW = swdData[nb].leW;
02450               nnb = CyclePrevAt (cPt, nb);
02451             }
02452           if (nnb == nb)
02453             {
02454               // cul-de-sac
02455               nb = -1;
02456               break;
02457             }
02458           nb = nnb;
02459         }
02460           while (nb >= 0 && nb != curBord && swdData[nb].misc != 0);
02461           if (nb < 0 || nb == curBord)
02462         {
02463           // retour en arriere
02464           int oPt;
02465           if (curDir)
02466             oPt = getEdge(curBord).st;
02467           else
02468             oPt = getEdge(curBord).en;
02469           curBord = swdData[curBord].precParc;
02470 //    if ( doDebug ) printf("retour vers %d\n",curBord);
02471           if (curBord < 0)
02472             break;
02473           if (oPt == getEdge(curBord).en)
02474             curDir = true;
02475           else
02476             curDir = false;
02477         }
02478           else
02479         {
02480           swdData[nb].misc = (void *) 1;
02481           swdData[nb].ind = searchInd++;
02482           if (cPt == getEdge(nb).st)
02483             {
02484               swdData[nb].riW = outsideW;
02485               swdData[nb].leW = outsideW + eData[nb].weight;
02486             }
02487           else
02488             {
02489               swdData[nb].leW = outsideW;
02490               swdData[nb].riW = outsideW - eData[nb].weight;
02491             }
02492           swdData[nb].precParc = curBord;
02493           swdData[curBord].suivParc = nb;
02494           curBord = nb;
02495 //        if ( doDebug ) printf("suite %d\n",curBord);
02496           if (cPt == getEdge(nb).en)
02497             curDir = false;
02498           else
02499             curDir = true;
02500         }
02501         }
02502       while (1 /*swdData[curBord].precParc >= 0 */ );
02503       // fin du cas non-oriente
02504     }
02505     }
02506   while (lastPtUsed < numberOfPoints());
02507 //      fflush(stdout);
02508 }

static double Shape::HalfRound ( double  x  )  [inline, static]

Definition at line 273 of file Shape.h.

Referenced by Avance(), and TesteAdjacency().

00274     {
00275         return ldexp(x, -5);
00276     }

bool Shape::hasBackData (  )  const [inline]

Definition at line 375 of file Shape.h.

References _has_back_data.

Referenced by Booleen(), Path::DoLeftJoin(), Path::DoRightJoin(), and sp_selected_path_boolop().

00375 { return _has_back_data; }

bool Shape::hasEdges (  )  const [inline]

Definition at line 370 of file Shape.h.

References _aretes.

Referenced by SPFlowtext::_buildExclusionShape(), SPFlowtext::_buildLayoutInput(), and UnionShape().

00370 { return (_aretes.empty() == false); }

bool Shape::hasPoints (  )  const [inline]

Definition at line 368 of file Shape.h.

References _pts.

Referenced by AssemblePoints(), CalcBBox(), distance(), distanceLessThanOrEqual(), SortPoints(), SortPointsRounded(), and sp_offset_top_point().

00368 { return (_pts.empty() == false); }

static double Shape::IHalfRound ( double  x  )  [inline, static]

Definition at line 278 of file Shape.h.

Referenced by TesteAdjacency().

00279     {
00280         return ldexp(x, 5);
00281     }

void Shape::initialiseEdgeData (  )  [private]

Definition at line 2127 of file Shape.cpp.

References ffgeom::dot(), eData, Shape::dg_arete::en, getEdge(), Barcode::Code39Ext::i, polyhedron_3d::length(), N, NULL, numberOfEdges(), pData, Geom::sqrt(), Shape::dg_arete::st, and swsData.

Referenced by Booleen(), and ConvertToShape().

02128 {
02129     int const N = numberOfEdges();
02130 
02131     for (int i = 0; i < N; i++) {
02132         eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
02133         eData[i].length = dot(eData[i].rdx, eData[i].rdx);
02134         eData[i].ilength = 1 / eData[i].length;
02135         eData[i].sqlength = sqrt(eData[i].length);
02136         eData[i].isqlength = 1 / eData[i].sqlength;
02137         eData[i].siEd = eData[i].rdx[1] * eData[i].isqlength;
02138         eData[i].coEd = eData[i].rdx[0] * eData[i].isqlength;
02139         
02140         if (eData[i].siEd < 0) {
02141             eData[i].siEd = -eData[i].siEd;
02142             eData[i].coEd = -eData[i].coEd;
02143         }
02144 
02145         swsData[i].misc = NULL;
02146         swsData[i].firstLinkedPoint = -1;
02147         swsData[i].stPt = swsData[i].enPt = -1;
02148         swsData[i].leftRnd = swsData[i].rightRnd = -1;
02149         swsData[i].nextSh = NULL;
02150         swsData[i].nextBo = -1;
02151         swsData[i].curPoint = -1;
02152         swsData[i].doneTo = -1;
02153   }
02154 }

void Shape::initialisePointData (  )  [private]

Definition at line 2110 of file Shape.cpp.

References _point_data_initialised, getPoint(), Barcode::Code39Ext::i, N, numberOfPoints(), pData, Round(), and voronoi::x.

Referenced by BeginQuickRaster(), Booleen(), ConvertToShape(), and Reoriente().

02111 {
02112     if (_point_data_initialised)
02113         return;
02114     int const N = numberOfPoints();
02115   
02116     for (int i = 0; i < N; i++) {
02117         pData[i].pending = 0;
02118         pData[i].edgeOnLeft = -1;
02119         pData[i].nextLinkedPoint = -1;
02120         pData[i].rx[0] = Round(getPoint(i).x[0]);
02121         pData[i].rx[1] = Round(getPoint(i).x[1]);
02122     }
02123 
02124     _point_data_initialised = true;
02125 }

void Shape::Inverse ( int  b  ) 

Definition at line 1974 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_sweep_dest_data, _has_voronoi_data, _pts, Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), Shape::dg_arete::nextE, Shape::dg_arete::nextS, Shape::dg_arete::prevE, Shape::dg_arete::prevS, Shape::dg_arete::st, Geom::NL::swap(), swdData, and voreData.

Referenced by AssembleAretes(), Booleen(), ConvertToShape(), GetWindings(), MakeOffset(), MakeTweak(), and Reoriente().

01975 {
01976   int swap;
01977   swap = getEdge(b).st;
01978   _aretes[b].st = getEdge(b).en;
01979   _aretes[b].en = swap;
01980   swap = getEdge(b).prevE;
01981   _aretes[b].prevE = getEdge(b).prevS;
01982   _aretes[b].prevS = swap;
01983   swap = getEdge(b).nextE;
01984   _aretes[b].nextE = getEdge(b).nextS;
01985   _aretes[b].nextS = swap;
01986   _aretes[b].dx = -getEdge(b).dx;
01987   if (getEdge(b).st >= 0)
01988     {
01989       _pts[getEdge(b).st].dO++;
01990       _pts[getEdge(b).st].dI--;
01991     }
01992   if (getEdge(b).en >= 0)
01993     {
01994       _pts[getEdge(b).en].dO--;
01995       _pts[getEdge(b).en].dI++;
01996     }
01997   if (_has_edges_data)
01998     eData[b].weight = -eData[b].weight;
01999   if (_has_sweep_dest_data)
02000     {
02001       int swap = swdData[b].leW;
02002       swdData[b].leW = swdData[b].riW;
02003       swdData[b].riW = swap;
02004     }
02005   if (_has_back_data)
02006     {
02007       double swat = ebData[b].tSt;
02008       ebData[b].tSt = ebData[b].tEn;
02009       ebData[b].tEn = swat;
02010     }
02011   if (_has_voronoi_data)
02012     {
02013       int swai = voreData[b].leF;
02014       voreData[b].leF = voreData[b].riF;
02015       voreData[b].riF = swai;
02016     }
02017 }

void Shape::MakeBackData ( bool  nVal  ) 

Definition at line 186 of file Shape.cpp.

References _has_back_data, ebData, and maxAr.

Referenced by Booleen(), ConvertToShape(), Copy(), Path::Fill(), MakeOffset(), MakeTweak(), and Path::Stroke().

00187 {
00188   if (nVal)
00189     {
00190       if (_has_back_data == false)
00191         {
00192           _has_back_data = true;
00193           ebData.resize(maxAr);
00194         }
00195     }
00196   else
00197     {
00198       if (_has_back_data)
00199         {
00200           _has_back_data = false;
00201           ebData.clear();
00202         }
00203     }
00204 }

void Shape::MakeEdgeData ( bool  nVal  )  [private]

Definition at line 86 of file Shape.cpp.

References _has_edges_data, eData, and maxAr.

Referenced by BeginQuickRaster(), BeginRaster(), Booleen(), CleanupSweep(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), EndQuickRaster(), EndRaster(), Reoriente(), and ResetSweep().

00087 {
00088   if (nVal)
00089     {
00090       if (_has_edges_data == false)
00091         {
00092           _has_edges_data = true;
00093           eData.resize(maxAr);
00094         }
00095     }
00096   else
00097     {
00098       if (_has_edges_data)
00099         {
00100           _has_edges_data = false;
00101           eData.clear();
00102         }
00103     }
00104 }

int Shape::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 
)

Definition at line 721 of file ShapeMisc.cpp.

References _aretes, _bbox_up_to_date, _has_back_data, _has_edges_data, _has_points_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _point_data_initialised, _pts, AddEdge(), Geom::cos(), CycleNextAt(), CyclePrevAt(), Path::DoLeftJoin(), Path::DoRightJoin(), ffgeom::dot(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, Inverse(), Geom::L2(), M_PI, MakeBackData(), MakeSweepDestData(), MakeSweepSrcData(), maxAr, maxPt, MiscNormalize, numberOfEdges(), numberOfPoints(), pData, Geom::pow(), Reset(), shape_input_err, shape_nothing_to_do, shape_polygon, SortEdges(), Geom::sqrt(), Shape::dg_arete::st, swdData, swrData, swsData, type, and voronoi::x.

Referenced by do_trace(), sp_offset_set_shape(), and sp_selected_path_do_offset().

00722 {
00723   Reset (0, 0);
00724   MakeBackData(a->_has_back_data);
00725 
00726     bool done_something = false;
00727   
00728   if (dec == 0)
00729   {
00730     _pts = a->_pts;
00731     if (numberOfPoints() > maxPt)
00732     {
00733       maxPt = numberOfPoints();
00734       if (_has_points_data) {
00735         pData.resize(maxPt);
00736         _point_data_initialised = false;
00737         _bbox_up_to_date = false;
00738         }
00739     }
00740     
00741     _aretes = a->_aretes;
00742     if (numberOfEdges() > maxAr)
00743     {
00744       maxAr = numberOfEdges();
00745       if (_has_edges_data)
00746     eData.resize(maxAr);
00747       if (_has_sweep_src_data)
00748         swsData.resize(maxAr);
00749       if (_has_sweep_dest_data)
00750         swdData.resize(maxAr);
00751       if (_has_raster_data)
00752         swrData.resize(maxAr);
00753       if (_has_back_data)
00754         ebData.resize(maxAr);
00755     }
00756     return 0;
00757   }
00758   if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
00759     return shape_input_err;
00760   
00761   a->SortEdges ();
00762   
00763   a->MakeSweepDestData (true);
00764   a->MakeSweepSrcData (true);
00765   
00766   for (int i = 0; i < a->numberOfEdges(); i++)
00767   {
00768     //              int    stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/;
00769     int stB = -1, enB = -1;
00770     if (dec > 0)
00771     {
00772       stB = a->CycleNextAt (a->getEdge(i).st, i);
00773       enB = a->CyclePrevAt (a->getEdge(i).en, i);
00774     }
00775     else
00776     {
00777       stB = a->CyclePrevAt (a->getEdge(i).st, i);
00778       enB = a->CycleNextAt (a->getEdge(i).en, i);
00779     }
00780     
00781     Geom::Point stD, seD, enD;
00782     double stL, seL, enL;
00783     stD = a->getEdge(stB).dx;
00784     seD = a->getEdge(i).dx;
00785     enD = a->getEdge(enB).dx;
00786 
00787     stL = sqrt (dot(stD,stD));
00788     seL = sqrt (dot(seD,seD));
00789     enL = sqrt (dot(enD,enD));
00790     MiscNormalize (stD);
00791     MiscNormalize (enD);
00792     MiscNormalize (seD);
00793     
00794     Geom::Point ptP;
00795     int stNo, enNo;
00796     ptP = a->getPoint(a->getEdge(i).st).x;
00797 
00798         double this_dec;
00799         if (do_profile && i2doc) {
00800             double alpha = 1;
00801             double x = (Geom::L2(ptP * (*i2doc) - Geom::Point(cx,cy))/radius);
00802             if (x > 1) {
00803                 this_dec = 0;
00804             } else if (x <= 0) {
00805                 this_dec = dec;
00806             } else {
00807                 this_dec = dec * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5);
00808             }
00809         } else {
00810             this_dec = dec;
00811         }
00812 
00813         if (this_dec != 0)
00814             done_something = true;
00815 
00816     int   usePathID=-1;
00817     int   usePieceID=0;
00818     double useT=0.0;
00819     if ( a->_has_back_data ) {
00820       if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
00821            && a->ebData[stB].tEn == a->ebData[i].tSt ) {
00822         usePathID=a->ebData[i].pathID;
00823         usePieceID=a->ebData[i].pieceID;
00824         useT=a->ebData[i].tSt;
00825       } else {
00826         usePathID=a->ebData[i].pathID;
00827         usePieceID=0;
00828         useT=0;
00829       }
00830     }
00831     if (dec > 0)
00832     {
00833       Path::DoRightJoin (this, this_dec, join, ptP, stD, seD, miter, stL, seL,
00834                          stNo, enNo,usePathID,usePieceID,useT);
00835       a->swsData[i].stPt = enNo;
00836       a->swsData[stB].enPt = stNo;
00837     }
00838     else
00839     {
00840       Path::DoLeftJoin (this, -this_dec, join, ptP, stD, seD, miter, stL, seL,
00841                         stNo, enNo,usePathID,usePieceID,useT);
00842       a->swsData[i].stPt = enNo;
00843       a->swsData[stB].enPt = stNo;
00844     }
00845   }
00846 
00847   if (dec < 0)
00848   {
00849     for (int i = 0; i < numberOfEdges(); i++)
00850       Inverse (i);
00851   }
00852 
00853   if ( _has_back_data ) {
00854     for (int i = 0; i < a->numberOfEdges(); i++)
00855     {
00856       int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
00857       ebData[nEd]=a->ebData[i];
00858     }
00859   } else {
00860     for (int i = 0; i < a->numberOfEdges(); i++)
00861     {
00862       AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
00863     }
00864   }
00865 
00866   a->MakeSweepSrcData (false);
00867   a->MakeSweepDestData (false);
00868   
00869   return (done_something? 0 : shape_nothing_to_do);
00870 }

void Shape::MakePointData ( bool  nVal  )  [private]

Allocates space for point cache or clears the cache.

Parameters:
nVal Allocate a cache (true) or clear it (false)

Definition at line 70 of file Shape.cpp.

References _bbox_up_to_date, _has_points_data, _point_data_initialised, maxPt, and pData.

Referenced by BeginQuickRaster(), BeginRaster(), Booleen(), CleanupSweep(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), EndQuickRaster(), EndRaster(), Reoriente(), and ResetSweep().

00071 {
00072   if (nVal)
00073     {
00074       if (_has_points_data == false)
00075         {
00076           _has_points_data = true;
00077           _point_data_initialised = false;
00078           _bbox_up_to_date = false;
00079           pData.resize(maxPt);
00080         }
00081     }
00082     /* no need to clean point data - keep it cached*/
00083 }

void Shape::MakeQuickRasterData ( bool  nVal  )  [private]

Definition at line 127 of file Shape.cpp.

References _has_quick_raster_data, maxAr, and qrsData.

Referenced by BeginQuickRaster(), Copy(), and EndQuickRaster().

00128 {
00129   if (nVal)
00130     {
00131       if (_has_quick_raster_data == false)
00132         {
00133           _has_quick_raster_data = true;
00134           qrsData = (quick_raster_data*)realloc(qrsData, maxAr * sizeof(quick_raster_data));
00135         }
00136     }
00137   else
00138     {
00139       if (_has_quick_raster_data)
00140         {
00141           _has_quick_raster_data = false;
00142         }
00143     }
00144 }

void Shape::MakeRasterData ( bool  nVal  )  [private]

Definition at line 107 of file Shape.cpp.

References _has_raster_data, maxAr, and swrData.

Referenced by BeginQuickRaster(), BeginRaster(), Copy(), EndQuickRaster(), and EndRaster().

00108 {
00109   if (nVal)
00110     {
00111       if (_has_raster_data == false)
00112         {
00113           _has_raster_data = true;
00114           swrData.resize(maxAr);
00115         }
00116     }
00117   else
00118     {
00119       if (_has_raster_data)
00120         {
00121           _has_raster_data = false;
00122           swrData.clear();
00123         }
00124     }
00125 }

void Shape::MakeSweepDestData ( bool  nVal  )  [private]

Definition at line 166 of file Shape.cpp.

References _has_sweep_dest_data, maxAr, and swdData.

Referenced by Booleen(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), MakeOffset(), MakeTweak(), and Reoriente().

00167 {
00168   if (nVal)
00169     {
00170       if (_has_sweep_dest_data == false)
00171         {
00172           _has_sweep_dest_data = true;
00173           swdData.resize(maxAr);
00174         }
00175     }
00176   else
00177     {
00178       if (_has_sweep_dest_data)
00179         {
00180           _has_sweep_dest_data = false;
00181           swdData.clear();
00182         }
00183     }
00184 }

void Shape::MakeSweepSrcData ( bool  nVal  )  [private]

Definition at line 146 of file Shape.cpp.

References _has_sweep_src_data, maxAr, and swsData.

Referenced by Booleen(), CleanupSweep(), ConvertToShape(), Copy(), MakeOffset(), MakeTweak(), and ResetSweep().

00147 {
00148   if (nVal)
00149     {
00150       if (_has_sweep_src_data == false)
00151         {
00152           _has_sweep_src_data = true;
00153           swsData.resize(maxAr);
00154         }
00155     }
00156   else
00157     {
00158       if (_has_sweep_src_data)
00159         {
00160           _has_sweep_src_data = false;
00161           swsData.clear();
00162         }
00163     }
00164 }

int Shape::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 
)

Definition at line 531 of file ShapeMisc.cpp.

References _aretes, _bbox_up_to_date, _has_back_data, _has_edges_data, _has_points_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _point_data_initialised, _pts, AddEdge(), Geom::detail::bezier_clipping::angle(), Geom::cos(), CycleNextAt(), CyclePrevAt(), Path::DoLeftJoin(), Path::DoRightJoin(), ffgeom::dot(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, Inverse(), Geom::Matrix::inverse(), Geom::L2(), M_PI, MakeBackData(), MakeSweepDestData(), MakeSweepSrcData(), maxAr, maxPt, MiscNormalize, numberOfEdges(), numberOfPoints(), pData, Point, Geom::pow(), Reset(), shape_input_err, shape_nothing_to_do, shape_polygon, Geom::sin(), SortEdges(), Geom::sqrt(), Shape::dg_arete::st, swdData, swrData, swsData, tweak_mode_push, tweak_mode_repel, tweak_mode_roughen, type, and voronoi::x.

Referenced by sp_tweak_dilate_recursive().

00532 {
00533   Reset (0, 0);
00534   MakeBackData(a->_has_back_data);
00535 
00536     bool done_something = false;
00537 
00538   if (power == 0)
00539   {
00540     _pts = a->_pts;
00541     if (numberOfPoints() > maxPt)
00542     {
00543       maxPt = numberOfPoints();
00544       if (_has_points_data) {
00545         pData.resize(maxPt);
00546         _point_data_initialised = false;
00547         _bbox_up_to_date = false;
00548         }
00549     }
00550     
00551     _aretes = a->_aretes;
00552     if (numberOfEdges() > maxAr)
00553     {
00554       maxAr = numberOfEdges();
00555       if (_has_edges_data)
00556           eData.resize(maxAr);
00557       if (_has_sweep_src_data)
00558         swsData.resize(maxAr);
00559       if (_has_sweep_dest_data)
00560         swdData.resize(maxAr);
00561       if (_has_raster_data)
00562         swrData.resize(maxAr);
00563       if (_has_back_data)
00564         ebData.resize(maxAr);
00565     }
00566     return 0;
00567   }
00568   if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
00569     return shape_input_err;
00570   
00571   a->SortEdges ();
00572   
00573   a->MakeSweepDestData (true);
00574   a->MakeSweepSrcData (true);
00575   
00576   for (int i = 0; i < a->numberOfEdges(); i++)
00577   {
00578     int stB = -1, enB = -1;
00579     if (power <= 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen)  {
00580       stB = a->CyclePrevAt (a->getEdge(i).st, i);
00581       enB = a->CycleNextAt (a->getEdge(i).en, i);
00582     } else {
00583       stB = a->CycleNextAt (a->getEdge(i).st, i);
00584       enB = a->CyclePrevAt (a->getEdge(i).en, i);
00585     }
00586     
00587     Geom::Point stD, seD, enD;
00588     double stL, seL, enL;
00589     stD = a->getEdge(stB).dx;
00590     seD = a->getEdge(i).dx;
00591     enD = a->getEdge(enB).dx;
00592 
00593     stL = sqrt (dot(stD,stD));
00594     seL = sqrt (dot(seD,seD));
00595     enL = sqrt (dot(enD,enD));
00596     MiscNormalize (stD);
00597     MiscNormalize (enD);
00598     MiscNormalize (seD);
00599     
00600     Geom::Point ptP;
00601     int stNo, enNo;
00602     ptP = a->getPoint(a->getEdge(i).st).x;
00603 
00604     Geom::Point to_center = ptP * (*i2doc) - c;
00605     Geom::Point to_center_normalized = (1/Geom::L2(to_center)) * to_center;
00606 
00607         double this_power;
00608         if (do_profile && i2doc) {
00609             double alpha = 1;
00610             double x;
00611         if (mode == tweak_mode_repel) {
00612                 x = (Geom::L2(to_center)/radius);
00613             } else {
00614                 x = (Geom::L2(ptP * (*i2doc) - c)/radius);
00615             }
00616             if (x > 1) {
00617                 this_power = 0;
00618             } else if (x <= 0) {
00619             if (mode == tweak_mode_repel) {
00620                     this_power = 0;
00621                 } else {
00622                     this_power = power;
00623                 }
00624             } else {
00625                 this_power = power * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5);
00626             }
00627         } else {
00628         if (mode == tweak_mode_repel) {
00629                 this_power = 0;
00630             } else {
00631                 this_power = power;
00632             }
00633         }
00634 
00635         if (this_power != 0)
00636             done_something = true;
00637 
00638         double scaler = 1 / (*i2doc).descrim();
00639 
00640         Geom::Point this_vec(0,0);
00641     if (mode == tweak_mode_push) {
00642             Geom::Matrix tovec (*i2doc);
00643             tovec[4] = tovec[5] = 0;
00644             tovec = tovec.inverse();
00645             this_vec = this_power * (vector * tovec) ;
00646         } else if (mode == tweak_mode_repel) {
00647             this_vec = this_power * scaler * to_center_normalized;
00648         } else if (mode == tweak_mode_roughen) {
00649         double angle = g_random_double_range(0, 2*M_PI);
00650         this_vec = g_random_double_range(0, 1) * this_power * scaler * Geom::Point(sin(angle), cos(angle));
00651         }
00652 
00653     int   usePathID=-1;
00654     int   usePieceID=0;
00655     double useT=0.0;
00656     if ( a->_has_back_data ) {
00657       if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
00658            && a->ebData[stB].tEn == a->ebData[i].tSt ) {
00659         usePathID=a->ebData[i].pathID;
00660         usePieceID=a->ebData[i].pieceID;
00661         useT=a->ebData[i].tSt;
00662       } else {
00663         usePathID=a->ebData[i].pathID;
00664         usePieceID=0;
00665         useT=0;
00666       }
00667     }
00668 
00669         if (mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen) {
00670             Path::DoLeftJoin (this, 0, join, ptP+this_vec, stD+this_vec, seD+this_vec, miter, stL, seL,
00671                                                 stNo, enNo,usePathID,usePieceID,useT);
00672             a->swsData[i].stPt = enNo;
00673             a->swsData[stB].enPt = stNo;
00674         } else {
00675             if (power > 0) {
00676                 Path::DoRightJoin (this, this_power * scaler, join, ptP, stD, seD, miter, stL, seL,
00677                                                      stNo, enNo,usePathID,usePieceID,useT);
00678                 a->swsData[i].stPt = enNo;
00679                 a->swsData[stB].enPt = stNo;
00680             } else {
00681                 Path::DoLeftJoin (this, -this_power * scaler, join, ptP, stD, seD, miter, stL, seL,
00682                                                     stNo, enNo,usePathID,usePieceID,useT);
00683                 a->swsData[i].stPt = enNo;
00684                 a->swsData[stB].enPt = stNo;
00685             }
00686         }
00687   }
00688 
00689   if (power < 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen)
00690   {
00691     for (int i = 0; i < numberOfEdges(); i++)
00692       Inverse (i);
00693   }
00694 
00695   if ( _has_back_data ) {
00696     for (int i = 0; i < a->numberOfEdges(); i++)
00697     {
00698       int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
00699       ebData[nEd]=a->ebData[i];
00700     }
00701   } else {
00702     for (int i = 0; i < a->numberOfEdges(); i++)
00703     {
00704       AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
00705     }
00706   }
00707 
00708   a->MakeSweepSrcData (false);
00709   a->MakeSweepDestData (false);
00710   
00711   return (done_something? 0 : shape_nothing_to_do);
00712 }

void Shape::MakeVoronoiData ( bool  nVal  ) 

Definition at line 206 of file Shape.cpp.

References _has_voronoi_data, maxAr, maxPt, voreData, and vorpData.

00207 {
00208   if (nVal)
00209     {
00210       if (_has_voronoi_data == false)
00211         {
00212           _has_voronoi_data = true;
00213           vorpData.resize(maxPt);
00214           voreData.resize(maxAr);
00215         }
00216     }
00217   else
00218     {
00219       if (_has_voronoi_data)
00220         {
00221           _has_voronoi_data = false;
00222           vorpData.clear();
00223           voreData.clear();
00224         }
00225     }
00226 }

void Shape::needEdgesSorting (  )  [inline]

Definition at line 373 of file Shape.h.

References _need_edges_sorting.

Referenced by nr_arena_shape_update_fill(), and nr_arena_shape_update_stroke().

00373 { _need_edges_sorting = true; }

void Shape::needPointsSorting (  )  [inline]

Definition at line 372 of file Shape.h.

References _need_points_sorting.

Referenced by nr_arena_shape_update_fill(), and nr_arena_shape_update_stroke().

00372 { _need_points_sorting = true; }

int Shape::NextAt ( int  p,
int  b 
) const [inline]

Definition at line 163 of file Shape.h.

References getEdge(), Shape::dg_arete::nextE, and Shape::dg_arete::nextS.

Referenced by _countUpDown(), AddEdge(), AssembleAretes(), Booleen(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), QuickScan(), Scan(), SortEdges(), sp_offset_distance_to_original(), sp_selected_path_boolop(), and SwapPoints().

00164     {
00165         if (p == getEdge(b).st) {
00166             return getEdge(b).nextS;
00167         }
00168         else if (p == getEdge(b).en) {
00169             return getEdge(b).nextE;
00170         }
00171 
00172         return -1;
00173     }

int Shape::numberOfEdges (  )  const [inline]

Definition at line 369 of file Shape.h.

References _aretes.

Referenced by _countUpDown(), AddEdge(), AssembleAretes(), AssemblePoints(), BeginQuickRaster(), BeginRaster(), Booleen(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), DirectQuickScan(), DirectScan(), distance(), distanceLessThanOrEqual(), GetWindings(), initialiseEdgeData(), MakeOffset(), MakeTweak(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Plot(), PtWinding(), QuickScan(), Reoriente(), Scan(), SortEdges(), sp_offset_distance_to_original(), sp_selected_path_boolop(), SubEdge(), SubPoint(), SwapEdges(), Validate(), and Winding().

00369 { return _aretes.size(); }

int Shape::numberOfPoints (  )  const [inline]

Definition at line 367 of file Shape.h.

References _pts.

Referenced by AddPoint(), AssembleAretes(), AssemblePoints(), Avance(), BeginQuickRaster(), BeginRaster(), Booleen(), CalcBBox(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), directedEulerian(), DirectQuickScan(), DirectScan(), distance(), distanceLessThanOrEqual(), Path::Fill(), GetWindings(), initialisePointData(), MakeOffset(), MakeTweak(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Plot(), QuickScan(), Reoriente(), Scan(), SortEdges(), SortPoints(), SortPointsRounded(), sp_offset_distance_to_original(), sp_selected_path_boolop(), SubPoint(), SwapPoints(), and Validate().

00367 { return _pts.size(); }

int Shape::Other ( int  p,
int  b 
) const [inline]

Definition at line 154 of file Shape.h.

References Shape::dg_arete::en, getEdge(), and Shape::dg_arete::st.

Referenced by AssembleAretes(), DirectScan(), and Scan().

00155     {
00156         if (getEdge(b).st == p) {
00157             return getEdge(b).en;
00158         }
00159         return getEdge(b).st;
00160     }

void Shape::Plot ( double  ix,
double  iy,
double  ir,
double  mx,
double  my,
bool  doPoint,
bool  edgesNo,
bool  pointNo,
bool  doDir,
char *  fileName 
)

Definition at line 17 of file ShapeDraw.cpp.

References Shape::dg_arete::en, getEdge(), getPoint(), Barcode::Code39Ext::i, numberOfEdges(), numberOfPoints(), Shape::dg_arete::st, and Shape::dg_point::x.

00019 {
00020   FILE*  outFile=fopen(fileName,"w+");
00021 //  fprintf(outFile,"\n\n\n");
00022   fprintf(outFile,"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n");
00023   fprintf(outFile,"<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.0//EN\"\n");
00024   fprintf(outFile,"\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n");
00025   fprintf(outFile,"<svg:svg\n");
00026   fprintf(outFile,"   id=\"svg1\"\n");
00027   fprintf(outFile,"   inkscape:version=\"0.38cvs\"\n");
00028   fprintf(outFile,"   xmlns:svg=\"http://www.w3.org/2000/svg\"\n");
00029   fprintf(outFile,"   xmlns:sodipodi=\"http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd\"\n");
00030   fprintf(outFile,"   xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\"\n");
00031   fprintf(outFile,"   xmlns:xlink=\"http://www.w3.org/1999/xlink\"\n");
00032   fprintf(outFile,"   width=\"210mm\"\n");
00033   fprintf(outFile,"   height=\"297mm\"\n");
00034   fprintf(outFile,"   sodipodi:docbase=\"/Volumes/Sancho/inkscapecvs\"\n");
00035   fprintf(outFile,"   sodipodi:docname=\"/Volumes/Sancho/inkscapecvs/modele.svg\">\n");
00036   fprintf(outFile,"  <svg:defs\n");
00037   fprintf(outFile,"     id=\"defs3\" />\n");
00038   fprintf(outFile,"  <sodipodi:namedview\n");
00039   fprintf(outFile,"     id=\"base\"\n");
00040   fprintf(outFile,"     pagecolor=\"#ffffff\"\n");
00041   fprintf(outFile,"     bordercolor=\"#666666\"\n");
00042   fprintf(outFile,"     borderopacity=\"1.0\"\n");
00043   fprintf(outFile,"     inkscape:pageopacity=\"0.0\"\n");
00044   fprintf(outFile,"     inkscape:pageshadow=\"2\"\n");
00045   fprintf(outFile,"     inkscape:zoom=\"0.43415836\"\n");
00046   fprintf(outFile,"     inkscape:cx=\"305.25952637\"\n");
00047   fprintf(outFile,"     inkscape:cy=\"417.84947271\"\n");
00048   fprintf(outFile,"     inkscape:window-width=\"640\"\n");
00049   fprintf(outFile,"     inkscape:window-height=\"496\"\n");
00050   fprintf(outFile,"     inkscape:window-x=\"20\"\n");
00051   fprintf(outFile,"     inkscape:window-y=\"42\" />\n");
00052   
00053     if ( doPoint ) {
00054         for (int i=0;i<numberOfPoints();i++) {
00055             double   ph=(getPoint(i).x[0]-ix)*ir+mx;
00056             double   pv=(getPoint(i).x[1]-iy)*ir+my;
00057       fprintf(outFile,"     <svg:circle cx=\"%f\" cy=\"%f\" r=\"5\" fill=\"none\" stroke=\"red\" stroke-width=\"0.25\" />\n",ph,pv); // localizing ok
00058     }
00059     }
00060   if ( pointsNo ) {
00061         for (int i=0;i<numberOfPoints();i++) {
00062             double   ph=(getPoint(i).x[0]-ix)*ir+mx;
00063             double   pv=(getPoint(i).x[1]-iy)*ir+my;
00064       fprintf(outFile,"     <svg:text x=\"%f\" y=\"%f\" font-family=\"Monaco\" font-size=\"5\" fill=\"blue\" >\n",ph-2,pv+1); // localizing ok
00065       fprintf(outFile,"%i\n",i);
00066       fprintf(outFile,"     </text>\n");
00067     }
00068   }
00069     {
00070         for (int i=0;i<numberOfEdges();i++) {
00071             int     stP=getEdge(i).st;
00072             int     enP=getEdge(i).en;
00073             if ( stP < 0 || enP < 0 ) continue;
00074             double   sh=(getPoint(stP).x[0]-ix)*ir+mx;
00075             double   sv=(getPoint(stP).x[1]-iy)*ir+my;
00076             double   eh=(getPoint(enP).x[0]-ix)*ir+mx;
00077             double   ev=(getPoint(enP).x[1]-iy)*ir+my;
00078             if ( doDir ) {
00079                 double   endh=(9*eh+1*sh)/10;
00080                 double   endv=(9*ev+1*sv)/10;
00081         fprintf(outFile,"     <svg:line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" stroke=\"black\" stroke-width=\"0.5\" />\n",sh,sv,endh,endv); // localizing ok
00082             } else {
00083         fprintf(outFile,"     <svg:line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" stroke=\"black\" stroke-width=\"0.5\" />\n",sh,sv,eh,ev); // localizing ok
00084             }
00085         }
00086     }
00087   if ( edgesNo ) {
00088         for (int i=0;i<numberOfEdges();i++) {
00089             int     stP=getEdge(i).st;
00090             int     enP=getEdge(i).en;
00091             if ( stP < 0 || enP < 0 ) continue;
00092             double   sh=(getPoint(stP).x[0]-ix)*ir+mx;
00093             double   sv=(getPoint(stP).x[1]-iy)*ir+my;
00094             double   eh=(getPoint(enP).x[0]-ix)*ir+mx;
00095             double   ev=(getPoint(enP).x[1]-iy)*ir+my;
00096       fprintf(outFile,"     <svg:text x=\"%f\" y=\"%f\" font-family=\"Monaco\" font-size=\"5\" fill=\"blue\" >\n",(sh+eh)/2+2,(sv+ev)/2); // localizing ok
00097       fprintf(outFile,"%i\n",i);
00098       fprintf(outFile,"     </text>\n");
00099         }
00100   }
00101   
00102   fprintf(outFile,"</svg>\n");
00103   fclose(outFile);
00104 
00105 }

int Shape::PrevAt ( int  p,
int  b 
) const [inline]

Definition at line 176 of file Shape.h.

References getEdge(), Shape::dg_arete::prevE, and Shape::dg_arete::prevS.

00177     {
00178         if (p == getEdge(b).st) {
00179             return getEdge(b).prevS;
00180         }
00181         else if (p == getEdge(b).en) {
00182             return getEdge(b).prevE;
00183         }
00184 
00185         return -1;
00186     }

int Shape::PtWinding ( const Geom::Point  px  )  const

Definition at line 2057 of file Shape.cpp.

References Geom::cross(), Shape::dg_arete::dx, getEdge(), getPoint(), Barcode::Code39Ext::i, numberOfEdges(), and Shape::dg_point::x.

02058 {
02059   int lr = 0, ll = 0, rr = 0;
02060   
02061   for (int i = 0; i < numberOfEdges(); i++)
02062   {
02063     Geom::Point const adir = getEdge(i).dx;
02064 
02065     Geom::Point const ast = getPoint(getEdge(i).st).x;
02066     Geom::Point const aen = getPoint(getEdge(i).en).x;
02067     
02068     //int const nWeight = eData[i].weight;
02069     int const nWeight = 1;
02070 
02071     if (ast[0] < aen[0]) {
02072       if (ast[0] > px[0]) continue;
02073       if (aen[0] < px[0]) continue;
02074     } else {
02075       if (ast[0] < px[0]) continue;
02076       if (aen[0] > px[0]) continue;
02077     }
02078     if (ast[0] == px[0]) {
02079       if (ast[1] >= px[1]) continue;
02080       if (aen[0] == px[0]) continue;
02081       if (aen[0] < px[0]) ll += nWeight;  else rr -= nWeight;
02082       continue;
02083     }
02084     if (aen[0] == px[0]) {
02085       if (aen[1] >= px[1]) continue;
02086       if (ast[0] == px[0]) continue;
02087       if (ast[0] < px[0]) ll -= nWeight; else rr += nWeight;
02088       continue;
02089     }
02090     
02091     if (ast[1] < aen[1]) {
02092       if (ast[1] >= px[1])  continue;
02093     } else {
02094       if (aen[1] >= px[1]) continue;
02095     }
02096 
02097     Geom::Point const diff = px - ast;
02098     double const cote = cross(diff, adir);
02099     if (cote == 0) continue;
02100     if (cote < 0) {
02101       if (ast[0] > px[0]) lr += nWeight;
02102     } else {
02103       if (ast[0] < px[0]) lr -= nWeight;
02104     }
02105   }
02106   return lr + (ll + rr) / 2;
02107 }

int Shape::PushIncidence ( Shape *  a,
int  cb,
int  pt,
double  theta 
) [private]

Definition at line 1982 of file ShapeSweep.cpp.

References iData, maxInc, n, nbInc, Shape::incidenceData::nextInc, Shape::incidenceData::pt, swsData, and Shape::incidenceData::theta.

Referenced by CreateIncidence(), and TesteAdjacency().

01983 {
01984   if (theta < 0 || theta > 1)
01985     return -1;
01986 
01987   if (nbInc >= maxInc)
01988     {
01989       maxInc = 2 * nbInc + 1;
01990       iData =
01991     (incidenceData *) g_realloc(iData, maxInc * sizeof (incidenceData));
01992     }
01993   int n = nbInc++;
01994   iData[n].nextInc = a->swsData[cb].firstLinkedPoint;
01995   iData[n].pt = pt;
01996   iData[n].theta = theta;
01997   a->swsData[cb].firstLinkedPoint = n;
01998   return n;
01999 }

int Shape::QuickRasterAddEdge ( int  bord,
double  x,
int  guess 
) [private]

Definition at line 395 of file ShapeRaster.cpp.

References Shape::quick_raster_data::bord, c, CmpQRs(), firstQRas, Shape::quick_raster_data::ind, lastQRas, nbQRas, Shape::quick_raster_data::next, Shape::quick_raster_data::prev, qrsData, and Shape::quick_raster_data::x.

Referenced by DirectQuickScan(), and QuickScan().

00396 {
00397     int no = nbQRas++;
00398     qrsData[no].bord = bord;
00399     qrsData[no].x = x;
00400     qrsData[bord].ind = no;
00401     qrsData[no].prev = -1;
00402     qrsData[no].next = -1;
00403     
00404     if ( no < 0 || no >= nbQRas ) {
00405         return -1;
00406     }
00407   
00408     if ( firstQRas < 0 ) {
00409         firstQRas = lastQRas = no;
00410         qrsData[no].prev = -1;
00411         qrsData[no].next = -1;
00412         return no;
00413     }
00414 
00415     if ( guess < 0 || guess >= nbQRas ) {
00416 
00417         int c = firstQRas;
00418         while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
00419             c = qrsData[c].next;
00420         }
00421         
00422         if ( c < 0 || c >= nbQRas ) {
00423             qrsData[no].prev = lastQRas;
00424             qrsData[lastQRas].next = no;
00425             lastQRas = no;
00426         } else {
00427             qrsData[no].prev = qrsData[c].prev;
00428             if ( qrsData[no].prev >= 0 ) {
00429                 qrsData[qrsData[no].prev].next=no;
00430             } else {
00431                 firstQRas = no;
00432             }
00433             
00434             qrsData[no].next = c;
00435             qrsData[c].prev = no;
00436         }
00437         
00438     } else {
00439         int c = guess;
00440         int stTst = CmpQRs(qrsData[c],qrsData[no]);
00441         if ( stTst == 0 ) {
00442 
00443             qrsData[no].prev = qrsData[c].prev;
00444             if ( qrsData[no].prev >= 0 ) {
00445                 qrsData[qrsData[no].prev].next = no;
00446             } else {
00447                 firstQRas = no;
00448             }
00449             
00450             qrsData[no].next = c;
00451             qrsData[c].prev = no;
00452             
00453         } else if ( stTst > 0 ) {
00454 
00455             while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) > 0 ) {
00456                 c = qrsData[c].prev;
00457             }
00458             
00459             if ( c < 0 || c >= nbQRas ) {
00460                 qrsData[no].next = firstQRas;
00461                 qrsData[firstQRas].prev = no; // firstQRas != -1
00462                 firstQRas = no;
00463             } else {
00464                 qrsData[no].next = qrsData[c].next;
00465                 if ( qrsData[no].next >= 0 ) {
00466                     qrsData[qrsData[no].next].prev = no;
00467                 } else {
00468                     lastQRas = no;
00469                 }
00470                 qrsData[no].prev = c;
00471                 qrsData[c].next = no;
00472             }
00473             
00474         } else {
00475 
00476             while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
00477                 c = qrsData[c].next;
00478             }
00479             
00480             if ( c < 0 || c >= nbQRas ) {
00481                 qrsData[no].prev = lastQRas;
00482                 qrsData[lastQRas].next = no;
00483                 lastQRas = no;
00484             } else {
00485                 qrsData[no].prev = qrsData[c].prev;
00486                 if ( qrsData[no].prev >= 0 ) {
00487                     qrsData[qrsData[no].prev].next = no;
00488                 } else {
00489                     firstQRas = no;
00490                 }
00491                 
00492                 qrsData[no].next = c;
00493                 qrsData[c].prev = no;
00494             }
00495         }
00496     }
00497   
00498     return no;
00499 }

int Shape::QuickRasterChgEdge ( int  oBord,
int  nbord,
double  x 
) [private]

Definition at line 376 of file ShapeRaster.cpp.

References Shape::quick_raster_data::bord, Shape::quick_raster_data::ind, qrsData, and Shape::quick_raster_data::x.

Referenced by QuickScan().

00377 {
00378     if ( oBord == nBord ) {
00379         return -1;
00380     }
00381     
00382     int no = qrsData[oBord].ind;
00383     if ( no >= 0 ) {
00384         qrsData[no].bord = nBord;
00385         qrsData[no].x = x;
00386         qrsData[oBord].ind = -1;
00387         qrsData[nBord].ind = no;
00388     }
00389     
00390     return no;
00391 }

void Shape::QuickRasterSort (  )  [private]

Definition at line 575 of file ShapeRaster.cpp.

References Shape::quick_raster_data::bord, CmpQRs(), firstQRas, Shape::quick_raster_data::ind, nbQRas, Shape::quick_raster_data::next, Shape::quick_raster_data::prev, qrsData, and QuickRasterSwapEdge().

Referenced by DirectQuickScan(), and QuickScan().

00576 {
00577     if ( nbQRas <= 1 ) {
00578         return;
00579     }
00580     
00581     int cb = qrsData[firstQRas].bord;
00582     
00583     while ( cb >= 0 ) {
00584         int bI = qrsData[cb].ind;
00585         int nI = qrsData[bI].next;
00586         
00587         if ( nI < 0 ) {
00588             break;
00589         }
00590     
00591         int ncb = qrsData[nI].bord;
00592         if ( CmpQRs(qrsData[nI], qrsData[bI]) < 0 ) {
00593             QuickRasterSwapEdge(cb, ncb);
00594             int pI = qrsData[bI].prev; // ca reste bI, puisqu'on a juste echange les contenus
00595             if ( pI < 0 ) {
00596                 cb = ncb; // en fait inutile; mais bon...
00597             } else {
00598                 int pcb = qrsData[pI].bord;
00599                 cb = pcb;
00600             }
00601         } else {
00602             cb = ncb;
00603         }
00604     }
00605 }

void Shape::QuickRasterSubEdge ( int  bord  )  [private]

Definition at line 503 of file ShapeRaster.cpp.

References Shape::quick_raster_data::bord, firstQRas, Shape::quick_raster_data::ind, lastQRas, nbQRas, Shape::quick_raster_data::next, Shape::quick_raster_data::prev, and qrsData.

Referenced by DirectQuickScan(), and QuickScan().

00504 {
00505     int no = qrsData[bord].ind;
00506     if ( no < 0 || no >= nbQRas ) {
00507         return; // euuhHHH
00508     }
00509     
00510     if ( qrsData[no].prev >= 0 ) {
00511         qrsData[qrsData[no].prev].next=qrsData[no].next;
00512     }
00513     
00514     if ( qrsData[no].next >= 0 ) {
00515         qrsData[qrsData[no].next].prev = qrsData[no].prev;
00516     }
00517     
00518     if ( no == firstQRas ) {
00519         firstQRas = qrsData[no].next;
00520     }
00521     
00522     if ( no == lastQRas ) {
00523         lastQRas = qrsData[no].prev;
00524     }
00525     
00526     qrsData[no].prev = qrsData[no].next = -1;
00527   
00528     int savInd = qrsData[no].ind;
00529     qrsData[no] = qrsData[--nbQRas];
00530     qrsData[no].ind = savInd;
00531     qrsData[qrsData[no].bord].ind = no;
00532     qrsData[bord].ind = -1;
00533   
00534     if ( nbQRas > 0 ) {
00535         if ( firstQRas == nbQRas ) {
00536             firstQRas = no;
00537         }
00538         if ( lastQRas == nbQRas ) {
00539             lastQRas = no;
00540         }
00541         if ( qrsData[no].prev >= 0 ) {
00542             qrsData[qrsData[no].prev].next = no;
00543         }
00544         if ( qrsData[no].next >= 0 ) {
00545             qrsData[qrsData[no].next].prev = no;
00546         }
00547     }  
00548 }

void Shape::QuickRasterSwapEdge ( int  a,
int  b 
) [private]

Definition at line 552 of file ShapeRaster.cpp.

References Shape::quick_raster_data::bord, Shape::quick_raster_data::ind, nbQRas, qrsData, and Shape::quick_raster_data::x.

Referenced by QuickRasterSort().

00553 {
00554     if ( a == b ) {
00555         return;
00556     }
00557     
00558     int na = qrsData[a].ind;
00559     int nb = qrsData[b].ind;
00560     if ( na < 0 || na >= nbQRas || nb < 0 || nb >= nbQRas ) {
00561         return; // errrm
00562     }
00563   
00564     qrsData[na].bord = b;
00565     qrsData[nb].bord = a;
00566     qrsData[a].ind = nb;
00567     qrsData[b].ind = na;
00568     
00569     double swd = qrsData[na].x;
00570     qrsData[na].x = qrsData[nb].x;
00571     qrsData[nb].x = swd;
00572 }

void Shape::QuickScan ( float &  pos,
int &  curP,
float  to,
AlphaLigne *  line,
float  step 
)

Definition at line 1524 of file ShapeRaster.cpp.

References _countUpDown(), _countUpDownTotalDegree2(), _updateIntersection(), AvanceEdge(), Shape::quick_raster_data::bord, CreateEdge(), DestroyEdge(), addnodes::e, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, max, min, nbQRas, NextAt(), NULL, numberOfEdges(), numberOfPoints(), qrsData, QuickRasterAddEdge(), QuickRasterChgEdge(), QuickRasterSort(), QuickRasterSubEdge(), Shape::dg_arete::st, swrData, Shape::quick_raster_data::x, Shape::dg_point::x, and voronoi::x.

01525 {
01526     if ( numberOfEdges() <= 1 ) {
01527         return;
01528     }
01529     if ( pos >= to ) {
01530         return;
01531     }
01532     
01533     int curPt = curP;
01534     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
01535         int nPt = curPt++;
01536 
01537         int nbUp;
01538         int nbDn;
01539         int upNo;
01540         int dnNo;
01541         if ( getPoint(nPt).totalDegree() == 2 ) {
01542             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
01543         } else {
01544             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
01545         }
01546         
01547         if ( nbDn <= 0 ) {
01548             upNo = -1;
01549         }
01550         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
01551             upNo = -1;
01552         }
01553 
01554         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
01555             int cb = getPoint(nPt).incidentEdge[FIRST];
01556             while ( cb >= 0 && cb < numberOfEdges() ) {
01557                 Shape::dg_arete const &e = getEdge(cb);
01558                 if ( nPt == std::max(e.st, e.en) ) {
01559                     if ( cb != upNo ) {
01560                         QuickRasterSubEdge(cb);
01561                         _updateIntersection(cb, nPt);
01562                         DestroyEdge(cb, line);
01563                     }
01564                 }
01565                 cb = NextAt(nPt,cb);
01566             }
01567         }
01568 
01569         // traitement du "upNo devient dnNo"
01570         int ins_guess = -1;
01571         if ( dnNo >= 0 ) {
01572             if ( upNo >= 0 ) {
01573                 ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
01574                 _updateIntersection(upNo, nPt);
01575                 DestroyEdge(upNo, line);
01576 
01577                 CreateEdge(dnNo, to, step);
01578                 swrData[dnNo].guess = swrData[upNo].guess;
01579             } else {
01580                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
01581                 CreateEdge(dnNo, to, step);
01582             }
01583         }
01584 
01585         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
01586             int cb = getPoint(nPt).incidentEdge[FIRST];
01587             while ( cb >= 0 && cb < numberOfEdges() ) {
01588                 Shape::dg_arete const &e = getEdge(cb);
01589                 if ( nPt == std::min(e.st, e.en) ) {
01590                     if ( cb != dnNo ) {
01591                         ins_guess = QuickRasterAddEdge(cb,getPoint(nPt).x[0], ins_guess);
01592                         CreateEdge(cb, to, step);
01593                     }
01594                 }
01595                 cb = NextAt(nPt,cb);
01596             }
01597         }
01598     }
01599 
01600     curP = curPt;
01601     if ( curPt > 0 ) {
01602         pos = getPoint(curPt-1).x[1];
01603     } else {
01604         pos = to;
01605     }
01606     
01607     pos = to;
01608     for (int i = 0; i < nbQRas; i++) {
01609         int cb = qrsData[i].bord;
01610         AvanceEdge(cb, to, line, true, step);
01611         qrsData[i].x = swrData[cb].curX;
01612     }
01613     
01614     QuickRasterSort();
01615 }

void Shape::QuickScan ( float &  pos,
int &  curP,
float  to,
FillRule  directed,
BitLigne *  line,
float  step 
)

Definition at line 1373 of file ShapeRaster.cpp.

References _countUpDown(), _countUpDownTotalDegree2(), _updateIntersection(), BitLigne::AddBord(), AvanceEdge(), Shape::quick_raster_data::bord, CreateEdge(), DestroyEdge(), addnodes::e, Shape::dg_arete::en, fill_nonZero, fill_oddEven, fill_positive, FIRST, firstQRas, getEdge(), getPoint(), Barcode::Code39Ext::i, Shape::dg_point::incidentEdge, max, min, nbQRas, Shape::quick_raster_data::next, NextAt(), NULL, numberOfEdges(), numberOfPoints(), qrsData, QuickRasterAddEdge(), QuickRasterChgEdge(), QuickRasterSort(), QuickRasterSubEdge(), Shape::dg_arete::st, swrData, Shape::quick_raster_data::x, Shape::dg_point::x, and voronoi::x.

01374 {
01375     if ( numberOfEdges() <= 1 ) {
01376         return;
01377     }
01378 
01379     if ( pos >= to ) {
01380         return;
01381     }
01382     
01383     if ( nbQRas > 1 ) {
01384         int curW = 0;
01385         float lastX = 0;
01386 
01387         if ( directed == fill_oddEven ) {
01388 
01389             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
01390                 int cb = qrsData[i].bord;
01391                 curW++;
01392                 curW &= 1;
01393                 if ( curW == 0 ) {
01394                     line->AddBord(lastX, swrData[cb].curX, true);
01395                 } else {
01396                     lastX = swrData[cb].curX;
01397                 }
01398             }
01399 
01400         } else if ( directed == fill_positive ) {
01401             // doesn't behave correctly; no way i know to do this without a ConvertToShape()
01402             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
01403                 int cb = qrsData[i].bord;
01404                 int oW = curW;
01405                 if ( swrData[cb].sens ) {
01406                     curW++;
01407                 } else {
01408                     curW--;
01409                 }
01410 
01411                 if ( curW <= 0 && oW > 0) {
01412                     line->AddBord(lastX, swrData[cb].curX, true);
01413                 } else if ( curW > 0 && oW <= 0 ) {
01414                     lastX = swrData[cb].curX;
01415                 }
01416             }
01417 
01418         } else if ( directed == fill_nonZero ) {
01419             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
01420                 int cb = qrsData[i].bord;
01421                 int oW = curW;
01422                 if ( swrData[cb].sens ) {
01423                     curW++;
01424                 } else {
01425                     curW--;
01426                 }
01427 
01428                 if ( curW == 0 && oW != 0) {
01429                     line->AddBord(lastX, swrData[cb].curX, true);
01430                 } else if ( curW != 0 && oW == 0 ) {
01431                     lastX = swrData[cb].curX;
01432                 }
01433             }
01434         }
01435     }
01436 
01437     int curPt = curP;
01438     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
01439         int nPt = -1;
01440         nPt = curPt++;
01441         
01442         int nbUp;
01443         int nbDn;
01444         int upNo;
01445         int dnNo;
01446         if ( getPoint(nPt).totalDegree() == 2 ) {
01447             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
01448         } else {
01449             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
01450         }
01451 
01452         if ( nbDn <= 0 ) {
01453             upNo = -1;
01454         }
01455         
01456         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
01457             upNo = -1;
01458         }
01459 
01460         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
01461             int cb = getPoint(nPt).incidentEdge[FIRST];
01462             while ( cb >= 0 && cb < numberOfEdges() ) {
01463                 Shape::dg_arete const &e = getEdge(cb);
01464                 if ( nPt == std::max(e.st, e.en) ) {
01465                     if ( cb != upNo ) {
01466                         QuickRasterSubEdge(cb);
01467                         _updateIntersection(cb, nPt);
01468                         DestroyEdge(cb, line);
01469                     }
01470                 }
01471                 cb = NextAt(nPt, cb);
01472             }
01473         }
01474         
01475         // traitement du "upNo devient dnNo"
01476         int ins_guess = -1;
01477         if ( dnNo >= 0 ) {
01478             if ( upNo >= 0 ) {
01479                 ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
01480                 _updateIntersection(upNo, nPt);
01481                 DestroyEdge(upNo, line);
01482                 
01483                 CreateEdge(dnNo, to, step);
01484             } else {
01485                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
01486                 CreateEdge(dnNo, to, step);
01487             }
01488         }
01489 
01490         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
01491             int cb = getPoint(nPt).incidentEdge[FIRST];
01492             while ( cb >= 0 && cb < numberOfEdges() ) {
01493                 Shape::dg_arete const &e = getEdge(cb);
01494                 if ( nPt == std::min(e.st, e.en) ) {
01495                     if ( cb != dnNo ) {
01496                         ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
01497                         CreateEdge(cb, to, step);
01498                     }
01499                 }
01500                 cb = NextAt(nPt,cb);
01501             }
01502         }
01503     }
01504     
01505     curP = curPt;
01506     if ( curPt > 0 ) {
01507         pos=getPoint(curPt - 1).x[1];
01508     } else {
01509         pos = to;
01510     }
01511     
01512     pos = to;
01513     for (int i = 0; i < nbQRas; i++) {
01514         int cb = qrsData[i].bord;
01515         AvanceEdge(cb, to, line, true, step);
01516         qrsData[i].x = swrData[cb].curX;
01517     }
01518     
01519     QuickRasterSort();
01520 }