Geom Namespace Reference

A convex cover is a sequence of convex polygons that completely cover the path. More...

Namespaces
namespace	detail
namespace	NL
namespace	PathInternal
Classes
union	dbl_64
class	BezierCurve
class	BezierCurve< 0 >
class	Bezier
struct	wrap
class	Circle
class	Circulator
struct	ResultTraits< double >
struct	ResultTraits< Point >
struct	FragmentConcept
struct	NearConcept
struct	OffsetableConcept
struct	ScalableConcept
struct	AddableConcept
struct	MultiplicableConcept
class	angle_cmp
class	ConvexHull
	ConvexHull A convexhull is a convex region - every point between two points in the convex hull is also in the convex hull. More...
struct	Crossing
struct	CrossingOrder
struct	Crosser
struct	CurveHelpers
class	Curve
class	D2
	The D2 class takes two instances of a scalar data type and treats them like a point. More...
class	Ellipse
class	EllipticalArc
class	Exception
class	LogicalError
class	RangeError
class	NotImplemented
class	InvariantsViolation
class	NotInvertible
class	InfiniteSolutions
class	ContinuityError
struct	SVGPathParseError
class	HLineSegment
class	VLineSegment
class	Interval
	This class represents a range of numbers that is never empty. More...
class	OptInterval
	OptInterval is an Interval that can be empty. More...
class	Line
class	Linear
class	Matrix
	The Matrix class. More...
class	Eigen
	Given a matrix (ignoring the translation) this returns the eigen values and vectors. More...
struct	SimpleCrosser
struct	MonoCrosser
class	Path
struct	PathVectorPosition
class	Piecewise
	Piecewise function class. More...
class	IPoint
class	Point
	Cartesian 2D point. More...
class	Poly
class	Quad
class	QuadTree
class	Ray
class	D2< Interval >
	Rect class. More...
class	OptRect
	The OptRect class can represent and empty Rect and non-empty Rects. More...
class	OldBezier
struct	rparams
class	Region
class	Linear2d
class	SBasis2d
class	SBasisCurve
class	SBasis
struct	ContainmentOrder
class	Shape
class	Bernsteins
	This function is called _a lot_. More...
class	sturm
class	SVGEllipticalArc
class	make_elliptical_arc
class	SVGPathSink
class	SVGPathGenerator
class	PathBuilder
struct	Event
struct	TransformConcept
class	Translate
class	Scale
class	Rotate
	Notionally an Geom::Matrix corresponding to rotation about the origin. More...
class	RectHull
Typedefs
typedef BezierCurve< 1 >	LineSegment
typedef BezierCurve< 2 >	QuadraticBezier
typedef BezierCurve< 3 >	CubicBezier
typedef Point	BezierCurve []
typedef double	Coord
	A "real" type with sufficient precision for coordinates.
typedef boost::optional< Crossing >	OptCrossing
typedef std::vector< Crossing >	Crossings
typedef std::vector< Crossings >	CrossingSet
typedef std::vector< Path >	PathVector
typedef D2< Interval >	Rect
	D2<Interval> specialization to Rect.
typedef SimpleCrosser	DefaultCrosser
typedef long	ICoord
typedef std::vector< Region >	Regions
typedef std::back_insert_iterator < std::vector< Path > >	iter
Enumerations
enum	IntersectorKind { intersects = 0, parallel, coincident, no_intersection }
enum	Dim2 { X = 0, Y = 1 }
enum	{ BOOLOP_JUST_A = 1, BOOLOP_JUST_B = 2, BOOLOP_BOTH = 4, BOOLOP_NEITHER = 8 }
enum	{   BOOLOP_NULL = 0, BOOLOP_INTERSECT = BOOLOP_BOTH, BOOLOP_SUBTRACT_A_B = BOOLOP_JUST_B, BOOLOP_IDENTITY_A = BOOLOP_JUST_A | BOOLOP_BOTH,   BOOLOP_SUBTRACT_B_A = BOOLOP_JUST_A, BOOLOP_IDENTITY_B = BOOLOP_JUST_B | BOOLOP_BOTH, BOOLOP_EXCLUSION = BOOLOP_JUST_A | BOOLOP_JUST_B, BOOLOP_UNION = BOOLOP_JUST_A | BOOLOP_JUST_B | BOOLOP_BOTH }
enum	NodeType { NODE_NONE, NODE_CUSP, NODE_SMOOTH, NODE_SYMM }
	What kind of node is this? This is the value for the node->type field. More...
Functions
double	deg_to_rad (double deg)
double	rad_to_deg (double rad)
double	map_circular_arc_on_unit_interval (double angle, double start_angle, double end_angle, bool cw=true)
Coord	map_unit_interval_on_circular_arc (Coord t, double start_angle, double end_angle, bool cw=true)
void	find_intersections (std::vector< std::pair< double, double > > &xs, D2< SBasis > const &A, D2< SBasis > const &B)
void	find_intersections (std::vector< std::pair< double, double > > &xs, std::vector< Point > const &A, std::vector< Point > const &B, double precision)
void	split (vector< Point > const &p, double t, vector< Point > &left, vector< Point > &right)
void	find_self_intersections (std::vector< std::pair< double, double > > &xs, D2< SBasis > const &A)
static double	EpsilonBy (double value, int eps)
static void	intersect_polish_root (D2< SBasis > const &A, double &s, D2< SBasis > const &B, double &t)
void	polish_intersections (std::vector< std::pair< double, double > > &xs, D2< SBasis > const &A, D2< SBasis > const &B)
double	hausdorfl (D2< SBasis > &A, D2< SBasis > const &B, double m_precision, double *a_t=0, double *b_t=0)
double	hausdorf (D2< SBasis > &A, D2< SBasis > const &B, double m_precision, double *a_t, double *b_t)
	Compute the symmetric Hausdorf distance.
void	find_intersections_bezier_clipping (std::vector< std::pair< double, double > > &xs, std::vector< Point > const &A, std::vector< Point > const &B, double precision=1e-5)
void	find_collinear_normal (std::vector< std::pair< double, double > > &xs, std::vector< Point > const &A, std::vector< Point > const &B, double precision=1e-5)
Point	middle_point (LineSegment const &_segment)
double	length (LineSegment const &_segment)
template<typename T >
D2< SBasis >	handles_to_sbasis (T const &handles, unsigned order)
static void	generate_bezier (Point bezier[], Point const data[], double const u[], unsigned const len, Point const &tHat1, Point const &tHat2, double const tolerance_sq)
	Fill in bezier[] based on the given data and tangent requirements, using a least-squares fit.
static void	estimate_lengths (Point bezier[], Point const data[], double const u[], unsigned len, Point const &tHat1, Point const &tHat2)
static void	estimate_bi (Point b[4], unsigned ei, Point const data[], double const u[], unsigned len)
static void	reparameterize (Point const d[], unsigned const len, double u[], BezierCurve const bezCurve)
	Given set of points and their parameterization, try to find a better assignment of parameter values for the points.
static double	NewtonRaphsonRootFind (BezierCurve const Q, Point const &P, double const u)
	Use Newton-Raphson iteration to find better root.
static Point	darray_center_tangent (Point const d[], unsigned const center, unsigned const len)
	Estimates the (backward) tangent at d[center], by averaging the two segments connected to d[center] (and then normalizing the result).
static Point	darray_right_tangent (Point const d[], unsigned const len)
	Estimates the (backward) tangent at d[last - 0.5].
static unsigned	copy_without_nans_or_adjacent_duplicates (Point const src[], unsigned src_len, Point dest[])
	Copy points from src to dest, filter out points containing NaN and adjacent points with equal x and y.
static void	chord_length_parameterize (Point const d[], double u[], unsigned const len)
	Assign parameter values to digitized points using relative distances between points.
static double	compute_max_error_ratio (Point const d[], double const u[], unsigned const len, BezierCurve const bezCurve, double const tolerance, unsigned *const splitPoint)
	Find the maximum squared distance of digitized points to fitted curve, and (if this maximum error is non-zero) set *splitPoint to the corresponding index.
static double	compute_hook (Point const &a, Point const &b, double const u, BezierCurve const bezCurve, double const tolerance)
	Whereas compute_max_error_ratio() checks for itself that each data point is near some point on the curve, this function checks that each point on the curve is near some data point (or near some point on the polyline defined by the data points, or something like that: we allow for a "reasonable curviness" from such a polyline).
int	bezier_fit_cubic (Point *bezier, Point const *data, int len, double error)
	Fit a single-segment Bezier curve to a set of digitized points.
int	bezier_fit_cubic_r (Point bezier[], Point const data[], int const len, double const error, unsigned const max_beziers)
	Fit a multi-segment Bezier curve to a set of digitized points, with possible weedout of identical points and NaNs.
int	bezier_fit_cubic_full (Point bezier[], int split_points[], Point const data[], int const len, Point const &tHat1, Point const &tHat2, double const error, unsigned const max_beziers)
	Fit a multi-segment Bezier curve to a set of digitized points, without possible weedout of identical points and NaNs.
static double	lensq (Point const p)
Point	bezier_pt (unsigned const degree, Point const V[], double const t)
	Evaluate a Bezier curve at parameter value t.
Point	darray_left_tangent (Point const d[], unsigned const len)
	Estimate the (forward) tangent at point d[first + 0.5].
Point	darray_left_tangent (Point const d[], unsigned const len, double const tolerance_sq)
	Estimate the (forward) tangent at point d[0].
Point	darray_right_tangent (Point const d[], unsigned const len, double const tolerance_sq)
	Estimates the (backward) tangent at d[last].
int	bezier_fit_cubic (Point bezier[], Point const data[], int len, double error)
template<typename iterator >
static void	cubic_bezier_poly_coeff (iterator b, Point *pc)
Coord	subdivideArr (Coord t, Coord const *v, Coord *left, Coord *right, unsigned order)
template<typename T >
T	bernsteinValueAt (double t, T const *c_, unsigned n)
void	bezier_to_sbasis (SBasis &sb, Bezier const &bz)
	Changes the basis of p to be sbasis.
Bezier	operator+ (const Bezier &a, double v)
Bezier	operator- (const Bezier &a, double v)
Bezier	operator* (const Bezier &a, double v)
Bezier	operator/ (const Bezier &a, double v)
Bezier	reverse (const Bezier &a)
Bezier	portion (const Bezier &a, double from, double to)
std::vector< Point >	bezier_points (const D2< Bezier > &a)
Bezier	derivative (const Bezier &a)
Bezier	integral (const Bezier &a)
OptInterval	bounds_fast (Bezier const &b)
OptInterval	bounds_exact (Bezier const &b)
OptInterval	bounds_local (Bezier const &b, OptInterval i)
std::ostream &	operator<< (std::ostream &out_file, const Bezier &b)
SBasis	cheb (unsigned n)
SBasis	cheb_series (unsigned n, double *cheb_coeff)
SBasis	clenshaw_series (unsigned m, double *cheb_coeff)
SBasis	chebyshev_approximant (double(*f)(double, void *), int order, Interval in, void *p)
double	f_interp (double x, void *p)
SBasis	chebyshev_approximant_interpolating (double(*f)(double, void *), int order, Interval in, void *p)
SBasis	chebyshev (unsigned n)
int	circle_circle_intersection (Point X0, double r0, Point X1, double r1, Point &p0, Point &p1)
template<typename T >
T	portion (const T &t, const Interval &i)
double	SignedTriangleArea (Point p0, Point p1, Point p2)
int	mod (int i, int l)
pair< map< int, int >, map < int, int > >	bridges (ConvexHull a, ConvexHull b)
std::vector< Point >	bridge_points (ConvexHull a, ConvexHull b)
unsigned	find_bottom_right (ConvexHull const &a)
ConvexHull	sweepline_intersection (ConvexHull const &a, ConvexHull const &b)
ConvexHull	intersection (ConvexHull, ConvexHull)
ConvexHull	merge (ConvexHull a, ConvexHull b)
ConvexHull	graham_merge (ConvexHull a, ConvexHull b)
bool	intersectp (ConvexHull a, ConvexHull b)
template<class T >
ConvexHull	operator* (ConvexHull const &p, T const &m)
ConvexHull	clip (ConvexHull const &ch, Point n, double d)
Coord	infinity ()
bool	are_near (Coord a, Coord b, double eps=EPSILON)
double	wrap_dist (double from, double to, double size, bool rev)
void	merge_crossings (Crossings &a, Crossings &b, unsigned i)
void	offset_crossings (Crossings &cr, double a, double b)
Crossings	reverse_ta (Crossings const &cr, std::vector< double > max)
Crossings	reverse_tb (Crossings const &cr, unsigned split, std::vector< double > max)
CrossingSet	reverse_ta (CrossingSet const &cr, unsigned split, std::vector< double > max)
CrossingSet	reverse_tb (CrossingSet const &cr, unsigned split, std::vector< double > max)
void	clean (Crossings &, Crossings &)
template<typename C >
std::vector< Rect >	bounds (C const &a)
void	sort_crossings (Crossings &cr, unsigned ix)
Coord	nearest_point (Point const &p, Curve const &c)
SBasis	L2 (D2< SBasis > const &a, unsigned k)
D2< SBasis >	multiply (Linear const &a, D2< SBasis > const &b)
D2< SBasis >	multiply (SBasis const &a, D2< SBasis > const &b)
D2< SBasis >	truncate (D2< SBasis > const &a, unsigned terms)
unsigned	sbasis_size (D2< SBasis > const &a)
double	tail_error (D2< SBasis > const &a, unsigned tail)
Piecewise< D2< SBasis > >	sectionize (D2< Piecewise< SBasis > > const &a)
D2< Piecewise< SBasis > >	make_cuts_independent (Piecewise< D2< SBasis > > const &a)
Piecewise< D2< SBasis > >	rot90 (Piecewise< D2< SBasis > > const &M)
Piecewise< SBasis >	cross (Piecewise< D2< SBasis > > const &a, Piecewise< D2< SBasis > > const &b)
Piecewise< D2< SBasis > >	operator* (Piecewise< D2< SBasis > > const &a, Matrix const &m)
Piecewise< D2< SBasis > >	force_continuity (Piecewise< D2< SBasis > > const &f, double tol, bool closed)
std::vector< Geom::Piecewise < Geom::D2< Geom::SBasis > > >	split_at_discontinuities (Geom::Piecewise< Geom::D2< Geom::SBasis > > const &pwsbin, double tol)
static void	set_first_point (Piecewise< D2< SBasis > > &f, Point a)
static void	set_last_point (Piecewise< D2< SBasis > > &f, Point a)
std::vector< Piecewise< D2 < SBasis > > >	fuse_nearby_ends (std::vector< Piecewise< D2< SBasis > > > const &f, double tol)
template<typename T >
D2< T >	reverse (const D2< T > &a)
template<typename T >
D2< T >	portion (const D2< T > &a, Coord f, Coord t)
template<typename T >
D2< T >	portion (const D2< T > &a, Interval i)
template<typename T >
bool	operator== (D2< T > const &a, D2< T > const &b)
template<typename T >
bool	operator!= (D2< T > const &a, D2< T > const &b)
template<typename T >
bool	are_near (D2< T > const &a, D2< T > const &b, double tol)
template<typename T >
D2< T >	operator+ (D2< T > const &a, D2< T > const &b)
template<typename T >
D2< T >	operator- (D2< T > const &a, D2< T > const &b)
template<typename T >
D2< T >	operator+= (D2< T > &a, D2< T > const &b)
template<typename T >
D2< T >	operator-= (D2< T > &a, D2< T > const &b)
template<typename T >
D2< T >	operator- (D2< T > const &a)
template<typename T >
D2< T >	operator* (D2< T > const &a, Point const &b)
template<typename T >
D2< T >	operator/ (D2< T > const &a, Point const &b)
template<typename T >
D2< T >	operator*= (D2< T > &a, Point const &b)
template<typename T >
D2< T >	operator/= (D2< T > &a, Point const &b)
template<typename T >
D2< T >	operator* (D2< T > const &a, double b)
template<typename T >
D2< T >	operator*= (D2< T > &a, double b)
template<typename T >
D2< T >	operator/ (D2< T > const &a, double b)
template<typename T >
D2< T >	operator/= (D2< T > &a, double b)
template<typename T >
D2< T >	operator* (D2< T > const &v, Matrix const &m)
template<typename T >
D2< T >	operator* (D2< T > const &a, T const &b)
template<typename T >
D2< T >	operator+ (D2< T > const &a, Point b)
template<typename T >
D2< T >	operator- (D2< T > const &a, Point b)
template<typename T >
D2< T >	operator+= (D2< T > &a, Point b)
template<typename T >
D2< T >	operator-= (D2< T > &a, Point b)
template<typename T >
T	dot (D2< T > const &a, D2< T > const &b)
template<typename T >
D2< T >	rot90 (D2< T > const &a)
template<typename T >
D2< T >	compose (D2< T > const &a, T const &b)
template<typename T >
D2< T >	compose_each (D2< T > const &a, D2< T > const &b)
template<typename T >
D2< T >	compose_each (T const &a, D2< T > const &b)
template<typename T >
D2< T >	derivative (D2< T > const &a)
template<typename T >
D2< T >	integral (D2< T > const &a)
template<typename T >
std::ostream &	operator<< (std::ostream &out_file, const Geom::D2< T > &in_d2)
	A function to print out the Point.
template<typename T >
OptRect	bounds_fast (const D2< T > &a)
template<typename T >
OptRect	bounds_exact (const D2< T > &a)
template<typename T >
OptRect	bounds_local (const D2< T > &a, const OptInterval &t)
IntersectorKind	line_intersection (Geom::Point const &n0, double const d0, Geom::Point const &n1, double const d1, Geom::Point &result)
	Finds the intersection of the two (infinite) lines defined by the points p such that dot(n0, p) == d0 and dot(n1, p) == d1.
int	intersector_ccw (const Geom::Point &p0, const Geom::Point &p1, const Geom::Point &p2)
bool	line_segment_intersectp (Geom::Point const &p00, Geom::Point const &p01, Geom::Point const &p10, Geom::Point const &p11)
	Determine whether the line segment from p00 to p01 intersects the infinite line passing through p10 and p11.
bool	segment_intersectp (Geom::Point const &p00, Geom::Point const &p01, Geom::Point const &p10, Geom::Point const &p11)
	Determine whether two line segments intersect.
IntersectorKind	line_segment_intersect (Geom::Point const &p00, Geom::Point const &p01, Geom::Point const &p10, Geom::Point const &p11, Geom::Point &result)
	Determine whether & where a line segments intersects an (infinite) line.
IntersectorKind	segment_intersect (Geom::Point const &p00, Geom::Point const &p01, Geom::Point const &p10, Geom::Point const &p11, Geom::Point &result)
	Determine whether & where two line segments intersect.
IntersectorKind	line_twopoint_intersect (Geom::Point const &p00, Geom::Point const &p01, Geom::Point const &p10, Geom::Point const &p11, Geom::Point &result)
	Determine whether & where two line segments intersect.
static bool	is_less (Point const &A, Point const &B)
static void	eliminate_duplicates_p (std::vector< Point > &pts)
std::vector< Geom::Point >	rect_line_intersect (Geom::Point const &c0, Geom::Point const &c1, Geom::Point const &p0, Geom::Point const &p1)
	Determine whether & where an (infinite) line intersects a rectangle.
boost::optional< LineSegment >	rect_line_intersect (Geom::Rect &r, Geom::LineSegment ls)
	Determine whether & where an (infinite) line intersects a rectangle.
boost::optional< LineSegment >	rect_line_intersect (Geom::Rect &r, Geom::Line l)
int	centroid (std::vector< Geom::Point > const &p, Geom::Point &centroid, double &area)
	polyCentroid: Calculates the centroid (xCentroid, yCentroid) and area of a polygon, given its vertices (x[0], y[0]) .
Interval	operator+ (const Interval &a, const Interval &b)
Interval	operator- (const Interval &a, const Interval &b)
Interval	operator+= (Interval &a, const Interval &b)
Interval	operator-= (Interval &a, const Interval &b)
Interval	operator* (const Interval &a, const Interval &b)
Interval	operator*= (Interval &a, const Interval &b)
Interval	unify (const Interval &a, const Interval &b)
OptInterval	intersect (const Interval &a, const Interval &b)
OptCrossing	intersection (Line const &l1, Line const &l2)
OptCrossing	intersection (Ray const &r1, Ray const &r2)
OptCrossing	intersection (LineSegment const &ls1, LineSegment const &ls2)
Line	make_angle_bisector_line (Line const &l1, Line const &l2)
double	distance (Point const &_point, Line const &_line)
bool	are_near (Point const &_point, Line const &_line, double eps=EPSILON)
bool	are_parallel (Line const &l1, Line const &l2, double eps=EPSILON)
bool	are_same (Line const &l1, Line const &l2, double eps=EPSILON)
bool	are_orthogonal (Line const &l1, Line const &l2, double eps=EPSILON)
bool	are_collinear (Point const &p1, Point const &p2, Point const &p3, double eps=EPSILON)
double	angle_between (Line const &l1, Line const &l2)
double	distance (Point const &_point, LineSegment const &_segment)
bool	are_near (Point const &_point, LineSegment const &_segment, double eps=EPSILON)
Line	make_orthogonal_line (Point const &_point, Line const &_line)
Line	make_parallel_line (Point const &_point, Line const &_line)
Line	make_bisector_line (LineSegment const &_segment)
Line	make_angle_bisector_line (Point const &A, Point const &O, Point const &B)
Point	projection (Point const &_point, Line const &_line)
LineSegment	projection (LineSegment const &_segment, Line const &_line)
OptCrossing	intersection (Ray const &r1, Line const &l2)
OptCrossing	intersection (Line const &l1, Ray const &r2)
OptCrossing	intersection (LineSegment const &ls1, Line const &l2)
OptCrossing	intersection (Line const &l1, LineSegment const &ls2)
OptCrossing	intersection (LineSegment const &ls1, Ray const &r2)
OptCrossing	intersection (Ray const &r1, LineSegment const &ls2)
double	lerp (double t, double a, double b)
Linear	reverse (Linear const &a)
Linear	operator+ (Linear const &a, Linear const &b)
Linear	operator- (Linear const &a, Linear const &b)
Linear &	operator+= (Linear &a, Linear const &b)
Linear &	operator-= (Linear &a, Linear const &b)
Linear	operator+ (Linear const &a, double b)
Linear	operator- (Linear const &a, double b)
Linear &	operator+= (Linear &a, double b)
Linear &	operator-= (Linear &a, double b)
bool	operator== (Linear const &a, Linear const &b)
bool	operator!= (Linear const &a, Linear const &b)
Linear	operator- (Linear const &a)
Linear	operator* (Linear const &a, double b)
Linear	operator/ (Linear const &a, double b)
Linear	operator*= (Linear &a, double b)
Linear	operator/= (Linear &a, double b)
Matrix	from_basis (Point const x_basis, Point const y_basis, Point const offset)
	Creates a Matrix given an axis and origin point.
Matrix	operator* (Matrix const &m0, Matrix const &m1)
Matrix	elliptic_quadratic_form (Matrix const &m)
	Given a matrix m such that unit_circle = m*x, this returns the quadratic form x*A*x = 1.
Matrix &	operator*= (Matrix &a, Matrix const &b)
std::ostream &	operator<< (std::ostream &out_file, const Geom::Matrix &m)
	A function to print out the Matrix (for debugging).
Matrix	identity ()
	Returns the Identity Matrix.
bool	operator== (Matrix const &a, Matrix const &b)
bool	operator!= (Matrix const &a, Matrix const &b)
double	nearest_point (Point const &p, D2< SBasis > const &c, D2< SBasis > const &dc, double from, double to)
std::vector< double >	all_nearest_points (Point const &p, D2< SBasis > const &c, D2< SBasis > const &dc, double from, double to)
double	nearest_point (Point const &p, Piecewise< D2< SBasis > > const &c, double from, double to)
std::vector< double >	all_nearest_points (Point const &p, Piecewise< D2< SBasis > > const &c, double from, double to)
double	nearest_point (Point const &p, Point const &A, Point const &v)
double	nearest_point (Point const &p, D2< SBasis > const &c, double from=0, double to=1)
std::vector< double >	all_nearest_points (Point const &p, D2< SBasis > const &c, double from=0, double to=1)
double	nearest_point (Point const &p, Piecewise< D2< SBasis > > const &c)
std::vector< double >	all_nearest_points (Point const &p, Piecewise< D2< SBasis > > const &c)
int	winding (Path const &path, Point p)
	This function computes the winding of the path, given a reference point.
bool	path_direction (Path const &p)
	This function should only be applied to simple paths (regions), as otherwise a boolean winding direction is undefined.
template<typename T >
void	append (T &a, T const &b)
	A little sugar for appending a list to another.
bool	linear_intersect (Point A0, Point A1, Point B0, Point B1, double &tA, double &tB, double &det)
	Finds the intersection between the lines defined by A0 & A1, and B0 & B1.
static void	intersect_polish_root (Curve const &A, double &s, Curve const &B, double &t)
void	pair_intersect (Curve const &A, double Al, double Ah, Curve const &B, double Bl, double Bh, Crossings &ret, unsigned depth=0)
	This uses the local bounds functions of curves to generically intersect two.
Crossings	pair_intersect (Curve const &A, Interval const &Ad, Curve const &B, Interval const &Bd)
void	mono_intersect (Curve const &A, double Al, double Ah, Curve const &B, double Bl, double Bh, Crossings &ret, double tol=0.1, unsigned depth=0)
Crossings	mono_intersect (Curve const &A, Interval const &Ad, Curve const &B, Interval const &Bd)
void	mono_pair (Path const &A, double Al, double Ah, Path const &B, double Bl, double Bh, Crossings &ret, double, unsigned depth=0)
	Takes two paths and time ranges on them, with the invariant that the paths are monotonic on the range.
