Inkscape: Shape Class Reference

Searching...

No Matches

A class to store/manipulate directed graphs. More...

#include <Shape.h>

Classes
struct	back_data
	A structure to store back data for an edge. More...

struct	dg_arete
	An edge in the directed graph. More...

struct	dg_point
	A point or vertex in the directed graph. More...

struct	edge_data
	Extra data that some algorithms use. More...

struct	edge_list
	A structure to help with sorting edges around a point. More...

struct	incidenceData

struct	point_data
	Extra data for points used at various occasions. More...

struct	raster_data

struct	sTreeChange
	A structure that represents a change that took place in the sweepline. More...

struct	sweep_dest_data

struct	sweep_src_data

Public Types
enum	sTreeChangeType { EDGE_INSERTED = 0 , EDGE_REMOVED = 1 , INTERSECTION = 2 }
	Enum describing all the events that can happen to a sweepline. More...

Public Member Functions
	Shape ()

	~Shape ()

void	MakeBackData (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 all data.

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 ()
	Sort the points (all points) only if needed.

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 ()
	Sort all edges (clockwise) around each point.

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)
	Extract contours from a directed graph.

void	ConvertToForme (Path dest, int nbP, Path const *orig, bool never_split=false)
	Extract contours from a directed graph while using back data.

void	ConvertToFormeNested (Path dest, int nbP, Path const orig, int &nbNest, int &nesting, int *&contStart, bool never_split=false)

int	ConvertToShape (Shape *a, FillRule directed=fill_nonZero, bool invert=false)
	Using a given fill rule, find all intersections in the shape given, create a new intersection free shape in the instance.

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::Affine i2doc=nullptr)

int	MakeTweak (int mode, Shape a, double dec, JoinType join, double miter, bool do_profile, Geom::Point c, Geom::Point vector, double radius, Geom::Affine i2doc)

int	PtWinding (const Geom::Point px) const

int	Winding (const Geom::Point px) const
	Compute the winding number of the point given.

void	BeginRaster (float &pos, int &curPt)

void	EndRaster ()

void	Scan (float &pos, int &curP, float to, float step)

void	Scan (float &pos, int &curP, float to, FloatLigne *line, bool exact, float step)

void	Transform (Geom::Affine const &tr)

int	numberOfPoints () const
	Returns number of points.

bool	hasPoints () const
	Do we have points?

int	numberOfEdges () const
	Returns number of edges.

bool	hasEdges () const
	Do we have edges?

void	needPointsSorting ()
	Do the points need sorting?

void	needEdgesSorting ()
	Do the edges need sorting?

bool	hasBackData () const
	Do we have back data?

dg_point const &	getPoint (int n) const
	Get a point.

dg_arete const &	getEdge (int n) const
	Get an edge.

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< 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)
	Initialize the point data cache.

void	MakeEdgeData (bool nVal)
	Initialize the edge data cache.

void	MakeSweepSrcData (bool nVal)
	Initialize the sweep source data cache.

void	MakeSweepDestData (bool nVal)
	Initialize the sweep destination data cache.

void	MakeRasterData (bool nVal)

void	SortPoints (int s, int e)
	Sort the points.

void	SortPointsByOldInd (int s, int e)
	Sort the points (take oldInd into account)

void	ResetSweep ()
	Prepare point data cache, edge data cache and sweep source cache.

void	CleanupSweep ()
	Clear point data cache, edge data cache and sweep source cache.

void	SortEdgesList (edge_list *edges, int s, int e)
	Sort edges given in a list.

void	TesteIntersection (SweepTree *t, Side s, bool onlyDiff)
	Test if there is an intersection of an edge on a particular side.

bool	TesteIntersection (SweepTree iL, SweepTree iR, Geom::Point &atx, double &atL, double &atR, bool onlyDiff)
	Test intersection between the two edges.

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)
	Sort the points and merge duplicate ones.

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)
	Add the event in chgts.

void	CheckAdjacencies (int lastPointNo, int lastChgtPt, Shape *shapeHead, int edgeHead)
	If there are points that lie on edges, mark this by modifying leftRnd and rightRnd variables.

void	CheckEdges (int lastPointNo, int lastChgtPt, Shape a, Shape b, BooleanOp mod)
	Check if there are edges to draw and draw them.

void	Avance (int lastPointNo, int lastChgtPt, Shape iS, int iB, Shape a, Shape *b, BooleanOp mod)
	Do the edge.

void	DoEdgeTo (Shape *iS, int iB, int iTo, bool direct, bool sens)
	Draw edge to a passed point.

void	GetWindings (bool brutal=false)
	Calculates the winding numbers to the left and right of all edges of this shape.

void	Validate ()

int	Winding (int nPt) const
	Get the winding number for a point but from the data left by the sweepline algorithm.

void	SortPointsRounded ()
	Sort all points by their rounded coordinates.

void	SortPointsRounded (int s, int e)
	Sort points by their rounded coordinates.

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	AddContour (Path dest, int num_orig, Path const *orig, int start_edge, bool never_split=false)
	Add a contour.

int	ReFormeLineTo (int bord, Path *dest, bool never_split)

int	ReFormeArcTo (int bord, Path dest, Path orig, bool never_split)

int	ReFormeCubicTo (int bord, Path dest, Path orig, bool never_split)

Static Private Member Functions
static int	CmpToVert (const Geom::Point ax, const Geom::Point bx, bool as, bool bs)
	Edge comparison function.

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_back_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

A class to store/manipulate directed graphs.

This class is at the heart of everything we do in Livarot. When you first populate a Shape by calling Path::Fill, it makes a directed graph of the type shape_graph. This one is exactly identical to the original polyline except that it's a graph. Later, you call Shape::ConvertToShape to create another directed graph from this one that is totally intersection free. All the intersections would have been calculated, edges broken up at those points, all edges flipped such that inside is to their left. You ofcourse need a fill rule to do this.

Once that's done, you can do all interesting operations such as Tweaking, Offsetting and Boolean Operations.

Definition at line 64 of file Shape.h.

Member Enumeration Documentation

◆ sTreeChangeType

enum Shape::sTreeChangeType

Enum describing all the events that can happen to a sweepline.

Enumerator
EDGE_INSERTED	A new edge got added.
EDGE_REMOVED	An edge got removed.
INTERSECTION	An intersection got detected.

Definition at line 81 of file Shape.h.

Constructor & Destructor Documentation

◆ Shape()

Shape::Shape ( )

Definition at line 26 of file Shape.cpp.

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

◆ ~Shape()

Shape::~Shape ( )

Definition at line 49 of file Shape.cpp.

References maxAr, and maxPt.

Member Function Documentation

◆ _countUpDown()

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 619 of file ShapeRaster.cpp.

References Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, NextAt(), numberOfEdges(), and Shape::dg_arete::st.

Referenced by Scan(), and Scan().

◆ _countUpDownTotalDegree2()

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 649 of file ShapeRaster.cpp.

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

Referenced by Scan().

◆ _updateIntersection()

void Shape::_updateIntersection	(	int	e,
		int	p
	)

private

Definition at line 671 of file ShapeRaster.cpp.

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

Referenced by Scan().

◆ AddChgt()

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

private

Add the event in chgts.

The function adds stuff to the edgehead and shapeHead linked lists as well as set the leftRnd and rightRnd in swsData of the edges.

Parameters

lastPointNo	The point that was just added in "this" shape.
lastChgtPt	Either lastPointNo if it's the left most point at that y level or whichever point is the left most at the same y level as lastPointNo.
shapeHead	The linked list from ConvertToShape and Booleen.
edgeHead	The linked list from ConvertToShape and Booleen.
type	The type of event this is.
lS	Pointer to the unique edge's shape if this is edge addition/removal or the left edge's shape if an intersection event.
lB	The unique edge (or the left edge if an intersection event).
rS	Pointer to the right edge's shape if this is an intersection event.
rB	The right edge if this is an intersection event.

Definition at line 3169 of file ShapeSweep.cpp.

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

Referenced by Booleen(), and ConvertToShape().

◆ AddContour()

void Shape::AddContour	(	Path *	dest,
		int	num_orig,
		Path const	orig,
		int	start_edge,
		bool	never_split = `false`
	)

private

Add a contour.

Parameters

