PathUtil Class Reference

Base class for path utility static functions. These functions operate on sections of paths, ie lists of doc coords, but do not process complete paths and hence cannot be included as member functions of the paths class. The class contains no member variables, just static member functions which would otherwise be global if not for the fabby idea of encompasing them together under a class structure. More...

#include <pathutil.h>

List of all members.

Static Public Member Functions
static BOOL	SplitLine (const double, const DocCoord *, UINT32 *, PathVerb *, DocCoord *)
	Splits a line element into two lines, returning the lists of new coord points and verbs.
static BOOL	SplitCurve (const double, const DocCoord *, UINT32 *, PathVerb *, DocCoord *)
	Splits a curve element into two curves, returning the lists of new control points and verbs.
static void	GetCurveCoefs (const DocCoord *, PtCoefs *)
	Converts a curve from Bezier form to Canonical form.
static DocCoord	PointOnLine (const double, const DocCoord *)
	Given a parameter t go and evaluate the point on the described line segment If t is out of range, ie t>1 or t<0 the end points of the line will be returned. ie the routine will not evaluate unbounded points.
static DocCoord	PointOnSemiCircle (const DocCoord &centre, const DocCoord &radialp, double t)
	Find a point on the circumference of a semicircle. The semicircle is specified by two points, it's centre and a point on the circumference. If c=0,0 and p=(1,0) then the semicircle exists in the y positive half of the plane from sweeping from (-1,0) at t==0 to (1.0) at t==1.0.
static DocCoord	PointOnCurve (double, const DocCoord *)
	This function returns the distance to the closest point on the curve and the parameter of this pointEvaluate a bezier curve, given a pointer to a set of control points and a parameter value.
static double	SqrDistance (const DocCoord &p1, const DocCoord &p2)
	Accurate squared distance function.
static double	SqrDistanceToLine (const DocCoord *, const DocCoord &, double *)
	Calculates the distance p1 is away from a line segment. The perpendicular distance is returned only when p1 is within the volume created by sweeping the line in the orthoganal direction. Otherwise the distance to the closest end point is returned.
static double	SqrDistanceToSemiCircle (const DocCoord *, const DocCoord &, double *)
	Calculates the distance p1 is away from a semi circle segment. plist[0] describes the centre of the semi circle plist[1] describes a point on the circumference of the circle. For instance say c the centre is (0,0) and cp the circumference point is (1,0) then the semicircle exists in the positive y half of the place and sweeps from (-1,0) to (1,0). Parameter space is param==0 at (-1,0) param==1 at ( 1,0) param==0.5 at ( 0,1).
static double	SqrDistanceToCurve (const UINT32, const DocCoord *, const DocCoord &, double *)
	Compute the parameter value of the point on a Bezier curve segment closest to some arbtitrary, user-input point. Return the squared distance to the curve.

---

Detailed Description

Base class for path utility static functions. These functions operate on sections of paths, ie lists of doc coords, but do not process complete paths and hence cannot be included as member functions of the paths class. The class contains no member variables, just static member functions which would otherwise be global if not for the fabby idea of encompasing them together under a class structure.

Author:

Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com>

Date:

24/8/94

Definition at line 142 of file pathutil.h.

---

Member Function Documentation

void PathUtil::GetCurveCoefs (  const DocCoord *  coords, PtCoefs *  coefs )  [static]