std::vector< double >	curve_mono_splits (Curve const &d)
	This returns the times when the x or y derivative is 0 in the curve.
std::vector< double >	offset_doubles (std::vector< double > const &x, double offs)
	Convenience function to add a value to each entry in a vector of doubles.
std::vector< double >	path_mono_splits (Path const &p)
	Finds all the monotonic splits for a path.
std::vector< std::vector < double > >	paths_mono_splits (std::vector< Path > const &ps)
	Applies path_mono_splits to multiple paths, and returns the results such that time-set i corresponds to Path i.
std::vector< std::vector< Rect > >	split_bounds (std::vector< Path > const &p, std::vector< std::vector< double > > splits)
	Processes the bounds for a list of paths and a list of splits on them, yielding a list of rects for each.
Crossings	curve_self_crossings (Curve const &a)
Crossings	self_crossings (Path const &p)
void	flip_crossings (Crossings &crs)
CrossingSet	crossings_among (std::vector< Path > const &p)
bool	contains (Path const &p, Point i, bool evenodd=true)
template<typename T >
Crossings	curve_sweep (Path const &a, Path const &b)
Crossings	crossings (Curve const &a, Curve const &b)
Crossings	crossings (Path const &a, Path const &b)
CrossingSet	crossings (std::vector< Path > const &a, std::vector< Path > const &b)
template<typename iter >
iter	inc (iter const &x, unsigned n)
static Piecewise< D2< SBasis > >	paths_to_pw (std::vector< Path > paths)
Coord	nearest_point (Point const &p, Path const &c)
PathVector	reverse_paths_and_order (PathVector const &path_in)
	Reverses all Paths and the order of paths in the vector as well.
OptRect	bounds_fast (PathVector const &pv)
OptRect	bounds_exact (PathVector const &pv)
boost::optional < PathVectorPosition >	nearestPoint (PathVector const &path_in, Point const &_point, double *distance_squared)
std::vector< PathVectorPosition >	allNearestPoints (PathVector const &path_in, Point const &_point, double *distance_squared)
void	operator*= (PathVector &path_in, Matrix const &m)
PathVector	operator* (PathVector const &path_in, Matrix const &m)
void	operator*= (PathVector &path_in, Translate const &m)
PathVector	operator* (PathVector const &path_in, Translate const &m)
void	operator+= (PathVector &path_in, Point const &p)
PathVector	operator+ (PathVector const &path_in, Point const &p)
Geom::Point	initialPoint (PathVector const &path_in)
Geom::Point	finalPoint (PathVector const &path_in)
Point	pointAt (PathVector const &path_in, PathVectorPosition const pvp)
Piecewise< SBasis >	divide (Piecewise< SBasis > const &a, Piecewise< SBasis > const &b, unsigned k)
Piecewise< SBasis >	divide (Piecewise< SBasis > const &a, Piecewise< SBasis > const &b, double tol, unsigned k, double zero)
Piecewise< SBasis >	divide (Piecewise< SBasis > const &a, SBasis const &b, double tol, unsigned k, double zero)
Piecewise< SBasis >	divide (SBasis const &a, Piecewise< SBasis > const &b, double tol, unsigned k, double zero)
Piecewise< SBasis >	divide (SBasis const &a, SBasis const &b, double tol, unsigned k, double zero)
std::map< double, unsigned >	compose_pullback (std::vector< double > const &values, SBasis const &g)
int	compose_findSegIdx (std::map< double, unsigned >::iterator const &cut, std::map< double, unsigned >::iterator const &next, std::vector< double > const &levels, SBasis const &g)
std::vector< double >	roots (Piecewise< SBasis > const &f)
std::vector< std::vector < double > >	multi_roots (Piecewise< SBasis > const &f, std::vector< double > const &values)
template<typename T >
FragmentConcept< T >::BoundsType	bounds_fast (const Piecewise< T > &f)
template<typename T >
FragmentConcept< T >::BoundsType	bounds_exact (const Piecewise< T > &f)
template<typename T >
FragmentConcept< T >::BoundsType	bounds_local (const Piecewise< T > &f, const OptInterval &_m)
template<typename T >
T	elem_portion (const Piecewise< T > &a, unsigned i, double from, double to)
template<typename T >
Piecewise< T >	partition (const Piecewise< T > &pw, std::vector< double > const &c)
	Piecewise<T> partition(const Piecewise<T> &pw, std::vector<double> const &c); Further subdivides the Piecewise<T> such that there is a cut at every value in c.
template<typename T >
Piecewise< T >	portion (const Piecewise< T > &pw, double from, double to)
	Piecewise<T> portion(const Piecewise<T> &pw, double from, double to); Returns a Piecewise<T> with a defined domain of [min(from, to), max(from, to)].
template<typename T >
Piecewise< T >	remove_short_cuts (Piecewise< T > const &f, double tol)
template<typename T >
Piecewise< T >	remove_short_cuts_extending (Piecewise< T > const &f, double tol)
template<typename T >
std::vector< double >	roots (const Piecewise< T > &pw)
template<typename T >
Piecewise< T >	operator+ (Piecewise< T > const &a, typename T::output_type b)
template<typename T >
Piecewise< T >	operator- (Piecewise< T > const &a, typename T::output_type b)
template<typename T >
Piecewise< T > &	operator+= (Piecewise< T > &a, typename T::output_type b)
template<typename T >
Piecewise< T > &	operator-= (Piecewise< T > &a, typename T::output_type b)
template<typename T >
Piecewise< T >	operator- (Piecewise< T > const &a)
template<typename T >
Piecewise< T >	operator* (Piecewise< T > const &a, double b)
template<typename T >
Piecewise< T >	operator* (Piecewise< T > const &a, T b)
template<typename T >
Piecewise< T >	operator/ (Piecewise< T > const &a, double b)
template<typename T >
Piecewise< T > &	operator*= (Piecewise< T > &a, double b)
template<typename T >
Piecewise< T > &	operator/= (Piecewise< T > &a, double b)
template<typename T >
Piecewise< T >	operator+ (Piecewise< T > const &a, Piecewise< T > const &b)
template<typename T >
Piecewise< T >	operator- (Piecewise< T > const &a, Piecewise< T > const &b)
template<typename T >
Piecewise< T > &	operator+= (Piecewise< T > &a, Piecewise< T > const &b)
template<typename T >
Piecewise< T > &	operator-= (Piecewise< T > &a, Piecewise< T > const &b)
template<typename T1 , typename T2 >
Piecewise< T2 >	operator* (Piecewise< T1 > const &a, Piecewise< T2 > const &b)
template<typename T >
Piecewise< T > &	operator*= (Piecewise< T > &a, Piecewise< T > const &b)
template<typename T >
Piecewise< T >	compose (Piecewise< T > const &f, SBasis const &g)
template<typename T >
Piecewise< T >	compose (Piecewise< T > const &f, Piecewise< SBasis > const &g)
template<typename T >
Piecewise< T >	integral (Piecewise< T > const &a)
template<typename T >
Piecewise< T >	derivative (Piecewise< T > const &a)
template<typename T >
Piecewise< T >	reverse (Piecewise< T > const &f)
Coord	L1 (Point const &p)
	Compute the L1 norm, or manhattan distance, of p.
Coord	LInfty (Point const &p)
	Compute the L infinity, or maximum, norm of p.
bool	is_zero (Point const &p)
	Returns true iff p is a zero vector, i.e. Point(0, 0).
bool	is_unit_vector (Point const &p)
Coord	atan2 (Point const p)
Coord	angle_between (Point const a, Point const b)
	compute the angle turning from a to b.
Point	unit_vector (Point const &a)
	Returns a version of a scaled to be a unit vector (within rounding error).
Point	abs (Point const &b)
Point	operator* (Point const &v, Matrix const &m)
Point	operator/ (Point const &p, Matrix const &m)
Point	constrain_angle (Point const &A, Point const &B, unsigned int n=4, Geom::Point const &dir=Geom::Point(1, 0))
	Constrains the angle (with respect to dir) of the line joining A and B to a multiple of pi/n.
Point	operator* (double const s, Point const &p)
std::ostream &	operator<< (std::ostream &out_file, const Geom::Point &in_pnt)
	A function to print out the Point.
Point	operator^ (Point const &a, Point const &b)
	This is a rotation (sort of).
bool	operator== (Point const &a, Point const &b)
bool	operator!= (Point const &a, Point const &b)
bool	operator<= (Point const &a, Point const &b)
	This is a lexicographical ordering for points.
Coord	L2 (Point const &p)
	Compute the L2, or euclidean, norm of p.
Coord	L2sq (Point const &p)
	Compute the square of L2 norm of p.
bool	are_near (Point const &a, Point const &b, double const eps=EPSILON)
Point	middle_point (Point const &P1, Point const &P2)
Point	rot90 (Point const &p)
	Returns p * Geom::rotate_degrees(90), but more efficient.
Point	lerp (double const t, Point const a, Point const b)
	Given two points and a parameter t [0, 1], return a point proportionally from a to b by t.
Coord	dot (Point const &a, Point const &b)
	compute the dot product (inner product) between the vectors a and b.
Coord	cross (Point const &a, Point const &b)
	Defined as dot(a, b.cw()).
Coord	distance (Point const &a, Point const &b)
	compute the euclidean distance between points a and b.
Coord	distanceSq (Point const &a, Point const &b)
	compute the square of the distance between points a and b.
std::vector< std::complex < double > >	solve (Poly const &pp)
std::vector< double >	solve_reals (Poly const &p)
double	polish_root (Poly const &p, double guess, double tol)
Poly	integral (Poly const &p)
Poly	derivative (Poly const &p)
Poly	compose (Poly const &a, Poly const &b)
Poly	divide (Poly const &a, Poly const &b, Poly &r)
Poly	gcd (Poly const &a, Poly const &b, const double)
Poly	operator* (double a, Poly const &b)
Poly	divide_out_root (Poly const &p, double x)
std::ostream &	operator<< (std::ostream &out_file, const Poly &in_poly)
double	distance (Point const &_point, Ray const &_ray)
bool	are_near (Point const &_point, Ray const &_ray, double eps=EPSILON)
bool	are_same (Ray const &r1, Ray const &r2, double eps=EPSILON)
double	angle_between (Ray const &r1, Ray const &r2, bool cw=true)
Ray	make_angle_bisector_ray (Ray const &r1, Ray const &r2)
Rect	unify (const Rect &, const Rect &)
Rect	union_list (std::vector< Rect > const &r)
double	distanceSq (Point const &p, Rect const &rect)
double	distance (Point const &p, Rect const &rect)
	Returns the smallest distance between p and rect.
OptRect	unify (OptRect const &a, OptRect const &b)
	Returns the smallest rectangle that encloses both rectangles.
OptRect	intersect (Rect const &a, Rect const &b)
static void	find_intersections_bezier_recursive (std::vector< std::pair< double, double > > &xs, OldBezier a, OldBezier b)
void	find_intersections_bezier_recursive (std::vector< std::pair< double, double > > &xs, vector< Geom::Point > const &A, vector< Geom::Point > const &B, double precision)
bool	intersect_BB (OldBezier a, OldBezier b)
void	recursively_intersect (OldBezier a, double t0, double t1, int deptha, OldBezier b, double u0, double u1, int depthb, std::vector< std::pair< double, double > > &parameters)
double	log4 (double x)
double	Lmax (Point p)
unsigned	wangs_theorem (OldBezier a)
static int	intersect_polish_f (const gsl_vector *x, void *params, gsl_vector *f)
static void	intersect_polish_root (OldBezier &A, double &s, OldBezier &B, double &t)
unsigned	outer_index (Regions const &ps)
Regions	regions_from_paths (std::vector< Path > const &ps)
std::vector< Path >	paths_from_regions (Regions const &rs)
Regions	sanitize_path (Path const &p)
Regions	region_boolean (bool rev, Region const &a, Region const &b, Crossings const &cr)
Regions	region_boolean (bool rev, Region const &a, Region const &b, Crossings const &cr_a, Crossings const &cr_b)
Regions	region_boolean (bool rev, Region const &a, Region const &b)
SBasis	extract_u (SBasis2d const &a, double u)
SBasis	extract_v (SBasis2d const &a, double v)
SBasis	compose (Linear2d const &a, D2< SBasis > const &p)
SBasis	compose (SBasis2d const &fg, D2< SBasis > const &p)
D2< SBasis >	compose_each (D2< SBasis2d > const &fg, D2< SBasis > const &p)
SBasis2d	partial_derivative (SBasis2d const &f, int dim)
D2< SBasis >	sb2dsolve (SBasis2d const &f, Geom::Point const &A, Geom::Point const &B, unsigned degmax)
	Finds a path which traces the 0 contour of f, traversing from A to B as a single d2<sbasis>.
D2< SBasis >	sb2d_cubic_solve (SBasis2d const &f, Geom::Point const &A, Geom::Point const &B)
	Finds a path which traces the 0 contour of f, traversing from A to B as a single cubic d2<sbasis>.
Linear	extract_u (Linear2d const &a, double u)
Linear	extract_v (Linear2d const &a, double v)
Linear2d	operator- (Linear2d const &a)
Linear2d	operator+ (Linear2d const &a, Linear2d const &b)
Linear2d	operator- (Linear2d const &a, Linear2d const &b)
Linear2d &	operator+= (Linear2d &a, Linear2d const &b)
Linear2d &	operator-= (Linear2d &a, Linear2d const &b)
Linear2d &	operator*= (Linear2d &a, double b)
bool	operator== (Linear2d const &a, Linear2d const &b)
bool	operator!= (Linear2d const &a, Linear2d const &b)
Linear2d	operator* (double const a, Linear2d const &b)
SBasis2d	operator- (const SBasis2d &p)
SBasis2d	operator+ (const SBasis2d &a, const SBasis2d &b)
SBasis2d	operator- (const SBasis2d &a, const SBasis2d &b)
SBasis2d &	operator+= (SBasis2d &a, const Linear2d &b)
SBasis2d &	operator-= (SBasis2d &a, const Linear2d &b)
SBasis2d &	operator+= (SBasis2d &a, double b)
SBasis2d &	operator-= (SBasis2d &a, double b)
SBasis2d &	operator*= (SBasis2d &a, double b)
SBasis2d &	operator/= (SBasis2d &a, double b)
SBasis2d	operator* (double k, SBasis2d const &a)
SBasis2d	operator* (SBasis2d const &a, SBasis2d const &b)
SBasis2d	shift (SBasis2d const &a, int sh)
SBasis2d	shift (Linear2d const &a, int sh)
SBasis2d	truncate (SBasis2d const &a, unsigned terms)
SBasis2d	multiply (SBasis2d const &a, SBasis2d const &b)
SBasis2d	integral (SBasis2d const &c)
SBasis2d	sqrt (SBasis2d const &a, int k)
SBasis2d	reciprocal (Linear2d const &a, int k)
SBasis2d	divide (SBasis2d const &a, SBasis2d const &b, int k)
SBasis2d	compose (SBasis2d const &a, SBasis2d const &b)
SBasis2d	compose (SBasis2d const &a, SBasis2d const &b, unsigned k)
SBasis2d	inverse (SBasis2d const &a, int k)
std::ostream &	operator<< (std::ostream &out_file, const Linear2d &bo)
std::ostream &	operator<< (std::ostream &out_file, const SBasis2d &p)
Piecewise< D2< SBasis > >	cutAtRoots (Piecewise< D2< SBasis > > const &M, double tol=1e-4)
Piecewise< SBasis >	atan2 (D2< SBasis > const &vect, double tol=.01, unsigned order=3)
	Return a function which gives the angle of vect at each point.
Piecewise< SBasis >	atan2 (Piecewise< D2< SBasis > >const &vect, double tol=.01, unsigned order=3)
	Return a function which gives the angle of vect at each point.
D2< Piecewise< SBasis > >	tan2 (SBasis const &angle, double tol=.01, unsigned order=3)
	tan2 is the pseudo-inverse of atan2.
D2< Piecewise< SBasis > >	tan2 (Piecewise< SBasis > const &angle, double tol=.01, unsigned order=3)
	tan2 is the pseudo-inverse of atan2.
Piecewise< D2< SBasis > >	unitVector (D2< SBasis > const &vect, double tol=.01, unsigned order=3)
	Return a Piecewise<D2<SBasis> > which points in the same direction as V_in, but has unit_length.
Piecewise< D2< SBasis > >	unitVector (Piecewise< D2< SBasis > > const &vect, double tol=.01, unsigned order=3)
	Return a Piecewise<D2<SBasis> > which points in the same direction as V_in, but has unit_length.
Piecewise< SBasis >	curvature (D2< SBasis > const &M, double tol=.01)
	returns a function giving the curvature at each point in M.
Piecewise< SBasis >	curvature (Piecewise< D2< SBasis > > const &M, double tol=.01)
	returns a function giving the curvature at each point in M.
Piecewise< SBasis >	arcLengthSb (D2< SBasis > const &M, double tol=.01)
	returns a function giving the arclength at each point in M.
Piecewise< SBasis >	arcLengthSb (Piecewise< D2< SBasis > > const &M, double tol=.01)
	returns a function giving the arclength at each point in M.
double	length (D2< SBasis > const &M, double tol=.01)
	Calculates the length of a D2<SBasis> through gsl integration.
double	length (Piecewise< D2< SBasis > > const &M, double tol=.01)
	Calculates the length of a Piecewise<D2<SBasis> > through gsl integration.
void	length_integrating (D2< SBasis > const &B, double &result, double &abs_error, double tol)
	Calculates the length of a D2<SBasis> through gsl integration.
Piecewise< D2< SBasis > >	arc_length_parametrization (D2< SBasis > const &M, unsigned order=3, double tol=.01)
	Reparameterise M to have unit speed.
Piecewise< D2< SBasis > >	arc_length_parametrization (Piecewise< D2< SBasis > > const &M, unsigned order=3, double tol=.01)
	Reparameterise M to have unit speed.
unsigned	centroid (Piecewise< D2< SBasis > > const &p, Point &centroid, double &area)
	Centroid using sbasis integration.
std::vector< D2< SBasis > >	cubics_fitting_curvature (Point const &M0, Point const &M1, Point const &dM0, Point const &dM1, double d2M0xdM0, double d2M1xdM1, int insist_on_speed_signs=1, double epsilon=1e-5)
	returns the cubics fitting direction and curvature of a given input curve at two points.
std::vector< D2< SBasis > >	cubics_fitting_curvature (Point const &M0, Point const &M1, Point const &dM0, Point const &dM1, Point const &d2M0, Point const &d2M1, int insist_on_speed_signs=1, double epsilon=1e-5)
std::vector< D2< SBasis > >	cubics_with_prescribed_curvature (Point const &M0, Point const &M1, Point const &dM0, Point const &dM1, double k0, double k1, int insist_on_speed_signs=1, double error=1e-5)
std::vector< double >	find_tangents (Point P, D2< SBasis > const &A)
	returns all the parameter values of A whose tangent passes through P.
Piecewise< SBasis >	abs (SBasis const &f)
	Return the absolute value of a function pointwise.
Piecewise< SBasis >	abs (Piecewise< SBasis > const &f)
	Return the absolute value of a function pointwise.
Piecewise< SBasis >	max (SBasis const &f, SBasis const &g)
	Return the greater of the two functions pointwise.
Piecewise< SBasis >	max (Piecewise< SBasis > const &f, SBasis const &g)
	Return the greater of the two functions pointwise.
Piecewise< SBasis >	max (SBasis const &f, Piecewise< SBasis > const &g)
	Return the greater of the two functions pointwise.
Piecewise< SBasis >	max (Piecewise< SBasis > const &f, Piecewise< SBasis > const &g)
	Return the greater of the two functions pointwise.
Piecewise< SBasis >	min (SBasis const &f, SBasis const &g)
	Return the more negative of the two functions pointwise.
Piecewise< SBasis >	min (Piecewise< SBasis > const &f, SBasis const &g)
	Return the more negative of the two functions pointwise.
Piecewise< SBasis >	min (SBasis const &f, Piecewise< SBasis > const &g)
	Return the more negative of the two functions pointwise.
Piecewise< SBasis >	min (Piecewise< SBasis > const &f, Piecewise< SBasis > const &g)
	Return the more negative of the two functions pointwise.
Piecewise< SBasis >	signSb (SBasis const &f)
	Return the sign of the two functions pointwise.
Piecewise< SBasis >	signSb (Piecewise< SBasis > const &f)
	Return the sign of the two functions pointwise.
static Piecewise< SBasis >	sqrt_internal (SBasis const &f, double tol, int order)
Piecewise< SBasis >	sqrt (SBasis const &f, double tol, int order)
	Compute the sqrt of a function.
Piecewise< SBasis >	sqrt (Piecewise< SBasis > const &f, double tol, int order)
	Compute the sqrt of a function.
Piecewise< SBasis >	sin (SBasis const &f, double tol, int order)
	Compute the sine of a function.
Piecewise< SBasis >	sin (Piecewise< SBasis > const &f, double tol, int order)
	Compute the sine of a function.
Piecewise< SBasis >	cos (Piecewise< SBasis > const &f, double tol, int order)
	Compute the cosine of a function.
Piecewise< SBasis >	cos (SBasis const &f, double tol, int order)
	Compute the cosine of a function.
void	truncateResult (Piecewise< SBasis > &f, int order)
Piecewise< SBasis >	reciprocalOnDomain (Interval range, double tol)
Piecewise< SBasis >	reciprocal (SBasis const &f, double tol, int order)
Piecewise< SBasis >	reciprocal (Piecewise< SBasis > const &f, double tol, int order)
Piecewise< SBasis >	interpolate (std::vector< double > times, std::vector< double > values, unsigned smoothness)
	Retruns a Piecewise SBasis with prescribed values at prescribed times.
Piecewise< SBasis >	log (SBasis const &f, double tol=1e-3, int order=3)
Piecewise< SBasis >	log (Piecewise< SBasis >const &f, double tol=1e-3, int order=3)
SBasis	poly_to_sbasis (Poly const &p)
	Changes the basis of p to be sbasis.
Poly	sbasis_to_poly (SBasis const &sb)
	Changes the basis of p to be monomial.
OptInterval	bounds_exact (SBasis const &a)
	Find the smallest interval that bounds a.
OptInterval	bounds_fast (const SBasis &sb, int order)
	Find a small interval that bounds a.
OptInterval	bounds_local (const SBasis &sb, const OptInterval &i, int order)
	Find a small interval that bounds a(t) for t in i to order order.
static int	upper_level (vector< double > const &levels, double x, double tol=0.)
static void	multi_roots_internal (SBasis const &f, SBasis const &df, std::vector< double > const &levels, std::vector< std::vector< double > > &roots, double htol, double vtol, double a, double fa, double b, double fb)
std::vector< std::vector < double > >	multi_roots (SBasis const &f, std::vector< double > const &levels, double htol, double vtol, double a, double b)
	Solve f(t)=c for several c at once.
void	subdiv_sbasis (SBasis const &s, std::vector< double > &roots, double left, double right)
std::vector< double >	roots1 (SBasis const &s)
std::vector< double >	roots (SBasis const &s)
	Find all t s.t s(t) = 0.
double	binomial (unsigned int n, unsigned int k)
int	sgn (unsigned int j, unsigned int k)
void	sbasis_to_bezier (Bezier &bz, SBasis const &sb, size_t sz)
	Changes the basis of p to be bernstein.
void	sbasis_to_bezier (std::vector< Point > &bz, D2< SBasis > const &sb, size_t sz)
	Changes the basis of p to be Bernstein.
void	bezier_to_sbasis (D2< SBasis > &sb, std::vector< Point > const &bz)
	Changes the basis of d2 p to be sbasis.
void	build_from_sbasis (Geom::PathBuilder &pb, D2< SBasis > const &B, double tol, bool only_cubicbeziers)
	Make a path from a d2 sbasis.
Path	path_from_sbasis (D2< SBasis > const &B, double tol, bool only_cubicbeziers)
	Make a path from a d2 sbasis.
std::vector< Geom::Path >	path_from_piecewise (Geom::Piecewise< Geom::D2< Geom::SBasis > > const &B, double tol, bool only_cubicbeziers)
	Make a path from a d2 sbasis.
Path	cubicbezierpath_from_sbasis (D2< SBasis > const &B, double tol)
SBasis	operator+ (const SBasis &a, const SBasis &b)
	Compute the pointwise sum of a and b (Exact).
SBasis	operator- (const SBasis &a, const SBasis &b)
	Compute the pointwise difference of a and b (Exact).
SBasis &	operator+= (SBasis &a, const SBasis &b)
	Compute the pointwise sum of a and b and store in a (Exact).
SBasis &	operator-= (SBasis &a, const SBasis &b)
	Compute the pointwise difference of a and b and store in a (Exact).
SBasis	operator* (SBasis const &a, double k)
	Compute the pointwise product of a and b (Exact).
SBasis &	operator*= (SBasis &a, double b)
	Compute the pointwise product of a and b and store the value in a (Exact).
SBasis	shift (SBasis const &a, int sh)
	multiply a by x^sh in place (Exact)
SBasis	shift (Linear const &a, int sh)
	multiply a by x^sh (Exact)
SBasis	multiply_add (SBasis const &a, SBasis const &b, SBasis c)
	Compute the pointwise product of a and b adding c (Exact).
SBasis	multiply (SBasis const &a, SBasis const &b)
	Compute the pointwise product of a and b (Exact).