dest	The pointer to the Path object where we want to add contours.
num_orig	The total number of path object points in the array orig.
orig	A pointer of Path object pointers. These are the original Path objects which were used to fill the directed graph.
start_edge	The first edge in the contour.
never_split	Always coalesce pieces that come from the same original path, and don't insert forced points.

Definition at line 900 of file ShapeMisc.cpp.

References _has_back_data, Path::Close(), descr_arcto, descr_cubicto, descr_lineto, ebData, FIRST, Path::ForcePoint(), getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, Path::LineTo(), Path::MoveTo(), orig, ReFormeArcTo(), ReFormeCubicTo(), ReFormeLineTo(), and swdData.

Referenced by ConvertToForme(), and ConvertToFormeNested().

◆ AddEdge() [1/2]

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

Definition at line 1052 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _need_edges_sorting, ConnectEnd(), ConnectStart(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), getPoint(), maxAr, Shape::dg_arete::nextE, Shape::dg_arete::nextS, numberOfEdges(), Shape::dg_arete::prevE, Shape::dg_arete::prevS, shape_graph, Shape::dg_arete::st, swdData, swrData, swsData, type, and Shape::dg_point::x.

Referenced by SPText::_buildLayoutInit(), Booleen(), DoEdgeTo(), Path::Fill(), MakeOffset(), MakeTweak(), and Path::Stroke().

◆ AddEdge() [2/2]

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

◆ AddPoint()

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

Definition at line 266 of file Shape.cpp.

References _has_points_data, _need_points_sorting, _pts, Shape::dg_point::dI, Shape::dg_point::dO, FIRST, Shape::dg_point::incidentEdge, LAST, maxPt, numberOfPoints(), Shape::dg_point::oldDegree, pData, Round(), and Shape::dg_point::x.

Referenced by SPText::_buildLayoutInit(), Booleen(), ConvertToShape(), and Path::Fill().

◆ Affiche()

void Shape::Affiche ( )

Definition at line 55 of file Shape.cpp.

References _aretes, and _pts.

◆ AssembleAretes()

void Shape::AssembleAretes ( FillRule directed = fill_nonZero )

private

Definition at line 2344 of file ShapeSweep.cpp.

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

Referenced by Booleen(), and ConvertToShape().

◆ AssemblePoints() [1/2]

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

private

Sort the points and merge duplicate ones.

Sort the points from st to en - 1. No idea why the parameters were set up in this weird way.

The function also sets up newInd to the new indices so everything else can update the indices instantly.

Parameters

st	The start of the range of points to sort.
en	One more than the end of the range of points to sort.

Returns: If st and en are the same, nothing is done and en is returned. Otherwise, an index one more than the last point in the sorted and merged list is returned. So say we gave the sequence of points indexed 2,4,5,6,7 and 4 and 5 were duplicates so final sequence would have indices 2,4,5,6 and the function will return 7.

Definition at line 2278 of file ShapeSweep.cpp.

References _pts, getPoint(), pData, SortPointsByOldInd(), and Shape::dg_point::x.

◆ AssemblePoints() [2/2]

void Shape::AssemblePoints ( Shape * a )

private

Definition at line 2326 of file ShapeSweep.cpp.

References _pts, AssemblePoints(), hasPoints(), iData, nbInc, numberOfEdges(), numberOfPoints(), pData, and swsData.

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

◆ Avance()

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

private

Do the edge.

That's a very vague thing to say but basically this function checks the leftRnd and rightRnd of the edge and if anything needs to be drawn, it draws them.

Most of the code you see in the function body deals with a very rare diagonal case that I suspect would be extremely rare. I'll add comments in the code body to further highlight this. But if you ignore all of that whatever remains is quite simple.

This picture shows you how the variables look like when Avance is called by CheckEdges which is called from a block of code in Shape::ConvertToShape or Shape::Booleen. You can see that lastPointNo is the point that just got added to the list and it has to be the left most, there can't be another point at the same y and to the left of lastPointNo. The reason is, the block which calls CheckEdges is called at the leftmost point at a particular y. You should also note how lastChgtPt is the left most point but just above lastPointNo (smaller y), can't be the same y.

This image is referred from code comments to help explain a point.

Parameters

lastPointNo	The new point that the sweepline just jumped on. No edge processing (adding/removal) has been done on the point yet. The point has only been added in "this" shape and this is its index.
lastChgtPt	This is hard to visualize but imagine the set of points having a y just smaller than lastPointNo's y and now within those points (if there are multiple ones), get the left most one. That's what lastChgtPt will be.
iS	The shape to which edge iB belongs.
iB	The index of the edge to draw/do.
a	Shape a. Not really used.
b	Shape b if called ultimately from Shape::Booleen.
mod	The mode of boolean operation.

Definition at line 3394 of file ShapeSweep.cpp.

References bool_op_diff, bool_op_symdiff, DoEdgeTo(), eData, getPoint(), HalfRound(), numberOfPoints(), and swsData.

Referenced by CheckEdges().

◆ AvanceEdge() [1/2]

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

private

Definition at line 480 of file ShapeRaster.cpp.

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

Referenced by AvanceEdge(), Scan(), and Scan().

◆ AvanceEdge() [2/2]

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

private

Definition at line 560 of file ShapeRaster.cpp.

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

◆ BeginRaster()

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

Definition at line 30 of file ShapeRaster.cpp.

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

◆ Booleen()

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

Definition at line 926 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(), Shape::dg_point::dI, directedEulerian(), Shape::dg_point::dO, ebData, eData, EDGE_INSERTED, EDGE_REMOVED, Shape::dg_arete::en, SweepEventQueue::extract(), fill_justDont, FIRST, getEdge(), getPoint(), GetWindings(), hasBackData(), Shape::dg_point::incidentEdge, initialiseEdgeData(), initialisePointData(), INTERSECTION, Inverse(), LEFT, MakeBackData(), MakeEdgeData(), MakePointData(), MakeSweepDestData(), MakeSweepSrcData(), NextAt(), node, numberOfEdges(), numberOfPoints(), pData, SweepEventQueue::peek(), SweepTree::RemoveEvent(), 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 Inkscape::ObjectSet::_pathBoolOp(), pathvector_cut(), and sp_pathvector_boolop().

◆ CalcBBox()

void Shape::CalcBBox ( bool strict_degree = false )

Definition at line 1963 of file Shape.cpp.

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

Referenced by SPOffset::set_shape(), and Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker().

◆ CheckAdjacencies()

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

private

If there are points that lie on edges, mark this by modifying leftRnd and rightRnd variables.

Please note that an adjacency means a point lying on an edge somewhere. This is checked by the function TesteAdjacency.

Before I go into discussing how it works please review the following figure to have an idea about how the points look like when this function is called from Shape::ConvertToShape.

This function has a main loop that runs on all events in chgts. Each event can either be an edge addition or edge addition or edge intersection. Each event (chgt) keeps four important things. A unique edge associated with the event. For addition/removal it's the main edge that got added/removed. For intersection it's the left one. It stores the right edge too in case of an intersection. Then there are two pointers to edges to the left and right in the sweepline at the time the event happened. This function does four things:

For the unique edge, get the leftRnd and rightRnd. Sets chLeN and chRiN depending on ptNo of the event and the leftRnd and rightRnd. See the code to see how this is done. We test all points ranging from lastChgtPt to leftRnd-1 for a possible adjacency with this unique edge. If found, we set leftRnd of the unique edge accordingly. We also test points in the range rightRnd+1 to lastPointNo (not included) for an adjacency and if found, we set rightRnd accordingly.
Exactly identical thing is done with the right edge (if this is an intersection event).
Then there is the possibility of having an edge on the left in the sweepline at the time the event happened. If that's the case, we do something very special. We check if the left edge's leftRnd is smaller than lastChgtPt, if not, it means the leftRnd got updated in the previous iteration of the main loop, thus, we don't need to take care of it or do anything about it. If it is smaller than lastChgtPt, we run a loop testing all points in the range chLeN..chRiN of having an adjacency with that edge. We update leftRnd and rightRnd of the left edge after doing some checks. This process gets repeated for all the edges to the left.
Same as 3 but for edges to the right.

3 and 4 are very useful. They deal with cases when you have some other edge's endpoint exactly on some edge and these modify leftRnd and rightRnd of the edge so that CheckEdges will later split that edge at that endpoint. For example, a shape like: SVG path: M 500,200 L 500,800 L 200,800 L 500,500 L 200,200 Z

