Shape.cpp revision 73414d61d2a26490922f272008d3b4ba1c46e3b8
/*
* nlivarot
*
* Created by fred on Thu Jun 12 2003.
*
*/
#include "Shape.h"
#include "livarot/sweep-event-queue.h"
#include "livarot/sweep-tree-list.h"
#include <libnr/nr-point-fns.h>
/*
* Shape instances handling.
* never (i repeat: never) modify edges and points links; use Connect() and Disconnect() instead
* the graph is stored as a set of points and edges, with edges in a doubly-linked list for each point.
*/
_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),
_bbox_up_to_date(false)
{
maxPt = 0;
maxAr = 0;
}
{
maxPt = 0;
maxAr = 0;
}
{
/*
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
}
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
}
*/
}
/**
* Allocates space for point cache or clears the cache
\param nVal Allocate a cache (true) or clear it (false)
*/
void
{
if (nVal)
{
if (_has_points_data == false)
{
_has_points_data = true;
_point_data_initialised = false;
_bbox_up_to_date = false;
}
}
/* no need to clean point data - keep it cached*/
}
void
{
if (nVal)
{
if (_has_edges_data == false)
{
_has_edges_data = true;
}
}
else
{
if (_has_edges_data)
{
_has_edges_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_raster_data == false)
{
_has_raster_data = true;
}
}
else
{
if (_has_raster_data)
{
_has_raster_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_quick_raster_data == false)
{
_has_quick_raster_data = true;
}
}
else
{
{
_has_quick_raster_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_sweep_src_data == false)
{
_has_sweep_src_data = true;
}
}
else
{
if (_has_sweep_src_data)
{
_has_sweep_src_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_sweep_dest_data == false)
{
_has_sweep_dest_data = true;
}
}
else
{
if (_has_sweep_dest_data)
{
_has_sweep_dest_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_back_data == false)
{
_has_back_data = true;
}
}
else
{
if (_has_back_data)
{
_has_back_data = false;
}
}
}
void
{
if (nVal)
{
if (_has_voronoi_data == false)
{
_has_voronoi_data = true;
}
}
else
{
if (_has_voronoi_data)
{
_has_voronoi_data = false;
}
}
}
/**
* Copy point and edge data from `who' into this object, discarding
* any cached data that we have.
*/
void
{
{
Reset (0, 0);
return;
}
MakePointData (false);
MakeEdgeData (false);
MakeSweepSrcData (false);
MakeSweepDestData (false);
MakeRasterData (false);
MakeQuickRasterData (false);
MakeBackData (false);
delete sTree;
delete sEvts;
_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;
_bbox_up_to_date = false;
}
/**
* Clear points and edges and prepare internal data using new size.
*/
void
{
if (pointCount > maxPt)
{
maxPt = pointCount;
if (_has_points_data)
if (_has_voronoi_data)
}
{
if (_has_edges_data)
if (_has_sweep_dest_data)
if (_has_sweep_src_data)
if (_has_back_data)
if (_has_voronoi_data)
}
_need_points_sorting = false;
_need_edges_sorting = false;
_point_data_initialised = false;
_bbox_up_to_date = false;
}
int
{
if (numberOfPoints() >= maxPt)
{
if (_has_points_data)
if (_has_voronoi_data)
}
dg_point p;
p.x = x;
p.oldDegree = -1;
if (_has_points_data)
{
}
if (_has_voronoi_data)
{
}
_need_points_sorting = true;
return n;
}
void
{
if (p < 0 || p >= numberOfPoints())
return;
_need_points_sorting = true;
int cb;
{
{
}
{
}
else
{
break;
}
}
if (p < numberOfPoints() - 1)
}
void
Shape::SwapPoints (int a, int b)
{
if (a == b)
return;
{
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
}
else
{
int cb;
while (cb >= 0)
{
{
}
{
}
}
while (cb >= 0)
{
{
}
{
}
}
while (cb >= 0)
{
{
}
{
}
}
}
{
}
if (_has_points_data)
{
// pData[pData[a].oldInd].newInd=a;
// pData[pData[b].oldInd].newInd=b;
}
if (_has_voronoi_data)
{
}
}
void
Shape::SwapPoints (int a, int b, int c)
{
if (a == b || b == c || a == c)
return;
SwapPoints (a, b);
SwapPoints (b, c);
}
void
Shape::SortPoints (void)
{
if (_need_points_sorting && hasPoints())
_need_points_sorting = false;
}
void
Shape::SortPointsRounded (void)
{
if (hasPoints())
}
void
Shape::SortPoints (int s, int e)
{
if (s >= e)
return;
if (e == s + 1)
{
SwapPoints (s, e);
return;
}
int ppos = (s + e) / 2;
{
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
ppos--;
continue; // sans changer le
}
{
ppos--;
break;
}
else
{
// oupsie
break;
}
}
if (test > 0)
{
break;
}
le++;
}
}
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
plast++;
continue; // sans changer ri
}
{
plast++;
break;
}
else
{
// oupsie
break;
}
}
if (test < 0)
{
break;
}
ri--;
}
}
{
{
le++;
ri--;
}
else
{
{
ppos--;
plast--;
}
{
ppos--;
plast--;
}
}
}
else
{
{
ppos++;
plast++;
}
{
ppos++;
plast++;
}
else
{
break;
}
}
}
}
void
Shape::SortPointsByOldInd (int s, int e)
{
if (s >= e)
return;
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);
return;
}
int ppos = (s + e) / 2;
{
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
ppos--;
continue; // sans changer le
}
{
ppos--;
break;
}
else
{
// oupsie
break;
}
}
if (test > 0)
{
break;
}
le++;
}
}
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
plast++;
continue; // sans changer ri
}
{
plast++;
break;
}
else
{
// oupsie
break;
}
}
if (test < 0)
{
break;
}
ri--;
}
}
{
{
le++;
ri--;
}
else
{
{
ppos--;
plast--;
}
{
ppos--;
plast--;
}
}
}
else
{
{
ppos++;
plast++;
}
{
ppos++;
plast++;
}
else
{
break;
}
}
}
}
void
Shape::SortPointsRounded (int s, int e)
{
if (s >= e)
return;
if (e == s + 1)
{
SwapPoints (s, e);
return;
}
int ppos = (s + e) / 2;
{
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
ppos--;
continue; // sans changer le
}
{
ppos--;
break;
}
else
{
// oupsie
break;
}
}
if (test > 0)
{
break;
}
le++;
}
}
{
do
{
int test = 0;
{
test = 1;
}
{
{
test = 1;
}
{
test = 0;
}
else
{
test = -1;
}
}
else
{
test = -1;
}
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
plast++;
continue; // sans changer ri
}
{
plast++;
break;
}
else
{
// oupsie
break;
}
}
if (test < 0)
{
break;
}
ri--;
}
}
{
{
le++;
ri--;
}
else
{
{
ppos--;
plast--;
}
{
ppos--;
plast--;
}
}
}
else
{
{
ppos++;
plast++;
}
{
ppos++;
plast++;
}
else
{
break;
}
}
}
}
/*
*
*/
int
{
return -1;
return -1;
type = shape_graph;
if (numberOfEdges() >= maxAr)
{
if (_has_edges_data)
if (_has_sweep_src_data)
if (_has_sweep_dest_data)
if (_has_raster_data)
if (_has_back_data)
if (_has_voronoi_data)
}
dg_arete a;
}
int const n = numberOfEdges() - 1;
ConnectStart (st, n);
ConnectEnd (en, n);
if (_has_edges_data)
{
}
if (_has_sweep_src_data)
{
}
if (_has_back_data)
{
}
if (_has_voronoi_data)
{
}
_need_edges_sorting = true;
return n;
}
int
{
return -1;
return -1;
{
while (cb >= 0)
{
return -1; // doublon
return -1; // doublon
}
}
type = shape_graph;
if (numberOfEdges() >= maxAr)
{
if (_has_edges_data)
if (_has_sweep_src_data)
if (_has_sweep_dest_data)
if (_has_raster_data)
if (_has_back_data)
if (_has_voronoi_data)
}
dg_arete a;
}
int const n = numberOfEdges() - 1;
ConnectStart (st, n);
ConnectEnd (en, n);
if (_has_edges_data)
{
}
if (_has_sweep_src_data)
{
}
if (_has_back_data)
{
}
if (_has_voronoi_data)
{
}
_need_edges_sorting = true;
return n;
}
void
{
if (e < 0 || e >= numberOfEdges())
return;
type = shape_graph;
DisconnectStart (e);
DisconnectEnd (e);
if (e < numberOfEdges() - 1)
_need_edges_sorting = true;
}
void
{
if (a == b)
return;
{
{
}
{
}
}
{
{
}
{
}
}
{
{
}
{
}
}
{
{
}
{
}
}
{
}
{
}
{
{
}
{
}
}
{
{
}
{
}
}
{
{
}
{
}
}
{
{
}
{
}
}
for (int i = 0; i < 2; i++) {
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == b) {
_pts[p].incidentEdge[i] = a;
}
}
if (p >= 0) {
if (getPoint(p).incidentEdge[i] == b) {
_pts[p].incidentEdge[i] = a;
}
}
if (p >= 0) {
_pts[p].incidentEdge[i] = b;
}
}
if (p >= 0) {
_pts[p].incidentEdge[i] = b;
}
}
}
if (_has_edges_data)
{
}
if (_has_sweep_src_data)
{
}
if (_has_sweep_dest_data)
{
}
if (_has_raster_data)
{
}
if (_has_back_data)
{
}
if (_has_voronoi_data)
{
}
}
void
{
if (a == b || b == c || a == c)
return;
SwapEdges (a, b);
SwapEdges (b, c);
}
void
{
if (_need_edges_sorting == false) {
return;
}
_need_edges_sorting = false;
for (int p = 0; p < numberOfPoints(); p++)
{
int const d = getPoint(p).totalDegree();
if (d > 1)
{
int cb;
int nb = 0;
while (cb >= 0)
{
int n = nb++;
{
}
else
{
}
}
for (int i = 0; i < nb; i++)
{
{
if (i > 0)
{
}
else
{
}
if (i < nb - 1)
{
}
else
{
}
}
else
{
if (i > 0)
{
}
else
{
}
if (i < nb - 1)
{
}
else
{
}
}
}
}
}
}
int
{
int tstAX = 0;
int tstAY = 0;
int tstBX = 0;
int tstBY = 0;
if (ax[0] > 0)
tstAX = 1;
if (ax[0] < 0)
tstAX = -1;
if (ax[1] > 0)
tstAY = 1;
if (ax[1] < 0)
tstAY = -1;
if (bx[0] > 0)
tstBX = 1;
if (bx[0] < 0)
tstBX = -1;
if (bx[1] > 0)
tstBY = 1;
if (bx[1] < 0)
tstBY = -1;
if (tstAX < 0)
{
if (tstAY < 0)
{
quadA = 7;
}
else if (tstAY == 0)
{
quadA = 6;
}
else if (tstAY > 0)
{
quadA = 5;
}
}
else if (tstAX == 0)
{
if (tstAY < 0)
{
quadA = 0;
}
else if (tstAY == 0)
{
quadA = -1;
}
else if (tstAY > 0)
{
quadA = 4;
}
}
else if (tstAX > 0)
{
if (tstAY < 0)
{
quadA = 1;
}
else if (tstAY == 0)
{
quadA = 2;
}
else if (tstAY > 0)
{
quadA = 3;
}
}
if (tstBX < 0)
{
if (tstBY < 0)
{
quadB = 7;
}
else if (tstBY == 0)
{
quadB = 6;
}
else if (tstBY > 0)
{
quadB = 5;
}
}
else if (tstBX == 0)
{
if (tstBY < 0)
{
quadB = 0;
}
else if (tstBY == 0)
{
quadB = -1;
}
else if (tstBY > 0)
{
quadB = 4;
}
}
else if (tstBX > 0)
{
if (tstBY < 0)
{
quadB = 1;
}
else if (tstBY == 0)
{
quadB = 2;
}
else if (tstBY > 0)
{
quadB = 3;
}
}
return 1;
return -1;
int tstSi = 0;
if ( tstSi == 0 ) {
}
return tstSi;
}
void
{
if (s >= e)
return;
if (e == s + 1) {
if ( cmpval > 0 ) { // priorite aux sortants
}
return;
}
int ppos = (s + e) / 2;
{
{
do
{
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
ppos--;
continue; // sans changer le
}
{
ppos--;
break;
}
else
{
// oupsie
break;
}
}
if (test > 0)
{
break;
}
le++;
}
}
{
do
{
if (test == 0)
{
// on colle les valeurs egales au pivot ensemble
{
plast++;
continue; // sans changer ri
}
{
plast++;
break;
}
else
{
// oupsie
break;
}
}
if (test < 0)
{
break;
}
ri--;
}
}
{
{
le++;
ri--;
}
{
ppos--;
plast--;
}
{
ppos--;
plast--;
}
else
{
break;
}
}
else
{
{
ppos++;
plast++;
}
{
ppos++;
plast++;
}
else
{
break;
}
}
}
}
/*
*
*/
void
Shape::ConnectStart (int p, int b)
{
DisconnectStart (b);
{
{
}
{
}
}
}
void
Shape::ConnectEnd (int p, int b)
{
DisconnectEnd (b);
{
{
}
{
}
}
}
void
Shape::DisconnectStart (int b)
{
return;
{
{
}
{
}
}
{
{
}
{
}
}
}
void
Shape::DisconnectEnd (int b)
{
return;
{
{
}
{
}
}
{
{
}
{
}
}
}
void
{
int swap;
{
}
{
}
if (_has_edges_data)
if (_has_sweep_dest_data)
{
}
if (_has_back_data)
{
}
if (_has_voronoi_data)
{
}
}
void
{
if (_bbox_up_to_date)
return;
if (hasPoints() == false)
{
_bbox_up_to_date = true;
return;
}
bool not_set=true;
for (int i = 0; i < numberOfPoints(); i++)
{
if ( not_set ) {
not_set=false;
} else {
}
}
}
_bbox_up_to_date = true;
}
// winding of a point with respect to the Shape
// 0= outside
// 1= inside (or -1, that usually the same)
// other=depends on your fill rule
// if the polygon is uncrossed, it's all the same, usually
int
{
for (int i = 0; i < numberOfEdges(); i++)
{
//int const nWeight = eData[i].weight;
int const nWeight = 1;
} else {
}
continue;
}
continue;
}
} else {
}
if (cote == 0) continue;
if (cote < 0) {
} else {
}
}
}
void Shape::initialisePointData()
{
return;
int const N = numberOfPoints();
for (int i = 0; i < N; i++) {
}
_point_data_initialised = true;
}
void Shape::initialiseEdgeData()
{
int const N = numberOfEdges();
for (int i = 0; i < N; i++) {
}
}
}
void Shape::clearIncidenceData()
{
}
/**
* A directed graph is Eulerian iff every vertex has equal indegree and outdegree.
*
* \param s Directed shape.
* \return true if s is Eulerian.
*/
bool directedEulerian(Shape const *s)
{
for (int i = 0; i < s->numberOfPoints(); i++) {
return false;
}
}
return true;
}
/**
* \param s Shape.
* \param p Point.
* \return Minimum distance from p to any of the points or edges of s.
*/
{
if ( s->hasPoints() == false) {
return 0.0;
}
/* Find the minimum distance from p to one of the points on s.
** Computing the dot product of the difference vector gives
** us the distance squared; we can leave the square root
** until the end.
*/
for (int i = 0; i < s->numberOfPoints(); i++) {
}
}
for (int i = 0; i < s->numberOfEdges(); i++) {
/* The edge has start and end points */
/* Update bdot if appropriate */
if ( el > 0.001 ) {
}
}
}
}
}
}
/**
* Returns true iff the L2 distance from \a thePt to this shape is <= \a max_l2.
* Distance = the min of distance to its points and distance to its edges.
* Points without edges are considered, which is maybe unwanted...
*
* This is largely similar to distance().
*
* \param s Shape.
* \param p Point.
* \param max_l2 L2 distance.
*/
{
if ( s->hasPoints() == false ) {
return false;
}
/* TODO: Consider using bbox to return early, perhaps conditional on nbPt or nbAr. */
/* TODO: Efficiency: In one test case (scribbling with the freehand tool to create a small number of long
** path elements), changing from a Distance method to a DistanceLE method reduced this
** function's CPU time from about 21% of total inkscape CPU time to 14-15% of total inkscape
** CPU time, due to allowing early termination. I don't know how much the L1 test helps, it
** may well be a case of premature optimization. Consider testing dot(offset, offset)
** instead.
*/
for (int i = 0; i < s->numberOfPoints(); i++) {
return true;
}
}
for (int i = 0; i < s->numberOfEdges(); i++) {
if ( el > 0.001 ) {
return true;
}
}
}
}
}
return false;
}
//};