![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/livarot/Shape.cpp b/src/livarot/Shape.cpp
index eead99225fb89816b29e7e7752dee947a5a0da21..c694cdd2776b958e2369a6e9f3b24ed921e42f97 100644 (file)
--- a/src/livarot/Shape.cpp
+++ b/src/livarot/Shape.cpp
*/
Shape::Shape()
- : iData(NULL),
+ : qrsData(NULL),
+ iData(NULL),
sTree(NULL),
sEvts(NULL),
_need_points_sorting(false),
_need_edges_sorting(false),
_has_points_data(false),
+ _point_data_initialised(false),
_has_edges_data(false),
_has_sweep_src_data(false),
_has_sweep_dest_data(false),
_has_raster_data(false),
_has_quick_raster_data(false),
_has_back_data(false),
- _has_voronoi_data(false)
+ _has_voronoi_data(false),
+ _bbox_up_to_date(false)
{
leftX = topY = rightX = bottomY = 0;
maxPt = 0;
{
maxPt = 0;
maxAr = 0;
+ free(qrsData);
}
void Shape::Affiche(void)
{
- /*
- printf("sh=%p nbPt=%i nbAr=%i\n",this,nbPt,nbAr); // localizing ok
- for (int i=0;i<nbPt;i++) {
- 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
+ printf("sh=%p nbPt=%i nbAr=%i\n", this, static_cast<int>(_pts.size()), static_cast<int>(_aretes.size())); // localizing ok
+ for (unsigned int i=0; i<_pts.size(); i++) {
+ 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
}
- for (int i=0;i<nbAr;i++) {
- 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
+ for (unsigned int i=0; i<_aretes.size(); i++) {
+ 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
}
- */
}
+/**
+ * Allocates space for point cache or clears the cache
+ \param nVal Allocate a cache (true) or clear it (false)
+ */
void
Shape::MakePointData (bool nVal)
{
if (nVal)
{
if (_has_points_data == false)
- {
- _has_points_data = true;
- pData.resize(maxPt);
- }
- }
- else
- {
- if (_has_points_data)
- {
- _has_points_data = false;
- pData.clear();
- }
- }
+ {
+ _has_points_data = true;
+ _point_data_initialised = false;
+ _bbox_up_to_date = false;
+ pData.resize(maxPt);
+ }
+ }
+ /* no need to clean point data - keep it cached*/
}
+
void
Shape::MakeEdgeData (bool nVal)
{
if (nVal)
{
if (_has_edges_data == false)
- {
- _has_edges_data = true;
- eData.resize(maxAr);
- }
+ {
+ _has_edges_data = true;
+ eData.resize(maxAr);
+ }
}
else
{
if (_has_edges_data)
- {
- _has_edges_data = false;
- eData.clear();
- }
+ {
+ _has_edges_data = false;
+ eData.clear();
+ }
}
}
+
void
Shape::MakeRasterData (bool nVal)
{
if (nVal)
{
if (_has_raster_data == false)
- {
- _has_raster_data = true;
- swrData.resize(maxAr);
- }
+ {
+ _has_raster_data = true;
+ swrData.resize(maxAr);
+ }
}
else
{
if (_has_raster_data)
- {
- _has_raster_data = false;
- swrData.clear();
- }
+ {
+ _has_raster_data = false;
+ swrData.clear();
+ }
}
}
void
if (nVal)
{
if (_has_quick_raster_data == false)
- {
- _has_quick_raster_data = true;
- qrsData.resize(maxAr);
- }
+ {
+ _has_quick_raster_data = true;
+ qrsData = (quick_raster_data*)realloc(qrsData, maxAr * sizeof(quick_raster_data));
+ }
}
else
{
if (_has_quick_raster_data)
- {
- _has_quick_raster_data = false;
- qrsData.clear();
- }
+ {
+ _has_quick_raster_data = false;
+ }
}
}
void
if (nVal)
{
if (_has_sweep_src_data == false)
- {
- _has_sweep_src_data = true;
- swsData.resize(maxAr);
- }
+ {
+ _has_sweep_src_data = true;
+ swsData.resize(maxAr);
+ }
}
else
{
if (_has_sweep_src_data)
- {
- _has_sweep_src_data = false;
- swsData.clear();
- }
+ {
+ _has_sweep_src_data = false;
+ swsData.clear();
+ }
}
}
void
if (nVal)
{
if (_has_sweep_dest_data == false)
- {
- _has_sweep_dest_data = true;
- swdData.resize(maxAr);
- }
+ {
+ _has_sweep_dest_data = true;
+ swdData.resize(maxAr);
+ }
}
else
{
if (_has_sweep_dest_data)
- {
- _has_sweep_dest_data = false;
- swdData.clear();
- }
+ {
+ _has_sweep_dest_data = false;
+ swdData.clear();
+ }
}
}
void
if (nVal)
{
if (_has_back_data == false)
- {
- _has_back_data = true;
- ebData.resize(maxAr);
- }
+ {
+ _has_back_data = true;
+ ebData.resize(maxAr);
+ }
}
else
{
if (_has_back_data)
- {
- _has_back_data = false;
- ebData.clear();
- }
+ {
+ _has_back_data = false;
+ ebData.clear();
+ }
}
}
void
if (nVal)
{
if (_has_voronoi_data == false)
- {
- _has_voronoi_data = true;
- vorpData.resize(maxPt);
- voreData.resize(maxAr);
- }
+ {
+ _has_voronoi_data = true;
+ vorpData.resize(maxPt);
+ voreData.resize(maxAr);
+ }
}
else
{
if (_has_voronoi_data)
- {
- _has_voronoi_data = false;
- vorpData.clear();
- voreData.clear();
- }
+ {
+ _has_voronoi_data = false;
+ vorpData.clear();
+ voreData.clear();
+ }
}
}
_need_points_sorting = who->_need_points_sorting;
_need_edges_sorting = who->_need_edges_sorting;
_has_points_data = false;
+ _point_data_initialised = false;
_has_edges_data = false;
_has_sweep_src_data = false;
_has_sweep_dest_data = false;
_has_quick_raster_data = false;
_has_back_data = false;
_has_voronoi_data = false;
+ _bbox_up_to_date = false;
_pts = who->_pts;
_aretes = who->_aretes;
}
+/**
+ * Clear points and edges and prepare internal data using new size.
+ */
void
-Shape::Reset (int n, int m)
+Shape::Reset (int pointCount, int edgeCount)
{
_pts.clear();
_aretes.clear();
type = shape_polygon;
- if (n > maxPt)
+ if (pointCount > maxPt)
{
- maxPt = n;
+ maxPt = pointCount;
if (_has_points_data)
- pData.resize(maxPt);
+ pData.resize(maxPt);
if (_has_voronoi_data)
- vorpData.resize(maxPt);
+ vorpData.resize(maxPt);
}
- if (m > maxAr)
+ if (edgeCount > maxAr)
{
- maxAr = m;
+ maxAr = edgeCount;
if (_has_edges_data)
- eData.resize(maxAr);
+ eData.resize(maxAr);
if (_has_sweep_dest_data)
- swdData.resize(maxAr);
+ swdData.resize(maxAr);
if (_has_sweep_src_data)
- swsData.resize(maxAr);
+ swsData.resize(maxAr);
if (_has_back_data)
- ebData.resize(maxAr);
+ ebData.resize(maxAr);
if (_has_voronoi_data)
- voreData.resize(maxAr);
+ voreData.resize(maxAr);
}
_need_points_sorting = false;
_need_edges_sorting = false;
+ _point_data_initialised = false;
+ _bbox_up_to_date = false;
}
int
{
maxPt = 2 * numberOfPoints() + 1;
if (_has_points_data)
- pData.resize(maxPt);
+ pData.resize(maxPt);
if (_has_voronoi_data)
- vorpData.resize(maxPt);
+ vorpData.resize(maxPt);
}
dg_point p;
pData[n].nextLinkedPoint = -1;
pData[n].askForWindingS = NULL;
pData[n].askForWindingB = -1;
+ pData[n].rx[0] = Round(p.x[0]);
+ pData[n].rx[1] = Round(p.x[1]);
}
if (_has_voronoi_data)
{
while (cb >= 0 && cb < numberOfEdges())
{
if (getEdge(cb).st == p)
- {
- int ncb = getEdge(cb).nextS;
- _aretes[cb].nextS = _aretes[cb].prevS = -1;
- _aretes[cb].st = -1;
- cb = ncb;
- }
+ {
+ int ncb = getEdge(cb).nextS;
+ _aretes[cb].nextS = _aretes[cb].prevS = -1;
+ _aretes[cb].st = -1;
+ cb = ncb;
+ }
else if (getEdge(cb).en == p)
- {
- int ncb = getEdge(cb).nextE;
- _aretes[cb].nextE = _aretes[cb].prevE = -1;
- _aretes[cb].en = -1;
- cb = ncb;
- }
+ {
+ int ncb = getEdge(cb).nextE;
+ _aretes[cb].nextE = _aretes[cb].prevE = -1;
+ _aretes[cb].en = -1;
+ cb = ncb;
+ }
else
- {
- break;
- }
+ {
+ break;
+ }
}
_pts[p].incidentEdge[FIRST] = _pts[p].incidentEdge[LAST] = -1;
if (p < numberOfPoints() - 1)
{
int cb = getPoint(a).incidentEdge[FIRST];
if (getEdge(cb).st == a)
- {
- _aretes[cb].st = numberOfPoints();
- }
+ {
+ _aretes[cb].st = numberOfPoints();
+ }
else if (getEdge(cb).en == a)
- {
- _aretes[cb].en = numberOfPoints();
- }
+ {
+ _aretes[cb].en = numberOfPoints();
+ }
cb = getPoint(a).incidentEdge[LAST];
if (getEdge(cb).st == a)
- {
- _aretes[cb].st = numberOfPoints();
- }
+ {
+ _aretes[cb].st = numberOfPoints();
+ }
else if (getEdge(cb).en == a)
- {
- _aretes[cb].en = numberOfPoints();
- }
+ {
+ _aretes[cb].en = numberOfPoints();
+ }
cb = getPoint(b).incidentEdge[FIRST];
if (getEdge(cb).st == b)
- {
- _aretes[cb].st = a;
- }
+ {
+ _aretes[cb].st = a;
+ }
else if (getEdge(cb).en == b)
- {
- _aretes[cb].en = a;
- }
+ {
+ _aretes[cb].en = a;
+ }
cb = getPoint(b).incidentEdge[LAST];
if (getEdge(cb).st == b)
- {
- _aretes[cb].st = a;
- }
+ {
+ _aretes[cb].st = a;
+ }
else if (getEdge(cb).en == b)
- {
- _aretes[cb].en = a;
- }
+ {
+ _aretes[cb].en = a;
+ }
cb = getPoint(a).incidentEdge[FIRST];
if (getEdge(cb).st == numberOfPoints())
- {
- _aretes[cb].st = b;
- }
+ {
+ _aretes[cb].st = b;
+ }
else if (getEdge(cb).en == numberOfPoints())
- {
- _aretes[cb].en = b;
- }
+ {
+ _aretes[cb].en = b;
+ }
cb = getPoint(a).incidentEdge[LAST];
if (getEdge(cb).st == numberOfPoints())
- {
- _aretes[cb].st = b;
- }
+ {
+ _aretes[cb].st = b;
+ }
else if (getEdge(cb).en == numberOfPoints())
- {
- _aretes[cb].en = b;
- }
+ {
+ _aretes[cb].en = b;
+ }
}
else
int cb;
cb = getPoint(a).incidentEdge[FIRST];
while (cb >= 0)
- {
- int ncb = NextAt (a, cb);
- if (getEdge(cb).st == a)
- {
- _aretes[cb].st = numberOfPoints();
- }
- else if (getEdge(cb).en == a)
- {
- _aretes[cb].en = numberOfPoints();
- }
- cb = ncb;
- }
+ {
+ int ncb = NextAt (a, cb);
+ if (getEdge(cb).st == a)
+ {
+ _aretes[cb].st = numberOfPoints();
+ }
+ else if (getEdge(cb).en == a)
+ {
+ _aretes[cb].en = numberOfPoints();
+ }
+ cb = ncb;
+ }
cb = getPoint(b).incidentEdge[FIRST];
while (cb >= 0)
- {
- int ncb = NextAt (b, cb);
- if (getEdge(cb).st == b)
- {
- _aretes[cb].st = a;
- }
- else if (getEdge(cb).en == b)
- {
- _aretes[cb].en = a;
- }
- cb = ncb;
- }
+ {
+ int ncb = NextAt (b, cb);
+ if (getEdge(cb).st == b)
+ {
+ _aretes[cb].st = a;
+ }
+ else if (getEdge(cb).en == b)
+ {
+ _aretes[cb].en = a;
+ }
+ cb = ncb;
+ }
cb = getPoint(a).incidentEdge[FIRST];
while (cb >= 0)
- {
- int ncb = NextAt (numberOfPoints(), cb);
- if (getEdge(cb).st == numberOfPoints())
- {
- _aretes[cb].st = b;
- }
- else if (getEdge(cb).en == numberOfPoints())
- {
- _aretes[cb].en = b;
- }
- cb = ncb;
- }
+ {
+ int ncb = NextAt (numberOfPoints(), cb);
+ if (getEdge(cb).st == numberOfPoints())
+ {
+ _aretes[cb].st = b;
+ }
+ else if (getEdge(cb).en == numberOfPoints())
+ {
+ _aretes[cb].en = b;
+ }
+ cb = ncb;
+ }
}
{
dg_point swap = getPoint(a);
if (e == s + 1)
{
if (getPoint(s).x[1] > getPoint(e).x[1]
- || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] > getPoint(e).x[0]))
- SwapPoints (s, e);
+ || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] > getPoint(e).x[0]))
+ SwapPoints (s, e);
return;
}
while (le < ppos || ri > plast)
{
if (le < ppos)
- {
- do
- {
- int test = 0;
- if (getPoint(le).x[1] > pvaly)
- {
- test = 1;
- }
- else if (getPoint(le).x[1] == pvaly)
- {
- if (getPoint(le).x[0] > pvalx)
- {
- test = 1;
- }
- else if (getPoint(le).x[0] == pvalx)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (le < ppos - 1)
- {
- SwapPoints (le, ppos - 1, ppos);
- ppos--;
- continue; // sans changer le
- }
- else if (le == ppos - 1)
- {
- ppos--;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test > 0)
- {
- break;
- }
- le++;
- }
- while (le < ppos);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (getPoint(le).x[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (getPoint(le).x[1] == pvaly)
+ {
+ if (getPoint(le).x[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (getPoint(le).x[0] == pvalx)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (le < ppos - 1)
+ {
+ SwapPoints (le, ppos - 1, ppos);
+ ppos--;
+ continue; // sans changer le
+ }
+ else if (le == ppos - 1)
+ {
+ ppos--;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test > 0)
+ {
+ break;
+ }
+ le++;
+ }
+ while (le < ppos);
+ }
if (ri > plast)
- {
- do
- {
- int test = 0;
- if (getPoint(ri).x[1] > pvaly)
- {
- test = 1;
- }
- else if (getPoint(ri).x[1] == pvaly)
- {
- if (getPoint(ri).x[0] > pvalx)
- {
- test = 1;
- }
- else if (getPoint(ri).x[0] == pvalx)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (ri > plast + 1)
- {
- SwapPoints (ri, plast + 1, plast);
- plast++;
- continue; // sans changer ri
- }
- else if (ri == plast + 1)
- {
- plast++;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test < 0)
- {
- break;
- }
- ri--;
- }
- while (ri > plast);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (getPoint(ri).x[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (getPoint(ri).x[1] == pvaly)
+ {
+ if (getPoint(ri).x[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (getPoint(ri).x[0] == pvalx)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (ri > plast + 1)
+ {
+ SwapPoints (ri, plast + 1, plast);
+ plast++;
+ continue; // sans changer ri
+ }
+ else if (ri == plast + 1)
+ {
+ plast++;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test < 0)
+ {
+ break;
+ }
+ ri--;
+ }
+ while (ri > plast);
+ }
if (le < ppos)
- {
- if (ri > plast)
- {
- SwapPoints (le, ri);
- le++;
- ri--;
- }
- else
- {
- if (le < ppos - 1)
- {
- SwapPoints (ppos - 1, plast, le);
- ppos--;
- plast--;
- }
- else if (le == ppos - 1)
- {
- SwapPoints (plast, le);
- ppos--;
- plast--;
- }
- }
- }
+ {
+ if (ri > plast)
+ {
+ SwapPoints (le, ri);
+ le++;
+ ri--;
+ }
+ else
+ {
+ if (le < ppos - 1)
+ {
+ SwapPoints (ppos - 1, plast, le);
+ ppos--;
+ plast--;
+ }
+ else if (le == ppos - 1)
+ {
+ SwapPoints (plast, le);
+ ppos--;
+ plast--;
+ }
+ }
+ }
else
- {
- if (ri > plast + 1)
- {
- SwapPoints (plast + 1, ppos, ri);
- ppos++;
- plast++;
- }
- else if (ri == plast + 1)
- {
- SwapPoints (ppos, ri);
- ppos++;
- plast++;
- }
- else
- {
- break;
- }
- }
+ {
+ if (ri > plast + 1)
+ {
+ SwapPoints (plast + 1, ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else if (ri == plast + 1)
+ {
+ SwapPoints (ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else
+ {
+ break;
+ }
+ }
}
SortPoints (s, ppos - 1);
SortPoints (plast + 1, e);
if (e == s + 1)
{
if (getPoint(s).x[1] > getPoint(e).x[1] || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] > getPoint(e).x[0])
- || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] == getPoint(e).x[0]
- && pData[s].oldInd > pData[e].oldInd))
- SwapPoints (s, e);
+ || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] == getPoint(e).x[0]
+ && pData[s].oldInd > pData[e].oldInd))
+ SwapPoints (s, e);
return;
}
while (le < ppos || ri > plast)
{
if (le < ppos)
- {
- do
- {
- int test = 0;
- if (getPoint(le).x[1] > pvaly)
- {
- test = 1;
- }
- else if (getPoint(le).x[1] == pvaly)
- {
- if (getPoint(le).x[0] > pvalx)
- {
- test = 1;
- }
- else if (getPoint(le).x[0] == pvalx)
- {
- if (pData[le].oldInd > pvali)
- {
- test = 1;
- }
- else if (pData[le].oldInd == pvali)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (le < ppos - 1)
- {
- SwapPoints (le, ppos - 1, ppos);
- ppos--;
- continue; // sans changer le
- }
- else if (le == ppos - 1)
- {
- ppos--;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test > 0)
- {
- break;
- }
- le++;
- }
- while (le < ppos);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (getPoint(le).x[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (getPoint(le).x[1] == pvaly)
+ {
+ if (getPoint(le).x[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (getPoint(le).x[0] == pvalx)
+ {
+ if (pData[le].oldInd > pvali)
+ {
+ test = 1;
+ }
+ else if (pData[le].oldInd == pvali)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (le < ppos - 1)
+ {
+ SwapPoints (le, ppos - 1, ppos);
+ ppos--;
+ continue; // sans changer le
+ }
+ else if (le == ppos - 1)
+ {
+ ppos--;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test > 0)
+ {
+ break;
+ }
+ le++;
+ }
+ while (le < ppos);
+ }
if (ri > plast)
- {
- do
- {
- int test = 0;
- if (getPoint(ri).x[1] > pvaly)
- {
- test = 1;
- }
- else if (getPoint(ri).x[1] == pvaly)
- {
- if (getPoint(ri).x[0] > pvalx)
- {
- test = 1;
- }
- else if (getPoint(ri).x[0] == pvalx)
- {
- if (pData[ri].oldInd > pvali)
- {
- test = 1;
- }
- else if (pData[ri].oldInd == pvali)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (ri > plast + 1)
- {
- SwapPoints (ri, plast + 1, plast);
- plast++;
- continue; // sans changer ri
- }
- else if (ri == plast + 1)
- {
- plast++;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test < 0)
- {
- break;
- }
- ri--;
- }
- while (ri > plast);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (getPoint(ri).x[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (getPoint(ri).x[1] == pvaly)
+ {
+ if (getPoint(ri).x[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (getPoint(ri).x[0] == pvalx)
+ {
+ if (pData[ri].oldInd > pvali)
+ {
+ test = 1;
+ }
+ else if (pData[ri].oldInd == pvali)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (ri > plast + 1)
+ {
+ SwapPoints (ri, plast + 1, plast);
+ plast++;
+ continue; // sans changer ri
+ }
+ else if (ri == plast + 1)
+ {
+ plast++;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test < 0)
+ {
+ break;
+ }
+ ri--;
+ }
+ while (ri > plast);
+ }
if (le < ppos)
- {
- if (ri > plast)
- {
- SwapPoints (le, ri);
- le++;
- ri--;
- }
- else
- {
- if (le < ppos - 1)
- {
- SwapPoints (ppos - 1, plast, le);
- ppos--;
- plast--;
- }
- else if (le == ppos - 1)
- {
- SwapPoints (plast, le);
- ppos--;
- plast--;
- }
- }
- }
+ {
+ if (ri > plast)
+ {
+ SwapPoints (le, ri);
+ le++;
+ ri--;
+ }
+ else
+ {
+ if (le < ppos - 1)
+ {
+ SwapPoints (ppos - 1, plast, le);
+ ppos--;
+ plast--;
+ }
+ else if (le == ppos - 1)
+ {
+ SwapPoints (plast, le);
+ ppos--;
+ plast--;
+ }
+ }
+ }
else
- {
- if (ri > plast + 1)
- {
- SwapPoints (plast + 1, ppos, ri);
- ppos++;
- plast++;
- }
- else if (ri == plast + 1)
- {
- SwapPoints (ppos, ri);
- ppos++;
- plast++;
- }
- else
- {
- break;
- }
- }
+ {
+ if (ri > plast + 1)
+ {
+ SwapPoints (plast + 1, ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else if (ri == plast + 1)
+ {
+ SwapPoints (ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else
+ {
+ break;
+ }
+ }
}
SortPointsByOldInd (s, ppos - 1);
SortPointsByOldInd (plast + 1, e);
if (e == s + 1)
{
if (pData[s].rx[1] > pData[e].rx[1]
- || (pData[s].rx[1] == pData[e].rx[1] && pData[s].rx[0] > pData[e].rx[0]))
- SwapPoints (s, e);
+ || (pData[s].rx[1] == pData[e].rx[1] && pData[s].rx[0] > pData[e].rx[0]))
+ SwapPoints (s, e);
return;
}
while (le < ppos || ri > plast)
{
if (le < ppos)
- {
- do
- {
- int test = 0;
- if (pData[le].rx[1] > pvaly)
- {
- test = 1;
- }
- else if (pData[le].rx[1] == pvaly)
- {
- if (pData[le].rx[0] > pvalx)
- {
- test = 1;
- }
- else if (pData[le].rx[0] == pvalx)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (le < ppos - 1)
- {
- SwapPoints (le, ppos - 1, ppos);
- ppos--;
- continue; // sans changer le
- }
- else if (le == ppos - 1)
- {
- ppos--;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test > 0)
- {
- break;
- }
- le++;
- }
- while (le < ppos);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (pData[le].rx[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (pData[le].rx[1] == pvaly)
+ {
+ if (pData[le].rx[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (pData[le].rx[0] == pvalx)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (le < ppos - 1)
+ {
+ SwapPoints (le, ppos - 1, ppos);
+ ppos--;
+ continue; // sans changer le
+ }
+ else if (le == ppos - 1)
+ {
+ ppos--;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test > 0)
+ {
+ break;
+ }
+ le++;
+ }
+ while (le < ppos);
+ }
if (ri > plast)
- {
- do
- {
- int test = 0;
- if (pData[ri].rx[1] > pvaly)
- {
- test = 1;
- }
- else if (pData[ri].rx[1] == pvaly)
- {
- if (pData[ri].rx[0] > pvalx)
- {
- test = 1;
- }
- else if (pData[ri].rx[0] == pvalx)
- {
- test = 0;
- }
- else
- {
- test = -1;
- }
- }
- else
- {
- test = -1;
- }
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (ri > plast + 1)
- {
- SwapPoints (ri, plast + 1, plast);
- plast++;
- continue; // sans changer ri
- }
- else if (ri == plast + 1)
- {
- plast++;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test < 0)
- {
- break;
- }
- ri--;
- }
- while (ri > plast);
- }
+ {
+ do
+ {
+ int test = 0;
+ if (pData[ri].rx[1] > pvaly)
+ {
+ test = 1;
+ }
+ else if (pData[ri].rx[1] == pvaly)
+ {
+ if (pData[ri].rx[0] > pvalx)
+ {
+ test = 1;
+ }
+ else if (pData[ri].rx[0] == pvalx)
+ {
+ test = 0;
+ }
+ else
+ {
+ test = -1;
+ }
+ }
+ else
+ {
+ test = -1;
+ }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (ri > plast + 1)
+ {
+ SwapPoints (ri, plast + 1, plast);
+ plast++;
+ continue; // sans changer ri
+ }
+ else if (ri == plast + 1)
+ {
+ plast++;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test < 0)
+ {
+ break;
+ }
+ ri--;
+ }
+ while (ri > plast);
+ }
if (le < ppos)
- {
- if (ri > plast)
- {
- SwapPoints (le, ri);
- le++;
- ri--;
- }
- else
- {
- if (le < ppos - 1)
- {
- SwapPoints (ppos - 1, plast, le);
- ppos--;
- plast--;
- }
- else if (le == ppos - 1)
- {
- SwapPoints (plast, le);
- ppos--;
- plast--;
- }
- }
- }
+ {
+ if (ri > plast)
+ {
+ SwapPoints (le, ri);
+ le++;
+ ri--;
+ }
+ else
+ {
+ if (le < ppos - 1)
+ {
+ SwapPoints (ppos - 1, plast, le);
+ ppos--;
+ plast--;
+ }
+ else if (le == ppos - 1)
+ {
+ SwapPoints (plast, le);
+ ppos--;
+ plast--;
+ }
+ }
+ }
else
- {
- if (ri > plast + 1)
- {
- SwapPoints (plast + 1, ppos, ri);
- ppos++;
- plast++;
- }
- else if (ri == plast + 1)
- {
- SwapPoints (ppos, ri);
- ppos++;
- plast++;
- }
- else
- {
- break;
- }
- }
+ {
+ if (ri > plast + 1)
+ {
+ SwapPoints (plast + 1, ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else if (ri == plast + 1)
+ {
+ SwapPoints (ppos, ri);
+ ppos++;
+ plast++;
+ }
+ else
+ {
+ break;
+ }
+ }
}
SortPointsRounded (s, ppos - 1);
SortPointsRounded (plast + 1, e);
{
maxAr = 2 * numberOfEdges() + 1;
if (_has_edges_data)
- eData.resize(maxAr);
+ eData.resize(maxAr);
if (_has_sweep_src_data)
- swsData.resize(maxAr);
+ swsData.resize(maxAr);
if (_has_sweep_dest_data)
- swdData.resize(maxAr);
+ swdData.resize(maxAr);
if (_has_raster_data)
- swrData.resize(maxAr);
+ swrData.resize(maxAr);
if (_has_back_data)
- ebData.resize(maxAr);
+ ebData.resize(maxAr);
if (_has_voronoi_data)
- voreData.resize(maxAr);
+ voreData.resize(maxAr);
}
dg_arete a;
int cb = getPoint(st).incidentEdge[FIRST];
while (cb >= 0)
{
- if (getEdge(cb).st == st && getEdge(cb).en == en)
- return -1; // doublon
- if (getEdge(cb).st == en && getEdge(cb).en == st)
- return -1; // doublon
- cb = NextAt (st, cb);
+ if (getEdge(cb).st == st && getEdge(cb).en == en)
+ return -1; // doublon
+ if (getEdge(cb).st == en && getEdge(cb).en == st)
+ return -1; // doublon
+ cb = NextAt (st, cb);
}
}
type = shape_graph;
{
maxAr = 2 * numberOfEdges() + 1;
if (_has_edges_data)
- eData.resize(maxAr);
+ eData.resize(maxAr);
if (_has_sweep_src_data)
- swsData.resize(maxAr);
+ swsData.resize(maxAr);
if (_has_sweep_dest_data)
- swdData.resize(maxAr);
+ swdData.resize(maxAr);
if (_has_raster_data)
- swrData.resize(maxAr);
+ swrData.resize(maxAr);
if (_has_back_data)
- ebData.resize(maxAr);
+ ebData.resize(maxAr);
if (_has_voronoi_data)
- voreData.resize(maxAr);
+ voreData.resize(maxAr);
}
dg_arete a;
if (getEdge(a).prevS >= 0 && getEdge(a).prevS != b)
{
if (getEdge(getEdge(a).prevS).st == getEdge(a).st)
- {
- _aretes[getEdge(a).prevS].nextS = b;
- }
+ {
+ _aretes[getEdge(a).prevS].nextS = b;
+ }
else if (getEdge(getEdge(a).prevS).en == getEdge(a).st)
- {
- _aretes[getEdge(a).prevS].nextE = b;
- }
+ {
+ _aretes[getEdge(a).prevS].nextE = b;
+ }
}
if (getEdge(a).nextS >= 0 && getEdge(a).nextS != b)
{
if (getEdge(getEdge(a).nextS).st == getEdge(a).st)
- {
- _aretes[getEdge(a).nextS].prevS = b;
- }
+ {
+ _aretes[getEdge(a).nextS].prevS = b;
+ }
else if (getEdge(getEdge(a).nextS).en == getEdge(a).st)
- {
- _aretes[getEdge(a).nextS].prevE = b;
- }
+ {
+ _aretes[getEdge(a).nextS].prevE = b;
+ }
}
if (getEdge(a).prevE >= 0 && getEdge(a).prevE != b)
{
if (getEdge(getEdge(a).prevE).st == getEdge(a).en)
- {
- _aretes[getEdge(a).prevE].nextS = b;
- }
+ {
+ _aretes[getEdge(a).prevE].nextS = b;
+ }
else if (getEdge(getEdge(a).prevE).en == getEdge(a).en)
- {
- _aretes[getEdge(a).prevE].nextE = b;
- }
+ {
+ _aretes[getEdge(a).prevE].nextE = b;
+ }
}
if (getEdge(a).nextE >= 0 && getEdge(a).nextE != b)
{
if (getEdge(getEdge(a).nextE).st == getEdge(a).en)
- {
- _aretes[getEdge(a).nextE].prevS = b;
- }
+ {
+ _aretes[getEdge(a).nextE].prevS = b;
+ }
else if (getEdge(getEdge(a).nextE).en == getEdge(a).en)
- {
- _aretes[getEdge(a).nextE].prevE = b;
- }
+ {
+ _aretes[getEdge(a).nextE].prevE = b;
+ }
}
if (getEdge(a).st >= 0)
{
if (getPoint(getEdge(a).st).incidentEdge[FIRST] == a)
- _pts[getEdge(a).st].incidentEdge[FIRST] = numberOfEdges();
+ _pts[getEdge(a).st].incidentEdge[FIRST] = numberOfEdges();
if (getPoint(getEdge(a).st).incidentEdge[LAST] == a)
- _pts[getEdge(a).st].incidentEdge[LAST] = numberOfEdges();
+ _pts[getEdge(a).st].incidentEdge[LAST] = numberOfEdges();
}
if (getEdge(a).en >= 0)
{
if (getPoint(getEdge(a).en).incidentEdge[FIRST] == a)
- _pts[getEdge(a).en].incidentEdge[FIRST] = numberOfEdges();
+ _pts[getEdge(a).en].incidentEdge[FIRST] = numberOfEdges();
if (getPoint(getEdge(a).en).incidentEdge[LAST] == a)
- _pts[getEdge(a).en].incidentEdge[LAST] = numberOfEdges();
+ _pts[getEdge(a).en].incidentEdge[LAST] = numberOfEdges();
}
if (getEdge(b).prevS >= 0 && getEdge(b).prevS != a)
{
if (getEdge(getEdge(b).prevS).st == getEdge(b).st)
- {
- _aretes[getEdge(b).prevS].nextS = a;
- }
+ {
+ _aretes[getEdge(b).prevS].nextS = a;
+ }
else if (getEdge(getEdge(b).prevS).en == getEdge(b).st)
- {
- _aretes[getEdge(b).prevS].nextE = a;
- }
+ {
+ _aretes[getEdge(b).prevS].nextE = a;
+ }
}
if (getEdge(b).nextS >= 0 && getEdge(b).nextS != a)
{
if (getEdge(getEdge(b).nextS).st == getEdge(b).st)
- {
- _aretes[getEdge(b).nextS].prevS = a;
- }
+ {
+ _aretes[getEdge(b).nextS].prevS = a;
+ }
else if (getEdge(getEdge(b).nextS).en == getEdge(b).st)
- {
- _aretes[getEdge(b).nextS].prevE = a;
- }
+ {
+ _aretes[getEdge(b).nextS].prevE = a;
+ }
}
if (getEdge(b).prevE >= 0 && getEdge(b).prevE != a)
{
if (getEdge(getEdge(b).prevE).st == getEdge(b).en)
- {
- _aretes[getEdge(b).prevE].nextS = a;
- }
+ {
+ _aretes[getEdge(b).prevE].nextS = a;
+ }
else if (getEdge(getEdge(b).prevE).en == getEdge(b).en)
- {
- _aretes[getEdge(b).prevE].nextE = a;
- }
+ {
+ _aretes[getEdge(b).prevE].nextE = a;
+ }
}
if (getEdge(b).nextE >= 0 && getEdge(b).nextE != a)
{
if (getEdge(getEdge(b).nextE).st == getEdge(b).en)
- {
- _aretes[getEdge(b).nextE].prevS = a;
- }
+ {
+ _aretes[getEdge(b).nextE].prevS = a;
+ }
else if (getEdge(getEdge(b).nextE).en == getEdge(b).en)
- {
- _aretes[getEdge(b).nextE].prevE = a;
- }
+ {
+ _aretes[getEdge(b).nextE].prevE = a;
+ }
}
int p = getEdge(b).st;
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == b) {
- _pts[p].incidentEdge[i] = a;
+ _pts[p].incidentEdge[i] = a;
}
}
p = getEdge(b).en;
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == b) {
- _pts[p].incidentEdge[i] = a;
+ _pts[p].incidentEdge[i] = a;
}
}
p = getEdge(a).st;
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == numberOfEdges()) {
- _pts[p].incidentEdge[i] = b;
+ _pts[p].incidentEdge[i] = b;
}
}
p = getEdge(a).en;
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == numberOfEdges()) {
- _pts[p].incidentEdge[i] = b;
+ _pts[p].incidentEdge[i] = b;
}
}
{
int const d = getPoint(p).totalDegree();
if (d > 1)
- {
- int cb;
- cb = getPoint(p).incidentEdge[FIRST];
- int nb = 0;
- while (cb >= 0)
- {
- int n = nb++;
- list[n].no = cb;
- if (getEdge(cb).st == p)
- {
- list[n].x = getEdge(cb).dx;
- list[n].starting = true;
- }
- else
- {
- list[n].x = -getEdge(cb).dx;
- list[n].starting = false;
- }
- cb = NextAt (p, cb);
- }
- SortEdgesList (list, 0, nb - 1);
- _pts[p].incidentEdge[FIRST] = list[0].no;
- _pts[p].incidentEdge[LAST] = list[nb - 1].no;
- for (int i = 0; i < nb; i++)
- {
- if (list[i].starting)
- {
- if (i > 0)
- {
- _aretes[list[i].no].prevS = list[i - 1].no;
- }
- else
- {
- _aretes[list[i].no].prevS = -1;
- }
- if (i < nb - 1)
- {
- _aretes[list[i].no].nextS = list[i + 1].no;
- }
- else
- {
- _aretes[list[i].no].nextS = -1;
- }
- }
- else
- {
- if (i > 0)
- {
- _aretes[list[i].no].prevE = list[i - 1].no;
- }
- else
- {
- _aretes[list[i].no].prevE = -1;
- }
- if (i < nb - 1)
- {
- _aretes[list[i].no].nextE = list[i + 1].no;
- }
- else
- {
- _aretes[list[i].no].nextE = -1;
- }
- }
- }
- }
+ {
+ int cb;
+ cb = getPoint(p).incidentEdge[FIRST];
+ int nb = 0;
+ while (cb >= 0)
+ {
+ int n = nb++;
+ list[n].no = cb;
+ if (getEdge(cb).st == p)
+ {
+ list[n].x = getEdge(cb).dx;
+ list[n].starting = true;
+ }
+ else
+ {
+ list[n].x = -getEdge(cb).dx;
+ list[n].starting = false;
+ }
+ cb = NextAt (p, cb);
+ }
+ SortEdgesList (list, 0, nb - 1);
+ _pts[p].incidentEdge[FIRST] = list[0].no;
+ _pts[p].incidentEdge[LAST] = list[nb - 1].no;
+ for (int i = 0; i < nb; i++)
+ {
+ if (list[i].starting)
+ {
+ if (i > 0)
+ {
+ _aretes[list[i].no].prevS = list[i - 1].no;
+ }
+ else
+ {
+ _aretes[list[i].no].prevS = -1;
+ }
+ if (i < nb - 1)
+ {
+ _aretes[list[i].no].nextS = list[i + 1].no;
+ }
+ else
+ {
+ _aretes[list[i].no].nextS = -1;
+ }
+ }
+ else
+ {
+ if (i > 0)
+ {
+ _aretes[list[i].no].prevE = list[i - 1].no;
+ }
+ else
+ {
+ _aretes[list[i].no].prevE = -1;
+ }
+ if (i < nb - 1)
+ {
+ _aretes[list[i].no].nextE = list[i + 1].no;
+ }
+ else
+ {
+ _aretes[list[i].no].nextE = -1;
+ }
+ }
+ }
+ }
}
g_free(list);
}
if (tstAX < 0)
{
if (tstAY < 0)
- {
- quadA = 7;
- }
+ {
+ quadA = 7;
+ }
else if (tstAY == 0)
- {
- quadA = 6;
- }
+ {
+ quadA = 6;
+ }
else if (tstAY > 0)
- {
- quadA = 5;
- }
+ {
+ quadA = 5;
+ }
}
else if (tstAX == 0)
{
if (tstAY < 0)
- {
- quadA = 0;
- }
+ {
+ quadA = 0;
+ }
else if (tstAY == 0)
- {
- quadA = -1;
- }
+ {
+ quadA = -1;
+ }
else if (tstAY > 0)
- {
- quadA = 4;
- }
+ {
+ quadA = 4;
+ }
}
else if (tstAX > 0)
{
if (tstAY < 0)
- {
- quadA = 1;
- }
+ {
+ quadA = 1;
+ }
else if (tstAY == 0)
- {
- quadA = 2;
- }
+ {
+ quadA = 2;
+ }
else if (tstAY > 0)
- {
- quadA = 3;
- }
+ {
+ quadA = 3;
+ }
}
if (tstBX < 0)
{
if (tstBY < 0)
- {
- quadB = 7;
- }
+ {
+ quadB = 7;
+ }
else if (tstBY == 0)
- {
- quadB = 6;
- }
+ {
+ quadB = 6;
+ }
else if (tstBY > 0)
- {
- quadB = 5;
- }
+ {
+ quadB = 5;
+ }
}
else if (tstBX == 0)
{
if (tstBY < 0)
- {
- quadB = 0;
- }
+ {
+ quadB = 0;
+ }
else if (tstBY == 0)
- {
- quadB = -1;
- }
+ {
+ quadB = -1;
+ }
else if (tstBY > 0)
- {
- quadB = 4;
- }
+ {
+ quadB = 4;
+ }
}
else if (tstBX > 0)
{
if (tstBY < 0)
- {
- quadB = 1;
- }
+ {
+ quadB = 1;
+ }
else if (tstBY == 0)
- {
- quadB = 2;
- }
+ {
+ quadB = 2;
+ }
else if (tstBY > 0)
- {
- quadB = 3;
- }
+ {
+ quadB = 3;
+ }
}
if (quadA < quadB)
return 1;
while (le < ppos || ri > plast)
{
if (le < ppos)
- {
- do
- {
+ {
+ do
+ {
int test = CmpToVert (pvalx, list[le].x,pvals,list[le].starting);
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (le < ppos - 1)
- {
- edge_list swap = list[le];
- list[le] = list[ppos - 1];
- list[ppos - 1] = list[ppos];
- list[ppos] = swap;
- ppos--;
- continue; // sans changer le
- }
- else if (le == ppos - 1)
- {
- ppos--;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test > 0)
- {
- break;
- }
- le++;
- }
- while (le < ppos);
- }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (le < ppos - 1)
+ {
+ edge_list swap = list[le];
+ list[le] = list[ppos - 1];
+ list[ppos - 1] = list[ppos];
+ list[ppos] = swap;
+ ppos--;
+ continue; // sans changer le
+ }
+ else if (le == ppos - 1)
+ {
+ ppos--;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test > 0)
+ {
+ break;
+ }
+ le++;
+ }
+ while (le < ppos);
+ }
if (ri > plast)
- {
- do
- {
+ {
+ do
+ {
int test = CmpToVert (pvalx, list[ri].x,pvals,list[ri].starting);
- if (test == 0)
- {
- // on colle les valeurs egales au pivot ensemble
- if (ri > plast + 1)
- {
- edge_list swap = list[ri];
- list[ri] = list[plast + 1];
- list[plast + 1] = list[plast];
- list[plast] = swap;
- plast++;
- continue; // sans changer ri
- }
- else if (ri == plast + 1)
- {
- plast++;
- break;
- }
- else
- {
- // oupsie
- break;
- }
- }
- if (test < 0)
- {
- break;
- }
- ri--;
- }
- while (ri > plast);
- }
+ if (test == 0)
+ {
+ // on colle les valeurs egales au pivot ensemble
+ if (ri > plast + 1)
+ {
+ edge_list swap = list[ri];
+ list[ri] = list[plast + 1];
+ list[plast + 1] = list[plast];
+ list[plast] = swap;
+ plast++;
+ continue; // sans changer ri
+ }
+ else if (ri == plast + 1)
+ {
+ plast++;
+ break;
+ }
+ else
+ {
+ // oupsie
+ break;
+ }
+ }
+ if (test < 0)
+ {
+ break;
+ }
+ ri--;
+ }
+ while (ri > plast);
+ }
if (le < ppos)
- {
- if (ri > plast)
- {
- edge_list swap = list[le];
- list[le] = list[ri];
- list[ri] = swap;
- le++;
- ri--;
- }
- else if (le < ppos - 1)
- {
- edge_list swap = list[ppos - 1];
- list[ppos - 1] = list[plast];
- list[plast] = list[le];
- list[le] = swap;
- ppos--;
- plast--;
- }
- else if (le == ppos - 1)
- {
- edge_list swap = list[plast];
- list[plast] = list[le];
- list[le] = swap;
- ppos--;
- plast--;
- }
- else
- {
- break;
- }
- }
+ {
+ if (ri > plast)
+ {
+ edge_list swap = list[le];
+ list[le] = list[ri];
+ list[ri] = swap;
+ le++;
+ ri--;
+ }
+ else if (le < ppos - 1)
+ {
+ edge_list swap = list[ppos - 1];
+ list[ppos - 1] = list[plast];
+ list[plast] = list[le];
+ list[le] = swap;
+ ppos--;
+ plast--;
+ }
+ else if (le == ppos - 1)
+ {
+ edge_list swap = list[plast];
+ list[plast] = list[le];
+ list[le] = swap;
+ ppos--;
+ plast--;
+ }
+ else
+ {
+ break;
+ }
+ }
else
- {
- if (ri > plast + 1)
- {
- edge_list swap = list[plast + 1];
- list[plast + 1] = list[ppos];
- list[ppos] = list[ri];
- list[ri] = swap;
- ppos++;
- plast++;
- }
- else if (ri == plast + 1)
- {
- edge_list swap = list[ppos];
- list[ppos] = list[ri];
- list[ri] = swap;
- ppos++;
- plast++;
- }
- else
- {
- break;
- }
- }
+ {
+ if (ri > plast + 1)
+ {
+ edge_list swap = list[plast + 1];
+ list[plast + 1] = list[ppos];
+ list[ppos] = list[ri];
+ list[ri] = swap;
+ ppos++;
+ plast++;
+ }
+ else if (ri == plast + 1)
+ {
+ edge_list swap = list[ppos];
+ list[ppos] = list[ri];
+ list[ri] = swap;
+ ppos++;
+ plast++;
+ }
+ else
+ {
+ break;
+ }
+ }
}
SortEdgesList (list, s, ppos - 1);
SortEdgesList (list, plast + 1, e);
if (getPoint(p).incidentEdge[LAST] >= 0)
{
if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
- {
- _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
- }
+ {
+ _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
+ }
else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
- {
- _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
- }
+ {
+ _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
+ }
}
_pts[p].incidentEdge[LAST] = b;
if (getPoint(p).incidentEdge[FIRST] < 0)
if (getPoint(p).incidentEdge[LAST] >= 0)
{
if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
- {
- _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
- }
+ {
+ _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
+ }
else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
- {
- _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
- }
+ {
+ _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
+ }
}
_pts[p].incidentEdge[LAST] = b;
if (getPoint(p).incidentEdge[FIRST] < 0)
if (getEdge(b).prevS >= 0)
{
if (getEdge(getEdge(b).prevS).st == getEdge(b).st)
- {
- _aretes[getEdge(b).prevS].nextS = getEdge(b).nextS;
- }
+ {
+ _aretes[getEdge(b).prevS].nextS = getEdge(b).nextS;
+ }
else if (getEdge(getEdge(b).prevS).en == getEdge(b).st)
- {
- _aretes[getEdge(b).prevS].nextE = getEdge(b).nextS;
- }
+ {
+ _aretes[getEdge(b).prevS].nextE = getEdge(b).nextS;
+ }
}
if (getEdge(b).nextS >= 0)
{
if (getEdge(getEdge(b).nextS).st == getEdge(b).st)
- {
- _aretes[getEdge(b).nextS].prevS = getEdge(b).prevS;
- }
+ {
+ _aretes[getEdge(b).nextS].prevS = getEdge(b).prevS;
+ }
else if (getEdge(getEdge(b).nextS).en == getEdge(b).st)
- {
- _aretes[getEdge(b).nextS].prevE = getEdge(b).prevS;
- }
+ {
+ _aretes[getEdge(b).nextS].prevE = getEdge(b).prevS;
+ }
}
if (getPoint(getEdge(b).st).incidentEdge[FIRST] == b)
_pts[getEdge(b).st].incidentEdge[FIRST] = getEdge(b).nextS;
if (getEdge(b).prevE >= 0)
{
if (getEdge(getEdge(b).prevE).st == getEdge(b).en)
- {
- _aretes[getEdge(b).prevE].nextS = getEdge(b).nextE;
- }
+ {
+ _aretes[getEdge(b).prevE].nextS = getEdge(b).nextE;
+ }
else if (getEdge(getEdge(b).prevE).en == getEdge(b).en)
- {
- _aretes[getEdge(b).prevE].nextE = getEdge(b).nextE;
- }
+ {
+ _aretes[getEdge(b).prevE].nextE = getEdge(b).nextE;
+ }
}
if (getEdge(b).nextE >= 0)
{
if (getEdge(getEdge(b).nextE).st == getEdge(b).en)
- {
- _aretes[getEdge(b).nextE].prevS = getEdge(b).prevE;
- }
+ {
+ _aretes[getEdge(b).nextE].prevS = getEdge(b).prevE;
+ }
else if (getEdge(getEdge(b).nextE).en == getEdge(b).en)
- {
- _aretes[getEdge(b).nextE].prevE = getEdge(b).prevE;
- }
+ {
+ _aretes[getEdge(b).nextE].prevE = getEdge(b).prevE;
+ }
}
if (getPoint(getEdge(b).en).incidentEdge[FIRST] == b)
_pts[getEdge(b).en].incidentEdge[FIRST] = getEdge(b).nextE;
void
Shape::CalcBBox (bool strict_degree)
{
+ if (_bbox_up_to_date)
+ return;
if (hasPoints() == false)
{
leftX = rightX = topY = bottomY = 0;
+ _bbox_up_to_date = true;
return;
}
leftX = rightX = getPoint(0).x[0];
}
}
}
+
+ _bbox_up_to_date = true;
}
// winding of a point with respect to the Shape
void Shape::initialisePointData()
{
+ if (_point_data_initialised)
+ return;
int const N = numberOfPoints();
for (int i = 0; i < N; i++) {
- pData[i].pending = 0;
- pData[i].edgeOnLeft = -1;
- pData[i].nextLinkedPoint = -1;
- pData[i].rx[0] = Round(getPoint(i).x[0]);
- pData[i].rx[1] = Round(getPoint(i).x[1]);
+ pData[i].pending = 0;
+ pData[i].edgeOnLeft = -1;
+ pData[i].nextLinkedPoint = -1;
+ pData[i].rx[0] = Round(getPoint(i).x[0]);
+ pData[i].rx[1] = Round(getPoint(i).x[1]);
}
+
+ _point_data_initialised = true;
}
void Shape::initialiseEdgeData()
int const N = numberOfEdges();
for (int i = 0; i < N; i++) {
- eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
- eData[i].length = dot(eData[i].rdx, eData[i].rdx);
- eData[i].ilength = 1 / eData[i].length;
- eData[i].sqlength = sqrt(eData[i].length);
- eData[i].isqlength = 1 / eData[i].sqlength;
- eData[i].siEd = eData[i].rdx[1] * eData[i].isqlength;
- eData[i].coEd = eData[i].rdx[0] * eData[i].isqlength;
-
- if (eData[i].siEd < 0) {
- eData[i].siEd = -eData[i].siEd;
- eData[i].coEd = -eData[i].coEd;
- }
-
- swsData[i].misc = NULL;
- swsData[i].firstLinkedPoint = -1;
- swsData[i].stPt = swsData[i].enPt = -1;
- swsData[i].leftRnd = swsData[i].rightRnd = -1;
- swsData[i].nextSh = NULL;
- swsData[i].nextBo = -1;
- swsData[i].curPoint = -1;
- swsData[i].doneTo = -1;
+ eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
+ eData[i].length = dot(eData[i].rdx, eData[i].rdx);
+ eData[i].ilength = 1 / eData[i].length;
+ eData[i].sqlength = sqrt(eData[i].length);
+ eData[i].isqlength = 1 / eData[i].sqlength;
+ eData[i].siEd = eData[i].rdx[1] * eData[i].isqlength;
+ eData[i].coEd = eData[i].rdx[0] * eData[i].isqlength;
+
+ if (eData[i].siEd < 0) {
+ eData[i].siEd = -eData[i].siEd;
+ eData[i].coEd = -eData[i].coEd;
+ }
+
+ swsData[i].misc = NULL;
+ swsData[i].firstLinkedPoint = -1;
+ swsData[i].stPt = swsData[i].enPt = -1;
+ swsData[i].leftRnd = swsData[i].rightRnd = -1;
+ swsData[i].nextSh = NULL;
+ swsData[i].nextBo = -1;
+ swsData[i].curPoint = -1;
+ swsData[i].doneTo = -1;
}
}
bool directedEulerian(Shape const *s)
{
for (int i = 0; i < s->numberOfPoints(); i++) {
- if (s->getPoint(i).dI != s->getPoint(i).dO) {
- return false;
- }
+ if (s->getPoint(i).dI != s->getPoint(i).dO) {
+ return false;
+ }
}
return true;
double distance(Shape const *s, NR::Point const &p)
{
if ( s->hasPoints() == false) {
- return 0.0;
+ return 0.0;
}
/* Find the minimum distance from p to one of the points on s.
double bdot = NR::dot(p - s->getPoint(0).x, p - s->getPoint(0).x);
for (int i = 0; i < s->numberOfPoints(); i++) {
- NR::Point const offset( p - s->getPoint(i).x );
- double ndot = NR::dot(offset, offset);
- if ( ndot < bdot ) {
- bdot = ndot;
- }
+ NR::Point const offset( p - s->getPoint(i).x );
+ double ndot = NR::dot(offset, offset);
+ if ( ndot < bdot ) {
+ bdot = ndot;
+ }
}
for (int i = 0; i < s->numberOfEdges(); i++) {
- if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
- /* The edge has start and end points */
- NR::Point const st(s->getPoint(s->getEdge(i).st).x); // edge start
- NR::Point const en(s->getPoint(s->getEdge(i).en).x); // edge end
-
- NR::Point const d(p - st); // vector between p and edge start
- NR::Point const e(en - st); // vector of the edge
- double const el = NR::dot(e, e); // edge length
-
- /* Update bdot if appropriate */
- if ( el > 0.001 ) {
- double const npr = NR::dot(d, e);
- if ( npr > 0 && npr < el ) {
- double const nl = fabs( NR::cross(d, e) );
- double ndot = nl * nl / el;
- if ( ndot < bdot ) {
- bdot = ndot;
- }
- }
- }
- }
+ if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
+ /* The edge has start and end points */
+ NR::Point const st(s->getPoint(s->getEdge(i).st).x); // edge start
+ NR::Point const en(s->getPoint(s->getEdge(i).en).x); // edge end
+
+ NR::Point const d(p - st); // vector between p and edge start
+ NR::Point const e(en - st); // vector of the edge
+ double const el = NR::dot(e, e); // edge length
+
+ /* Update bdot if appropriate */
+ if ( el > 0.001 ) {
+ double const npr = NR::dot(d, e);
+ if ( npr > 0 && npr < el ) {
+ double const nl = fabs( NR::cross(d, e) );
+ double ndot = nl * nl / el;
+ if ( ndot < bdot ) {
+ bdot = ndot;
+ }
+ }
+ }
+ }
}
return sqrt(bdot);
bool distanceLessThanOrEqual(Shape const *s, NR::Point const &p, double const max_l2)
{
if ( s->hasPoints() == false ) {
- return false;
+ return false;
}
/* TODO: Consider using bbox to return early, perhaps conditional on nbPt or nbAr. */
@@ -2248,31 +2268,31 @@ bool distanceLessThanOrEqual(Shape const *s, NR::Point const &p, double const ma
double const max_l1 = max_l2 * M_SQRT2;
for (int i = 0; i < s->numberOfPoints(); i++) {
- NR::Point const offset( p - s->getPoint(i).x );
- double const l1 = NR::L1(offset);
- if ( (l1 <= max_l2) || ((l1 <= max_l1) && (NR::L2(offset) <= max_l2)) ) {
- return true;
- }
+ NR::Point const offset( p - s->getPoint(i).x );
+ double const l1 = NR::L1(offset);
+ if ( (l1 <= max_l2) || ((l1 <= max_l1) && (NR::L2(offset) <= max_l2)) ) {
+ return true;
+ }
}
for (int i = 0; i < s->numberOfEdges(); i++) {
- if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
- NR::Point const st(s->getPoint(s->getEdge(i).st).x);
- NR::Point const en(s->getPoint(s->getEdge(i).en).x);
- NR::Point const d(p - st);
- NR::Point const e(en - st);
- double const el = NR::L2(e);
- if ( el > 0.001 ) {
- NR::Point const e_unit(e / el);
- double const npr = NR::dot(d, e_unit);
- if ( npr > 0 && npr < el ) {
- double const nl = fabs(NR::cross(d, e_unit));
- if ( nl <= max_l2 ) {
- return true;
- }
- }
- }
- }
+ if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
+ NR::Point const st(s->getPoint(s->getEdge(i).st).x);
+ NR::Point const en(s->getPoint(s->getEdge(i).en).x);
+ NR::Point const d(p - st);
+ NR::Point const e(en - st);
+ double const el = NR::L2(e);
+ if ( el > 0.001 ) {
+ NR::Point const e_unit(e / el);
+ double const npr = NR::dot(d, e_unit);
+ if ( npr > 0 && npr < el ) {
+ double const nl = fabs(NR::cross(d, e_unit));
+ if ( nl <= max_l2 ) {
+ return true;
+ }
+ }
+ }
+ }
}
return false;