Definition at line 2937 of file ShapeSweep.cpp.

References chgts, getPoint(), LEFT, node, RIGHT, swsData, TesteAdjacency(), and Shape::dg_point::x.

Referenced by Booleen(), and ConvertToShape().

◆ CheckEdges()

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

private

Check if there are edges to draw and draw them.

Parameters

lastPointNo	The point that was just added. See the figure above.
lastChgtPt	See the figure above.
a	The main shape a.
b	The other shape if called from Shape::Booleen.
mod	The boolean operation mode if called from Shape::Booleen.

Definition at line 3307 of file ShapeSweep.cpp.

References Avance(), chgts, LEFT, node, RIGHT, and swsData.

Referenced by Booleen(), and ConvertToShape().

◆ CleanupSweep()

void Shape::CleanupSweep ( )

private

Clear point data cache, edge data cache and sweep source cache.

Definition at line 58 of file ShapeSweep.cpp.

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

Referenced by Booleen(), and ConvertToShape().

◆ clearIncidenceData()

void Shape::clearIncidenceData ( )

private

Definition at line 2100 of file Shape.cpp.

References iData, maxInc, and nbInc.

Referenced by Booleen(), and ConvertToShape().

◆ CmpToVert()

int Shape::CmpToVert	(	const Geom::Point	ax,
		const Geom::Point	bx,
		bool	as,
		bool	bs
	)

staticprivate

Edge comparison function.

The function returns +1 when a swap is needed. The arguments are arranged in a weird way. Say you have two edges: w x y z and you wanna ask if w and x should be swapped, you pass parameters such that ax = x & bx = w.

The explaination of the function in the code body uses this picture to help explain.

Parameters

ax	The right edge in the list before sorting.
bx	The left edge in the list before sorting.
as	True if the edge of vector ax started from the point. False if it ended there.
bs	True if the edge of vector bx started from the point. False if it ended there.

Returns: A positive number if the arrangement bx ax is wrong and should be swapped.

Definition at line 1482 of file Shape.cpp.

References bs.

Referenced by SortEdgesList().

◆ ConnectEnd()

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

Definition at line 1828 of file Shape.cpp.

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

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

◆ ConnectStart()

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

Definition at line 1802 of file Shape.cpp.

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

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

◆ ConvertToForme() [1/2]

void Shape::ConvertToForme ( Path * dest )

Extract contours from a directed graph.

The function doesn't care about any back data and thus all contours will be made up of line segments. Any original curves would be lost.

The traversal algorithm is totally identical to GetWindings with minor differences.

Parameters

[out] dest Pointer to the path where the extracted contours will be stored.

Definition at line 42 of file ShapeMisc.cpp.

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