SBasis	integral (SBasis const &c)
	Compute the integral of a (Exact).
SBasis	derivative (SBasis const &a)
	Compute the derivative of a (Exact).
SBasis	sqrt (SBasis const &a, int k)
	Compute the sqrt of a.
SBasis	reciprocal (Linear const &a, int k)
	Compute the recpirocal of a.
SBasis	divide (SBasis const &a, SBasis const &b, int k)
	Compute a / b to k terms.
SBasis	compose (SBasis const &a, SBasis const &b)
	Compute a composed with b.
SBasis	compose (SBasis const &a, SBasis const &b, unsigned k)
	Compute a composed with b to k terms.
SBasis	inverse (SBasis a, int k)
	find the function a^-1 such that a^-1 composed with a to k terms is the identity function
SBasis	sin (Linear b, int k)
	Compute the sine of a to k terms.
SBasis	cos (Linear bo, int k)
	Compute the cosine of a.
SBasis	compose_inverse (SBasis const &f, SBasis const &g, unsigned order, double zero)
	compute fog^-1.
SBasis	reverse (SBasis const &a)
	Returns a function which reverses the domain of a.
SBasis	operator- (const SBasis &p)
SBasis	operator* (double k, SBasis const &a)
SBasis	operator/ (SBasis const &a, double k)
SBasis &	operator/= (SBasis &a, double b)
SBasis	operator+ (const SBasis &a, double b)
SBasis	operator- (const SBasis &a, double b)
SBasis &	operator+= (SBasis &a, double b)
SBasis &	operator-= (SBasis &a, double b)
SBasis	truncate (SBasis const &a, unsigned terms)
SBasis	operator* (SBasis const &a, SBasis const &b)
SBasis &	operator*= (SBasis &a, SBasis const &b)
unsigned	valuation (SBasis const &a, double tol=0)
	Returns the degree of the first non zero coefficient.
SBasis	portion (const SBasis &t, double from, double to)
	Returns the sbasis on domain [0,1] that was t on [from, to].
SBasis	portion (const SBasis &t, Interval ivl)
std::ostream &	operator<< (std::ostream &out_file, const Linear &bo)
std::ostream &	operator<< (std::ostream &out_file, const SBasis &p)
void	first_false (std::vector< std::vector< bool > > visited, unsigned &i, unsigned &j)
unsigned	find_crossing (Crossings const &cr, Crossing x, unsigned i)
Shape	shape_boolean (bool rev, Shape const &a, Shape const &b, CrossingSet const &crs)
Shape	shape_boolean (bool rev, Shape const &a, Shape const &b)
std::vector< double >	region_sizes (Shape const &a)
Shape	shape_boolean_ra (bool rev, Shape const &a, Shape const &b, CrossingSet const &crs)
Shape	shape_boolean_rb (bool rev, Shape const &a, Shape const &b, CrossingSet const &crs)
Shape	boolop (Shape const &a, Shape const &b, unsigned flags, CrossingSet const &crs)
Shape	boolop (Shape const &a, Shape const &b, unsigned flags)
int	paths_winding (std::vector< Path > const &ps, Point p)
void	add_to_shape (Shape &s, Path const &p, bool fill)
int	inner_winding (Path const &p, std::vector< Path > const &ps)
double	fudgerize (double d, bool rev)
unsigned	pick_coincident (unsigned ix, unsigned jx, bool &rev, std::vector< Path > const &ps, CrossingSet const &crs)
unsigned	crossing_along (double t, unsigned ix, unsigned jx, bool dir, Crossings const &crs)
void	crossing_dual (unsigned &i, unsigned &j, CrossingSet const &crs)
void	outer_crossing (unsigned &ix, unsigned &jx, bool &dir, std::vector< Path > const &ps, CrossingSet const &crs)
std::vector< Path >	inner_sanitize (std::vector< Path > const &ps)
Shape	sanitize (std::vector< Path > const &ps)
Shape	stopgap_cleaner (std::vector< Path > const &ps)
CrossingSet	crossings_between (Shape const &a, Shape const &b)
Shape	boolop (Shape const &, Shape const &, unsigned flags, CrossingSet &)
std::vector< Path >	desanitize (Shape const &s)
template<class t >
static int	SGN (t x)
void	find_bernstein_roots (double const *w, unsigned degree, std::vector< double > &solutions, unsigned depth, double left_t, double right_t, bool use_secant)
static Geom::Point	Bezier (Geom::Point const *V, unsigned degree, double t, Geom::Point *Left, Geom::Point *Right)
unsigned	crossing_count (Geom::Point const *V, unsigned degree)
static unsigned	control_poly_flat_enough (Geom::Point const *V, unsigned degree)
static double	compute_x_intercept (Geom::Point const *V, unsigned degree)
void	find_parametric_bezier_roots (Geom::Point const *w, unsigned degree, std::vector< double > &solutions, unsigned depth)
unsigned	crossing_count (double const *V, unsigned degree, double left_t, double right_t)
template<class charT >
std::basic_ostream< charT > &	operator<< (std::basic_ostream< charT > &os, const SVGEllipticalArc &ea)
void	parse_svg_path (char const *str, SVGPathSink &sink) throw (SVGPathParseError)
std::vector< Path >	parse_svg_path (char const *str) throw (SVGPathParseError)
std::vector< Path >	read_svgd (char const *name) throw (SVGPathParseError)
void	output (Curve const &curve, SVGPathSink &sink)
void	output (HLineSegment const &curve, SVGPathSink &sink)
void	output (VLineSegment const &curve, SVGPathSink &sink)
void	output (LineSegment const &curve, SVGPathSink &sink)
void	output (SVGEllipticalArc const &curve, SVGPathSink &sink)
template<typename T >
bool	output_as (Curve const &curve, SVGPathSink &sink)
void	output_svg_path (Path &path, SVGPathSink &sink)
std::vector< std::vector < unsigned > >	sweep_bounds (std::vector< Rect > rs, Dim2 d)
	Make a list of pairs of self intersections in a list of Rects.
std::vector< std::vector < unsigned > >	sweep_bounds (std::vector< Rect > a, std::vector< Rect > b, Dim2 d)
	Make a list of pairs of red-blue intersections between two lists of Rects.
std::vector< std::vector < unsigned > >	fake_cull (unsigned a, unsigned b)
Matrix	operator* (Translate const &t, Scale const &s)
Matrix	operator* (Translate const &t, Rotate const &r)
Matrix	operator* (Scale const &s, Translate const &t)
Matrix	operator* (Scale const &s, Matrix const &m)
Matrix	operator* (Matrix const &m, Translate const &t)
Matrix	operator* (Matrix const &m, Scale const &s)
Matrix	operator* (Matrix const &m, Rotate const &r)
Translate	pow (Translate const &t, int n)
Coord	pow (Coord x, long n)
Scale	pow (Scale const &s, int n)
Rotate	pow (Rotate x, long n)
Matrix	pow (Matrix x, long n)
Point	operator* (Point const &v, Translate const &t)
Point	operator* (Point const &p, Scale const &s)
Point	operator* (Point const &v, Rotate const &r)
Rotate	pow (Rotate t, int n)
Matrix	pow (Matrix t, int n)
void	binomial_coefficients (std::vector< size_t > &bc, size_t n)
bool	logical_xor (bool a, bool b)
template<class T >
int	sgn (const T &x)
	Sign function - indicates the sign of a numeric type.
template<class T >
T	sqr (const T &x)
template<class T >
T	cube (const T &x)
template<class T >
const T &	between (const T &min, const T &max, const T &x)
	Between function - returns true if a number x is within a range.
double	round (double const x)
	Returns x rounded to the nearest integer.
double	decimal_round (double const x, int const places)
	Returns x rounded to the nearest places decimal places.
NodeType	get_nodetype (Curve const &c_incoming, Curve const &c_outgoing)
bool	transform_equalp (Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon)
bool	translate_equalp (Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon)
bool	matrix_equalp (Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon)
Variables
static Point const	unconstrained_tangent (0, 0)
const Coord	EPSILON = 1e-5
const double	INV_EPS = (1L<<14)
const unsigned	MAXDEPTH = 23
const double	BEPSILON = ldexp(1.0,(-MAXDEPTH-1))
const double	SECANT_EPSILON = 1e-13
unsigned	total_steps
unsigned	total_subs

---

Detailed Description

A convex cover is a sequence of convex polygons that completely cover the path.

Specific nodetype geometry functions for Inkscape, not provided my lib2geom.

Various utility functions.

Shapes are special paths on which boolops can be performed.

Various geometrical calculations.

For now a convex hull class is included here (the convex-hull header is wrong)

Authors: Michael G. Sloan <mgsloan@gmail.com> Nathan Hurst <njh@mail.csse.monash.edu.au> MenTaLguY <mental@rydia.net>

Copyright 2007-2009 Authors

This library is free software; you can redistribute it and/or modify it either under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation (the "LGPL") or, at your option, under the terms of the Mozilla Public License Version 1.1 (the "MPL"). If you do not alter this notice, a recipient may use your version of this file under either the MPL or the LGPL.

You should have received a copy of the LGPL along with this library in the file COPYING-LGPL-2.1; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA You should have received a copy of the MPL along with this library in the file COPYING-MPL-1.1

The contents of this file are subject to the Mozilla Public License Version 1.1 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.mozilla.org/MPL/

This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the LGPL or the MPL for the specific language governing rights and limitations.

Copyright 2008 Marco Cecchetti <mrcekets at gmail.com> Copyright 2007 Johan Engelen <goejendaagh@zonnet.nl> Copyright 2006 Michael G. Sloan <mgsloan@gmail.com>

This library is free software; you can redistribute it and/or modify it either under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation (the "LGPL") or, at your option, under the terms of the Mozilla Public License Version 1.1 (the "MPL"). If you do not alter this notice, a recipient may use your version of this file under either the MPL or the LGPL.

You should have received a copy of the LGPL along with this library in the file COPYING-LGPL-2.1; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA You should have received a copy of the MPL along with this library in the file COPYING-MPL-1.1

The contents of this file are subject to the Mozilla Public License Version 1.1 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.mozilla.org/MPL/

This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the LGPL or the MPL for the specific language governing rights and limitations.

Author: Johan Engelen <goejendaagh@zonnet.nl>

Copyright (C) 2008 Johan Engelen

Released under GNU GPL

---

Typedef Documentation

typedef Point Geom::BezierCurve[]

Definition at line 61 of file bezier-utils.cpp.

typedef double Geom::Coord

A "real" type with sufficient precision for coordinates.

You may safely assume that double (or even float) provides enough precision for storing on-canvas points, and hence that double provides enough precision for dot products of differences of on-canvas points.

Definition at line 47 of file coord.h.

typedef std::vector<Crossing> Geom::Crossings

Definition at line 125 of file crossing.h.

typedef std::vector<Crossings> Geom::CrossingSet

Definition at line 127 of file crossing.h.

typedef BezierCurve< 3 > Geom::CubicBezier

Definition at line 193 of file bezier-curve.h.

typedef SimpleCrosser Geom::DefaultCrosser

Definition at line 85 of file path-intersection.h.

typedef long Geom::ICoord

Definition at line 9 of file point-l.h.

typedef std::back_insert_iterator<std::vector<Path> > Geom::iter

Definition at line 144 of file svg-path.h.

typedef BezierCurve< 1 > Geom::LineSegment

Definition at line 191 of file bezier-curve.h.

typedef boost::optional<Crossing> Geom::OptCrossing

Definition at line 63 of file crossing.h.

typedef std::vector< Geom::Path > Geom::PathVector

Definition at line 76 of file 2geom/forward.h.

typedef BezierCurve< 2 > Geom::QuadraticBezier

Definition at line 192 of file bezier-curve.h.

typedef D2< Interval > Geom::Rect

D2<Interval> specialization to Rect.

Definition at line 82 of file 2geom/forward.h.

typedef std::vector<Region> Geom::Regions

Definition at line 89 of file region.h.

---

Enumeration Type Documentation

anonymous enum

Enumerator:

BOOLOP_JUST_A
BOOLOP_JUST_B
BOOLOP_BOTH
BOOLOP_NEITHER

Definition at line 48 of file 2geom/shape.h.

     {
  BOOLOP_JUST_A  = 1,
  BOOLOP_JUST_B  = 2,
  BOOLOP_BOTH    = 4,
  BOOLOP_NEITHER = 8
};

anonymous enum

Enumerator:

BOOLOP_NULL
BOOLOP_INTERSECT
BOOLOP_SUBTRACT_A_B
BOOLOP_IDENTITY_A
BOOLOP_SUBTRACT_B_A
BOOLOP_IDENTITY_B
BOOLOP_EXCLUSION
BOOLOP_UNION

Definition at line 55 of file 2geom/shape.h.

     {
  BOOLOP_NULL         = 0,
  BOOLOP_INTERSECT    = BOOLOP_BOTH,
  BOOLOP_SUBTRACT_A_B = BOOLOP_JUST_B,
  BOOLOP_IDENTITY_A   = BOOLOP_JUST_A | BOOLOP_BOTH,
  BOOLOP_SUBTRACT_B_A = BOOLOP_JUST_A,
  BOOLOP_IDENTITY_B   = BOOLOP_JUST_B | BOOLOP_BOTH,
  BOOLOP_EXCLUSION    = BOOLOP_JUST_A | BOOLOP_JUST_B,
  BOOLOP_UNION        = BOOLOP_JUST_A | BOOLOP_JUST_B | BOOLOP_BOTH
};

enum Geom::Dim2

Enumerator:

X
Y

Definition at line 17 of file 2geom/point.h.

{ X=0, Y=1 };

enum Geom::IntersectorKind

Enumerator:

intersects
parallel
coincident
no_intersection

Definition at line 47 of file 2geom/geom.h.

                     {
    intersects = 0,
    parallel,
    coincident,
    no_intersection
};

enum Geom::NodeType

What kind of node is this? This is the value for the node->type field.

NodeType indicates the degree of continuity required for the node. I think that the corresponding integer indicates which derivate is connected. (Thus 2 means that the node is continuous to the second derivative, i.e. has matching endpoints and tangents)

Enumerator:

NODE_NONE	Discontinuous node, usually either start or endpoint of a path.
NODE_CUSP	This node continuously joins two segments, but the unit tangent is discontinuous.
NODE_SMOOTH	This node continuously joins two segments, with continuous *unit* tangent.
NODE_SYMM	This node is symmetric. I.e. continously joins two segments with continuous derivative

Definition at line 26 of file geom-nodetype.h.

             {
    NODE_NONE,
    NODE_CUSP,
    NODE_SMOOTH,
    NODE_SYMM
} NodeType;

---

Function Documentation

Piecewise< SBasis > Geom::abs

(

Piecewise< SBasis > const &

f

)

Return the absolute value of a function pointwise.

Parameters:

f

function

Piecewise< SBasis > Geom::abs

(

SBasis const &

f

)

Return the absolute value of a function pointwise.

Parameters:

f

function

Point Geom::abs

(

Point const &

b

)

void Geom::add_to_shape	(	Shape &	s,
		Path const &	p,
		bool	fill
	)

Definition at line 308 of file 2geom/shape.cpp.

References Geom::Shape::content.

                                                      {
    if(fill)
        s.content.push_back(Region(p).asFill());
    else
        s.content.push_back(Region(p).asHole());
}

std::vector<double> Geom::all_nearest_points	(	Point const &	p,
		Piecewise< D2< SBasis > > const &	c
	)			[inline]

Definition at line 124 of file nearest-point.h.

References all_nearest_points(), and c.

{
    return all_nearest_points(p, c, c.cuts[0], c.cuts[c.size()]);
}

std::vector<double> Geom::all_nearest_points	(	Point const &	p,
		D2< SBasis > const &	c,
		double	from = 0,
		double	to = 1
	)			[inline]

Definition at line 95 of file nearest-point.h.

References all_nearest_points(), and derivative().

{
    return all_nearest_points(p, c,  Geom::derivative(c), from, to);
}

std::vector< double > Geom::all_nearest_points	(	Point const &	p,
		Piecewise< D2< SBasis > > const &	c,
		double	from,
		double	to
	)

std::vector< double > Geom::all_nearest_points	(	Point const &	p,
		D2< SBasis > const &	c,
		D2< SBasis > const &	dc,
		double	from,
		double	to
	)

Referenced by all_nearest_points(), Geom::SBasisCurve::allNearestPoints(), and Geom::Curve::allNearestPoints().

std::vector< PathVectorPosition > Geom::allNearestPoints	(	PathVector const &	path_in,
		Point const &	_point,
		double *	distance_squared
	)

double Geom::angle_between	(	Ray const &	r1,
		Ray const &	r2,
		bool	cw = true
	)			[inline]

Definition at line 220 of file ray.h.

References Geom::detail::bezier_clipping::angle(), angle_between(), M_PI, and Geom::Ray::versor().

{
    double angle = angle_between(r1.versor(), r2.versor());
    if (angle < 0) angle += 2*M_PI;
    if (!cw) angle = 2*M_PI - angle;
    return angle;
}

double Geom::angle_between	(	Point const	a,
		Point const	b
	)

compute the angle turning from a to b.

compute the angle turning from a to b (signed).

This should give for angle_between(a, rot90(a)); This works by projecting b onto the basis defined by a, rot90(a)

double Geom::angle_between	(	Line const &	l1,
		Line const &	l2
	)			[inline]

Definition at line 303 of file line.h.

References Geom::detail::bezier_clipping::angle(), M_PI, and Geom::Line::versor().

Referenced by Inkscape::UI::Handle::_getDragTip(), angle_between(), Inkscape::LivePathEffect::append_half_circle(), Geom::Ellipse::arc(), Geom::SVGEllipticalArc::calculate_center_and_extreme_angles(), Inkscape::UI::SkewHandle::computeTransform(), Inkscape::UI::RotateHandle::computeTransform(), Inkscape::LivePathEffect::LPEAngleBisector::doEffect_path(), Inkscape::LivePathEffect::LPETextLabel::doEffect_pwd2(), Inkscape::UI::Handle::dragged(), Inkscape::UI::Node::grabbed(), Inkscape::LivePathEffect::CR::KnotHolderEntityRotationAngle::knot_set(), Inkscape::LivePathEffect::CR::KnotHolderEntityStartingAngle::knot_set(), make_angle_bisector_line(), make_angle_bisector_ray(), set_pos_and_anchor(), and Inkscape::LivePathEffect::TextParam::setPosAndAnchor().

{
    double angle = angle_between(l1.versor(), l2.versor());
    if (angle < 0) angle += M_PI;
    if (angle == M_PI) angle = 0;
    return angle;
}

template<typename T >

void Geom::append	(	T &	a,
		T const &	b
	)			[inline]

A little sugar for appending a list to another.

Definition at line 52 of file 2geom/shape.cpp.

Referenced by boolop(), curve_mono_splits(), and curve_self_crossings().

                              {
    a.insert(a.end(), b.begin(), b.end());
}

Piecewise< D2< SBasis > > Geom::arc_length_parametrization	(	Piecewise< D2< SBasis > > const &	M,
		unsigned	order = 3,
		double	tol = .01
	)

Reparameterise M to have unit speed.

Parameters:

	M	the Element.
	tol	the maximum error allowed.
	order	the maximum degree to use for approximation

Definition at line 430 of file sbasis-geometric.cpp.

References arc_length_parametrization(), Geom::Piecewise< T >::concat(), Barcode::Code39Ext::i, and org::w3c::dom::svg::result.

                                            {
    Piecewise<D2<SBasis> > result;
    for (unsigned i=0; i<M.size(); i++ ){
        Piecewise<D2<SBasis> > uniform_seg=arc_length_parametrization(M[i],order,tol);
        result.concat(uniform_seg);
    }
    return(result);
}

Piecewise< D2< SBasis > > Geom::arc_length_parametrization	(	D2< SBasis > const &	M,
		unsigned	order = 3,
		double	tol = .01
	)

Reparameterise M to have unit speed.

Parameters:

	M	the Element.
	tol	the maximum error allowed.
	order	the maximum degree to use for approximation

Definition at line 401 of file sbasis-geometric.cpp.

References arcLengthSb(), Geom::SBasis::at0(), Geom::SBasis::at1(), compose(), compose_inverse(), Geom::Piecewise< T >::cuts, Barcode::Code39Ext::i, Geom::Piecewise< T >::push(), Geom::Piecewise< T >::push_cut(), Geom::Piecewise< T >::segs, and Geom::Piecewise< T >::size().

Referenced by arc_length_parametrization(), Inkscape::LivePathEffect::LPECurveStitch::doEffect_path(), Inkscape::LivePathEffect::LPERecursiveSkeleton::doEffect_pwd2(), Inkscape::LivePathEffect::LPEPatternAlongPath::doEffect_pwd2(), Inkscape::LivePathEffect::LPEEnvelope::doEffect_pwd2(), Inkscape::LivePathEffect::LPEBendPath::doEffect_pwd2(), set_pos_and_anchor(), and Inkscape::LivePathEffect::TextParam::setPosAndAnchor().

                                      {
    Piecewise<D2<SBasis> > u;
    u.push_cut(0);

    Piecewise<SBasis> s = arcLengthSb(Piecewise<D2<SBasis> >(M),tol);
    for (unsigned i=0; i < s.size();i++){
        double t0=s.cuts[i],t1=s.cuts[i+1];
        D2<SBasis> sub_M = compose(M,Linear(t0,t1));
        D2<SBasis> sub_u;
        for (unsigned dim=0;dim<2;dim++){
            SBasis sub_s = s.segs[i];
            sub_s-=sub_s.at0();
            sub_s/=sub_s.at1();
            sub_u[dim]=compose_inverse(sub_M[dim],sub_s, order, tol);
        }
        u.push(sub_u,s(t1));
    }
    return u;
}

Piecewise< SBasis > Geom::arcLengthSb	(	Piecewise< D2< SBasis > > const &	M,
		double	tol = .01
	)

returns a function giving the arclength at each point in M.

Parameters:

	M	the Element.
	tol	the maximum error allowed.

Definition at line 320 of file sbasis-geometric.cpp.

References derivative(), dot(), integral(), length(), M, Geom::Piecewise< T >::segs, and sqrt().

                                                            {
    Piecewise<D2<SBasis> > dM = derivative(M);
    Piecewise<SBasis> dMlength = sqrt(dot(dM,dM),tol,3);
    Piecewise<SBasis> length = integral(dMlength);
    length-=length.segs.front().at0();
    return length;
}

Piecewise< SBasis > Geom::arcLengthSb	(	D2< SBasis > const &	M,
		double	tol = .01
	)

returns a function giving the arclength at each point in M.

Parameters:

	M	the Element.
	tol	the maximum error allowed.

Definition at line 334 of file sbasis-geometric.cpp.

Referenced by arc_length_parametrization(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Inkscape::LivePathEffect::LPERuler::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), and SPCurve::stretch_endpoints().

                                                {
    return arcLengthSb(Piecewise<D2<SBasis> >(M), tol);
}

bool Geom::are_collinear	(	Point const &	p1,
		Point const &	p2,
		Point const &	p3,
		double	eps = EPSILON
	)			[inline]

Definition at line 293 of file line.h.

References are_near(), and cross().

{
    return are_near( cross(p3, p2) - cross(p3, p1) + cross(p2, p1), 0, eps);
}

bool Geom::are_near	(	Point const &	_point,
		Ray const &	_ray,
		double	eps = EPSILON
	)			[inline]

Definition at line 205 of file ray.h.

References are_near(), and distance().

{
    return are_near(distance(_point, _ray), 0, eps);
}

bool Geom::are_near	(	Point const &	a,
		Point const &	b,
		double const	eps = EPSILON
	)			[inline]

Definition at line 188 of file 2geom/point.h.

References are_near(), X, and Y.

                                                                               {
    return ( are_near(a[X],b[X],eps) && are_near(a[Y],b[Y],eps) );
}

bool Geom::are_near	(	Point const &	_point,
		LineSegment const &	_segment,
		double	eps = EPSILON
	)			[inline]

Definition at line 319 of file line.h.

References are_near(), and distance().

{
    return are_near(distance(_point, _segment), 0, eps);
}

bool Geom::are_near	(	Point const &	_point,
		Line const &	_line,
		double	eps = EPSILON
	)			[inline]

Definition at line 267 of file line.h.

References are_near(), and distance().

{
    return are_near(distance(_point, _line), 0, eps);
}

template<typename T >

bool Geom::are_near	(	D2< T > const &	a,
		D2< T > const &	b,
		double	tol
	)			[inline]

Definition at line 150 of file d2.h.

References are_near().

                                                     {
    boost::function_requires<NearConcept<T> >();
    return are_near(a[0], b[0]) && are_near(a[1], b[1]);
}

bool Geom::are_near	(	Coord	a,
		Coord	b,
		double	eps = EPSILON
	)			[inline]

Definition at line 54 of file coord.h.