Converts a curve from Bezier form to Canonical form. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: coords  = a pointer to 4 control point doccoords defining a curve [INPUTS] coefs  = a set of curve coefficients. [OUTPUTS] Returns: None Definition at line 492 of file pathutil.cpp. { // Read the curve coordinates. INT32 X0,Y0,X1,Y1,X2,Y2,X3,Y3; X0 = coords->x; Y0 = coords->y; coords++; X1 = coords->x; Y1 = coords->y; coords++; X2 = coords->x; Y2 = coords->y; coords++; X3 = coords->x; Y3 = coords->y; // Calculate the curve coefficients. coefs->ax = X3-X0+3*(X1-X2); coefs->ay = Y3-Y0+3*(Y1-Y2); coefs->bx = 3*(X2-2*X1+X0); coefs->by = 3*(Y2-2*Y1+Y0); coefs->cx = 3*(X1-X0); coefs->cy = 3*(Y1-Y0); }

DocCoord PathUtil::PointOnCurve (  double  t, const DocCoord *  plist )  [static]

This function returns the distance to the closest point on the curve and the parameter of this pointEvaluate a bezier curve, given a pointer to a set of control points and a parameter value. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: t  = parameter to evaluate curve at [INPUTS] plist = pointer to list of 4 curve control points. [OUTPUTS]  Returns: A DocCoord describing the point on the curve Definition at line 897 of file pathutil.cpp. { PtCoefs p; DocCoord c; PathUtil::GetCurveCoefs(plist, &p); // calculate coefs block if (t<0) t=0; // clamp range of parameter if (t>1) t=1; // Eval bezier at specified parameter double dx = t*(p.cx+t*(p.bx+t*p.ax)); double dy = t*(p.cy+t*(p.by+t*p.ay)); c.x = plist->x + (INT32)(dx+0.5); c.y = plist->y + (INT32)(dy+0.5); return c; }

DocCoord PathUtil::PointOnLine (  const double  t, const DocCoord *  ptlist )  [static]

Given a parameter t go and evaluate the point on the described line segment If t is out of range, ie t>1 or t<0 the end points of the line will be returned. ie the routine will not evaluate unbounded points. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: t  = parameter at which to evaluate point [INPUTS] ptlist = pointer to two doc coords describing start and end of the line [OUTPUTS]  Returns: DocCoord, an evaluation of a point on the specified line Definition at line 621 of file pathutil.cpp. { INT32 x0,y0,x1,y1; x0 = ptlist[0].x; y0 = ptlist[0].y; x1 = ptlist[1].x; y1 = ptlist[1].y; DocCoord d; if (t<=0.0) { d.x = x0; d.y = y0; return d; } if (t>=1.0) { d.x = x1; d.y = y1; return d; } d.x = x0 + (INT32)(t*(x1-x0)+0.5); d.y = y0 + (INT32)(t*(y1-y0)+0.5); return d; }

DocCoord PathUtil::PointOnSemiCircle (  const DocCoord &  centre, const DocCoord &  radialp, double  t )  [static]

Find a point on the circumference of a semicircle. The semicircle is specified by two points, it's centre and a point on the circumference. If c=0,0 and p=(1,0) then the semicircle exists in the y positive half of the plane from sweeping from (-1,0) at t==0 to (1.0) at t==1.0. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 05/03/97 Parameters: centre  = the centre point of the circle [INPUTS] radialp = another point (anywhere, but assumed to be somewhere on the radius of the circle. t = a parameter (0..1) defining the parametric locus about the centre from 0 to pi radians. -  [OUTPUTS] Returns: A new doc coord which is a point on the circles perimeter which corresponds to the parameter t. At t==1 the function will evaluate to radialp At t==0 the function will evaluate to centre-(radialp-centre) Errors: None. Definition at line 143 of file pathutil.cpp. { double X = (double)(radialp.x - centre.x); double Y = (double)(radialp.y - centre.y); double p = t * XS_PI; // spin clockwise. double s = sin(p); double c = -cos(p); DocCoord r; // circular rounding maybe? r.x = (INT32)(X*c - Y*s) + centre.x; r.y = (INT32)(X*s + Y*c) + centre.y; return r; }

BOOL PathUtil::SplitCurve (  const double  t, const DocCoord *  plist, UINT32 *  NumElements, PathVerb *  OutVerbs, DocCoord *  OutCoords )  [static]

Splits a curve element into two curves, returning the lists of new control points and verbs. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: t  = parameter at which to split the curve [INPUTS] plist = pointer to 4 curve control points to split NumElements  = number of elements generated [OUTPUTS] OutVerbs = output verbs list OutCoords = output coords list Returns: True if the curve could be split, False if not. Definition at line 406 of file pathutil.cpp. { // check t is in range for this split. if (t < SPLIT_EPSILON) return FALSE; if (t > (1.0 - SPLIT_EPSILON)) return FALSE; // fill in the path verb array, these are all curveto's for (INT32 i=0; i<6; i++) OutVerbs[i] = PT_BEZIERTO; // read the four curve control points INT32 x0,y0,x1,y1,x2,y2,x3,y3; x0 = plist[0].x; // note this should be move,line,curve y0 = plist[0].y; x1 = plist[1].x; // these should all be curveto's y1 = plist[1].y; x2 = plist[2].x; y2 = plist[2].y; x3 = plist[3].x; y3 = plist[3].y; // now calculate six new coordinates from the given 4 double tx,ty; tx = x1+t*(x2-x1); ty = y1+t*(y2-y1); double Lx1,Ly1,Lx2,Ly2,Rx0,Ry0,Rx1,Ry1,Rx2,Ry2; Lx1 = x0+t*(x1-x0); Ly1 = y0+t*(y1-y0); Rx2 = x2+t*(x3-x2); Ry2 = y2+t*(y3-y2); Lx2 = Lx1+t*(tx-Lx1); Ly2 = Ly1+t*(ty-Ly1); Rx1 = tx+t*(Rx2-tx); Ry1 = ty+t*(Ry2-ty); Rx0 = Lx2+t*(Rx1-Lx2); Ry0 = Ly2+t*(Ry1-Ly2); // set the return values OutCoords[0].x = (INT32)(Lx1+0.5); OutCoords[0].y = (INT32)(Ly1+0.5); OutCoords[1].x = (INT32)(Lx2+0.5); OutCoords[1].y = (INT32)(Ly2+0.5); OutCoords[2].x = (INT32)(Rx0+0.5); OutCoords[2].y = (INT32)(Ry0+0.5); OutCoords[3].x = (INT32)(Rx1+0.5); OutCoords[3].y = (INT32)(Ry1+0.5); OutCoords[4].x = (INT32)(Rx2+0.5); OutCoords[4].y = (INT32)(Ry2+0.5); OutCoords[5].x = x3; OutCoords[5].y = y3; // Set the output number of elements. *NumElements = 6; return TRUE; }

BOOL PathUtil::SplitLine (  const double  t, const DocCoord *  plist, UINT32 *  NumElements, PathVerb *  Verbs, DocCoord *  Coords )  [static]

Splits a line element into two lines, returning the lists of new coord points and verbs. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: t  = parameter at which to split the line [INPUTS] plist = pointer to 2 doc coords describing the line NumElements  = number of elements generated after split [OUTPUTS] OutVerbs = pointer to verbs list to output data to OutCoords = pointer to coords list to output data to Returns: True if the line can be split, False if not. Definition at line 317 of file pathutil.cpp. { // check t is in range for this split. if (t < SPLIT_EPSILON) return FALSE; if (t > (1.0 - SPLIT_EPSILON)) return FALSE; // read the lines start and end points INT32 x0,y0,x1,y1; x0 = plist[0].x; y0 = plist[0].y; x1 = plist[1].x; y1 = plist[1].y; // fill in the output block details Verbs[0] = PT_LINETO; Coords[0].x = x0 + (INT32)(t*(x1-x0)+0.5); Coords[0].y = y0 + (INT32)(t*(y1-y0)+0.5); Verbs[1] = PT_LINETO; Coords[1].x = x1; Coords[1].y = y1; *NumElements = 2; return TRUE; }

double PathUtil::SqrDistance (  const DocCoord &  p1, const DocCoord &  p2 )  [static]

Accurate squared distance function. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 20/8/94 Parameters: two  coordinates [INPUTS] None  [OUTPUTS] Returns: the squared distance between the two coordinates Errors: None. Definition at line 264 of file pathutil.cpp. { double dx = (double) (p2.x - p1.x); double dy = (double) (p2.y - p1.y); return ((dx*dx)+(dy*dy)); }

double PathUtil::SqrDistanceToCurve (  const UINT32  split, const DocCoord *  V, const DocCoord &  P, double *  mu )  [static]

Compute the parameter value of the point on a Bezier curve segment closest to some arbtitrary, user-input point. Return the squared distance to the curve. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: split  = max level at which to split the curve (usually 64) [INPUTS] P = The user-supplied point V = Control points of cubic Bezier mu  holds the parameter value of the closest point on the curve, 0<=mu<=1 [OUTPUTS] Returns: The squared distance to the curve Definition at line 1407 of file pathutil.cpp. { Point2 *w; // Ctrl pts for 5th-degree equ Point2 lcurve[DEGREE+1]; // Local double version of control polygon double t_candidate[W_DEGREE]; // Possible roots INT32 n_solutions; // Number of roots found double t; // Parameter value of closest pt double dist; // Closest squared distance to curve // Convert control polygon to double type for (INT32 i=0; i < DEGREE+1; i++) { lcurve[i].x = (double) V[i].x; lcurve[i].y = (double) V[i].y; } Point2 p; p.x = (double) P.x; p.y = (double) P.y; // Convert problem to 5th-degree Bezier form w = ConvertToBezierForm(p, lcurve); // Find all possible roots of 5th-degree equation n_solutions = FindRoots(w, W_DEGREE, t_candidate, 0); CCFree((char *)w); // Compare distances of P to all candidates, and to t=0, and t=1 { double new_dist; Point2 q; Vector2 v; // Check distance to beginning of curve, where t = 0 dist = V2SquaredLength(V2Sub(&p, lcurve, &v)); t = 0.0; // Find distances for candidate points for (INT32 i = 0; i < n_solutions; i++) { q = Bezier(lcurve, DEGREE, t_candidate[i], NULL, NULL); new_dist = V2SquaredLength(V2Sub(&p, &q, &v)); if (new_dist < dist) { dist = new_dist; t = t_candidate[i]; } } // Finally, look at distance to end point, where t = 1 new_dist = V2SquaredLength(V2Sub(&p, &(lcurve[DEGREE]), &v)); if (new_dist < dist) { dist = new_dist; t = 1.0; } } *mu = t; return dist; }

double PathUtil::SqrDistanceToLine (  const DocCoord *  plist, const DocCoord &  p1, double *  t )  [static]

Calculates the distance p1 is away from a line segment. The perpendicular distance is returned only when p1 is within the volume created by sweeping the line in the orthoganal direction. Otherwise the distance to the closest end point is returned. Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: plist  = a pointer to two doc coordinates describing a line [INPUTS] p1 = the point to find the squared distance to t  = the parameter at which the closest point exists [OUTPUTS] Returns: a double, the distance a given point is away from a line element Definition at line 541 of file pathutil.cpp. { // get hold of the lines end point coordinates INT32 x0,y0,x1,y1; x0 = plist[0].x; y0 = plist[0].y; x1 = plist[1].x; y1 = plist[1].y; INT32 pdx = (x1-x0); INT32 pdy = (y1-y0); // calculate the parameter at which the closest point exists // on an infinite line passing through (x0,y0),(x1,y1) // t=numdot/dendot. double numdot,dendot; numdot = (double)(p1.x - plist[0].x)*pdx + (double)(p1.y-plist[0].y)*pdy; dendot = (double)pdx*pdx + (double)pdy*pdy; // if t is less then zero then the closest point lies behind // the start point of the vector, hence return the squared // distance to the startpoint if (numdot<=0 || dendot<=0) { *t = 0.0; return (SqrDistance(p1, plist[0])); } // if t is greater than or equal to 1 then the closest point // lies beyond the line segment, ie on the projected line // beyond (x1,y1). So return the squared distance to that end // point. if (dendot<=numdot) { *t = 1.0; return (SqrDistance(p1,plist[1])); } // ok the closest point lies somewhere inside the line segment // (x0,y0),(x1,y1) so return its parameter and the squared // distance to it. *t = numdot/dendot; double c = (double)pdy*p1.x - (double)pdx*p1.y; double d = (double)y1*x0 - (double)y0*x1; double e = (c-d)*(c-d); return fabs(e/dendot); }

double PathUtil::SqrDistanceToSemiCircle (  const DocCoord *  plist, const DocCoord &  p, double *  param )  [static]

Calculates the distance p1 is away from a semi circle segment. plist[0] describes the centre of the semi circle plist[1] describes a point on the circumference of the circle. For instance say c the centre is (0,0) and cp the circumference point is (1,0) then the semicircle exists in the positive y half of the place and sweeps from (-1,0) to (1,0). Parameter space is param==0 at (-1,0) param==1 at ( 1,0) param==0.5 at ( 0,1). Author: Mike_Kenny (Xara Group Ltd) <camelotdev@xara.com> Date: 22/08/94 Parameters: plist  = a pointer to two doc coordinates describing a half circle [INPUTS] p1 = the point to find the squared distance to param  = the parameter at which the closest point exists [OUTPUTS] Returns: a double, the distance a given point is away from a line element Definition at line 188 of file pathutil.cpp. { double ex,ey,px,py,Px,Py,l,t; DocCoord c = plist[0]; // the centre point DocCoord e = plist[1]; // the end point DocCoord q; // translate to origin ex = e.x-c.x; ey = e.y-c.y; px = p.x-c.x; py = p.y-c.y; // build a (ex,ey) based transform l = sqrt(ex*ex+ey*ey); if (l!=0) { ex=ex/l; ey=ex/l; } // transform the click point to local canonical Px = px*ex+py*ey; Py = py*ex-px*ey; // are we below the half circle if (Py>0) { // no then calculate the dot product angle l = sqrt(Px*Px+Py*Py); if (l!=0) Px=Px/l; t = (XS_PI - acos(Px))/XS_PI; q = PathUtil::PointOnSemiCircle(c,p,t); } else { // yes then decide start point or endpoint if (Px>0) { t=1.0; q=e; } else { t=0.0; q=e-(c-e); } } // set the output parameter (*param)=t; // calculate the squared distance return PathUtil::SqrDistance(p,q); }

---

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

• Kernel/pathutil.h (r1785/r751)
• Kernel/pathutil.cpp (r1785/r1282)

---