Referenced by Inkscape::ObjectSet::_pathBoolOp(), ConvertToForme(), ConvertToFormeNested(), Inkscape::UI::Tools::do_trace(), item_find_paths(), refresh_offset_source(), SPOffset::set_shape(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_remove_inner(), sp_selected_path_create_offset_object(), sp_selected_path_do_offset(), and Inkscape::UI::Tools::sp_tweak_dilate_recursive().

◆ ConvertToForme() [2/2]

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

Extract contours from a directed graph while using back data.

Since back data is used, the original curves are preserved.

Parameters

[out]	dest	Pointer to the path where the extracted contours will be stored.
	nbP	Number of paths that were originally fed to the directed graph with Path::Fill.
	orig	An array of pointers to Path, one Path object for each path id in the graph.

Definition at line 192 of file ShapeMisc.cpp.

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

◆ ConvertToFormeNested()

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

Definition at line 343 of file ShapeMisc.cpp.

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

Referenced by Inkscape::ObjectSet::_pathBoolOp(), and pathvector_cut().

◆ ConvertToShape()

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

Using a given fill rule, find all intersections in the shape given, create a new intersection free shape in the instance.

The word "instance" or "this" is used throughout the documentation to refer to the instance on which the function was called.

Details of the algorithm: The function does four things more or less:

Find all self-intersections in the shape.
Reconstruct the directed graph with the intersections now converted to vertices.
Compute winding number seeds for later use by GetWindings.
Do some processing on edges by calling AssembleAretes.
Compute winding numbers and accordingly manipulate edges. (Deciding whether to keep, invert or destroy them)

Finding self-intersections and reconstruction happens simultaneously. The function has a huge loop that moves a sweepline top to bottom, finding intersections and reconstructing the new directed graph. Edges are added/removed in the sweepline tree sTree and intersections detected go in sEvts. All events (Edge Addition/Removal/Intersection) that take place at a constant y value are recorded in an array named chgts and the function call to CheckEdges does the reconstruction.

One important thing to note is that usually in a Bentley-Ottman sweepline algorithm, the heap also contains endpoints (where edges start or end) but in this implementation that's not the case. The main loop takes care of the endpoints and the heap takes care of intersections only.

If you want a good theoretical overview of how all these things are done, please see the docs in livarot-doxygen.cpp.

Parameters

a	The pointer to the shape that we want to process.
directed	The fill rule.
invert	TODO: Be sure about what this does

Returns: 0 if everything went good, error code otherwise. (see LivarotDefs.h)

Definition at line 171 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(), Shape::dg_point::dI, directedEulerian(), Shape::dg_point::dO, eData, EDGE_INSERTED, EDGE_REMOVED, Shape::dg_arete::en, SweepEventQueue::extract(), fill_justDont, fill_nonZero, fill_oddEven, fill_positive, FIRST, getEdge(), getPoint(), GetWindings(), Shape::dg_point::incidentEdge, initialiseEdgeData(), initialisePointData(), INTERSECTION, Inverse(), invert(), LEFT, MakeBackData(), MakeEdgeData(), MakePointData(), MakeSweepDestData(), MakeSweepSrcData(), NextAt(), node, numberOfEdges(), numberOfPoints(), pData, SweepEventQueue::peek(), SweepTree::RemoveEvent(), 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 Inkscape::ObjectSet::_pathBoolOp(), Inkscape::UI::Tools::TextTool::_updateCursor(), Inkscape::UI::Tools::do_trace(), item_find_paths(), refresh_offset_source(), SPOffset::set_shape(), Inkscape::Text::Layout::ShapeScanlineMaker::ShapeScanlineMaker(), sp_offset_distance_to_original(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_remove_inner(), Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect(), sp_selected_path_create_offset_object(), sp_selected_path_do_offset(), and Inkscape::UI::Tools::sp_tweak_dilate_recursive().

◆ Copy()

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 195 of file Shape.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, _need_edges_sorting, _need_points_sorting, _point_data_initialised, _pts, MakeBackData(), MakeEdgeData(), MakePointData(), MakeRasterData(), MakeSweepDestData(), MakeSweepSrcData(), numberOfEdges(), numberOfPoints(), Reset(), sEvts, sTree, and type.

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

◆ CreateEdge()

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

private

Definition at line 446 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 Scan(), and Scan().

◆ CreateIncidence()

int Shape::CreateIncidence	(	Shape *	a,
		int	cb,
		int	pt
	)

private

Definition at line 2145 of file ShapeSweep.cpp.

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

◆ CycleNextAt()

int Shape::CycleNextAt	(	int	p,
		int	b
	)		const

inline

Definition at line 216 of file Shape.h.

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

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

◆ CyclePrevAt()

int Shape::CyclePrevAt	(	int	p,
		int	b
	)		const

inline

Definition at line 235 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().

◆ DestroyEdge()

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

private

Definition at line 512 of file ShapeRaster.cpp.

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

Referenced by Scan().

◆ DisconnectEnd()

void Shape::DisconnectEnd ( int b )

Definition at line 1888 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().

◆ DisconnectStart()

void Shape::DisconnectStart ( int b )

Definition at line 1853 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().

◆ DoEdgeTo()

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

private

Draw edge to a passed point.

You might ask, don't we need two points to draw an edge. Well iB is the original edge passed. The edge stores the last point until which it was drawn. We will simply draw an edge between that last point and the point iTo.

Say that lp is the last point drawn and iTo is the new point. The edge will be drawn in the following fashion depending on the values of direct and sens

direct & sens : lp -> iTo !direct & sens : iTo -> lp direct & !sens : iTo -> lp !direct & !sens : lp -> iTo

If the edges had back data, the backdata for the new points is carefully calculated by doing some maths so the correct t values are found. The function also updates "last point drawn" of that edge to the point iTo. There is one more important thing that this function does. If the edge iB has a linked list of points associated with it (due to computation of seed winding numbers) then we make sure to transfer that linked list of points to the new edge that we just drew and destroy the association with the original edge iB.

Parameters

iS	The shape to which the original edge belongs.
iB	The original edge in shape iS.
iTo	The point to draw the edge to.
direct	Used to control direction of the edge.
sens	Used to control direction of the edge.

Definition at line 3572 of file ShapeSweep.cpp.

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

Referenced by Avance().

◆ EndRaster()

void Shape::EndRaster ( )

Definition at line 68 of file ShapeRaster.cpp.

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

◆ ForceToPolygon()

void Shape::ForceToPolygon ( )

Definition at line 66 of file ShapeSweep.cpp.

References shape_polygon, and type.

◆ getEdge()

dg_arete const & Shape::getEdge ( int n ) const

inline

Get an edge.

Be careful about the index.

Parameters

n	Index of the edge.

Returns: Reference to the edge.

Definition at line 548 of file Shape.h.

References _aretes.

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

◆ getPoint()

dg_point const & Shape::getPoint ( int n ) const

inline

Get a point.

Be careful about the index.

Parameters

n	Index of the point.

Returns: Reference to the point.

Definition at line 537 of file Shape.h.

References _pts.

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

◆ GetWindings()

void Shape::GetWindings ( bool brutal = false )

private

Calculates the winding numbers to the left and right of all edges of this shape.

The winding numbers that are calculated are stored in swdData.

The winding number computation algorithm is a very interesting one and I'll get into its details too. The algorithm essentially follows sub-graphs to calculate winding numbers. A sub-graph is basically a set of edges and points that are connected to each other in the sense that you can walk on the edges to move around them. The winding number computation algorithm starts at the top most (and left most if there are multiple points at same y). There, it is known that the winding number outside the edges is definitely 0 since it's the outer most point. However, when you are starting on an edge that's inside the shape, a rectangle inside another one, you need to know what outside winding number really is for that point. See the following image to see what I mean.

For the outer contour, we know it's definitely 0 but for the inside one it needs to be calculated and it's -1. There are two ways to figure out this "seed" winding number. You can either iterate through all edges and calculate it manually. This is known as the brutual method. The other method is to use the winding number info left from the sweepline algorithm.

I have explained the winding number computation algorithm in detail in the code comments. Once we have a seed, we start walking on the edges. Once you have the left and right winding number for the first edge, you can move to its endpoint and depending on the relative directions of the edge vectors, you can definitely calculate the winding number for the next edge. See the code comments for details on this procedure.

Basically, given the winding numbers to the left and right of the current edge, and the orientation of the next edge with this one, we can calculate the winding number of the next edge and then repeat this process.

Parameters

brutal Should the algorithm use winding number seeds left by the sweepline or brutually compute the seeds?

Definition at line 2526 of file ShapeSweep.cpp.

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

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

◆ HalfRound()

static double Shape::HalfRound ( double x )

inlinestatic

Definition at line 356 of file Shape.h.

Referenced by Avance(), and TesteAdjacency().

◆ hasBackData()

bool Shape::hasBackData ( ) const

inline

Do we have back data?

Returns: True if we do, false otherwise.

Definition at line 526 of file Shape.h.

References _has_back_data.

Referenced by Inkscape::ObjectSet::_pathBoolOp(), Booleen(), sp_pathvector_boolop(), and Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect().

◆ hasEdges()

bool Shape::hasEdges ( ) const

inline

Do we have edges?

Returns: True if we do, false otherwise.

Definition at line 505 of file Shape.h.

References _aretes.

◆ hasPoints()

bool Shape::hasPoints ( ) const

inline

Do we have points?

Returns: True if we do, false otherwise.

Definition at line 491 of file Shape.h.

References _pts.

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

◆ IHalfRound()

static double Shape::IHalfRound ( double x )

inlinestatic

Definition at line 361 of file Shape.h.

Referenced by TesteAdjacency().

◆ initialiseEdgeData()

void Shape::initialiseEdgeData ( )

private

Definition at line 2070 of file Shape.cpp.

References dot(), eData, Shape::dg_arete::en, getEdge(), N, numberOfEdges(), pData, Shape::dg_arete::st, and swsData.

Referenced by Booleen(), and ConvertToShape().

◆ initialisePointData()

void Shape::initialisePointData ( )

private

Definition at line 2054 of file Shape.cpp.

References _point_data_initialised, getPoint(), N, numberOfPoints(), pData, and Round().

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

◆ Inverse()

void Shape::Inverse ( int b )

Definition at line 1924 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_sweep_dest_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, and swdData.

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

◆ MakeBackData()

void Shape::MakeBackData ( bool nVal )

Definition at line 169 of file Shape.cpp.

References _has_back_data, ebData, and maxAr.

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

◆ MakeEdgeData()

void Shape::MakeEdgeData ( bool nVal )

private

Initialize the edge data cache.

Parameters

nVal	If set to true, it sets some flags and then resizes eData to maxAr. If set to false, it clears all edge data.

Definition at line 87 of file Shape.cpp.

References _has_edges_data, eData, and maxAr.

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

◆ MakeOffset()

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::Affine *	i2doc = `nullptr`
	)

Definition at line 748 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(), CycleNextAt(), CyclePrevAt(), dot(), Shape::dg_arete::dx, ebData, eData, Shape::dg_arete::en, getEdge(), getPoint(), Inverse(), Geom::L2(), MakeBackData(), MakeSweepDestData(), MakeSweepSrcData(), maxAr, maxPt, numberOfEdges(), numberOfPoints(), pData, Reset(), shape_input_err, shape_nothing_to_do, shape_polygon, SortEdges(), Shape::dg_arete::st, swdData, swrData, swsData, type, and Shape::dg_point::x.

Referenced by Inkscape::UI::Tools::do_trace(), SPOffset::set_shape(), and sp_selected_path_do_offset().

◆ MakePointData()

void Shape::MakePointData ( bool nVal )

private

Initialize the point data cache.

Allocates space for point cache or clears the cache.

Parameters

nVal	If set to true, it sets some flags and then resizes pData to maxPt. Does nothing if false.
nVal	Allocate a cache (true) or clear it (false)

Definition at line 71 of file Shape.cpp.

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

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

◆ MakeRasterData()

void Shape::MakeRasterData ( bool nVal )

private

Definition at line 108 of file Shape.cpp.

References _has_raster_data, maxAr, and swrData.

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

◆ MakeSweepDestData()

void Shape::MakeSweepDestData ( bool nVal )

private

Initialize the sweep destination data cache.

Parameters

nVal	If set to true, it sets some flags and then resizes swdData to maxAr. If set to false, it clears all swdData.

Definition at line 149 of file Shape.cpp.

References _has_sweep_dest_data, maxAr, and swdData.

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

◆ MakeSweepSrcData()

void Shape::MakeSweepSrcData ( bool nVal )

private

Initialize the sweep source data cache.

Parameters

nVal	If set to true, it sets some flags and then resizes swsData to maxAr. If set to false, it clears all swsData.

Definition at line 129 of file Shape.cpp.

References _has_sweep_src_data, maxAr, and swsData.

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

◆ MakeTweak()

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::Affine *	i2doc
	)

◆ needEdgesSorting()

void Shape::needEdgesSorting ( )

inline

Do the edges need sorting?

Returns: True if we do, false otherwise.

Definition at line 519 of file Shape.h.

References _need_edges_sorting.

◆ needPointsSorting()

void Shape::needPointsSorting ( )

inline

Do the points need sorting?

Returns: True if we do, false otherwise.

Definition at line 512 of file Shape.h.

References _need_points_sorting.

◆ NextAt()

int Shape::NextAt	(	int	p,
		int	b
	)		const

inline

Definition at line 190 of file Shape.h.

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