Referenced by Inkscape::UI::PathManipulator::_createControlPointsFromGeometry(), Inkscape::UI::ControlPointSelection::_keyboardScale(), Inkscape::UI::TransformHandleSet::_updateVisibility(), Geom::SVGEllipticalArc::allNearestPoints(), Geom::EllipticalArc::allNearestPoints(), Inkscape::LivePathEffect::are_colinear(), are_collinear(), are_near(), are_orthogonal(), are_parallel(), are_same(), SvgPathGeomTest::bpathEqual(), Geom::SVGEllipticalArc::calculate_center_and_extreme_angles(), Geom::EllipticalArc::calculate_center_and_extreme_angles(), Inkscape::UI::SkewHandle::computeTransform(), Inkscape::UI::ScaleSideHandle::computeTransform(), Inkscape::UI::ScaleCornerHandle::computeTransform(), Geom::NearConcept< T >::constraints(), Inkscape::LivePathEffect::LPESpiro::doEffect(), Inkscape::LivePathEffect::LPECurveStitch::doEffect_path(), Inkscape::LivePathEffect::LPEExtrude::doEffect_pwd2(), Geom::detail::intersection_impl(), Geom::detail::bezier_clipping::is_constant(), is_straight_curve(), Geom::SVGEllipticalArc::isDegenerate(), Geom::EllipticalArc::isDegenerate(), Geom::Matrix::isIdentity(), Geom::Matrix::isRotation(), Geom::Matrix::isScale(), Geom::Matrix::isSingular(), Geom::Matrix::isTranslation(), Geom::Matrix::isUniformScale(), make_angle_bisector_ray(), Geom::make_elliptical_arc::make_elliptiarc(), Inkscape::UI::Handle::move(), Geom::SVGEllipticalArc::nearestPoint(), Geom::EllipticalArc::nearestPoint(), SPCurve::nodes_in_path(), Geom::Matrix::onlyScaleAndTranslation(), pick_coincident(), Geom::detail::bezier_clipping::pick_orientation_line(), Inkscape::UI::Node::pickBestType(), Geom::SVGEllipticalArc::portion(), Geom::EllipticalArc::portion(), Inkscape::LivePathEffect::LPECurveStitch::resetDefaults(), Inkscape::LivePathEffect::LPEBendPath::resetDefaults(), Geom::SVGEllipticalArc::roots(), Geom::EllipticalArc::roots(), Geom::Ellipse::set(), Geom::Ray::setBy2Points(), Geom::Line::setBy2Points(), Geom::Matrix::setExpansionX(), Geom::Matrix::setExpansionY(), Inkscape::UI::Handle::setPosition(), Inkscape::Extension::Internal::LaTeXTextRenderer::sp_flowtext_render(), sp_guide_description(), sp_svg_transform_write(), Inkscape::Extension::Internal::LaTeXTextRenderer::sp_text_render(), Geom::Ellipse::transformed(), Geom::Curve::unitTangentAt(), and SPDesktop::zoom_quick().

{ return fabs(a-b) <= eps; }

bool Geom::are_orthogonal	(	Line const &	l1,
		Line const &	l2,
		double	eps = EPSILON
	)			[inline]

Definition at line 286 of file line.h.

References are_near(), Geom::Point::ccw(), Geom::Point::cw(), and Geom::Line::versor().

{
    return ( are_near(l1.versor(), l2.versor().cw(), eps)
             || are_near(l1.versor(), l2.versor().ccw(), eps) );
}

bool Geom::are_parallel	(	Line const &	l1,
		Line const &	l2,
		double	eps = EPSILON
	)			[inline]

Definition at line 273 of file line.h.

References are_near(), and Geom::Line::versor().

Referenced by are_same().

{
    return ( are_near(l1.versor(), l2.versor(), eps)
             || are_near(l1.versor(), -l2.versor(), eps) );
}

bool Geom::are_same	(	Ray const &	r1,
		Ray const &	r2,
		double	eps = EPSILON
	)			[inline]

Definition at line 211 of file ray.h.

References are_near(), Geom::Ray::origin(), and Geom::Ray::versor().

{
    return are_near(r1.versor(), r2.versor(), eps)
            && are_near(r1.origin(), r2.origin(), eps);
}

bool Geom::are_same	(	Line const &	l1,
		Line const &	l2,
		double	eps = EPSILON
	)			[inline]

Definition at line 280 of file line.h.

References are_near(), are_parallel(), and Geom::Line::origin().

{
    return are_parallel(l1, l2, eps) && are_near(l1.origin(), l2, eps);
}

Piecewise< SBasis > Geom::atan2	(	Piecewise< D2< SBasis > >const &	vect,
		double	tol = .01,
		unsigned	order = 3
	)

Return a function which gives the angle of vect at each point.

Parameters:

	vect	a piecewise parameteric curve.
	tol	the maximum error allowed.
	order	the maximum degree to use for approximation

Definition at line 157 of file sbasis-geometric.cpp.

References Geom::detail::bezier_clipping::angle(), Geom::D2< T >::at0(), atan2(), Geom::Piecewise< T >::concat(), cutAtRoots(), Geom::Piecewise< T >::cuts, derivative(), divide(), Barcode::Code39Ext::i, integral(), RescaleForNonVanishingEnds(), org::w3c::dom::svg::result, Geom::Piecewise< T >::segs, Geom::Piecewise< T >::setDomain(), Geom::Piecewise< T >::size(), voronoi::x, and voronoi::y.

                                                                         {
    Piecewise<SBasis> result;
    Piecewise<D2<SBasis> > v = cutAtRoots(vect,tol);
    result.cuts.push_back(v.cuts.front());
    for (unsigned i=0; i<v.size(); i++){

        D2<SBasis> vi = RescaleForNonVanishingEnds(v.segs[i]);
        SBasis x=vi[0], y=vi[1];
        Piecewise<SBasis> angle;
        angle = divide (x*derivative(y)-y*derivative(x), x*x+y*y, tol, order);

        //TODO: I don't understand this - sign.
        angle = integral(-angle);
        Point vi0 = vi.at0(); 
        angle += -std::atan2(vi0[1],vi0[0]) - angle[0].at0();
        //TODO: deal with 2*pi jumps form one seg to the other...
        //TODO: not exact at t=1 because of the integral.
        //TODO: force continuity?

        angle.setDomain(Interval(v.cuts[i],v.cuts[i+1]));
        result.concat(angle);   
    }
    return result;
}

Piecewise< SBasis > Geom::atan2	(	D2< SBasis > const &	vect,
		double	tol = .01,
		unsigned	order = 3
	)

Return a function which gives the angle of vect at each point.

Parameters:

	vect	a piecewise parameteric curve.
	tol	the maximum error allowed.
	order	the maximum degree to use for approximation

Definition at line 188 of file sbasis-geometric.cpp.

References atan2().

                                                             {
    return atan2(Piecewise<D2<SBasis> >(vect),tol,order);
}

double Geom::atan2

(

Point const

p

)

Referenced by Inkscape::Text::Layout::_calculateCursorShapeForEmpty(), Inkscape::UI::ControlPointSelection::_keyboardRotate(), Inkscape::UI::Dialogs::GuidelinePropertiesDialog::_setup(), SPGuide::angle(), Geom::Ray::angle(), Geom::Line::angle(), Geom::detail::bezier_clipping::angle(), Avoid::angleBetween(), atan2(), Geom::SVGEllipticalArc::boundsExact(), Geom::EllipticalArc::boundsExact(), Geom::SVGEllipticalArc::calculate_center_and_extreme_angles(), Geom::EllipticalArc::calculate_center_and_extreme_angles(), Inkscape::Text::Layout::characterBoundingBox(), compute_ends(), Inkscape::LivePathEffect::LPEGears::doEffect_path(), Inkscape::Text::Layout::fitToPathAlign(), Proj::TransfMat3x4::get_infinite_angle(), get_snap_vector(), gr_knot_moved_handler(), grayMapSobel(), SpiralKnotHolderEntityOuter::knot_set(), SpiralKnotHolderEntityInner::knot_set(), StarKnotHolderEntity2::knot_set(), StarKnotHolderEntity1::knot_set(), ArcKnotHolderEntityEnd::knot_set(), ArcKnotHolderEntityStart::knot_set(), PatternKnotHolderEntityAngle::knot_set(), Avoid::Router::markConnectors(), Inkscape::UI::Widget::Rotateable::on_motion(), Inkscape::UI::Widget::Rotateable::on_release(), persp3d_rotate_VP(), Box3D::pos_angle(), Inkscape::Text::Layout::queryCursorShape(), Inkscape::SelTrans::rotateRequest(), Geom::Ellipse::set(), setup_path(), Inkscape::UI::Widget::RegisteredVector::setValue(), sp_color_wheel_button_press(), sp_color_wheel_motion_notify(), sp_color_wheel_render_hue_wheel(), sp_dt_guide_event(), sp_dyna_draw_apply(), sp_eraser_apply(), Inkscape::Extension::Internal::LaTeXTextRenderer::sp_flowtext_render(), sp_item_gradient_set_coords(), sp_pattern_extract_theta(), sp_selection_rotate_screen(), sp_shape_marker_get_transform(), sp_shape_marker_get_transform_at_end(), sp_shape_marker_get_transform_at_start(), sp_spiral_drag(), sp_star_drag(), sp_te_adjust_rotation_screen(), Inkscape::Extension::Internal::LaTeXTextRenderer::sp_text_render(), Gear::spawn(), spdc_pen_set_angle_distance_status_message(), spiro_seg_to_bpath(), NrPointFnsTest::testAtan2(), Geom::Ellipse::transformed(), tweak_colors_in_gradient(), and unclump_dist().

template<typename T >

T Geom::bernsteinValueAt	(	double	t,
		T const *	c_,
		unsigned	n
	)			[inline]

Definition at line 98 of file bezier.h.

References Barcode::Code39Ext::i.

Referenced by Geom::Bezier::valueAndDerivatives().

                                                             {
    double u = 1.0 - t;
    double bc = 1;
    double tn = 1;
    T tmp = c_[0]*u;
    for(unsigned i=1; i<n; i++){
        tn = tn*t;
        bc = bc*(n-i+1)/i;
        tmp = (tmp + tn*bc*c_[i])*u;
    }
    return (tmp + tn*t*c_[n]);
}

template<class T >

const T& Geom::between	(	const T &	min,
		const T &	max,
		const T &	x
	)			[inline]

Between function - returns true if a number x is within a range.

The values delimiting the range and the number must have the same type.

Definition at line 56 of file utils.h.

    { return min < x && max > x; }

static Geom::Point Geom::Bezier	(	Geom::Point const *	V,
		unsigned	degree,
		double	t,
		Geom::Point *	Left,
		Geom::Point *	Right
	)			[static]

Definition at line 188 of file solve-bezier-parametric.cpp.

References Barcode::Code39Ext::i, and lerp().

Referenced by Geom::BezierCurve< 1 >::BezierCurve(), derivative(), operator*(), operator+(), operator-(), operator/(), portion(), and reverse().

{
    Geom::Point Vtemp[degree+1][degree+1];

    /* Copy control points  */
    std::copy(V, V+degree+1, Vtemp[0]);

    /* Triangle computation */
    for (unsigned i = 1; i <= degree; i++) {    
        for (unsigned j = 0; j <= degree - i; j++) {
            Vtemp[i][j] = lerp(t, Vtemp[i-1][j], Vtemp[i-1][j+1]);
        }
    }
    
    for (unsigned j = 0; j <= degree; j++)
        Left[j]  = Vtemp[j][0];
    for (unsigned j = 0; j <= degree; j++)
        Right[j] = Vtemp[degree-j][j];

    return (Vtemp[degree][0]);
}

int Geom::bezier_fit_cubic	(	Point	bezier[],
		Point const	data[],
		int	len,
		double	error
	)

int Geom::bezier_fit_cubic	(	Point *	bezier,
		Point const *	data,
		int	len,
		double	error
	)

Fit a single-segment Bezier curve to a set of digitized points.

Returns:

Number of segments generated, or -1 on error.

Definition at line 116 of file bezier-utils.cpp.

References bezier_fit_cubic_r().

Referenced by Inkscape::UI::PathManipulator::_deleteStretch().

{
    return bezier_fit_cubic_r(bezier, data, len, error, 1);
}

int Geom::bezier_fit_cubic_full	(	Point	bezier[],
		int	split_points[],
		Point const	data[],
		int const	len,
		Point const &	tHat1,
		Point const &	tHat2,
		double const	error,
		unsigned const	max_beziers
	)

Fit a multi-segment Bezier curve to a set of digitized points, without possible weedout of identical points and NaNs.

Precondition:

data is uniqued, i.e. not exist i: data[i] == data[i + 1].

Parameters:

	max_beziers	Maximum number of generated segments
	Result	array, must be large enough for n. segments * 4 elements.

Referenced by fit_and_split(), and sp_spiral_fit_and_draw().

int Geom::bezier_fit_cubic_r	(	Point	bezier[],
		Point const	data[],
		int const	len,
		double const	error,
		unsigned const	max_beziers
	)

Fit a multi-segment Bezier curve to a set of digitized points, with possible weedout of identical points and NaNs.

Parameters:

	max_beziers	Maximum number of generated segments
	Result	array, must be large enough for n. segments * 4 elements.

Returns:

Number of segments generated, or -1 on error.

Referenced by bezier_fit_cubic(), fit_and_split(), interpolate(), and sketch_interpolate().

std::vector<Point> Geom::bezier_points

(

const D2< Bezier > &

a

)

[inline]

Definition at line 352 of file bezier.h.

References NR::d, Barcode::Code39Ext::i, uniconv-ext::p, and org::w3c::dom::svg::result.

Referenced by Geom::BezierCurve< 1 >::points().

                                                             {
    std::vector<Point> result;
    for(unsigned i = 0; i <= a[0].order(); i++) {
        Point p;
        for(unsigned d = 0; d < 2; d++) p[d] = a[d][i];
        result.push_back(p);
    }
    return result;
}

Point Geom::bezier_pt	(	unsigned const	degree,
		Point const	V[],
		double const	t
	)

Evaluate a Bezier curve at parameter value t.

Parameters:

	degree	The degree of the Bezier curve: 3 for cubic, 2 for quadratic etc. Must be less than 4.
	V	The control points for the Bezier curve. Must have (degree+1) elements.
	t	The "parameter" value, specifying whereabouts along the curve to evaluate. Typically in the range [0.0, 1.0].

Let s = 1 - t. BezierII(1, V) gives (s, t) * V, i.e. t of the way from V[0] to V[1]. BezierII(2, V) gives (s**2, 2*s*t, t**2) * V. BezierII(3, V) gives (s**3, 3 s**2 t, 3s t**2, t**3) * V.

The derivative of BezierII(i, V) with respect to t is i * BezierII(i-1, V'), where for all j, V'[j] = V[j + 1] - V[j].

Pascal's triangle.

Referenced by compute_hook(), compute_max_error_ratio(), and NewtonRaphsonRootFind().

void Geom::bezier_to_sbasis	(	D2< SBasis > &	sb,
		std::vector< Point > const &	bz
	)

Changes the basis of d2 p to be sbasis.

Parameters:

p

the d2 Bernstein basis polynomial

Returns:

the d2 Symmetric basis polynomial

if the degree is even q is the order in the symmetrical power basis, if the degree is odd q is the order + 1 n is always the polynomial degree, i. e. the Bezier order

void Geom::bezier_to_sbasis	(	SBasis &	sb,
		Bezier const &	bz
	)

Changes the basis of p to be sbasis.

Parameters:

p

the Bernstein basis polynomial

Returns:

the Symmetric basis polynomial

if the degree is even q is the order in the symmetrical power basis, if the degree is odd q is the order + 1 n is always the polynomial degree, i. e. the Bezier order

Definition at line 188 of file sbasis-to-bezier.cpp.

References binomial(), Geom::SBasis::clear(), Geom::Bezier::order(), Geom::SBasis::resize(), and sgn().

Referenced by handles_to_sbasis(), and Geom::Bezier::toSBasis().

{
    size_t n = bz.order();
    size_t q = (n+1) / 2;
    size_t even = (n & 1u) ? 0 : 1;
    sb.clear();
    sb.resize(q + even, Linear(0, 0));
    double Tjk;
    for (size_t k = 0; k < q; ++k)
    {
        for (size_t j = k; j < q; ++j)
        {
            Tjk = sgn(j, k) * binomial(n-j-k, j-k) * binomial(n, k);
            sb[j][0] += (Tjk * bz[k]);
            sb[j][1] += (Tjk * bz[n-k]); // n-j <-> [j][1]
        }
        for (size_t j = k+1; j < q; ++j)
        {
            Tjk = sgn(j, k) * binomial(n-j-k-1, j-k-1) * binomial(n, k);
            sb[j][0] += (Tjk * bz[n-k]);
            sb[j][1] += (Tjk * bz[k]);   // n-j <-> [j][1]
        }
    }
    if (even)
    {
        for (size_t k = 0; k < q; ++k)
        {
            Tjk = sgn(q,k) * binomial(n, k);
            sb[q][0] += (Tjk * (bz[k] + bz[n-k]));
        }
        sb[q][0] += (binomial(n, q) * bz[q]);
        sb[q][1] = sb[q][0];
    }
    sb[0][0] = bz[0];
    sb[0][1] = bz[n];
}

double Geom::binomial	(	unsigned int	n,
		unsigned int	k
	)			[inline]

Definition at line 77 of file sbasis-to-bezier.cpp.

Referenced by bezier_to_sbasis().

{
    return choose<double>(n, k);
}

void Geom::binomial_coefficients	(	std::vector< size_t > &	bc,
		size_t	n
	)

Referenced by Geom::NL::LFMBezier::LFMBezier().

Shape Geom::boolop	(	Shape const &	,
		Shape const &	,
		unsigned	flags,
		CrossingSet &
	)

Shape Geom::boolop	(	Shape const &	a,
		Shape const &	b,
		unsigned	flags
	)

Shape Geom::boolop	(	Shape const &	a,
		Shape const &	b,
		unsigned	flags,
		CrossingSet const &	crs
	)

Definition at line 231 of file 2geom/shape.cpp.

References append(), BOOLOP_EXCLUSION, BOOLOP_IDENTITY_A, BOOLOP_IDENTITY_B, BOOLOP_INTERSECT, BOOLOP_NEITHER, BOOLOP_SUBTRACT_A_B, BOOLOP_SUBTRACT_B_A, BOOLOP_UNION, content, Geom::Shape::content, Geom::Shape::inverse(), shape_boolean(), shape_boolean_ra(), shape_boolean_rb(), and THROW_NOTIMPLEMENTED.

                                                                                     {
    THROW_NOTIMPLEMENTED();
    flags &= 15;
    if(flags <= BOOLOP_UNION) {
        switch(flags) {
            case BOOLOP_INTERSECT:    return shape_boolean(true, a, b, crs);
            case BOOLOP_SUBTRACT_A_B: return shape_boolean_rb(true, a, b, crs);
            case BOOLOP_IDENTITY_A:   return a;
            case BOOLOP_SUBTRACT_B_A: return shape_boolean_ra(true, a, b, crs);
            case BOOLOP_IDENTITY_B:   return b;
            case BOOLOP_EXCLUSION: {
                Shape res = shape_boolean_rb(true, a, b, crs);
                append(res.content, shape_boolean_ra(true, a, b, crs).content);
                return res;
            }
            case BOOLOP_UNION:        return shape_boolean(false, a, b);
        }
    } else {
        flags = ~flags & 15;
        switch(flags - BOOLOP_NEITHER) {
            case BOOLOP_SUBTRACT_A_B: return shape_boolean_ra(false, a, b, crs);
            case BOOLOP_SUBTRACT_B_A: return shape_boolean_rb(false, a, b, crs);
            case BOOLOP_EXCLUSION: {
                Shape res = shape_boolean_ra(false, a, b, CrossingSet(crs));
                append(res.content, shape_boolean_rb(false, a, b, CrossingSet(crs)).content);
                return res;
            }
        }
        return boolop(a, b, flags, crs).inverse();
    }
    return Shape();
}

template<typename C >

std::vector<Rect> Geom::bounds

(

C const &

a

)

[inline]

Definition at line 130 of file crossing.h.

References Barcode::Code39Ext::i.

Referenced by Geom::Path::boundsExact(), Geom::Path::boundsFast(), Geom::Shape::containment_list(), Geom::Crosser< Path >::crossings(), curve_sweep(), Inkscape::Extension::Internal::Grid::effect(), outer_crossing(), set_to_accumulated(), sp_canvas_group_update(), sp_export_detect_size(), sp_export_selection_modified(), sp_selection_tile(), and sp_selection_to_marker().

                                   {
    std::vector<Rect> rs;
    for (unsigned i = 0; i < a.size(); i++) {
        OptRect bb = a[i].boundsFast();
        if (bb) {
            rs.push_back(*bb);
        }
    }
    return rs;
}

OptInterval Geom::bounds_exact

(

SBasis const &

a

)

Find the smallest interval that bounds a.

Parameters:

a

sbasis function

Returns:

inteval

template<typename T >

FragmentConcept<T>::BoundsType Geom::bounds_exact

(

const Piecewise< T > &

f

)

[inline]

Definition at line 280 of file piecewise.h.

References bounds_exact(), Geom::Piecewise< T >::empty(), Barcode::Code39Ext::i, and Geom::Piecewise< T >::size().

                                                                                 {
    boost::function_requires<FragmentConcept<T> >();

    if(f.empty()) return typename FragmentConcept<T>::BoundsType();
    typename FragmentConcept<T>::BoundsType ret(bounds_exact(f[0]));
    for(unsigned i = 1; i < f.size(); i++)
        ret.unionWith(bounds_exact(f[i]));
    return ret;
}

OptRect Geom::bounds_exact

(

PathVector const &

pv

)

template<typename T >

OptRect Geom::bounds_exact

(

const D2< T > &

a

)

[inline]

Definition at line 441 of file d2.h.

References bounds_exact(), X, and Y.

                                     {
    boost::function_requires<FragmentConcept<T> >();
    return OptRect(bounds_exact(a[X]), bounds_exact(a[Y]));
}

OptInterval Geom::bounds_exact

(

Bezier const &

b

)

[inline]

Definition at line 388 of file bezier.h.

References Geom::Bezier::toSBasis().

Referenced by bounds_exact(), bounds_local(), Geom::SBasisCurve::boundsExact(), Geom::BezierCurve< 1 >::boundsExact(), Geom::FragmentConcept< T >::constraints(), Inkscape::LivePathEffect::LPECurveStitch::doEffect_path(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Inkscape::LivePathEffect::LPERoughHatches::doEffect_pwd2(), Inkscape::LivePathEffect::LPERecursiveSkeleton::doEffect_pwd2(), Inkscape::LivePathEffect::LPEPatternAlongPath::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), Inkscape::LivePathEffect::LPERoughHatches::linearSnake(), and Inkscape::LivePathEffect::LPECurveStitch::resetDefaults().

                                                  {
    return bounds_exact(b.toSBasis());
}

OptInterval Geom::bounds_fast	(	const SBasis &	sb,
		int	order
	)

Find a small interval that bounds a.

Parameters:

a

sbasis function

Returns:

inteval

template<typename T >

FragmentConcept<T>::BoundsType Geom::bounds_fast

(

const Piecewise< T > &

f

)

[inline]

Definition at line 269 of file piecewise.h.

References bounds_fast(), Geom::Piecewise< T >::empty(), Barcode::Code39Ext::i, and Geom::Piecewise< T >::size().

                                                                                {
    boost::function_requires<FragmentConcept<T> >();

    if(f.empty()) return typename FragmentConcept<T>::BoundsType();
    typename FragmentConcept<T>::BoundsType ret(bounds_fast(f[0]));
    for(unsigned i = 1; i < f.size(); i++)
        ret.unionWith(bounds_fast(f[i]));
    return ret;
}

OptRect Geom::bounds_fast

(

PathVector const &

pv

)

template<typename T >

OptRect Geom::bounds_fast

(

const D2< T > &

a

)

[inline]

Definition at line 436 of file d2.h.

References bounds_fast(), X, and Y.

                                    {
    boost::function_requires<FragmentConcept<T> >();
    return OptRect(bounds_fast(a[X]), bounds_fast(a[Y]));
}

OptInterval Geom::bounds_fast

(

Bezier const &

b

)

[inline]

Definition at line 383 of file bezier.h.

References Geom::Interval::fromArray(), and Geom::Bezier::size().

Referenced by bounds_fast(), bounds_local(), Geom::SBasisCurve::boundsFast(), Geom::BezierCurve< 1 >::boundsFast(), compose(), Geom::FragmentConcept< T >::constraints(), subdiv_sbasis(), and Geom::SBasis::tailError().

                                                 {
    return Interval::fromArray(&const_cast<Bezier&>(b).c_[0], b.size());
}

OptInterval Geom::bounds_local	(	const SBasis &	sb,
		const OptInterval &	i,
		int	order
	)

Find a small interval that bounds a(t) for t in i to order order.

Parameters:

	sb	sbasis function
	i	domain interval
	order	number of terms

Returns:

interval

template<typename T >

FragmentConcept<T>::BoundsType Geom::bounds_local	(	const Piecewise< T > &	f,
		const OptInterval &	_m
	)			[inline]

Definition at line 291 of file piecewise.h.

References bounds_exact(), bounds_local(), Geom::Piecewise< T >::empty(), org::w3c::dom::svg::f, Barcode::Code39Ext::i, Geom::Interval::isSingular(), Geom::Interval::max(), Geom::Interval::min(), Geom::Piecewise< T >::segN(), and Geom::Piecewise< T >::segT().

                                                                                                        {
    boost::function_requires<FragmentConcept<T> >();

    if(f.empty() || !_m) return typename FragmentConcept<T>::BoundsType();
    Interval const &m = *_m;
    if(m.isSingular()) return typename FragmentConcept<T>::BoundsType(f(m.min()));

    unsigned fi = f.segN(m.min()), ti = f.segN(m.max());
    double ft = f.segT(m.min(), fi), tt = f.segT(m.max(), ti);

    if(fi == ti) return bounds_local(f[fi], Interval(ft, tt));

    typename FragmentConcept<T>::BoundsType ret(bounds_local(f[fi], Interval(ft, 1.)));
    for(unsigned i = fi + 1; i < ti; i++)
        ret.unionWith(bounds_exact(f[i]));
    if(tt != 0.) ret.unionWith(bounds_local(f[ti], Interval(0., tt)));

    return ret;
}

template<typename T >

OptRect Geom::bounds_local	(	const D2< T > &	a,
		const OptInterval &	t
	)			[inline]

Definition at line 446 of file d2.h.

References bounds_local(), X, and Y.

                                                           {
    boost::function_requires<FragmentConcept<T> >();
    return OptRect(bounds_local(a[X], t), bounds_local(a[Y], t));
}

OptInterval Geom::bounds_local	(	Bezier const &	b,
		OptInterval	i
	)			[inline]

Definition at line 392 of file bezier.h.

References bounds_fast(), and portion().

Referenced by bounds_local(), Geom::SBasisCurve::boundsLocal(), Geom::BezierCurve< 1 >::boundsLocal(), Geom::FragmentConcept< T >::constraints(), and multi_roots_internal().

                                                                 {
    //return bounds_local(b.toSBasis(), i);
    if (i) {
        return bounds_fast(portion(b, i->min(), i->max()));
    } else {
        return OptInterval();
    }
}

std::vector< Point > Geom::bridge_points	(	ConvexHull	a,
		ConvexHull	b
	)

pair< map<int, int>, map<int, int> > Geom::bridges	(	ConvexHull	a,
		ConvexHull	b
	)

Definition at line 348 of file convex-cover.cpp.

References Geom::ConvexHull::boundary, cross(), NR::d, addnodes::e, org::w3c::dom::svg::f, and h.

                                    {
    map<int, int> abridges;
    map<int, int> bbridges;

    for(unsigned ia = 0; ia < a.boundary.size(); ia++) {
        for(unsigned ib = 0; ib < b.boundary.size(); ib++) {
            Point d = b[ib] - a[ia];
            Geom::Coord e = cross(d, a[ia - 1] - a[ia]), f = cross(d, a[ia + 1] - a[ia]);
            Geom::Coord g = cross(d, b[ib - 1] - a[ia]), h = cross(d, b[ib + 1] - a[ia]);
            if     (e > 0 && f > 0 && g > 0 && h > 0) abridges[ia] = ib;
            else if(e < 0 && f < 0 && g < 0 && h < 0) bbridges[ib] = ia;
        }
    }

    return make_pair(abridges, bbridges);
}

void Geom::build_from_sbasis	(	Geom::PathBuilder &	pb,
		D2< SBasis > const &	B,
		double	tol,
		bool	only_cubicbeziers
	)

Make a path from a d2 sbasis.

Parameters:

p

the d2 Symmetric basis polynomial

Returns:

a Path

If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves.

Definition at line 342 of file sbasis-to-bezier.cpp.

References Geom::D2< T >::at1(), compose(), Geom::SVGPathGenerator< OutputIterator >::curveTo(), Geom::D2< T >::isFinite(), Geom::SVGPathGenerator< OutputIterator >::lineTo(), sbasis_size(), sbasis_to_bezier(), tail_error(), and THROW_EXCEPTION.

                                                                                                     {
    if (!B.isFinite()) {
        THROW_EXCEPTION("assertion failed: B.isFinite()");
    }
    if(tail_error(B, 2) < tol || sbasis_size(B) == 2) { // nearly cubic enough
        if( !only_cubicbeziers && (sbasis_size(B) <= 1) ) {
            pb.lineTo(B.at1());
        } else {
            std::vector<Geom::Point> bez;
            sbasis_to_bezier(bez, B, 4);
            pb.curveTo(bez[1], bez[2], bez[3]);
        }
    } else {
        build_from_sbasis(pb, compose(B, Linear(0, 0.5)), tol, only_cubicbeziers);
        build_from_sbasis(pb, compose(B, Linear(0.5, 1)), tol, only_cubicbeziers);
    }
}

unsigned Geom::centroid	(	Piecewise< D2< SBasis > > const &	p,
		Point &	centroid,
		double &	area
	)

Centroid using sbasis integration.

Parameters:

	p	the Element.
	centroid	on return contains the centroid of the shape
	area	on return contains the signed area of the shape.

This approach uses green's theorem to compute the area and centroid using integrals. For curved shapes this is much faster than converting to polyline. Note that without an uncross operation the output is not the absolute area.

Returned values: 0 for normal execution; 2 if area is zero, meaning centroid is meaningless.

Definition at line 518 of file sbasis-geometric.cpp.

References Geom::D2< T >::at0(), Geom::SBasis::at0(), Geom::D2< T >::at1(), Geom::SBasis::at1(), cross(), derivative(), dot(), Barcode::Code39Ext::i, integral(), multiply(), uniconv-ext::p, and rot90().

                                                                                      {
    Point centroid_tmp(0,0);
    double atmp = 0;
    for(unsigned i = 0; i < p.size(); i++) {
        SBasis curl = dot(p[i], rot90(derivative(p[i])));
        SBasis A = integral(curl);
        D2<SBasis> C = integral(multiply(curl, p[i]));
        atmp += A.at1() - A.at0();
        centroid_tmp += C.at1()- C.at0(); // first moment.
    }
// join ends
    centroid_tmp *= 2;
    Point final = p[p.size()-1].at1(), initial = p[0].at0();
    const double ai = cross(final, initial);
    atmp += ai;
    centroid_tmp += (final + initial)*ai; // first moment.
    
    area = atmp / 2;
    if (atmp != 0) {
        centroid = centroid_tmp / (3 * atmp);
        return 0;
    }
    return 2;
}

int Geom::centroid	(	std::vector< Geom::Point > const &	p,
		Geom::Point &	centroid,
		double &	area
	)

polyCentroid: Calculates the centroid (xCentroid, yCentroid) and area of a polygon, given its vertices (x[0], y[0]) .

.. (x[n-1], y[n-1]). It is assumed that the contour is closed, i.e., that the vertex following (x[n-1], y[n-1]) is (x[0], y[0]). The algebraic sign of the area is positive for counterclockwise ordering of vertices in x-y plane; otherwise negative.

Returned values: 0 for normal execution; 1 if the polygon is degenerate (number of vertices < 3); 2 if area = 0 (and the centroid is undefined).

for now we require the path to be a polyline and assume it is closed.

Referenced by Inkscape::LivePathEffect::LPEPathLength::doEffect_pwd2().

SBasis Geom::cheb

(

unsigned

n

)

Definition at line 14 of file chebyshev.cpp.

References Barcode::Code39Ext::i, and Geom::SBasis::push_back().

Referenced by cheb_series().

                        {
    static std::vector<SBasis> basis;
    if(basis.empty()) {
        basis.push_back(Linear(1,1));
        basis.push_back(Linear(0,1));
    }
    for(unsigned i = basis.size(); i <= n; i++) {
        basis.push_back(Linear(0,2)*basis[i-1] - basis[i-2]);
    }
    
    return basis[n];
}

SBasis Geom::cheb_series	(	unsigned	n,
		double *	cheb_coeff
	)

Definition at line 27 of file chebyshev.cpp.

References cheb(), Barcode::Code39Ext::i, and polyhedron_3d::r.

                                                   {
    SBasis r;
    for(unsigned i = 0; i < n; i++) {
        double cof = cheb_coeff[i];
        //if(i == 0)
        //cof /= 2;
        r += cheb(i)*cof;
    }
    
    return r;
}

SBasis Geom::chebyshev

(

unsigned

n

)

SBasis Geom::chebyshev_approximant	(	double(*)(double, void *)	f,
		int	order,
		Interval	in,
		void *	p
	)

SBasis Geom::chebyshev_approximant_interpolating	(	double(*)(double, void *)	f,
		int	order,
		Interval	in,
		void *	p
	)

static void Geom::chord_length_parameterize	(	Point const	d[],
		double	u[],
		unsigned const	len
	)			[static]

Assign parameter values to digitized points using relative distances between points.

Precondition:

Parameter array u must have space for len items.

Todo:

It's been reported that u[len - 1] can differ from 1.0 on some systems (amd64), despite it having been calculated as x / x where x is isFinite and non-zero.

Todo:

It's been reported that u[len - 1] can differ from 1.0 on some systems (amd64), despite it having been calculated as x / x where x is isFinite and non-zero.

Definition at line 841 of file bezier-utils.cpp.

References distance(), double, addnodes::e, Barcode::Code39Ext::i, and IS_FINITE.

{
    if(!( 2 <= len ))
        return;

    /* First let u[i] equal the distance travelled along the path from d[0] to d[i]. */
    u[0] = 0.0;
    for (unsigned i = 1; i < len; i++) {
        double const dist = distance(d[i], d[i-1]);
        u[i] = u[i-1] + dist;
    }

    /* Then scale to [0.0 .. 1.0]. */
    double tot_len = u[len - 1];
    if(!( tot_len != 0 ))
        return;
    if (IS_FINITE(tot_len)) {
        for (unsigned i = 1; i < len; ++i) {
            u[i] /= tot_len;
        }
    } else {
        /* We could do better, but this probably never happens anyway. */
        for (unsigned i = 1; i < len; ++i) {
            u[i] = i / (double) ( len - 1 );
        }
    }

    if (u[len - 1] != 1) {
        double const diff = u[len - 1] - 1;
        if (fabs(diff) > 1e-13) {
            assert(0); // No warnings in 2geom
            //g_warning("u[len - 1] = %19g (= 1 + %19g), expecting exactly 1",
            //          u[len - 1], diff);
        }
        u[len - 1] = 1;
    }

#ifdef BEZIER_DEBUG
    assert( u[0] == 0.0 && u[len - 1] == 1.0 );
    for (unsigned i = 1; i < len; i++) {
        assert( u[i] >= u[i-1] );
    }
#endif
}

int Geom::circle_circle_intersection	(	Point	X0,
		double	r0,
		Point	X1,
		double	r1,
		Point &	p0,
		Point &	p1
	)

Definition at line 49 of file circle-circle.cpp.

References org::w3c::dom::svg::a, NR::d, h, L2(), polyhedron_3d::r, rot90(), and sqrt().

{
  /* dx and dy are the vertical and horizontal distances between
   * the circle centers.
   */
  Point D = X1 - X0;

  /* Determine the straight-line distance between the centers. */
  double d = L2(D);

  /* Check for solvability. */
  if (d > (r0 + r1))
  {
    /* no solution. circles do not intersect. */
    return 0;
  }
  if (d <= fabs(r0 - r1))
  {
    /* no solution. one circle is contained in the other */
    return 1;
  }
  
  /* 'point 2' is the point where the line through the circle
   * intersection points crosses the line between the circle
   * centers.  
   */

  /* Determine the distance from point 0 to point 2. */
  double a = ((r0*r0) - (r1*r1) + (d*d)) / (2.0 * d) ;

  /* Determine the coordinates of point 2. */
  Point p2 = X0 + D * (a/d);

  /* Determine the distance from point 2 to either of the
   * intersection points.
   */
  double h = sqrt((r0*r0) - (a*a));

  /* Now determine the offsets of the intersection points from
   * point 2.
   */
  Point r = (h/d)*rot90(D);

  /* Determine the absolute intersection points. */
  p0 = p2 + r;
  p1 = p2 - r;

  return 2;
}

void Geom::clean	(	Crossings &	,
		Crossings &
	)

SBasis Geom::clenshaw_series	(	unsigned	m,
		double *	cheb_coeff
	)

b_n = a_n b_n-1 = 2*x*b_n + a_n-1 b_n-k = 2*x*b_{n-k+1} + a_{n-k} - b_{n - k + 2} b_0 = x*b_1 + a_0 - b_2

Definition at line 39 of file chebyshev.cpp.

References org::w3c::dom::svg::a, b, NR::d, and voronoi::y.

                                                       {
    double a = -1, b = 1;
    SBasis d, dd;
    SBasis y = (Linear(0, 2) - (a+b)) / (b-a);
    SBasis y2 = 2*y;
    for(int j = m - 1; j >= 1; j--) {
        SBasis sv = d;
        d = y2*d - dd + cheb_coeff[j];
        dd = sv;
    }
    
    return y*d - dd + 0.5*cheb_coeff[0];
}

ConvexHull Geom::clip	(	ConvexHull const &	ch,
		Point	n,
		double	d
	)

SBasis Geom::compose	(	SBasis const &	a,
		SBasis const &	b,
		unsigned	k
	)

Compute a composed with b to k terms.

Parameters:

a,b

sbasis functions

Returns:

sbasis a(b(t))

return a0 + s(a1 + s(a2 +... where s = (1-u)u; ak =(1 - u)a^0_k + ua^1_k

SBasis Geom::compose	(	SBasis const &	a,
		SBasis const &	b
	)

Compute a composed with b.

Parameters:

a,b

sbasis functions

Returns:

sbasis a(b(t))

return a0 + s(a1 + s(a2 +... where s = (1-u)u; ak =(1 - u)a^0_k + ua^1_k

SBasis2d Geom::compose	(	SBasis2d const &	a,
		SBasis2d const &	b,
		unsigned	k
	)

SBasis2d Geom::compose	(	SBasis2d const &	a,
		SBasis2d const &	b
	)

SBasis Geom::compose	(	SBasis2d const &	fg,
		D2< SBasis > const &	p
	)

SBasis Geom::compose	(	Linear2d const &	a,
		D2< SBasis > const &	p
	)

Poly Geom::compose	(	Poly const &	a,
		Poly const &	b
	)

template<typename T >

Piecewise<T> Geom::compose	(	Piecewise< T > const &	f,
		Piecewise< SBasis > const &	g
	)			[inline]

Definition at line 712 of file piecewise.h.

References compose(), Geom::Piecewise< T >::concat(), Geom::Piecewise< T >::cuts, Barcode::Code39Ext::i, org::w3c::dom::svg::result, Geom::Piecewise< T >::segs, and Geom::Piecewise< T >::setDomain().

                                                                       {
  Piecewise<T> result;
  for(unsigned i = 0; i < g.segs.size(); i++){
      Piecewise<T> fgi=compose(f, g.segs[i]);
      fgi.setDomain(Interval(g.cuts[i], g.cuts[i+1]));
      result.concat(fgi);
  }
  return result;
}

template<typename T >

Piecewise<T> Geom::compose	(	Piecewise< T > const &	f,
		SBasis const &	g
	)			[inline]

Definition at line 666 of file piecewise.h.

References bounds_fast(), compose(), compose_findSegIdx(), compose_pullback(), Geom::Piecewise< T >::cuts, Geom::Piecewise< T >::empty(), org::w3c::dom::svg::f, Geom::SBasis::isZero(), Geom::Interval::max(), Geom::Interval::min(), Geom::Piecewise< T >::push(), org::w3c::dom::svg::result, Geom::Piecewise< T >::segs, and Geom::Piecewise< T >::size().

                                                            {
    Piecewise<T> result;
    if (f.empty()) return result;
    if (g.isZero()) return Piecewise<T>(f(0));
    if (f.size()==1){
        double t0 = f.cuts[0], width = f.cuts[1] - t0;
        return (Piecewise<T>) compose(f.segs[0],compose(Linear(-t0 / width, (1-t0) / width), g));
    }

    //first check bounds...
    Interval bs = *bounds_fast(g);
    if (f.cuts.front() > bs.max()  || bs.min() > f.cuts.back()){
        int idx = (bs.max() < f.cuts[1]) ? 0 : f.cuts.size()-2;
        double t0 = f.cuts[idx], width = f.cuts[idx+1] - t0;
        return (Piecewise<T>) compose(f.segs[idx],compose(Linear(-t0 / width, (1-t0) / width), g));
    }

    std::vector<double> levels;//we can forget first and last cuts...
    levels.insert(levels.begin(),f.cuts.begin()+1,f.cuts.end()-1);
    //TODO: use a std::vector<pairs<double,unsigned> > instead of a map<double,unsigned>.
    std::map<double,unsigned> cuts_pb = compose_pullback(levels,g);

    //-- Compose each piece of g with the relevant seg of f.
    result.cuts.push_back(0.);
    std::map<double,unsigned>::iterator cut=cuts_pb.begin();
    std::map<double,unsigned>::iterator next=cut; next++;
    while(next!=cuts_pb.end()){
        //assert(std::abs(int((*cut).second-(*next).second))<1);
        //TODO: find a way to recover from this error? the root finder missed some root;
        //  the levels/variations of f might be too close/fast...
        int idx = compose_findSegIdx(cut,next,levels,g);
        double t0=(*cut).first;
        double t1=(*next).first;

        SBasis sub_g=compose(g, Linear(t0,t1));
        sub_g=compose(Linear(-f.cuts[idx]/(f.cuts[idx+1]-f.cuts[idx]),
                             (1-f.cuts[idx])/(f.cuts[idx+1]-f.cuts[idx])),sub_g);
        result.push(compose(f[idx],sub_g),t1);
        cut++;
        next++;
    }
    return(result);
}

template<typename T >

D2<T> Geom::compose	(	D2< T > const &	a,
		T const &	b
	)			[inline]

Definition at line 364 of file d2.h.

References Barcode::Code39Ext::i, and polyhedron_3d::r.

Referenced by arc_length_parametrization(), Inkscape::LivePathEffect::bend(), build_from_sbasis(), compose(), compose_each(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Inkscape::LivePathEffect::LPERecursiveSkeleton::doEffect_pwd2(), Inkscape::LivePathEffect::LPEPatternAlongPath::doEffect_pwd2(), Inkscape::LivePathEffect::LPEEnvelope::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), Inkscape::LivePathEffect::LPEBendPath::doEffect_pwd2(), Inkscape::Whiteboard::XMLNodeTracker::generateKey(), Inkscape::Widgets::LayerSelector::LayerSelector(), Geom::SBasis::operator()(), Geom::Piecewise< T >::operator()(), Gear::path(), portion(), solve_lambda0(), sqrt_internal(), subdiv_sbasis(), and unitVector().

                                      {
    D2<T> r;
    for(unsigned i = 0; i < 2; i++)
        r[i] = compose(a[i],b);
    return r;
}

D2< SBasis > Geom::compose_each	(	D2< SBasis2d > const &	fg,
		D2< SBasis > const &	p
	)

template<typename T >

D2<T> Geom::compose_each	(	T const &	a,
		D2< T > const &	b
	)			[inline]

Definition at line 382 of file d2.h.

References compose(), Barcode::Code39Ext::i, and polyhedron_3d::r.

                                           {
    D2<T> r;
    for(unsigned i = 0; i < 2; i++)
        r[i] = compose(a,b[i]);
    return r;
}

template<typename T >

D2<T> Geom::compose_each	(	D2< T > const &	a,
		D2< T > const &	b
	)			[inline]

Definition at line 373 of file d2.h.

References compose(), Barcode::Code39Ext::i, and polyhedron_3d::r.

Referenced by Inkscape::LivePathEffect::LPELattice::doEffect_pwd2().

                                               {
    D2<T> r;
    for(unsigned i = 0; i < 2; i++)
        r[i] = compose(a[i],b[i]);
    return r;
}

int Geom::compose_findSegIdx	(	std::map< double, unsigned >::iterator const &	cut,
		std::map< double, unsigned >::iterator const &	next,
		std::vector< double > const &	levels,
		SBasis const &	g
	)

Referenced by compose().

SBasis Geom::compose_inverse	(	SBasis const &	f,
		SBasis const &	g,
		unsigned	order,
		double	zero
	)

compute fog^-1.

Parameters:

f,g

sbasis functions

Returns:

sbasis f(g^-1(t)).

("zero" = double comparison threshold. *!*we might divide by "zero"*!*) TODO: compute order according to tol? TODO: requires g(0)=0 & g(1)=1 atm... adaptation to other cases should be obvious!

Referenced by arc_length_parametrization().

std::map< double, unsigned > Geom::compose_pullback	(	std::vector< double > const &	values,
		SBasis const &	g
	)

Referenced by compose().

static double Geom::compute_hook	(	Point const &	a,
		Point const &	b,
		double const	u,
		BezierCurve const	bezCurve,
		double const	tolerance
	)			[static]

Whereas compute_max_error_ratio() checks for itself that each data point is near some point on the curve, this function checks that each point on the curve is near some data point (or near some point on the polyline defined by the data points, or something like that: we allow for a "reasonable curviness" from such a polyline).

"Reasonable curviness" means we draw a circle centred at the midpoint of a..b, of radius proportional to the length |a - b|, and require that each point on the segment of bezCurve between the parameters of a and b be within that circle. If any point P on the bezCurve segment is outside of that allowable region (circle), then we return some metric that increases with the distance from P to the circle.

Given that this is a fairly arbitrary criterion for finding appropriate places for sharp corners, we test only one point on bezCurve, namely the point on bezCurve with parameter halfway between our estimated parameters for a and b. (Alternatives are taking the farthest of a few parameters between those of a and b, or even using a variant of NewtonRaphsonFindRoot() for finding the maximum rather than minimum distance.)

Todo:

effic: Hooks are very rare. We could start by comparing distsq, only resorting to the more expensive L2 in cases of uncertainty.

Todo:

effic: Hooks are very rare. We could start by comparing distsq, only resorting to the more expensive L2 in cases of uncertainty.

Definition at line 977 of file bezier-utils.cpp.

References bezier_pt(), and distance().

Referenced by compute_max_error_ratio().

{
    Point const P = bezier_pt(3, bezCurve, u);
    double const dist = distance((a+b)*.5, P);
    if (dist < tolerance) {
        return 0;
    }
    double const allowed = distance(a, b) + tolerance;
    return dist / allowed;
}

static double Geom::compute_max_error_ratio	(	Point const	d[],
		double const	u[],
		unsigned const	len,
		BezierCurve const	bezCurve,
		double const	tolerance,
		unsigned *const	splitPoint
	)			[static]

Find the maximum squared distance of digitized points to fitted curve, and (if this maximum error is non-zero) set *splitPoint to the corresponding index.

Precondition:

2 <= len.

u[0] == 0.

u[len - 1] == 1.0.

Postcondition:

((ret == 0.0) || ((*splitPoint < len - 1) && (*splitPoint != 0 || ret < 0.0))).

Definition at line 906 of file bezier-utils.cpp.

References bezier_pt(), compute_hook(), Barcode::Code39Ext::i, lensq(), and sqrt().

{
    assert( 2 <= len );
    unsigned const last = len - 1;
    assert( bezCurve[0] == d[0] );
    assert( bezCurve[3] == d[last] );
    assert( u[0] == 0.0 );
    assert( u[last] == 1.0 );
    /* I.e. assert that the error for the first & last points is zero.
     * Otherwise we should include those points in the below loop.
     * The assertion is also necessary to ensure 0 < splitPoint < last.
     */

    double maxDistsq = 0.0; /* Maximum error */
    double max_hook_ratio = 0.0;
    unsigned snap_end = 0;
    Point prev = bezCurve[0];
    for (unsigned i = 1; i <= last; i++) {
        Point const curr = bezier_pt(3, bezCurve, u[i]);
        double const distsq = lensq( curr - d[i] );
        if ( distsq > maxDistsq ) {
            maxDistsq = distsq;
            *splitPoint = i;
        }
        double const hook_ratio = compute_hook(prev, curr, .5 * (u[i - 1] + u[i]), bezCurve, tolerance);
        if (max_hook_ratio < hook_ratio) {
            max_hook_ratio = hook_ratio;
            snap_end = i;
        }
        prev = curr;
    }

    double const dist_ratio = sqrt(maxDistsq) / tolerance;
    double ret;
    if (max_hook_ratio <= dist_ratio) {
        ret = dist_ratio;
    } else {
        assert(0 < snap_end);
        ret = -max_hook_ratio;
        *splitPoint = snap_end - 1;
    }
    assert( ret == 0.0
              || ( ( *splitPoint < last )
                   && ( *splitPoint != 0 || ret < 0. ) ) );
    return ret;
}

static double Geom::compute_x_intercept	(	Geom::Point const *	V,
		unsigned	degree
	)			[static]

Definition at line 172 of file solve-bezier-parametric.cpp.

References X, and Y.

{
    const Geom::Point A = V[degree] - V[0];

    return (A[Geom::X]*V[0][Geom::Y] - A[Geom::Y]*V[0][Geom::X]) / -A[Geom::Y];
}

Point Geom::constrain_angle	(	Point const &	A,
		Point const &	B,
		unsigned int	n,
		Point const &	dir
	)

Constrains the angle (with respect to dir) of the line joining A and B to a multiple of pi/n.

Referenced by Inkscape::UI::Handle::dragged().

bool Geom::contains	(	Path const &	p,
		Point	i,
		bool	evenodd = true
	)			[inline]

Definition at line 49 of file path-intersection.h.

References winding().

Referenced by Avoid::EdgeInf::firstBlocker().

                                                                   {
    return (evenodd ? winding(p, i) % 2 : winding(p, i)) != 0;
}

static unsigned Geom::control_poly_flat_enough	(	Geom::Point const *	V,
		unsigned	degree
	)			[static]

Definition at line 112 of file solve-bezier-parametric.cpp.

References org::w3c::dom::svg::a, b, BEPSILON, c, NR::d, Avoid::dist(), distance(), error(), Barcode::Code39Ext::i, max(), min(), X, and Y.

{
    /* Find the perpendicular distance from each interior control point to line connecting V[0] and
     * V[degree] */

    /* Derive the implicit equation for line connecting first */
    /*  and last control points */
    const double a = V[0][Geom::Y] - V[degree][Geom::Y];
    const double b = V[degree][Geom::X] - V[0][Geom::X];
    const double c = V[0][Geom::X] * V[degree][Geom::Y] - V[degree][Geom::X] * V[0][Geom::Y];

    const double abSquared = (a * a) + (b * b);

    double distance[degree]; /* Distances from pts to line */
    for (unsigned i = 1; i < degree; i++) {
        /* Compute distance from each of the points to that line */
        double & dist(distance[i-1]);
        const double d = a * V[i][Geom::X] + b * V[i][Geom::Y] + c;
        dist = d*d / abSquared;
        if (d < 0.0)
            dist = -dist;
    }


    // Find the largest distance
    double max_distance_above = 0.0;
    double max_distance_below = 0.0;
    for (unsigned i = 0; i < degree-1; i++) {
        const double d = distance[i];
        if (d < 0.0)
            max_distance_below = std::min(max_distance_below, d);
        if (d > 0.0)
            max_distance_above = std::max(max_distance_above, d);
    }

    const double intercept_1 = (c + max_distance_above) / -a;
    const double intercept_2 = (c + max_distance_below) / -a;

    /* Compute bounding interval*/
    const double left_intercept = std::min(intercept_1, intercept_2);
    const double right_intercept = std::max(intercept_1, intercept_2);

    const double error = 0.5 * (right_intercept - left_intercept);
    
    if (error < BEPSILON)
        return 1;
    
    return 0;
}

static unsigned Geom::copy_without_nans_or_adjacent_duplicates	(	Point const	src[],
		unsigned	src_len,
		Point	dest[]
	)			[static]

Copy points from src to dest, filter out points containing NaN and adjacent points with equal x and y.

Returns:

length of dest

Definition at line 161 of file bezier-utils.cpp.

References IS_NAN, Point, X, and Y.

{
    unsigned si = 0;
    for (;;) {
        if ( si == src_len ) {
            return 0;
        }
        if (!IS_NAN(src[si][X]) &&
            !IS_NAN(src[si][Y])) {
            dest[0] = Point(src[si]);
            ++si;
            break;
        }
        si++;
    }
    unsigned di = 0;
    for (; si < src_len; ++si) {
        Point const src_pt = Point(src[si]);
        if ( src_pt != dest[di]
             && !IS_NAN(src_pt[X])
             && !IS_NAN(src_pt[Y])) {
            dest[++di] = src_pt;
        }
    }
    unsigned dest_len = di + 1;
    assert( dest_len <= src_len );
    return dest_len;
}

SBasis Geom::cos	(	Linear	bo,
		int	k
	)

Compute the cosine of a.

Parameters:

b

linear function

Returns:

sbasis cos(a)

It is recommended to use the piecewise version unless you have good reason.

Piecewise< SBasis > Geom::cos	(	SBasis const &	f,
		double	tol,
		int	order
	)

Compute the cosine of a function.

Parameters:

	f	function
	tol	maximum error
	order	maximum degree polynomial to use

Piecewise< SBasis > Geom::cos	(	Piecewise< SBasis > const &	f,
		double	tol,
		int	order
	)

Compute the cosine of a function.

Parameters:

	f	function
	tol	maximum error
	order	maximum degree polynomial to use

Referenced by Gear::_arc(), Inkscape::Text::Layout::_calculateCursorShapeForEmpty(), Inkscape::LivePathEffect::_circle(), Inkscape::Text::Layout::_getGlyphTransformMatrix(), Gear::_involute(), Inkscape::UI::ControlPointSelection::_pointDragged(), Geom::SVGEllipticalArc::allNearestPoints(), Geom::EllipticalArc::allNearestPoints(), Geom::Ray::angle(), Geom::Line::angle(), arc2path(), ArcAnglesAndCenter(), Gear::base_diameter(), Geom::SVGEllipticalArc::boundsExact(), Geom::EllipticalArc::boundsExact(), lwpolyline::bulge_end_angle(), polyline::bulge_end_angle(), lwpolyline::bulge_start_angle(), polyline::bulge_start_angle(), Geom::SVGEllipticalArc::calculate_center_and_extreme_angles(), Geom::EllipticalArc::calculate_center_and_extreme_angles(), clonetiler_get_transform(), Inkscape::LivePathEffect::LPETextLabel::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), get_snap_vector(), gr_knot_moved_midpoint_handler(), Geom::Ellipse::implicit_form_coefficients(), integrate_spiro(), Inkscape::Filters::DistantLight::light_vector(), Shape::MakeOffset(), Shape::MakeTweak(), Avoid::Router::markConnectors(), NormalDistribution(), Geom::SVGEllipticalArc::pointAtAngle(), Geom::EllipticalArc::pointAtAngle(), Geom::Point::polar(), Inkscape::Text::Layout::queryCursorShape(), Inkscape::Filters::FilterColorMatrix::render(), Geom::SVGEllipticalArc::roots(), Geom::EllipticalArc::roots(), org::w3c::dom::svg::SVGMatrix::rotate(), rotate_degrees(), org::w3c::dom::svg::SVGMatrix::rotateFromVector(), Inkscape::SelTrans::rotateRequest(), Geom::Ellipse::set(), Proj::TransfMat3x4::set_infinite_direction(), set_pos_and_anchor(), Inkscape::LivePathEffect::TextParam::setPosAndAnchor(), sp_arc_get_xy(), sp_color_wheel_paint(), sp_color_wheel_recalc_triangle(), sp_dyna_draw_apply(), sp_eraser_apply(), sp_genericellipse_set_shape(), sp_genericellipse_snappoints(), sp_spiral_get_tangent(), sp_spiral_get_xy(), sp_spray_recursive(), sp_star_get_xy(), sp_star_position_set(), sp_te_get_cursor_coords(), sp_tweak_dilate_recursive(), spdc_endpoint_snap_rotation(), spiro_seg_to_bpath(), Inkscape::Filters::SpotLight::SpotLight(), tan2(), Path::TangentOnArcAt(), NrRotateTest::testCtorsCompares(), text2text(), Geom::SVGEllipticalArc::toSBasis(), Geom::EllipticalArc::toSBasis(), Geom::Ellipse::transformed(), tweak_profile(), Geom::SVGEllipticalArc::valueAtAngle(), and Geom::EllipticalArc::valueAtAngle().

Coord Geom::cross	(	Point const &	a,
		Point const &	b
	)			[inline]

Defined as dot(a, b.cw()).

Definition at line 218 of file 2geom/point.h.

References Geom::Point::cw(), and dot().

{ return dot(a, b.cw()); }

Piecewise<SBasis> Geom::cross	(	Piecewise< D2< SBasis > > const &	a,
		Piecewise< D2< SBasis > > const &	b
	)

Definition at line 110 of file d2-sbasis.cpp.

References org::w3c::dom::svg::a, b, Geom::Piecewise< T >::cuts, Barcode::Code39Ext::i, partition(), Geom::Piecewise< T >::push(), Geom::Piecewise< T >::push_cut(), org::w3c::dom::svg::result, and Geom::Piecewise< T >::segs.

Referenced by Inkscape::LivePathEffect::are_colinear(), are_collinear(), bridges(), centroid(), Geom::ConvexHull::centroid_and_area(), Shape::CmpToVert(), cubics_fitting_curvature(), curvature(), Inkscape::LivePathEffect::LPEKnot::doEffect_path(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Path::DoJoin(), Path::DoLeftJoin(), Path::DoRightJoin(), SweepTree::Find(), Geom::Matrix::flips(), SweepTree::InsertAt(), Geom::detail::bezier_clipping::is_a_right_turn(), linear_intersect(), Geom::detail::bezier_clipping::orientation_line(), Path::OutlineJoin(), pick_coincident(), Shape::PtWinding(), Path::RecBezierTo(), Path::RecCubicTo(), Path::RecRound(), SignedTriangleArea(), Path::Surface(), Path::TangentOnBezAt(), Path::TangentOnCubAt(), Shape::TesteAdjacency(), Shape::TesteIntersection(), and Shape::Winding().

                                            {
  Piecewise<SBasis > result;
  if (a.empty() || b.empty()) return result;
  Piecewise<D2<SBasis> > aa = partition(a,b.cuts);
  Piecewise<D2<SBasis> > bb = partition(b,a.cuts);

  result.push_cut(aa.cuts.front());
  for (unsigned i=0; i<a.size(); i++){
    result.push(cross(aa.segs[i],bb.segs[i]),aa.cuts[i+1]);
  }
  return result;
}

unsigned Geom::crossing_along	(	double	t,
		unsigned	ix,
		unsigned	jx,
		bool	dir,
		Crossings const &	crs
	)

Referenced by inner_sanitize(), and outer_crossing().

unsigned Geom::crossing_count	(	double const *	V,
		unsigned	degree,
		double	left_t,
		double	right_t
	)

unsigned Geom::crossing_count	(	Geom::Point const *	V,
		unsigned	degree
	)

Definition at line 88 of file solve-bezier-parametric.cpp.

References Barcode::Code39Ext::i, SGN(), sign, and Y.

{
    unsigned    n_crossings = 0;    /*  Number of zero-crossings */
    
    int old_sign = SGN(V[0][Geom::Y]);
    for (unsigned i = 1; i <= degree; i++) {
        int sign = SGN(V[i][Geom::Y]);
        if (sign != old_sign)
            n_crossings++;
        old_sign = sign;
    }
    return n_crossings;
}

void Geom::crossing_dual	(	unsigned &	i,
		unsigned &	j,
		CrossingSet const &	crs
	)

Referenced by inner_sanitize().

CrossingSet Geom::crossings	(	std::vector< Path > const &	a,
		std::vector< Path > const &	b
	)			[inline]

Definition at line 102 of file path-intersection.h.

References c, and Geom::SimpleCrosser::crossings().

                                                                                   {
    DefaultCrosser c = DefaultCrosser();
    return c.crossings(a, b);
}

Crossings Geom::crossings	(	Path const &	a,
		Path const &	b
	)			[inline]

Definition at line 97 of file path-intersection.h.

References c, and Geom::SimpleCrosser::crossings().

                                                           {
    DefaultCrosser c = DefaultCrosser();
    return c.crossings(a, b);
}

Crossings Geom::crossings	(	Curve const &	a,
		Curve const &	b
	)			[inline]

Definition at line 92 of file path-intersection.h.

References c, and Geom::SimpleCrosser::crossings().

Referenced by Inkscape::ObjectSnapper::_snapPathsConstrained(), Avoid::buildOrthogonalNudgingOrderInfo(), Avoid::cost(), crossings_between(), Inkscape::SnappedCurve::intersect(), region_boolean(), and try_get_intersect_point_with_item_recursive().

                                                             {
    DefaultCrosser c = DefaultCrosser();
    return c.crossings(a, b);
}

CrossingSet Geom::crossings_among

(

std::vector< Path > const &

p

)

Referenced by inner_sanitize().

CrossingSet Geom::crossings_between	(	Shape const &	a,
		Shape const &	b
	)			[inline]

Definition at line 114 of file 2geom/shape.h.

References Geom::Shape::content, crossings(), and paths_from_regions().

{ return crossings(paths_from_regions(a.content), paths_from_regions(b.content)); }

template<class T >

T Geom::cube

(

const T &

x

)

[inline]

Definition at line 51 of file utils.h.

{return x * x * x;}

template<typename iterator >

static void Geom::cubic_bezier_poly_coeff	(	iterator	b,
		Point *	pc
	)			[inline, static]

Definition at line 66 of file bezier-utils.h.

References c, Barcode::Code39Ext::i, and Point.

                                               {
    double c[10] = {1, 
            -3, 3, 
            3, -6, 3,
            -1, 3, -3, 1};

    int cp = 0;

    for(int i = 0; i < 4; i++) {
        pc[i] = Point(0,0);
        ++b;
    }
    for(int i = 0; i < 4; i++) {
        --b;
        for(int j = 0; j <= i; j++) {
            pc[3 - j] += c[cp]*(*b);
            cp++;
        }
    }
}

Path Geom::cubicbezierpath_from_sbasis	(	D2< SBasis > const &	B,
		double	tol
	)			[inline]

Definition at line 68 of file sbasis-to-bezier.h.

References path_from_sbasis().

Referenced by Path::AddCurve(), feed_curve_to_cairo(), geom_curve_bbox_wind_distance(), pathv_to_linear_and_cubic_beziers(), Inkscape::Extension::Internal::PrintLatex::print_2geomcurve(), and sp_svg_write_curve().

    { return path_from_sbasis(B, tol, true); }

std::vector< D2< SBasis > > Geom::cubics_fitting_curvature	(	Point const &	M0,
		Point const &	M1,
		Point const &	dM0,
		Point const &	dM1,
		Point const &	d2M0,
		Point const &	d2M1,
		int	insist_on_speed_signs = 1,
		double	epsilon = 1e-5
	)

Definition at line 719 of file sbasis-geometric.cpp.

References cross(), and cubics_fitting_curvature().

                                        {
    double d2M0xdM0 = cross(d2M0,dM0);
    double d2M1xdM1 = cross(d2M1,dM1);
    return cubics_fitting_curvature(M0,M1,dM0,dM1,d2M0xdM0,d2M1xdM1,insist_on_speed_signs,epsilon);
}

std::vector< D2< SBasis > > Geom::cubics_fitting_curvature	(	Point const &	M0,
		Point const &	M1,
		Point const &	dM0,
		Point const &	dM1,
		double	d2M0xdM0,
		double	d2M1xdM1,
		int	insist_on_speed_signs = 1,
		double	epsilon = 1e-5
	)

returns the cubics fitting direction and curvature of a given input curve at two points.

The input can be the value, speed, and acceleration or value, speed, and cross(acceleration,speed) of the original curve at the both ends. (the second is often technically usefull, as it avoids unnecessary division by |v|^2) Recall that K=1/R=cross(acceleration,speed)/|speed|^3.

Moreover, a 7-th argument 'insist_on_speed_signs' can be supplied to select solutions: If insist_on_speed_signs == 1, only consider solutions where speeds at both ends are positively proportional to the given ones. If insist_on_speed_signs == 0, allow speeds to point in the opposite direction (both at the same time) If insist_on_speed_signs == -1, allow speeds to point in both direction independantly.

Definition at line 625 of file sbasis-geometric.cpp.

References org::w3c::dom::svg::a, c, cross(), curvature(), Barcode::Code39Ext::i, org::w3c::dom::svg::result, solve_lambda0(), sqrt(), and Geom::Piecewise< T >::valueAt().

Referenced by cubics_fitting_curvature(), and cubics_with_prescribed_curvature().

                                        {
    std::vector<D2<SBasis> > result;

    //speed of cubic bezier will be lambda0*dM0 and lambda1*dM1,
    //with lambda0 and lambda1 s.t. curvature at both ends is the same
    //as the curvature of the given curve.
    std::vector<double> lambda0,lambda1;
    double dM1xdM0=cross(dM1,dM0);
    if (fabs(dM1xdM0)<epsilon){
        if (fabs(d2M0xdM0)<epsilon || fabs(d2M1xdM1)<epsilon){
            return result;
        }
        double lbda02 = 6.*cross(M1-M0,dM0)/d2M0xdM0;
        double lbda12 =-6.*cross(M1-M0,dM1)/d2M1xdM1;
        if (lbda02<0 || lbda12<0){
            return result;
        }
        lambda0.push_back(std::sqrt(lbda02) );
        lambda1.push_back(std::sqrt(lbda12) );
    }else{
        //solve:  lambda1 = a0 lambda0^2 + c0
        //        lambda0 = a1 lambda1^2 + c1
        double a0,c0,a1,c1;
        a0 = -d2M0xdM0/2/dM1xdM0;
        c0 =  3*cross(M1-M0,dM0)/dM1xdM0;
        a1 = -d2M1xdM1/2/dM1xdM0;
        c1 = -3*cross(M1-M0,dM1)/dM1xdM0;

        if (fabs(a0)<epsilon){
            lambda1.push_back( c0 );
            lambda0.push_back( a1*c0*c0 + c1 );
        }else if (fabs(a1)<epsilon){
            lambda0.push_back( c1 );
            lambda1.push_back( a0*c1*c1 + c0 );
        }else{
            //find lamda0 by solving a deg 4 equation d0+d1*X+...+d4*X^4=0
            double a[5];
            a[0] = c1+a1*c0*c0;
            a[1] = -1;
            a[2] = 2*a1*a0*c0;
            a[3] = 0;
            a[4] = a1*a0*a0;
            //vector<double> solns=solve_poly(a,4);
            vector<double> solns=solve_lambda0(a0,a1,c0,c1,insist_on_speed_signs);
            for (unsigned i=0;i<solns.size();i++){
                double lbda0=solns[i];
                double lbda1=c0+a0*lbda0*lbda0;
                //is this solution pointing in the + direction at both ends?
                if (lbda0>=0. && lbda1>=0.){
                    lambda0.push_back( lbda0);
                    lambda1.push_back( lbda1);
                }
                //is this solution pointing in the - direction at both ends?
                else if (lbda0<=0. && lbda1<=0. && insist_on_speed_signs<=0){
                    lambda0.push_back( lbda0);
                    lambda1.push_back( lbda1);
                }
                //ok,this solution is pointing in the + and - directions.
                else if (insist_on_speed_signs<0){
                    lambda0.push_back( lbda0);
                    lambda1.push_back( lbda1);
                }
            }
        }
    }
    
    for (unsigned i=0; i<lambda0.size(); i++){
        Point V0 = lambda0[i]*dM0;
        Point V1 = lambda1[i]*dM1;
        D2<SBasis> cubic;
        for(unsigned dim=0;dim<2;dim++){
            SBasis c(2, Linear());
            c[0] = Linear(M0[dim],M1[dim]);
            c[1] = Linear( M0[dim]-M1[dim]+V0[dim],
                           -M0[dim]+M1[dim]-V1[dim]);
            cubic[dim] = c;
        }
#if 0
           Piecewise<SBasis> k = curvature(result);
           double dM0_l = dM0.length();
           double dM1_l = dM1.length();
           g_warning("Target radii: %f, %f", dM0_l*dM0_l*dM0_l/d2M0xdM0,dM1_l*dM1_l*dM1_l/d2M1xdM1);
           g_warning("Obtained radii: %f, %f",1/k.valueAt(0),1/k.valueAt(1));
#endif
        result.push_back(cubic);
    }
    return(result);
}

std::vector< D2< SBasis > > Geom::cubics_with_prescribed_curvature	(	Point const &	M0,
		Point const &	M1,
		Point const &	dM0,
		Point const &	dM1,
		double	k0,
		double	k1,
		int	insist_on_speed_signs = 1,
		double	error = 1e-5
	)

Definition at line 730 of file sbasis-geometric.cpp.

References cubics_fitting_curvature(), and Geom::Point::length().

                                                {
    double length;
    length = dM0.length();
    double d2M0xdM0 = k0*length*length*length;
    length = dM1.length();
    double d2M1xdM1 = k1*length*length*length;
    return cubics_fitting_curvature(M0,M1,dM0,dM1,d2M0xdM0,d2M1xdM1,insist_on_speed_signs,epsilon);
}

Piecewise< SBasis > Geom::curvature	(	Piecewise< D2< SBasis > > const &	V,
		double	tol = .01
	)

returns a function giving the curvature at each point in M.

Parameters:

	M	the Element.
	tol	the maximum error allowed.

Todo: claimed incomplete. Check.

Definition at line 379 of file sbasis-geometric.cpp.

References Geom::Piecewise< T >::concat(), curvature(), cutAtRoots(), Geom::Piecewise< T >::cuts, Barcode::Code39Ext::i, org::w3c::dom::svg::result, Geom::Piecewise< T >::segs, Geom::Piecewise< T >::setDomain(), and Geom::Piecewise< T >::size().

                                                          {
    Piecewise<SBasis> result;
    Piecewise<D2<SBasis> > VV = cutAtRoots(V);
    result.cuts.push_back(VV.cuts.front());
    for (unsigned i=0; i<VV.size(); i++){
        Piecewise<SBasis> curv_seg;
        curv_seg = curvature(VV.segs[i],tol);
        curv_seg.setDomain(Interval(VV.cuts[i],VV.cuts[i+1]));
        result.concat(curv_seg);
    }
    return result;
}

Piecewise< SBasis > Geom::curvature	(	D2< SBasis > const &	M,
		double	tol = .01
	)

returns a function giving the curvature at each point in M.

Parameters:

	M	the Element.
	tol	the maximum error allowed.

Todo: claimed incomplete. Check.

Definition at line 361 of file sbasis-geometric.cpp.

References cross(), derivative(), divide(), dot(), org::w3c::dom::svg::result, and unitVector().

Referenced by cubics_fitting_curvature(), curvature(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), and sp_connector_toolbox_selection_changed().

                                               {
    D2<SBasis> dM=derivative(M);
    Piecewise<SBasis> result;
    Piecewise<D2<SBasis> > unitv = unitVector(dM,tol);
    Piecewise<SBasis> dMlength = dot(Piecewise<D2<SBasis> >(dM),unitv);
    Piecewise<SBasis> k = cross(derivative(unitv),unitv);
    k = divide(k,dMlength,tol,3);
    return(k);
}

std::vector<double> Geom::curve_mono_splits

(

Curve const &

d

)

This returns the times when the x or y derivative is 0 in the curve.

Definition at line 461 of file path-intersection.cpp.

References append(), Geom::Curve::derivative(), Geom::Curve::roots(), X, and Y.

Referenced by curve_self_crossings().

                                                    {
    Curve* deriv = d.derivative();
    std::vector<double> rs = d.roots(0, X);
    append(rs, d.roots(0, Y));
    delete deriv;
    std::sort(rs.begin(), rs.end());
    return rs;
}

Crossings Geom::curve_self_crossings

(

Curve const &

a

)

Definition at line 625 of file path-intersection.cpp.

References append(), curve_mono_splits(), Barcode::Code39Ext::i, and pair_intersect().

                                               {
    Crossings res;
    std::vector<double> spl;
    spl.push_back(0);
    append(spl, curve_mono_splits(a));
    spl.push_back(1);
    for(unsigned i = 1; i < spl.size(); i++)
        for(unsigned j = i+1; j < spl.size(); j++)
            pair_intersect(a, spl[i-1], spl[i], a, spl[j-1], spl[j], res);
    return res;
}

template<typename T >

Crossings Geom::curve_sweep	(	Path const &	a,
		Path const &	b
	)			[inline]

Definition at line 54 of file path-intersection.h.

References bounds(), Barcode::Code39Ext::i, offset_crossings(), Geom::Path::size(), and sweep_bounds().

                                                    {
    T t;
    Crossings ret;
    std::vector<Rect> bounds_a = bounds(a), bounds_b = bounds(b);
    std::vector<std::vector<unsigned> > ixs = sweep_bounds(bounds_a, bounds_b);
    for(unsigned i = 0; i < a.size(); i++) {
        for(std::vector<unsigned>::iterator jp = ixs[i].begin(); jp != ixs[i].end(); jp++) {
            Crossings cc = t.crossings(a[i], b[*jp]);
            offset_crossings(cc, i, *jp);
            ret.insert(ret.end(), cc.begin(), cc.end());
        }
    }
    return ret;
}

Piecewise< D2< SBasis > > Geom::cutAtRoots	(	Piecewise< D2< SBasis > > const &	M,
		double	tol = 1e-4
	)

Definition at line 136 of file sbasis-geometric.cpp.

References Barcode::Code39Ext::i, M, partition(), polyhedron_3d::r, roots(), and vect_intersect().

Referenced by atan2(), curvature(), and unitVector().

                                                            {
    vector<double> rts;
    for (unsigned i=0; i<M.size(); i++){
        vector<double> seg_rts = roots((M.segs[i])[0]);
        seg_rts = vect_intersect(seg_rts, roots((M.segs[i])[1]), ZERO);
        Linear mapToDom = Linear(M.cuts[i],M.cuts[i+1]);
        for (unsigned r=0; r<seg_rts.size(); r++){
            seg_rts[r]= mapToDom(seg_rts[r]);
        }
        rts.insert(rts.end(),seg_rts.begin(),seg_rts.end());
    }
    return partition(M,rts);
}

static Point Geom::darray_center_tangent	(	Point const	d[],
		unsigned const	center,
		unsigned const	len
	)			[static]

Estimates the (backward) tangent at d[center], by averaging the two segments connected to d[center] (and then normalizing the result).

Note:

The tangent is "backwards", i.e. it is with respect to decreasing index rather than increasing index.

Precondition:

(0 < center < len - 1) and d is uniqued (at least in the immediate vicinity of center).

Definition at line 815 of file bezier-utils.cpp.

References Geom::Point::normalize(), and rot90().

{
    assert( center != 0 );
    assert( center < len - 1 );

    Point ret;
    if ( d[center + 1] == d[center - 1] ) {
        /* Rotate 90 degrees in an arbitrary direction. */
        Point const diff = d[center] - d[center - 1];
        ret = rot90(diff);
    } else {
        ret = d[center - 1] - d[center + 1];
    }
    ret.normalize();
    return ret;
}

Point Geom::darray_left_tangent	(	Point const	d[],
		unsigned const	len,
		double const	tolerance_sq
	)

Estimate the (forward) tangent at point d[0].

Unlike the center and right versions, this calculates the tangent in the way one might expect, i.e., wrt increasing index into d.

Precondition:

2 <= len.

d[0] != d[1].

all[p in d] in_svg_plane(p).

Postcondition:

is_unit_vector(ret).

Point Geom::darray_left_tangent	(	Point const	d[],
		unsigned const	len
	)

Estimate the (forward) tangent at point d[first + 0.5].

Unlike the center and right versions, this calculates the tangent in the way one might expect, i.e., wrt increasing index into d.

Precondition:

(2 <= len) and (d[0] != d[1]).

Referenced by generate_bezier().

Point Geom::darray_right_tangent	(	Point const	d[],
		unsigned const	len,
		double const	tolerance_sq
	)

Estimates the (backward) tangent at d[last].

Note:

The tangent is "backwards", i.e. it is with respect to decreasing index rather than increasing index.

Precondition:

2 <= len.

d[len - 1] != d[len - 2].

all[p in d] in_svg_plane(p).

static Point Geom::darray_right_tangent	(	Point const	d[],
		unsigned const	len
	)			[static]

Estimates the (backward) tangent at d[last - 0.5].

Note:

The tangent is "backwards", i.e. it is with respect to decreasing index rather than increasing index.

Precondition:

2 <= len.

d[len - 1] != d[len - 2].

all[p in d] in_svg_plane(p).

Definition at line 732 of file bezier-utils.cpp.

References unit_vector().

Referenced by generate_bezier().

{
    assert( 2 <= len );
    unsigned const last = len - 1;
    unsigned const prev = last - 1;
    assert( d[last] != d[prev] );
    return unit_vector( d[prev] - d[last] );
}

double Geom::decimal_round	(	double const	x,
		int const	places
	)			[inline]

Returns x rounded to the nearest places decimal places.

Implemented in terms of round, i.e. we make no guarantees as to what happens if x is half way between two rounded numbers.

Note: places is the number of decimal places without using scientific (e) notation, not the number of significant figures. This function may not be suitable for values of x whose magnitude is so far from 1 that one would want to use scientific (e) notation.

places may be negative: e.g. places = -2 means rounding to a multiple of .01

Definition at line 76 of file utils.h.

References pow(), and round().

Referenced by operator<<(), and Geom::Point::round().

                                                              {
    //TODO: possibly implement with modulus instead?
    double const multiplier = std::pow(10.0, places);
    return round( x * multiplier ) / multiplier;
}

double Geom::deg_to_rad

(

double

deg

)

[inline]

Definition at line 44 of file angle.h.

References M_PI.

Referenced by sp_svg_transform_read().

{ return deg*M_PI/180.0;}

SBasis Geom::derivative

(

SBasis const &

a

)

Compute the derivative of a (Exact).

Parameters:

a

sbasis functions

Returns:

sbasis da/dt

Poly Geom::derivative

(

Poly const &

p

)

template<typename T >

Piecewise<T> Geom::derivative

(

Piecewise< T > const &

a

)

[inline]

Definition at line 752 of file piecewise.h.

References Geom::Piecewise< T >::cuts, derivative(), Barcode::Code39Ext::i, org::w3c::dom::svg::result, and Geom::Piecewise< T >::segs.

                                               {
    Piecewise<T> result;
    result.segs.resize(a.segs.size());
    result.cuts = a.cuts;
    for(unsigned i = 0; i < a.segs.size(); i++){
        result.segs[i] = derivative(a.segs[i])/(a.cuts[i+1]-a.cuts[i]);
    }
    return result;
}

template<typename T >

D2<T> Geom::derivative

(

D2< T > const &

a

)

[inline]

Definition at line 411 of file d2.h.

References derivative(), X, and Y.

                                  {
    return D2<T>(derivative(a[X]), derivative(a[Y]));
}

Bezier Geom::derivative

(

const Bezier &

a

)

[inline]

Definition at line 362 of file bezier.h.

References Bezier(), Geom::Bezier::c_, Barcode::Code39Ext::i, and Geom::Bezier::order().

Referenced by all_nearest_points(), arcLengthSb(), atan2(), Geom::BezierCurve< 1 >::boundsLocal(), centroid(), curvature(), Geom::SBasisCurve::derivative(), derivative(), length_integrating(), nearest_point(), and Geom::sturm::sturm().

                                           {
    //if(a.order() == 1) return Bezier(0.0);
    if(a.order() == 1) return Bezier(a.c_[1]-a.c_[0]);
    Bezier der(Bezier::Order(a.order()-1));

    for(unsigned i = 0; i < a.order(); i++) {
        der.c_[i] = a.order()*(a.c_[i+1] - a.c_[i]);
    }
    return der;
}

std::vector<Path> Geom::desanitize

(

Shape const &

s

)

[inline]

Definition at line 131 of file 2geom/shape.h.

References Geom::Shape::getContent(), and paths_from_regions().

                                                   {
    return paths_from_regions(s.getContent());
}

double Geom::distance	(	Point const &	p,
		Rect const &	rect
	)			[inline]

Returns the smallest distance between p and rect.

Definition at line 190 of file rect.h.

References distanceSq(), and sqrt().

{
    return std::sqrt(distanceSq(p, rect));
}

double Geom::distance	(	Point const &	_point,
		Ray const &	_ray
	)			[inline]

Definition at line 198 of file ray.h.

References distance(), Geom::Ray::nearestPoint(), and Geom::Ray::pointAt().

{
    double t = _ray.nearestPoint(_point);
    return distance(_point, _ray.pointAt(t));
}

Coord Geom::distance	(	Point const &	a,
		Point const &	b
	)			[inline]

compute the euclidean distance between points a and b.

TODO: hypot safer/faster?

Definition at line 221 of file 2geom/point.h.

References L2().

{ return L2(a - b); }

double Geom::distance	(	Point const &	_point,
		LineSegment const &	_segment
	)			[inline]

Definition at line 312 of file line.h.

References L2(), Geom::BezierCurve< order >::nearestPoint(), and Geom::BezierCurve< order >::pointAt().

{
    double t = _segment.nearestPoint(_point);
    return L2(_point - _segment.pointAt(t));
}

double Geom::distance	(	Point const &	_point,
		Line const &	_line
	)			[inline]

Definition at line 254 of file line.h.

References Geom::Point::ccw(), dot(), Geom::Line::isDegenerate(), Geom::Line::origin(), and Geom::Line::versor().

Referenced by Inkscape::UI::PathManipulator::_updateDragPoint(), are_near(), box3d_half_line_crosses_joining_line(), chord_length_parameterize(), compute_hook(), control_poly_flat_enough(), distance(), Inkscape::LivePathEffect::LPEGears::doEffect_path(), Inkscape::UI::Node::dragged(), Inkscape::UI::Handle::dragged(), estimate_lengths(), Inkscape::UI::Node::setType(), and vector_stretch().

{
    if ( _line.isDegenerate() )
    {
        return distance( _point, _line.origin() );
    }
    else
    {
        return fabs( dot(_point - _line.origin(), _line.versor().ccw()) );
    }
}

double Geom::distanceSq	(	Point const &	p,
		Rect const &	rect
	)			[inline]

Definition at line 164 of file rect.h.

References Geom::D2< Interval >::bottom(), Geom::D2< Interval >::left(), Geom::D2< Interval >::right(), Geom::D2< Interval >::top(), X, and Y.

{
    double dx = 0, dy = 0;
    if ( p[X] < rect.left() )
    {
        dx = p[X] - rect.left();
    }
    else if ( p[X] > rect.right() )
    {
        dx = rect.right() - p[X];
    }
    if ( p[Y] < rect.top() )
    {
        dy = rect.top() - p[Y];
    }
    else if (  p[Y] > rect.bottom() )
    {
        dy = p[Y] - rect.bottom();
    }
    return dx*dx + dy*dy;
}

Coord Geom::distanceSq	(	Point const &	a,
		Point const &	b
	)			[inline]

compute the square of the distance between points a and b.

Definition at line 224 of file 2geom/point.h.

References L2sq().

Referenced by Geom::SVGEllipticalArc::allNearestPoints(), Geom::Path::allNearestPoints(), Geom::EllipticalArc::allNearestPoints(), distance(), and Geom::Path::nearestPoint().

{ return L2sq(a - b); }

SBasis Geom::divide	(	SBasis const &	a,
		SBasis const &	b,
		int	k
	)

Compute a / b to k terms.

Parameters:

a,b

sbasis functions

Returns:

sbasis a/b

It is recommended to use the piecewise version unless you have good reason.

SBasis2d Geom::divide	(	SBasis2d const &	a,
		SBasis2d const &	b,
		int	k
	)

Poly Geom::divide	(	Poly const &	a,
		Poly const &	b,
		Poly &	r
	)

Piecewise< SBasis > Geom::divide	(	SBasis const &	a,
		SBasis const &	b,
		double	tol,
		unsigned	k,
		double	zero
	)

Piecewise< SBasis > Geom::divide	(	SBasis const &	a,
		Piecewise< SBasis > const &	b,
		double	tol,
		unsigned	k,
		double	zero
	)

Piecewise< SBasis > Geom::divide	(	Piecewise< SBasis > const &	a,
		SBasis const &	b,
		double	tol,
		unsigned	k,
		double	zero
	)

Piecewise< SBasis > Geom::divide	(	Piecewise< SBasis > const &	a,
		Piecewise< SBasis > const &	b,
		double	tol,
		unsigned	k,
		double	zero
	)

Piecewise< SBasis > Geom::divide	(	Piecewise< SBasis > const &	a,
		Piecewise< SBasis > const &	b,
		unsigned	k
	)

Referenced by atan2(), curvature(), Inkscape::LivePathEffect::LPEPerspectivePath::doEffect_pwd2(), and Geom::sturm::sturm().

Poly Geom::divide_out_root	(	Poly const &	p,
		double	x
	)

Coord Geom::dot	(	Point const &	a,
		Point const &	b
	)			[inline]

compute the dot product (inner product) between the vectors a and b.

Definition at line 216 of file 2geom/point.h.

{ return a[0] * b[0] + a[1] * b[1]; }

template<typename T >

T Geom::dot	(	D2< T > const &	a,
		D2< T > const &	b
	)			[inline]

Definition at line 314 of file d2.h.

References Barcode::Code39Ext::i, and polyhedron_3d::r.

Referenced by arcLengthSb(), Geom::make_elliptical_arc::bound_exceeded(), centroid(), cross(), curvature(), distance(), distance(), Geom::detail::bezier_clipping::distance_control_points(), distanceLessThanOrEqual(), DistanceToCubic(), Geom::Piecewise< T >::dot(), estimate_lengths(), Geom::Line::fromNormalDistance(), Geom::ConvexHull::furthest(), intersect_polish_root(), L2(), length_integrating(), lensq(), Box3D::Line::lie_on_same_side(), line_intersection(), line_segment_intersect(), line_twopoint_intersect(), Geom::ConvexHull::narrowest_diameter(), Geom::Ray::nearestPoint(), NewtonRaphsonRootFind(), RecDistanceToCubic(), rect_line_intersect(), Inkscape::SelTrans::rotateRequest(), segment_intersect(), sp_dyna_draw_context_root_handler(), sp_guide_distance_from_pt(), sp_guideline_point(), Geom::Line::timeAtProjection(), and unitVector().

                                      {
    boost::function_requires<AddableConcept<T> >();
    boost::function_requires<MultiplicableConcept<T> >();

    T r;
    for(unsigned i = 0; i < 2; i++)
        r += a[i] * b[i];
    return r;
}

template<typename T >

T Geom::elem_portion	(	const Piecewise< T > &	a,
		unsigned	i,
		double	from,
		double	to
	)			[inline]

Definition at line 313 of file piecewise.h.

References Geom::Piecewise< T >::cuts, portion(), and Geom::Piecewise< T >::size().

Referenced by partition(), portion(), and remove_short_cuts_extending().

                                                                          {
    assert(i < a.size());
    double rwidth = 1 / (a.cuts[i+1] - a.cuts[i]);
    return portion( a[i], (from - a.cuts[i]) * rwidth, (to - a.cuts[i]) * rwidth );
}

static void Geom::eliminate_duplicates_p

(

std::vector< Point > &

pts

)

[static]

Definition at line 231 of file 2geom/geom.cpp.

References is_less().

Referenced by rect_line_intersect().

{
    unsigned int size = pts.size();

    if (size < 2)
        return;

    if (size == 2) {
        if (pts[0] == pts[1]) {
            pts.pop_back();
        }
    } else {
        std::sort(pts.begin(), pts.end(), &is_less);
        if (size == 3) {
            if (pts[0] == pts[1]) {
                pts.erase(pts.begin());
            } else if (pts[1] == pts[2]) {
                pts.pop_back();
            }
        } else {
            // we have size == 4
            if (pts[2] == pts[3]) {
                pts.pop_back();
            }
            if (pts[0] == pts[1]) {
                pts.erase(pts.begin());
            }
        }
    }
}

Matrix Geom::elliptic_quadratic_form

(

Matrix const &

m

)

Given a matrix m such that unit_circle = m*x, this returns the quadratic form x*A*x = 1.

Referenced by NrMatrixTest::testEllipticQuadraticForm().

static double Geom::EpsilonBy	(	double	value,
		int	eps
	)			[static]

Definition at line 361 of file recursive-bezier-intersection.cpp.

Referenced by intersect_polish_root().

{
    dbl_64 s;
    s.d64 = value;
    s.i64 += eps;
    return s.d64;
}

static void Geom::estimate_bi	(	Point	b[4],
		unsigned	ei,
		Point const	data[],
		double const	u[],
		unsigned	len
	)			[static]

Definition at line 500 of file bezier-utils.cpp.

References b, B0, B1, B2, B3, NR::d, and Barcode::Code39Ext::i.

Referenced by generate_bezier().

{
    if(!(1 <= ei && ei <= 2))
        return;
    unsigned const oi = 3 - ei;
    double num[2] = {0., 0.};
    double den = 0.;
    for (unsigned i = 0; i < len; ++i) {
        double const ui = u[i];
        double const b[4] = {
            B0(ui),
            B1(ui),
            B2(ui),
            B3(ui)
        };

        for (unsigned d = 0; d < 2; ++d) {
            num[d] += b[ei] * (b[0]  * bezier[0][d] +
                               b[oi] * bezier[oi][d] +
                               b[3]  * bezier[3][d] +
                               - data[i][d]);
        }
        den -= b[ei] * b[ei];
    }

    if (den != 0.) {
        for (unsigned d = 0; d < 2; ++d) {
            bezier[ei][d] = num[d] / den;
        }
    } else {
        bezier[ei] = ( oi * bezier[0] + ei * bezier[3] ) / 3.;
    }
}

static void Geom::estimate_lengths	(	Point	bezier[],
		Point const	data[],
		double const	u[],
		unsigned	len,
		Point const &	tHat1,
		Point const &	tHat2
	)			[static]

Todo:

Check whether this special-casing is necessary now that NewtonRaphsonRootFind handles non-positive denominator.

Todo:

Check whether this special-casing is necessary now that NewtonRaphsonRootFind handles non-positive denominator.

Definition at line 395 of file bezier-utils.cpp.

References B0, B1, B2, B3, distance(), dot(), addnodes::e, Barcode::Code39Ext::i, and X.

Referenced by generate_bezier().

{
    double C[2][2];   /* Matrix C. */
    double X[2];      /* Matrix X. */

    /* Create the C and X matrices. */
    C[0][0] = 0.0;
    C[0][1] = 0.0;
    C[1][0] = 0.0;
    C[1][1] = 0.0;
    X[0]    = 0.0;
    X[1]    = 0.0;

    /* First and last control points of the Bezier curve are positioned exactly at the first and
       last data points. */
    bezier[0] = data[0];
    bezier[3] = data[len - 1];

    for (unsigned i = 0; i < len; i++) {
        /* Bezier control point coefficients. */
        double const b0 = B0(uPrime[i]);
        double const b1 = B1(uPrime[i]);
        double const b2 = B2(uPrime[i]);
        double const b3 = B3(uPrime[i]);

        /* rhs for eqn */
        Point const a1 = b1 * tHat1;
        Point const a2 = b2 * tHat2;

        C[0][0] += dot(a1, a1);
        C[0][1] += dot(a1, a2);
        C[1][0] = C[0][1];
        C[1][1] += dot(a2, a2);

        /* Additional offset to the data point from the predicted point if we were to set bezier[1]
           to bezier[0] and bezier[2] to bezier[3]. */
        Point const shortfall
            = ( data[i]
                - ( ( b0 + b1 ) * bezier[0] )
                - ( ( b2 + b3 ) * bezier[3] ) );
        X[0] += dot(a1, shortfall);
        X[1] += dot(a2, shortfall);
    }

    /* We've constructed a pair of equations in the form of a matrix product C * alpha = X.
       Now solve for alpha. */
    double alpha_l, alpha_r;

    /* Compute the determinants of C and X. */
    double const det_C0_C1 = C[0][0] * C[1][1] - C[1][0] * C[0][1];
    if ( det_C0_C1 != 0 ) {
        /* Apparently Kramer's rule. */
        double const det_C0_X  = C[0][0] * X[1]    - C[0][1] * X[0];
        double const det_X_C1  = X[0]    * C[1][1] - X[1]    * C[0][1];
        alpha_l = det_X_C1 / det_C0_C1;
        alpha_r = det_C0_X / det_C0_C1;
    } else {
        /* The matrix is under-determined.  Try requiring alpha_l == alpha_r.
         *
         * One way of implementing the constraint alpha_l == alpha_r is to treat them as the same
         * variable in the equations.  We can do this by adding the columns of C to form a single
         * column, to be multiplied by alpha to give the column vector X.
         *
         * We try each row in turn.
         */
        double const c0 = C[0][0] + C[0][1];
        if (c0 != 0) {
            alpha_l = alpha_r = X[0] / c0;
        } else {
            double const c1 = C[1][0] + C[1][1];
            if (c1 != 0) {
                alpha_l = alpha_r = X[1] / c1;
            } else {
                /* Let the below code handle this. */
                alpha_l = alpha_r = 0.;
            }
        }
    }

    /* If alpha negative, use the Wu/Barsky heuristic (see text).  (If alpha is 0, you get
       coincident control points that lead to divide by zero in any subsequent
       NewtonRaphsonRootFind() call.) */
    if ( alpha_l < 1.0e-6 ||
         alpha_r < 1.0e-6   )
    {
        alpha_l = alpha_r = distance(data[0], data[len-1]) / 3.0;
    }

    /* Control points 1 and 2 are positioned an alpha distance out on the tangent vectors, left and
       right, respectively. */
    bezier[1] = alpha_l * tHat1 + bezier[0];
    bezier[2] = alpha_r * tHat2 + bezier[3];

    return;
}

Linear Geom::extract_u	(	Linear2d const &	a,
		double	u
	)			[inline]

Definition at line 90 of file sbasis-2d.h.

                                                     {
    return Linear(a[0]*(1-u) +
                  a[1]*u,
                  a[2]*(1-u) +
                  a[3]*u);
}

SBasis Geom::extract_u	(	SBasis2d const &	a,
		double	u
	)

Linear Geom::extract_v	(	Linear2d const &	a,
		double	v
	)			[inline]

Definition at line 96 of file sbasis-2d.h.

                                                     {
    return Linear(a[0]*(1-v) +
                  a[2]*v,
                  a[1]*(1-v) +
                  a[3]*v);
}

SBasis Geom::extract_v	(	SBasis2d const &	a,
		double	v
	)

double Geom::f_interp	(	double	x,
		void *	p
	)

Definition at line 82 of file chebyshev.cpp.

References Geom::wrap::f, Geom::wrap::fa, Geom::wrap::fb, Geom::wrap::in, and Geom::wrap::pp.

                                   {
    struct wrap *wr = (struct wrap *)p;
    double z = (x - wr->in[0]) / (wr->in[1] - wr->in[0]);
    return (wr->f)(x, wr->pp) - ((1 - z)*wr->fa + z*wr->fb);
}

std::vector< std::vector< unsigned > > Geom::fake_cull	(	unsigned	a,
		unsigned	b
	)

Geom::Point Geom::finalPoint

(

PathVector const &

path_in

)

[inline]

Definition at line 97 of file pathvector.h.

Referenced by Inkscape::LivePathEffect::LPELineSegment::doEffect_path().

{
    return path_in.back().finalPoint();
}

void Geom::find_bernstein_roots	(	double const *	w,
		unsigned	degree,
		std::vector< double > &	solutions,
		unsigned	depth,
		double	left_t,
		double	right_t,
		bool	use_secant
	)

Referenced by Geom::Bezier::roots().

unsigned Geom::find_bottom_right

(

ConvexHull const &

a

)

void Geom::find_collinear_normal	(	std::vector< std::pair< double, double > > &	xs,
		std::vector< Point > const &	A,
		std::vector< Point > const &	B,
		double	precision = 1e-5
	)

Definition at line 1246 of file bezier-clipping.cpp.

References Geom::detail::bezier_clipping::get_solutions().

{
    using detail::bezier_clipping::get_solutions;
    using detail::bezier_clipping::collinear_normal_tag;
    get_solutions<collinear_normal_tag>(xs, A, B, precision);
}

unsigned Geom::find_crossing	(	Crossings const &	cr,
		Crossing	x,
		unsigned	i
	)

Definition at line 89 of file 2geom/shape.cpp.

                                                                    {
    return std::lower_bound(cr.begin(), cr.end(), x, CrossingOrder(i)) - cr.begin();
}

void Geom::find_intersections	(	std::vector< std::pair< double, double > > &	xs,
		std::vector< Point > const &	A,
		std::vector< Point > const &	B,
		double	precision
	)

void Geom::find_intersections	(	std::vector< std::pair< double, double > > &	xs,
		D2< SBasis > const &	A,
		D2< SBasis > const &	B
	)

Referenced by Inkscape::LivePathEffect::LPEKnotNS::CrossingPoints::CrossingPoints().

void Geom::find_intersections_bezier_clipping	(	std::vector< std::pair< double, double > > &	xs,
		std::vector< Point > const &	A,
		std::vector< Point > const &	B,
		double	precision = 1e-5
	)

Definition at line 1268 of file bezier-clipping.cpp.

References Geom::detail::bezier_clipping::get_solutions().

{
    using detail::bezier_clipping::get_solutions;
    using detail::bezier_clipping::intersection_point_tag;
    get_solutions<intersection_point_tag>(xs, A, B, precision);
}

void Geom::find_intersections_bezier_recursive	(	std::vector< std::pair< double, double > > &	xs,
		vector< Geom::Point > const &	A,
		vector< Geom::Point > const &	B,
		double	precision
	)

Definition at line 63 of file recursive-bezier-intersection.cpp.

References org::w3c::dom::svg::a, b, find_intersections_bezier_recursive(), and Geom::OldBezier::p.

                                      {
    OldBezier a, b;
    a.p = A;
    b.p = B;
    return find_intersections_bezier_recursive(xs, a,b);
}

void Geom::find_intersections_bezier_recursive	(	std::vector< std::pair< double, double > > &	xs,
		OldBezier	a,
		OldBezier	b
	)			[static]

Definition at line 445 of file recursive-bezier-intersection.cpp.

References intersect_BB(), recursively_intersect(), and wangs_theorem().

Referenced by find_intersections_bezier_recursive().

{
    if( intersect_BB( a, b ) )
    {
    recursively_intersect( a, 0., 1., wangs_theorem(a),
                               b, 0., 1., wangs_theorem(b),
                               xs);
    }
    /*for(unsigned i = 0; i < xs.size(); i++)
        intersect_polish_root(a, xs[i].first,
        b, xs[i].second);*/
    std::sort(xs.begin(), xs.end());
}

void Geom::find_parametric_bezier_roots	(	Geom::Point const *	w,
		unsigned	degree,
		std::vector< double > &	solutions,
		unsigned	depth
	)

void Geom::find_self_intersections	(	std::vector< std::pair< double, double > > &	xs,
		D2< SBasis > const &	A
	)

Referenced by Inkscape::LivePathEffect::LPEKnotNS::CrossingPoints::CrossingPoints().

std::vector<double> Geom::find_tangents	(	Point	P,
		D2< SBasis > const &	A
	)

returns all the parameter values of A whose tangent passes through P.

Definition at line 747 of file sbasis-geometric.cpp.

References Geom::D2< T >::cross(), Geom::detail::bezier_clipping::derivative(), roots(), and shift().

                                                              {
    SBasis crs (cross(A - P, derivative(A)));
    crs = shift(crs*Linear(-1, 0)*Linear(-1, 0), -2); // We know that there is a double root at t=0 so we divide out t^2
// JFB points out that this is equivalent to (t-1)^2 followed by a divide by s^2 (shift)
    return roots(crs);
}

void Geom::first_false	(	std::vector< std::vector< bool > >	visited,
		unsigned &	i,
		unsigned &	j
	)

Definition at line 78 of file 2geom/shape.cpp.

References scour::end, and org::w3c::dom::find().

                                                                                {
    for(i = 0, j = 0; i < visited.size(); i++) {
        std::vector<bool>::iterator unvisited = std::find(visited[i].begin(), visited[i].end(), false);
        if(unvisited != visited[i].end()) {
            j = unvisited - visited[i].begin();
            break;
        }
    }
}

void Geom::flip_crossings

(

Crossings &

crs

)

Definition at line 762 of file path-intersection.cpp.

References Barcode::Code39Ext::i.

                                    {
    for(unsigned i = 0; i < crs.size(); i++)
        crs[i] = Crossing(crs[i].tb, crs[i].ta, crs[i].b, crs[i].a, !crs[i].dir);
}

Piecewise<D2<SBasis> > Geom::force_continuity	(	Piecewise< D2< SBasis > > const &	f,
		double	tol,
		bool	closed
	)

Definition at line 135 of file d2-sbasis.cpp.

References c, Geom::SBasis::empty(), org::w3c::dom::svg::f, L2sq(), org::w3c::dom::svg::result, and Geom::Piecewise< T >::segs.

Referenced by Inkscape::LivePathEffect::LPERecursiveSkeleton::doEffect_pwd2(), Inkscape::LivePathEffect::LPEPatternAlongPath::doEffect_pwd2(), Inkscape::LivePathEffect::LPEEnvelope::doEffect_pwd2(), Inkscape::LivePathEffect::LPEDynastroke::doEffect_pwd2(), and Inkscape::LivePathEffect::LPEBendPath::doEffect_pwd2().

{
    if (f.size()==0) return f;
    Piecewise<D2<SBasis> > result=f;
    unsigned cur   = (closed)? 0:1;
    unsigned prev  = (closed)? f.size()-1:0;
    while(cur<f.size()){
        Point pt0 = f.segs[prev].at1();
        Point pt1 = f.segs[cur ].at0();
        if (tol<=0 || L2sq(pt0-pt1)<tol*tol){
            pt0 = (pt0+pt1)/2;
            for (unsigned dim=0; dim<2; dim++){
                SBasis &prev_sb=result.segs[prev][dim];
                SBasis &cur_sb =result.segs[cur][dim];
                Coord const c=pt0[dim];
                if (prev_sb.empty()) {
                  prev_sb = SBasis(Linear(0.0, c));
                } else {
                  prev_sb[0][1] = c;
                }
                if (cur_sb.empty()) {
                  cur_sb = SBasis(Linear(c, 0.0));
                } else {
                  cur_sb[0][0] = c;
                }
            }
        }
        prev = cur++;
    }
    return result;
}

Matrix Geom::from_basis	(	Point const	x_basis,
		Point const	y_basis,
		Point const	offset
	)

Creates a Matrix given an axis and origin point.

The axis is represented as two vectors, which represent skew, rotation, and scaling in two dimensions. from_basis(Point(1, 0), Point(0, 1), Point(0, 0)) would return the identity matrix.

Parameters:

	x_basis	the vector for the x-axis.
	y_basis	the vector for the y-axis.
	offset	the translation applied by the matrix.

Returns:

The new Matrix.

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

double Geom::fudgerize	(	double	d,
		bool	rev
	)

Definition at line 320 of file 2geom/shape.cpp.

Referenced by pick_coincident().

                                     {
    double ret = rev ? d - 0.01 : d + 0.01;
    if(ret < 0) ret = 0;
    return ret;
}

std::vector<Piecewise<D2<SBasis> > > Geom::fuse_nearby_ends	(	std::vector< Piecewise< D2< SBasis > > > const &	f,
		double	tol
	)

Definition at line 215 of file d2-sbasis.cpp.

References org::w3c::dom::svg::a, b, Geom::Piecewise< T >::concat(), org::w3c::dom::svg::f, Geom::Piecewise< T >::firstValue(), Barcode::Code39Ext::i, L2(), Geom::Piecewise< T >::lastValue(), org::w3c::dom::svg::result, Geom::Piecewise< T >::segs, set_first_point(), and set_last_point().

Referenced by Inkscape::LivePathEffect::LPEPatternAlongPath::doEffect_pwd2().

                                                                                                            {

    if ( f.size()==0 ) return f;
    std::vector<Piecewise<D2<SBasis> > > result;
    std::vector<std::vector<unsigned> > pre_result;
    for (unsigned i=0; i<f.size(); i++){
        bool inserted = false;
        Point a = f[i].firstValue();
        Point b = f[i].lastValue();
        for (unsigned j=0; j<pre_result.size(); j++){
            Point aj = f.at(pre_result[j].back()).lastValue();
            Point bj = f.at(pre_result[j].front()).firstValue();
            if ( L2(a-aj) < tol ) {
                pre_result[j].push_back(i);
                inserted = true;
                break;
            }
            if ( L2(b-bj) < tol ) {
                pre_result[j].insert(pre_result[j].begin(),i);
                inserted = true;
                break;
            }
        }
        if (!inserted) {
            pre_result.push_back(std::vector<unsigned>());
            pre_result.back().push_back(i);
        }
    }
    for (unsigned i=0; i<pre_result.size(); i++){
        Piecewise<D2<SBasis> > comp;
        for (unsigned j=0; j<pre_result[i].size(); j++){
            Piecewise<D2<SBasis> > new_comp = f.at(pre_result[i][j]);
            if ( j>0 ){
                set_first_point( new_comp, comp.segs.back().at1() );
            }
            comp.concat(new_comp);
        }
        if ( L2(comp.firstValue()-comp.lastValue()) < tol ){
            //TODO: check sizes!!!
            set_last_point( comp, comp.segs.front().at0() ); 
        }
        result.push_back(comp);
    }
    return result;
    return f;
}

Poly Geom::gcd	(	Poly const &	a,
		Poly const &	b,
		const	double
	)

static void Geom::generate_bezier	(	Point	bezier[],
		Point const	data[],
		double const	u[],
		unsigned const	len,
		Point const &	tHat1,
		Point const &	tHat2,
		double const	tolerance_sq
	)			[static]

Fill in bezier[] based on the given data and tangent requirements, using a least-squares fit.

Each of tHat1 and tHat2 should be either a zero vector or a unit vector. If it is zero, then bezier[1 or 2] is estimated without constraint; otherwise, it bezier[1 or 2] is placed in the specified direction from bezier[0 or 3].

Parameters:

tolerance_sq

Used only for an initial guess as to tangent directions when tHat1 or tHat2 is zero.

Definition at line 368 of file bezier-utils.cpp.

References darray_left_tangent(), darray_right_tangent(), estimate_bi(), estimate_lengths(), is_zero(), and unit_vector().

{
    bool const est1 = is_zero(tHat1);
    bool const est2 = is_zero(tHat2);
    Point est_tHat1( est1
                         ? darray_left_tangent(data, len, tolerance_sq)
                         : tHat1 );
    Point est_tHat2( est2
                         ? darray_right_tangent(data, len, tolerance_sq)
                         : tHat2 );
    estimate_lengths(bezier, data, u, len, est_tHat1, est_tHat2);
    /* We find that darray_right_tangent tends to produce better results
       for our current freehand tool than full estimation. */
    if (est1) {
        estimate_bi(bezier, 1, data, u, len);
        if (bezier[1] != bezier[0]) {
            est_tHat1 = unit_vector(bezier[1] - bezier[0]);
        }
        estimate_lengths(bezier, data, u, len, est_tHat1, est_tHat2);
    }
}

NodeType Geom::get_nodetype	(	Curve const &	c_incoming,
		Curve const &	c_outgoing
	)

Referenced by Inkscape::LivePathEffect::LPESpiro::doEffect(), and sp_shape_snappoints().

ConvexHull Geom::graham_merge	(	ConvexHull	a,
		ConvexHull	b
	)

if we modified graham scan to work top to bottom as proposed in lect754.pdf we could replace the angle sort with a simple merge sort type algorithm. furthermore, we could do the graham scan online, avoiding a bunch of memory copies. That would probably be linear. -- njh

template<typename T >

D2<SBasis> Geom::handles_to_sbasis	(	T const &	handles,
		unsigned	order
	)			[inline]

Definition at line 70 of file bezier-to-sbasis.h.

References bezier_to_sbasis(), and Barcode::Code39Ext::i.

{
    D2<SBasis> sbc;
    size_t sz = order + 1;
    std::vector<Point> v;
    v.reserve(sz);
    for (size_t i = 0; i < sz; ++i)
        v.push_back(handles[i]);
    bezier_to_sbasis(sbc, v);
    return sbc;
}

double Geom::hausdorf	(	D2< SBasis > &	A,
		D2< SBasis > const &	B,
		double	m_precision,
		double *	a_t,
		double *	b_t
	)

Compute the symmetric Hausdorf distance.

double Geom::hausdorfl	(	D2< SBasis > &	A,
		D2< SBasis > const &	B,
		double	m_precision,
		double *	a_t,
		double *	b_t
	)

Compute the Hausdorf distance from A to B only.

Matrix Geom::identity

(

)

[inline]

Returns the Identity Matrix.

Definition at line 136 of file matrix.h.

Referenced by Inkscape::ObjectSnapper::_collectPaths(), Inkscape::Extension::Internal::CairoRenderContext::_createPatternPainter(), Inkscape::ObjectSnapper::_snapPaths(), box3d_set_transform(), clip_ref_changed(), clonetiler_get_transform(), Inkscape::UI::SkewHandle::computeTransform(), Inkscape::UI::ScaleSideHandle::computeTransform(), Inkscape::UI::ScaleCornerHandle::computeTransform(), connector_spacing_changed(), Inkscape::ObjectSnapper::constrainedSnap(), Inkscape::Extension::Internal::CairoRenderer::createContext(), SPGradientTest::createSuiteSubclass(), do_trace(), do_update(), feed_path_to_cairo(), Inkscape::ObjectSnapper::freeSnap(), generate_marker(), Inkscape::Filters::FilterUnits::get_matrix_user2units(), Inkscape::ObjectSnapper::guideConstrainedSnap(), Inkscape::ObjectSnapper::guideFreeSnap(), i2anc_affine(), i2i_affine(), SPItem::init(), font_instance::InitTheFace(), Inkscape::Extension::Internal::LaTeXTextRenderer::LaTeXTextRenderer(), font_instance::LoadGlyph(), mask_ref_changed(), nr_arena_shape_update_fill(), nr_arena_shape_update_stroke(), Inkscape::LivePathEffect::GroupBBoxEffect::original_bbox(), paint(), Path_for_item(), Inkscape::UI::PathManipulator::PathManipulator(), pattern_tile(), Inkscape::Filters::FilterImage::render(), Inkscape::LivePathEffect::LPERoughHatches::resetDefaults(), Inkscape::LivePathEffect::LPEExtrude::resetDefaults(), Inkscape::SelTrans::scaleRequest(), set_to_accumulated(), Inkscape::UI::Widget::RegisteredTransformedPoint::setTransform(), Inkscape::SelTrans::skewRequest(), sp_canvas_item_i2w_affine(), sp_canvas_item_init(), sp_canvastext_init(), sp_document_setup_viewport(), sp_dyna_draw_context_root_handler(), sp_flood_do_flood_fill(), sp_flowtext_modified(), sp_flowtext_print(), sp_flowtext_show(), sp_flowtext_update(), sp_gradient_convert_to_userspace(), sp_gradient_init(), sp_gradient_reset_to_userspace(), sp_gradient_set(), sp_image_set_curve(), sp_item_gradient_get_coords(), sp_item_group_ungroup(), sp_item_invoke_show(), sp_item_set(), sp_item_transform_repr(), sp_item_update(), sp_item_write_transform(), sp_line_set_transform(), sp_lineargradient_painter_new(), sp_marker_update(), sp_offset_move_compensate(), sp_path_set_transform(), sp_root_build(), sp_root_update(), sp_selected_path_create_offset_object(), sp_selected_path_do_offset(), sp_selected_path_simplify_item(), sp_selection_group_impl(), sp_selection_paste_impl(), sp_shape_print(), Inkscape::Extension::Internal::sp_shape_render(), sp_shape_show(), sp_shape_update(), sp_svg_transform_read(), sp_symbol_init(), Inkscape::Extension::Internal::sp_symbol_render(), sp_symbol_update(), sp_text_modified(), sp_text_print(), sp_text_show(), sp_text_update(), sp_use_get_parent_transform(), sp_use_get_root_transform(), sp_use_unlink(), sp_use_update(), Inkscape::SelTrans::stretchRequest(), SPGradientTest::testGetG2dGetGs2dSetGs2d(), SvgAffineTest::testReadIdentity(), SPGradientTest::testSetGradientTransform(), and SvgAffineTest::testWriteIdentity().

                         {
    return Matrix(1.0, 0.0,
                  0.0, 1.0,
                  0.0, 0.0);
}

template<typename iter >

iter Geom::inc	(	iter const &	x,
		unsigned	n
	)			[inline]

Definition at line 73 of file 2geom/path.cpp.

References Barcode::Code39Ext::i.

Referenced by Geom::Path::appendPortionTo().

                                    {
  iter ret = x;
  for(unsigned i = 0; i < n; i++)
    ret++;
  return ret;
}

Coord Geom::infinity

(

)

[inline]

Definition at line 51 of file coord.h.

Referenced by NR::Rect::_inf(), gr_knot_moved_handler(), and Inkscape::LivePathEffect::ArrayParam< StorageType >::readsvg().

{  return std::numeric_limits<Coord>::infinity();  }

Geom::Point Geom::initialPoint

(

PathVector const &

path_in

)

[inline]

Definition at line 91 of file pathvector.h.

Referenced by Inkscape::LivePathEffect::LPELineSegment::doEffect_path(), and Inkscape::LivePathEffect::LPEConstructGrid::doEffect_path().

{
    return path_in.front().initialPoint();
}

std::vector<Path> Geom::inner_sanitize

(

std::vector< Path > const &

ps

)

Definition at line 416 of file 2geom/shape.cpp.

References Geom::Path::append(), crossing_along(), crossing_dual(), crossings_among(), Geom::Crossing::getTime(), outer_crossing(), uniconv-ext::p, pick_coincident(), reverse(), Geom::Path::size(), and Geom::Path::STITCH_DISCONTINUOUS.

                                                           {
    CrossingSet crs(crossings_among(ps));
    
    Regions chunks;
    
    std::vector<bool> used_path(ps.size(), false);
    std::vector<std::vector<bool> > visited;
    for(unsigned i = 0; i < crs.size(); i++)
        visited.push_back(std::vector<bool>(crs[i].size(), false));
    
    std::vector<Path> result_paths;
    
    while(true) {
        unsigned ix = 0, jx = 0;
        bool dir = false;

        //find an outer crossing by trying various paths and checking if the crossings are used
        for(; ix < crs.size(); ix++) {
            //TODO: optimize so it doesn't unecessarily check stuff
            bool cont = true;
            for(unsigned j = 0; j < crs[ix].size(); j++) {
                if(!visited[ix][j]) { cont = false; break; }
            }
            if(cont) continue;
            unsigned rix = ix, rjx = jx;
            outer_crossing(rix, rjx, dir, ps, crs);
            if(rix >= crs.size() || visited[rix][rjx]) continue;
            ix = rix; jx = rjx;
            break;
        }
        if(ix == crs.size()) break;
        crossing_dual(ix, jx, crs);

        dir = !dir;

        Path res;
        do {
            visited[ix][jx] = true;
            //unsigned nix = ix, njx = jx;
            //crossing_dual(nix, njx, crs);
            //visited[nix][njx] = true;
            unsigned fix = ix, fjx = jx;
            
            bool new_dir = dir;
            
            jx = crossing_along(crs[ix][jx].getTime(ix), ix, jx, dir, crs[ix]);
            if(crs[ix][jx].a != crs[ix][jx].b) crossing_dual(ix, jx, crs); else new_dir = !new_dir;
            jx = pick_coincident(ix, jx, new_dir, ps, crs);
            
            //unsigned nix = ix, njx = jx;
            //crossing_dual(nix, njx, crs);
            
            Crossing from = crs[fix][fjx],
                     to = crs[ix][jx];
            if(dir) {
                // backwards
#ifdef SHAPE_DEBUG
                std::cout << "r" << ix << "[" << from.getTime(ix)  << ", " << to.getTime(ix) << "]\n";
#endif
                Path p = ps[ix].portion(from.getTime(ix), to.getTime(ix)).reverse();
                for(unsigned i = 0; i < p.size(); i++)
                    res.append(p[i], Path::STITCH_DISCONTINUOUS);
            } else {
                // forwards
#ifdef SHAPE_DEBUG
                std::cout << "f" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n";
#endif
                ps[ix].appendPortionTo(res, from.getTime(ix), to.getTime(ix));
            }
            dir = new_dir;
        } while(!visited[ix][jx]);
#ifdef SHAPE_DEBUG
        std::cout << "added " << res.size() << "\n";
#endif
        result_paths.push_back(res);
    }
    for(unsigned i = 0; i < crs.size(); i++) {
        if(crs[i].empty() && !used_path[i])
            result_paths.push_back(ps[i]);
    }
    return result_paths;
}

int Geom::inner_winding	(	Path const &	p,
		std::vector< Path > const &	ps
	)

Definition at line 315 of file 2geom/shape.cpp.

References Geom::Path::initialPoint(), paths_winding(), and winding().

                                                             {
    Point pnt = p.initialPoint();
    return paths_winding(ps, pnt) - winding(p, pnt) + 1;
}

SBasis Geom::integral

(

SBasis const &

c

)

Compute the integral of a (Exact).

Parameters:

a

sbasis functions

Returns:

sbasis integral(a)

SBasis2d Geom::integral

(

SBasis2d const &

c

)

Poly Geom::integral

(

Poly const &

p

)

template<typename T >

Piecewise<T> Geom::integral

(

Piecewise< T > const &

a

)

[inline]

Definition at line 738 of file piecewise.h.

References c, Geom::Piecewise< T >::cuts, Barcode::Code39Ext::i, integral(), org::w3c::dom::svg::result, and Geom::Piecewise< T >::segs.

                                             {
    Piecewise<T> result;
    result.segs.resize(a.segs.size());
    result.cuts = a.cuts;
    typename T::output_type c = a.segs[0].at0();
    for(unsigned i = 0; i < a.segs.size(); i++){
        result.segs[i] = integral(a.segs[i])*(a.cuts[i+1]-a.cuts[i]);
        result.segs[i]+= c-result.segs[i].at0();
        c = result.segs[i].at1();
    }
    return result;
}

template<typename T >

D2<T> Geom::integral

(

D2< T > const &

a

)

[inline]

Definition at line 415 of file d2.h.

References integral(), X, and Y.

                                {
    return D2<T>(integral(a[X]), integral(a[Y]));
}

Bezier Geom::integral

(

const Bezier &

a

)

[inline]

Definition at line 373 of file bezier.h.

References Barcode::Code39Ext::i, and Geom::Bezier::order().

Referenced by arcLengthSb(), atan2(), centroid(), Inkscape::LivePathEffect::LPESketch::doEffect_pwd2(), Inkscape::LivePathEffect::LPEPathLength::doEffect_pwd2(), and integral().

                                         {
    Bezier inte(Bezier::Order(a.order()+1));

    inte[0] = 0;
    for(unsigned i = 0; i < inte.order(); i++) {
        inte[i+1] = inte[i] + a[i]/(inte.order());
    }
    return inte;
}

Piecewise< SBasis > Geom::interpolate	(	std::vector< double >	times,
		std::vector< double >	values,
		unsigned	smoothness
	)

Retruns a Piecewise SBasis with prescribed values at prescribed times.

Parameters:

	times,:	vector of times at which the values are given. Should be sorted in increasing order.
	values,:	vector of prescribed values. Should have the same size as times and be sorted accordingly.
	smoothness,:	(defaults to 1) regularity class of the result: 0=piecewise linear, 1=continuous derivative, etc...

OptRect Geom::intersect	(	Rect const &	a,
		Rect const &	b
	)			[inline]

Definition at line 250 of file rect.h.

References intersect(), X, and Y.

                                                         {
    return OptRect(intersect(a[X], b[X]), intersect(a[Y], b[Y]));
}

OptInterval Geom::intersect	(	const Interval &	a,
		const Interval &	b
	)			[inline]

Definition at line 257 of file interval.h.

References Geom::Interval::max(), max(), min, and Geom::Interval::min().

Referenced by intersect().

                                                                     {
    Coord u = std::max(a.min(), b.min()),
          v = std::min(a.max(), b.max());
    //technically >= might be incorrect, but singulars suck
    return u > v ? OptInterval()
                  : OptInterval(Interval(u, v));
}

bool Geom::intersect_BB	(	OldBezier	a,
		OldBezier	b
	)

Definition at line 170 of file recursive-bezier-intersection.cpp.

References Geom::OldBezier::bounds().

Referenced by find_intersections_bezier_recursive(), and recursively_intersect().

                                              {
    double minax, maxax, minay, maxay;
    a.bounds(minax, maxax, minay, maxay);
    double minbx, maxbx, minby, maxby;
    b.bounds(minbx, maxbx, minby, maxby);
    // Test bounding box of b against bounding box of a
    // Not >= : need boundary case
    return not( ( minax > maxbx ) || ( minay > maxby )
                || ( minbx > maxax ) || ( minby > maxay ) );
}

static int Geom::intersect_polish_f	(	const gsl_vector *	x,
		void *	params,
		gsl_vector *	f
	)			[static]

Definition at line 341 of file recursive-bezier-intersection.cpp.

Referenced by intersect_polish_root().

{
    const double x0 = gsl_vector_get (x, 0);
    const double x1 = gsl_vector_get (x, 1);

    Geom::Point dx = ((struct rparams *) params)->A(x0) -
        ((struct rparams *) params)->B(x1);

    gsl_vector_set (f, 0, dx[0]);
    gsl_vector_set (f, 1, dx[1]);

    return GSL_SUCCESS;
}

static void Geom::intersect_polish_root	(	OldBezier &	A,
		double &	s,
		OldBezier &	B,
		double &	t
	)			[static]

Definition at line 370 of file recursive-bezier-intersection.cpp.

References c, addnodes::e, EpsilonBy(), org::w3c::dom::svg::f, intersect_polish_f(), L1(), n, status, and voronoi::x.

                                                            {
    const gsl_multiroot_fsolver_type *T;
    gsl_multiroot_fsolver *sol;

    int status;
    size_t iter = 0;

    const size_t n = 2;
    struct rparams p = {A, B};
    gsl_multiroot_function f = {&intersect_polish_f, n, &p};

    double x_init[2] = {s, t};
    gsl_vector *x = gsl_vector_alloc (n);

    gsl_vector_set (x, 0, x_init[0]);
    gsl_vector_set (x, 1, x_init[1]);

    T = gsl_multiroot_fsolver_hybrids;
    sol = gsl_multiroot_fsolver_alloc (T, 2);
    gsl_multiroot_fsolver_set (sol, &f, x);

    do
    {
        iter++;
        status = gsl_multiroot_fsolver_iterate (sol);

        if (status)   /* check if solver is stuck */
            break;

        status =
            gsl_multiroot_test_residual (sol->f, 1e-12);
    }
    while (status == GSL_CONTINUE && iter < 1000);

    s = gsl_vector_get (sol->x, 0);
    t = gsl_vector_get (sol->x, 1);

    gsl_multiroot_fsolver_free (sol);
    gsl_vector_free (x);
    
    // This code does a neighbourhood search for minor improvements.
    double best_v = L1(A(s) - B(t));
    //std::cout  << "------\n" <<  best_v << std::endl;
    Point best(s,t);
    while (true) {
        Point trial = best;
        double trial_v = best_v;
        for(int nsi = -1; nsi < 2; nsi++) {
        for(int nti = -1; nti < 2; nti++) {
            Point n(EpsilonBy(best[0], nsi),
                    EpsilonBy(best[1], nti));
            double c = L1(A(n[0]) - B(n[1]));
            //std::cout << c << "; ";
            if (c < trial_v) {
                trial = n;
                trial_v = c;
            }
        }
        }
        if(trial == best) {
            //std::cout << "\n" << s << " -> " << s - best[0] << std::endl;
            //std::cout << t << " -> " << t - best[1] << std::endl;
            //std::cout << best_v << std::endl;
            s = best[0];
            t = best[1];
            return;
        } else {
            best = trial;
            best_v = trial_v;
        }
    }
}

static void Geom::intersect_polish_root	(	Curve const &	A,
		double &	s,
		Curve const &	B,
		double &	t
	)			[static]

we want to solve J*(x1 - x0) = f(x0)

|dA(s)[0] -dB(t)[0]| (X1 - X0) = A(s) - B(t) |dA(s)[1] -dB(t)[1]|

Definition at line 229 of file path-intersection.cpp.

References dot(), addnodes::e, Barcode::Code39Ext::i, intersect_polish_f(), Geom::Matrix::inverse(), n, Geom::Curve::pointAndDerivatives(), and status.

                                                  {
    std::vector<Point> as, bs;
    as = A.pointAndDerivatives(s, 2);
    bs = B.pointAndDerivatives(t, 2);
    Point F = as[0] - bs[0];
    double best = dot(F, F);

    for(int i = 0; i < 4; i++) {

        // We're using the standard transformation matricies, which is numerically rather poor.  Much better to solve the equation using elimination.

        Matrix jack(as[1][0], as[1][1],
                    -bs[1][0], -bs[1][1],
                    0, 0);
        Point soln = (F)*jack.inverse();
        double ns = s - soln[0];
        double nt = t - soln[1];

        if (ns<0) ns=0;
        else if (ns>1) ns=1;
        if (nt<0) nt=0;
        else if (nt>1) nt=1;

        as = A.pointAndDerivatives(ns, 2);
        bs = B.pointAndDerivatives(nt, 2);
        F = as[0] - bs[0];
        double trial = dot(F, F);
        if (trial > best*0.1) // we have standards, you know
            // At this point we could do a line search
            break;
        best = trial;
        s = ns;
        t = nt;
    }

#ifdef HAVE_GSL
    if(0) { // the GSL version is more accurate, but taints this with GPL
        const size_t n = 2;
        struct rparams p = {A, B};
        gsl_multiroot_function f = {&intersect_polish_f, n, &p};

        double x_init[2] = {s, t};
        gsl_vector *x = gsl_vector_alloc (n);

        gsl_vector_set (x, 0, x_init[0]);
        gsl_vector_set (x, 1, x_init[1]);

        const gsl_multiroot_fsolver_type *T = gsl_multiroot_fsolver_hybrids;
        gsl_multiroot_fsolver *sol = gsl_multiroot_fsolver_alloc (T, 2);
        gsl_multiroot_fsolver_set (sol, &f, x);

        int status = 0;
        size_t iter = 0;
        do
        {
            iter++;
            status = gsl_multiroot_fsolver_iterate (sol);

            if (status)   /* check if solver is stuck */
                break;

            status =
                gsl_multiroot_test_residual (sol->f, 1e-12);
        }
        while (status == GSL_CONTINUE && iter < 1000);

        s