Referenced by _countUpDown(), Inkscape::ObjectSet::_pathBoolOp(), AddEdge(), AssembleAretes(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Scan(), Scan(), SortEdges(), sp_offset_distance_to_original(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect(), and SwapPoints().

◆ numberOfEdges()

int Shape::numberOfEdges ( ) const

inline

Returns number of edges.

Returns: Number of edges.

Definition at line 498 of file Shape.h.

References _aretes.

Referenced by _countUpDown(), Inkscape::ObjectSet::_pathBoolOp(), AddEdge(), AddEdge(), AssembleAretes(), AssemblePoints(), BeginRaster(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), distance(), distanceLessThanOrEqual(), GetWindings(), initialiseEdgeData(), MakeOffset(), MakeTweak(), Plot(), PtWinding(), Reoriente(), Scan(), Scan(), SortEdges(), sp_offset_distance_to_original(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect(), SubEdge(), SubPoint(), SwapEdges(), Validate(), Winding(), and Winding().

◆ numberOfPoints()

int Shape::numberOfPoints ( ) const

inline

Returns number of points.

Returns: Number of points.

Definition at line 484 of file Shape.h.

References _pts.

Referenced by Inkscape::ObjectSet::_pathBoolOp(), AddPoint(), AssembleAretes(), AssemblePoints(), Avance(), BeginRaster(), Booleen(), CalcBBox(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), directedEulerian(), distance(), distanceLessThanOrEqual(), Path::Fill(), GetWindings(), initialisePointData(), MakeOffset(), MakeTweak(), Plot(), Reoriente(), Scan(), Scan(), SortEdges(), SortPoints(), SortPointsRounded(), sp_offset_distance_to_original(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect(), SubPoint(), SwapPoints(), and Validate().

◆ Other()

int Shape::Other	(	int	p,
		int	b
	)		const

inline

Definition at line 181 of file Shape.h.

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

Referenced by AssembleAretes(), and Scan().

◆ Plot()

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 26 of file ShapeDraw.cpp.

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

◆ PrevAt()

int Shape::PrevAt	(	int	p,
		int	b
	)		const

inline

Definition at line 203 of file Shape.h.

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

◆ PtWinding()

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

Definition at line 2001 of file Shape.cpp.

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

Referenced by Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect().

◆ PushIncidence()

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

private

Definition at line 2125 of file ShapeSweep.cpp.

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

Referenced by CreateIncidence(), and TesteAdjacency().

◆ ReFormeArcTo()

int Shape::ReFormeArcTo	(	int	bord,
		Path *	dest,
		Path *	orig,
		bool	never_split
	)

private

Definition at line 1016 of file ShapeMisc.cpp.

References PathDescrArcTo::angle, Path::ArcTo(), PathDescrArcTo::clockwise, delta, Path::descr_cmd, ebData, getEdge(), getPoint(), PathDescrArcTo::large, PathDescrArcTo::p, Path::PrevPoint(), PathDescrArcTo::rx, PathDescrArcTo::ry, swdData, and Shape::dg_point::x.

Referenced by AddContour().

◆ ReFormeCubicTo()

int Shape::ReFormeCubicTo	(	int	bord,
		Path *	dest,
		Path *	orig,
		bool	never_split
	)

private

Definition at line 1076 of file ShapeMisc.cpp.

References Path::CubicTo(), Path::descr_cmd, ebData, PathDescrCubicTo::end, getEdge(), getPoint(), PathDescrCubicTo::p, Path::PrevPoint(), PathDescrCubicTo::start, swdData, and Shape::dg_point::x.

Referenced by AddContour().

◆ ReFormeLineTo()

int Shape::ReFormeLineTo	(	int	bord,
		Path *	dest,
		bool	never_split
	)

private

Definition at line 984 of file ShapeMisc.cpp.

References ebData, getEdge(), getPoint(), Path::LineTo(), swdData, and Shape::dg_point::x.

Referenced by AddContour().

◆ Reoriente()

int Shape::Reoriente ( Shape * a )

◆ Reset()

void Shape::Reset	(	int	n = `0`,
		int	m = `0`
	)

Clear all data.

Clear points and edges and prepare internal data using new size.

Set shape type to shape_polygon. Clear all points and edges. Make room for enough points and edges.

Parameters

n	Number of points to make space for.
m	Number of edges to make space for.

Definition at line 235 of file Shape.cpp.

References _aretes, _bbox_up_to_date, _has_back_data, _has_edges_data, _has_points_data, _has_sweep_dest_data, _has_sweep_src_data, _need_edges_sorting, _need_points_sorting, _point_data_initialised, _pts, ebData, eData, maxAr, maxPt, pData, shape_polygon, swdData, swsData, and type.

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

◆ ResetSweep()

void Shape::ResetSweep ( )

private

Prepare point data cache, edge data cache and sweep source cache.

Definition at line 50 of file ShapeSweep.cpp.

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

Referenced by Booleen(), and ConvertToShape().

◆ Round()

static double Shape::Round ( double x )

inlinestatic

Definition at line 350 of file Shape.h.

Referenced by AddPoint(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), and initialisePointData().

◆ Scan() [1/2]

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

Definition at line 82 of file ShapeRaster.cpp.

References _countUpDown(), SweepTreeList::add(), AvanceEdge(), SweepTree::bord, CreateEdge(), AVLTree::elem, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, AVLTree::Leftmost(), NextAt(), node, numberOfEdges(), numberOfPoints(), Other(), SweepTreeList::racine, RIGHT, sEvts, Shape::dg_arete::st, sTree, swrData, and Shape::dg_point::x.

◆ Scan() [2/2]

void Shape::Scan	(	float &	pos,
		int &	curP,
		float	to,
		FloatLigne *	line,
		bool	exact,
		float	step
	)

◆ SortEdges()

void Shape::SortEdges ( )

Sort all edges (clockwise) around each point.

The function operates on each point and ensures that the linked list of the edges connected to a point is in the clockwise direction spatially. The clockwise angle that an edge line segment makes with the -y axis should increase (or remain same) as we move forward in the linked list of edges.

This sorting is done using edge vectors however note that if an edge ends at a point instead of starting from there, we invert the edge to make the edge vector look like it started from there.

Definition at line 1393 of file Shape.cpp.

References _aretes, _need_edges_sorting, _pts, Shape::dg_arete::dx, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, NextAt(), Shape::edge_list::no, numberOfEdges(), numberOfPoints(), SortEdgesList(), Shape::edge_list::starting, Shape::dg_point::totalDegree(), and Shape::edge_list::x.

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

◆ SortEdgesList()

void Shape::SortEdgesList	(	edge_list *	edges,
		int	s,
		int	e
	)

private

Sort edges given in a list.

Swapping is done in place so the original list will be modified to a sorted one.

Edges between (inclusive) edges[s] and edges[e] are all sorted.

Parameters

edges	The list of edges to sort.
s	The index of the beginning of the list to sort.
s	The index of the end of the list to sort.

Definition at line 1639 of file Shape.cpp.

References CmpToVert(), SortEdgesList(), Shape::edge_list::starting, test(), and Shape::edge_list::x.

Referenced by SortEdges(), and SortEdgesList().

◆ SortPoints() [1/2]

void Shape::SortPoints ( )

Sort the points (all points) only if needed.

(checked by flag)

See the index version of SortPoints since this is exactly the same.

Definition at line 467 of file Shape.cpp.

References _need_points_sorting, hasPoints(), numberOfPoints(), and SortPoints().

Referenced by BeginRaster(), SortPoints(), SortPoints(), and sp_offset_top_point().

◆ SortPoints() [2/2]

void Shape::SortPoints	(	int	s,
		int	e
	)

private

Sort the points.

Nothing fancy here. Please note, sorting really means just making sure the points exist in the array in a sorted manner. All we do here is just change the point's position in the array according to their location in physical space and make sure all edges still point to the original point they were pointing to. (:-D)

Sorting condition: Given two points LEFT and RIGHT (where LEFT's index < RIGHT's index) we swap only if LEFT.y > RIGHT.y || (LEFT.y == RIGHT.y && LEFT.x > RIGHT.x)

After sorting, not only are the points sorted in _pts, but also in pData. So both arrays will have same index for the same point.

Sorting algorithm looks like quick sort.

Parameters

s	The start index.
e	The end index.

Definition at line 482 of file Shape.cpp.

References getPoint(), SortPoints(), SwapPoints(), test(), and Shape::dg_point::x.

◆ SortPointsByOldInd()

void Shape::SortPointsByOldInd	(	int	s,
		int	e
	)

private

Sort the points (take oldInd into account)

Same as SortPoints except the sorting condition.

Sorting condition: Given two points LEFT and RIGHT (where LEFT's index < RIGHT's index) we swap only if LEFT.y > RIGHT.y || (LEFT.y == RIGHT.y && LEFT.x > RIGHT.x) || (LEFT.y == RIGHT.y && LEFT.x == RIGHT.x && LEFT.oldInd > RIGHT.oldInd)

After sorting, not only are the points sorted in _pts, but also in pData. So both arrays will have same index for the same point.

Parameters

s	The start index.
e	The end index.

Definition at line 663 of file Shape.cpp.

References getPoint(), pData, SortPointsByOldInd(), SwapPoints(), test(), and Shape::dg_point::x.

Referenced by AssemblePoints(), and SortPointsByOldInd().

◆ SortPointsRounded() [1/2]

void Shape::SortPointsRounded ( )

private

Sort all points by their rounded coordinates.

Definition at line 475 of file Shape.cpp.

References hasPoints(), numberOfPoints(), and SortPointsRounded().

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

◆ SortPointsRounded() [2/2]

void Shape::SortPointsRounded	(	int	s,
		int	e
	)

private

Sort points by their rounded coordinates.

Exactly the same as SortPoints but instead of using the actual point coordinates rounded coordinates are used.

Parameters

s	The start index.
e	The end index.

Definition at line 868 of file Shape.cpp.

References pData, SortPointsRounded(), SwapPoints(), and test().

◆ SubEdge()

void Shape::SubEdge ( int e )

Definition at line 1177 of file Shape.cpp.

References _aretes, _need_edges_sorting, DisconnectEnd(), DisconnectStart(), numberOfEdges(), shape_graph, SwapEdges(), and type.

Referenced by Inkscape::ObjectSet::_pathBoolOp(), Booleen(), ConvertToShape(), Reoriente(), sp_pathvector_boolop(), and Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect().

◆ SubPoint()

void Shape::SubPoint ( int p )

Definition at line 298 of file Shape.cpp.

References _aretes, _need_points_sorting, _pts, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, Shape::dg_arete::nextE, Shape::dg_arete::nextS, numberOfEdges(), numberOfPoints(), and SwapPoints().

◆ SwapEdges() [1/2]

void Shape::SwapEdges	(	int	a,
		int	b
	)

Definition at line 1191 of file Shape.cpp.

References _aretes, _has_back_data, _has_edges_data, _has_raster_data, _has_sweep_dest_data, _has_sweep_src_data, _pts, ebData, eData, Shape::dg_arete::en, FIRST, getEdge(), getPoint(), LAST, Shape::dg_arete::nextE, Shape::dg_arete::nextS, numberOfEdges(), Shape::dg_arete::prevE, Shape::dg_arete::prevS, Shape::dg_arete::st, swdData, swrData, and swsData.

Referenced by AssembleAretes(), Booleen(), SubEdge(), and SwapEdges().

◆ SwapEdges() [2/2]

void Shape::SwapEdges	(	int	a,
		int	b,
		int	c
	)

Definition at line 1384 of file Shape.cpp.

References c, and SwapEdges().

◆ SwapPoints() [1/2]

void Shape::SwapPoints	(	int	a,
		int	b
	)

Definition at line 333 of file Shape.cpp.

References _aretes, _has_points_data, _pts, FIRST, getEdge(), getPoint(), Shape::dg_point::incidentEdge, LAST, NextAt(), numberOfPoints(), and pData.

Referenced by SortPoints(), SortPointsByOldInd(), SortPointsRounded(), SubPoint(), and SwapPoints().

◆ SwapPoints() [2/2]

void Shape::SwapPoints	(	int	a,
		int	b,
		int	c
	)

Definition at line 458 of file Shape.cpp.

References c, and SwapPoints().

◆ TesteAdjacency()

bool Shape::TesteAdjacency	(	Shape *	iL,
		int	ilb,
		const Geom::Point	atx,
		int	nPt,
		bool	push
	)

private

Definition at line 2871 of file ShapeSweep.cpp.

References dot(), eData, Shape::dg_arete::en, getEdge(), HalfRound(), IHalfRound(), pData, PushIncidence(), Shape::dg_arete::st, and swsData.

Referenced by CheckAdjacencies().

◆ TesteIntersection() [1/3]

bool Shape::TesteIntersection	(	Shape *	iL,
		Shape *	iR,
		int	ilb,
		int	irb,
		Geom::Point &	atx,
		double &	atL,
		double &	atR,
		bool	onlyDiff
	)

private

Definition at line 2733 of file ShapeSweep.cpp.

References Geom::Affine::det(), det(), eData, Shape::dg_arete::en, getEdge(), pData, and Shape::dg_arete::st.

◆ TesteIntersection() [2/3]

bool Shape::TesteIntersection	(	SweepTree *	iL,
		SweepTree *	iR,
		Geom::Point &	atx,
		double &	atL,
		double &	atR,
		bool	onlyDiff
	)

private

Test intersection between the two edges.

This is the function that does the actual checking.

An important point to remember is that left and right aren't just two names for the edges, that's how the edges should be in the sweepline at the moment, otherwise, the intersection won't be detected.

This is a very special point as it prevents detecting an intersection that has already passed. See when an intersection has already passed, the order of nodes in the sweepline have switched, thus the function won't detect the intersection.

This picture is related to the intersection point calculation formulas:

\[ |\vec{slDot}| = |\vec{left}||\vec{sl}|\sin\theta_{sl}\]

\[ |\vec{elDot}| = |\vec{left}||\vec{el}|\sin\theta_{el}\]

These cross products (weirdly named) do have a direction too but you need to figure that out with your fingers. These here only give us the magnitude, however the actual variables in code also have a positive or negative sign depending on the direction. Index finger of right hand to the first vector, middle finger to the second vector and if thumb points out of page, cross product is negative, if it points in the page, cross product is positive. From figure 2 you can already guess that \( slDot < 0\) and \( elDot > 0 \). So let's rewrite the formula in the code while taking into account these signs.

\[ \vec{atx} = \frac{-|\vec{slDot}|*\vec{rEn} -|\vec{elDot}|*\vec{rSt}}{-|\vec{slDot}|-|\vec{elDot}|}\]

You can cancel out all the minus signs:

\[ \vec{atx} = \frac{|\vec{slDot}|*\vec{rEn} + |\vec{elDot}|*\vec{rSt}}{|\vec{slDot}|+|\vec{elDot}|}\]

\[ \vec{atx} = \frac{|\vec{left}||\vec{sl}||\sin\theta_{sl}|*\vec{rEn} + |\vec{left}||\vec{el}||\sin\theta_{el}|*\vec{rSt}}{|\vec{left}||\vec{sl}||\sin\theta_{sl}| + |\vec{left}||\vec{el}||\sin\theta_{el}|} \]

We can cancel the left and we are left with (no word twisting intended):

\[ \vec{atx} = \frac{|\vec{sl}||\sin\theta_{sl}|*\vec{rEn} + |\vec{el}||\sin\theta_{el}|*\vec{rSt}}{||\vec{sl}||\sin\theta_{sl}| + |\vec{el}||\sin\theta_{el}|} \]

\[ \vec{atx} = \frac{|\vec{sl}||\sin\theta_{sl}|}{|\vec{sl}||\sin\theta_{sl}|+|\vec{el}||\sin\theta_{el}|}*\vec{rEn} + \frac{|\vec{el}||\sin\theta_{el}|}{|\vec{sl}||\sin\theta_{sl}|+|\vec{el}||\sin\theta_{el}|}*\vec{rSt} \]

What you see here is a simple variant of the midpoint formula that can give us the intersection point. The sin terms when combined with sl or el are simply the perpendiculars you see in figure 2 and 3. See how the perpendiculars' relative length change as the intersection point changes on the right edge? This is exactly the mechanism used to find out the intersection point and its time on each edge. Look at figure 3, the point I'm trying to make is that the red perpendicular's length divided by sum of length of both red and blue perpendiculars is the same factor as the (length of the part of the right edge that's to the "right" of intersection) divided by total length of right edge. These ratios are exactly what we use to find the intersection point as well as the time of these intersection points.

Parameters

iL	Pointer to the left edge's node.
iR	Pointer to the right edge's node.
atx	The point of intersection. The function sets this if an intersection was detected.
atL	The time on the left edge at the intersection point.
atR	The time on the right edge at the intersection point.
onlyDiff	My best guess about onlyDiff is it stands for "only different". Only detect intersections if both edges come from different shapes, otherwise don't bother.

Returns: true if intersection detected, otherwise false.

Definition at line 1763 of file ShapeSweep.cpp.

References ang(), SweepTree::bord, eData, Shape::dg_arete::en, getEdge(), pData, SweepTree::src, and Shape::dg_arete::st.

◆ TesteIntersection() [3/3]

void Shape::TesteIntersection	(	SweepTree *	t,
		Side	s,
		bool	onlyDiff
	)

private

Test if there is an intersection of an edge on a particular side.

The actual intersection checking is performed by the other TesteIntersection and this function calls it, creating an intersection event if an intersection is detected.

Parameters

t	The pointer to the node of the edge whose intersection we wanna test.
s	The side that we want to test for intersection. If RIGHT, the edge on the right is tested with this one. If LEFT, the edge on the left is tested with this one.
onlyDiff	My best guess about onlyDiff is it stands for "only different". Only detect intersections if both edges come from different shapes, otherwise don't bother.

Definition at line 1739 of file ShapeSweep.cpp.

References SweepEventQueue::add(), AVLTree::elem, LEFT, sEvts, and TesteIntersection().

Referenced by Booleen(), ConvertToShape(), TesteIntersection(), and Validate().

◆ Transform()

void Shape::Transform ( Geom::Affine const & tr )

inline

Definition at line 419 of file Shape.h.

References _pts.

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

◆ Validate()

void Shape::Validate ( )

private

Definition at line 3281 of file ShapeSweep.cpp.

References Shape::dg_arete::dx, eData, getEdge(), getPoint(), numberOfEdges(), numberOfPoints(), pData, TesteIntersection(), and Shape::dg_point::x.

◆ Winding() [1/2]

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

Compute the winding number of the point given.

(brutually)

The function works by bringing in a ray from (px.x, -infinity) to (px.x, px.y) and seeing how many edges it cuts and the direction of those edges. It uses this information to compute the winding number.

The way this function works is that it iterates through all the edges and for each edge it checks if the ray will intersect the edge and in which orientation. See the function body to see exactly how this works.

The algorithm is quite simple. For edges that simply cut the ray, we check the direction of the edge and accordingly add/subtract from a variable to keep track of the winding. However, a different case comes up when an edge has an endpoint that cuts the ray. You can just see the direction and maybe change the same variable, but then the problem is, another edge connected to the same point will also do the same and you'd have two additions when you should only have one. Hence, the solution is, we create two variables ll and rr and add/subtract to them, then, we sum them and divide by 2 to get the contribution to the winding number.

Parameters

px	The point whose winding number to compute

Returns: The winding number of the point px.

Definition at line 2180 of file ShapeSweep.cpp.

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

Referenced by GetWindings().

◆ Winding() [2/2]

int Shape::Winding ( int nPt ) const

private

Get the winding number for a point but from the data left by the sweepline algorithm.

Parameters

nPt	Index of the point whose finding number we wanna calculate.

Definition at line 2156 of file ShapeSweep.cpp.

References getEdge(), numberOfEdges(), pData, and swdData.

Friends And Related Symbol Documentation

◆ SweepEvent

friend class SweepEvent

friend

Definition at line 553 of file Shape.h.

◆ SweepEventQueue

friend class SweepEventQueue

friend

Definition at line 554 of file Shape.h.

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

◆ SweepTree

friend class SweepTree

friend

Definition at line 552 of file Shape.h.

Member Data Documentation

◆ _aretes

std::vector<dg_arete> Shape::_aretes

private

The array of edges

Definition at line 1077 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Affiche(), AssembleAretes(), Booleen(), ConnectEnd(), ConnectStart(), Copy(), DisconnectEnd(), DisconnectStart(), getEdge(), hasEdges(), Inverse(), MakeOffset(), MakeTweak(), numberOfEdges(), Reoriente(), Reset(), SortEdges(), SubEdge(), SubPoint(), SwapEdges(), and SwapPoints().

◆ _bbox_up_to_date

bool Shape::_bbox_up_to_date

private

the leftX/rightX/topY/bottomY are up to date

Definition at line 1074 of file Shape.h.

Referenced by CalcBBox(), Copy(), MakeOffset(), MakePointData(), MakeTweak(), Reoriente(), and Reset().

◆ _has_back_data

bool Shape::_has_back_data

private

Definition at line 1073 of file Shape.h.

Referenced by AddContour(), AddEdge(), AddEdge(), AssembleAretes(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), Copy(), DoEdgeTo(), hasBackData(), Inverse(), MakeBackData(), MakeOffset(), MakeTweak(), Reset(), and SwapEdges().

◆ _has_edges_data

bool Shape::_has_edges_data

private

the eData array is allocated

Definition at line 1069 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Copy(), Inverse(), MakeEdgeData(), MakeOffset(), MakeTweak(), Reoriente(), Reset(), and SwapEdges().

◆ _has_points_data

bool Shape::_has_points_data

private

the pData array is allocated

Definition at line 1067 of file Shape.h.

Referenced by AddPoint(), Copy(), MakeOffset(), MakePointData(), MakeTweak(), Reoriente(), Reset(), and SwapPoints().

◆ _has_raster_data

bool Shape::_has_raster_data

private

the swrData array is allocated

Definition at line 1072 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Copy(), MakeOffset(), MakeRasterData(), MakeTweak(), Reoriente(), and SwapEdges().

◆ _has_sweep_dest_data

bool Shape::_has_sweep_dest_data

private

the swdData array is allocated

Definition at line 1071 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Copy(), Inverse(), MakeOffset(), MakeSweepDestData(), MakeTweak(), Reoriente(), Reset(), and SwapEdges().

◆ _has_sweep_src_data

bool Shape::_has_sweep_src_data

private

the swsData array is allocated

Definition at line 1070 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Copy(), MakeOffset(), MakeSweepSrcData(), MakeTweak(), Reoriente(), Reset(), and SwapEdges().

◆ _need_edges_sorting

bool Shape::_need_edges_sorting

private

edges have been added: maybe they are not ordered clockwise

nota: if you remove an edge, the clockwise order still holds

Definition at line 1065 of file Shape.h.

Referenced by AddEdge(), AddEdge(), Booleen(), ConvertToShape(), Copy(), needEdgesSorting(), Reoriente(), Reset(), SortEdges(), and SubEdge().

◆ _need_points_sorting

bool Shape::_need_points_sorting

private

points have been added or removed: we need to sort the points again

Definition at line 1064 of file Shape.h.

Referenced by AddPoint(), Copy(), needPointsSorting(), Reset(), SortPoints(), and SubPoint().

◆ _point_data_initialised

bool Shape::_point_data_initialised

private

the pData array is up to date

Definition at line 1068 of file Shape.h.

Referenced by Copy(), initialisePointData(), MakeOffset(), MakePointData(), MakeTweak(), Reoriente(), and Reset().

◆ _pts

std::vector<dg_point> Shape::_pts

private

The array of points

Definition at line 1076 of file Shape.h.

Referenced by AddPoint(), Affiche(), AssemblePoints(), AssemblePoints(), Booleen(), ConnectEnd(), ConnectStart(), ConvertToShape(), Copy(), DisconnectEnd(), DisconnectStart(), getPoint(), hasPoints(), Inverse(), MakeOffset(), MakeTweak(), numberOfPoints(), Reoriente(), Reset(), SortEdges(), SubPoint(), SwapEdges(), SwapPoints(), and Transform().

◆ bottomY

double Shape::bottomY

Definition at line 434 of file Shape.h.

Referenced by CalcBBox(), SPOffset::set_shape(), and Shape().

◆ chgts

std::vector<sTreeChange> Shape::chgts

An array to store all the changes that happen to a sweepline within a y value

Definition at line 424 of file Shape.h.

Referenced by AddChgt(), Booleen(), CheckAdjacencies(), CheckEdges(), and ConvertToShape().

◆ ebData

std::vector<back_data> Shape::ebData

Stores the back data for each edge.

Definition at line 422 of file Shape.h.

Referenced by Inkscape::ObjectSet::_pathBoolOp(), AddContour(), AddEdge(), AddEdge(), AssembleAretes(), Booleen(), DoEdgeTo(), Path::Fill(), Inverse(), MakeBackData(), MakeOffset(), MakeTweak(), ReFormeArcTo(), ReFormeCubicTo(), ReFormeLineTo(), Reset(), sp_pathvector_boolop(), Inkscape::LivePathEffect::sp_pathvector_boolop_slice_intersect(), and SwapEdges().

◆ eData

std::vector<edge_data> Shape::eData

private

Extra edge data

Definition at line 1081 of file Shape.h.

Referenced by AddEdge(), AddEdge(), AssembleAretes(), Avance(), BeginRaster(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), CreateIncidence(), DoEdgeTo(), SweepTree::Find(), SweepTree::Find(), GetWindings(), initialiseEdgeData(), Inverse(), MakeEdgeData(), MakeOffset(), MakeTweak(), Reoriente(), Reset(), SwapEdges(), TesteAdjacency(), TesteIntersection(), TesteIntersection(), Validate(), and Winding().

◆ iData

incidenceData* Shape::iData

Definition at line 428 of file Shape.h.

Referenced by AssemblePoints(), clearIncidenceData(), and PushIncidence().

◆ leftX

double Shape::leftX

Definition at line 434 of file Shape.h.

Referenced by CalcBBox(), SPOffset::set_shape(), and Shape().

◆ maxAr

int Shape::maxAr

Definition at line 474 of file Shape.h.

Referenced by AddEdge(), AddEdge(), MakeBackData(), MakeEdgeData(), MakeOffset(), MakeRasterData(), MakeSweepDestData(), MakeSweepSrcData(), MakeTweak(), Reoriente(), Reset(), Shape(), and ~Shape().

◆ maxInc

int Shape::maxInc

Definition at line 426 of file Shape.h.

Referenced by clearIncidenceData(), and PushIncidence().

◆ maxPt

int Shape::maxPt

Definition at line 473 of file Shape.h.

Referenced by AddPoint(), MakeOffset(), MakePointData(), MakeTweak(), Reoriente(), Reset(), Shape(), and ~Shape().

◆ nbInc

int Shape::nbInc

Definition at line 425 of file Shape.h.

Referenced by AssemblePoints(), clearIncidenceData(), and PushIncidence().

◆ pData

std::vector<point_data> Shape::pData

private

Extra point data

Definition at line 1085 of file Shape.h.

Referenced by SweepEventQueue::add(), AddPoint(), AssembleAretes(), AssemblePoints(), AssemblePoints(), BeginRaster(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), CreateIncidence(), DoEdgeTo(), SweepTree::Find(), SweepTree::Find(), GetWindings(), initialiseEdgeData(), initialisePointData(), SweepTree::InsertAt(), SweepEvent::MakeDelete(), MakeOffset(), MakePointData(), MakeTweak(), Reoriente(), Reset(), SortPointsByOldInd(), SortPointsRounded(), SwapPoints(), TesteAdjacency(), TesteIntersection(), TesteIntersection(), Validate(), Winding(), and Winding().

◆ rightX

double Shape::rightX

Definition at line 434 of file Shape.h.

Referenced by CalcBBox(), SPOffset::set_shape(), and Shape().

◆ sEvts

SweepEventQueue* Shape::sEvts

Intersection events that we have detected that are to come. Sorted so closest one gets popped.

Definition at line 431 of file Shape.h.

Referenced by BeginRaster(), Booleen(), ConvertToShape(), Copy(), EndRaster(), Scan(), Scan(), and TesteIntersection().

◆ sTree

SweepTreeList* Shape::sTree

Pointer to store the sweepline tree. To our use at least, it's a linear list of the edges that intersect with sweepline.

Definition at line 430 of file Shape.h.

Referenced by BeginRaster(), Booleen(), ConvertToShape(), Copy(), EndRaster(), Scan(), and Scan().

◆ swdData

std::vector<sweep_dest_data> Shape::swdData

private

Definition at line 1083 of file Shape.h.

Referenced by AddContour(), AddEdge(), AddEdge(), Booleen(), ConvertToForme(), ConvertToForme(), ConvertToFormeNested(), ConvertToShape(), GetWindings(), Inverse(), MakeOffset(), MakeSweepDestData(), MakeTweak(), ReFormeArcTo(), ReFormeCubicTo(), ReFormeLineTo(), Reoriente(), Reset(), SwapEdges(), and Winding().

◆ swrData

std::vector<raster_data> Shape::swrData

private

Definition at line 1084 of file Shape.h.

Referenced by _updateIntersection(), AddEdge(), AddEdge(), AvanceEdge(), AvanceEdge(), BeginRaster(), CreateEdge(), DestroyEdge(), MakeOffset(), MakeRasterData(), MakeTweak(), SweepTree::Relocate(), Reoriente(), Scan(), Scan(), and SwapEdges().

◆ swsData

std::vector<sweep_src_data> Shape::swsData

private

Definition at line 1082 of file Shape.h.

Referenced by AddChgt(), AddEdge(), AddEdge(), AssembleAretes(), AssemblePoints(), Avance(), Booleen(), CheckAdjacencies(), CheckEdges(), ConvertToShape(), DoEdgeTo(), initialiseEdgeData(), MakeOffset(), MakeSweepSrcData(), MakeTweak(), PushIncidence(), SweepTree::Relocate(), Reoriente(), Reset(), SwapEdges(), SweepTree::SwapWithRight(), and TesteAdjacency().

◆ topY

double Shape::topY

Definition at line 434 of file Shape.h.

Referenced by CalcBBox(), SPOffset::set_shape(), and Shape().

◆ type

int Shape::type

Definition at line 477 of file Shape.h.

Referenced by AddChgt(), AddEdge(), AddEdge(), Booleen(), ConvertToShape(), Copy(), ForceToPolygon(), MakeOffset(), MakeTweak(), Reoriente(), Reset(), Shape(), and SubEdge().

The documentation for this class was generated from the following files:

/builds/inkscape/inkscape/src/livarot/Shape.h
/builds/inkscape/inkscape/src/livarot/Shape.cpp
/builds/inkscape/inkscape/src/livarot/ShapeDraw.cpp
/builds/inkscape/inkscape/src/livarot/ShapeMisc.cpp
/builds/inkscape/inkscape/src/livarot/ShapeRaster.cpp
/builds/inkscape/inkscape/src/livarot/ShapeSweep.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Member Enumeration Documentation

◆ sTreeChangeType

Constructor & Destructor Documentation

◆ Shape()

◆ ~Shape()

Member Function Documentation

◆ _countUpDown()

◆ _countUpDownTotalDegree2()

◆ _updateIntersection()

◆ AddChgt()

◆ AddContour()

◆ AddEdge() [1/2]

◆ AddEdge() [2/2]

◆ AddPoint()

◆ Affiche()

◆ AssembleAretes()

◆ AssemblePoints() [1/2]

◆ AssemblePoints() [2/2]

◆ Avance()

◆ AvanceEdge() [1/2]

◆ AvanceEdge() [2/2]

◆ BeginRaster()

◆ Booleen()

◆ CalcBBox()

◆ CheckAdjacencies()

◆ CheckEdges()

◆ CleanupSweep()

◆ clearIncidenceData()

◆ CmpToVert()

◆ ConnectEnd()

◆ ConnectStart()

◆ ConvertToForme() [1/2]

◆ ConvertToForme() [2/2]

◆ ConvertToFormeNested()

◆ ConvertToShape()

◆ Copy()

◆ CreateEdge()

◆ CreateIncidence()

◆ CycleNextAt()

◆ CyclePrevAt()

◆ DestroyEdge()

◆ DisconnectEnd()

◆ DisconnectStart()

◆ DoEdgeTo()

◆ EndRaster()

◆ ForceToPolygon()

◆ getEdge()

◆ getPoint()

◆ GetWindings()

◆ HalfRound()

◆ hasBackData()

◆ hasEdges()

◆ hasPoints()

◆ IHalfRound()

◆ initialiseEdgeData()

◆ initialisePointData()

◆ Inverse()

◆ MakeBackData()

◆ MakeEdgeData()

◆ MakeOffset()

◆ MakePointData()

◆ MakeRasterData()

◆ MakeSweepDestData()

◆ MakeSweepSrcData()

◆ MakeTweak()

◆ needEdgesSorting()

◆ needPointsSorting()

◆ NextAt()

◆ numberOfEdges()

◆ numberOfPoints()