pointsOnBezier: Generates points along a Bezier curve or spline

In bezier: Toolkit for Bezier Curves and Splines

Description

This function provides three different functionalities for generating points along a Bezier curve or spline. The first generates approximately evenly spaced points along a Bezier, optimizing point position according to specified convergence criteria. The second functionality places points along a Bezier such that the distance between consecutive points does not exceed a specified Euclidean distance. This second functionality does not generate evenly spaced points along the curve, instead providing a more rapid routine for generating a large number of points on a Bezier more evenly spaced than with parametric point generation. The last functionality generates adjoining points along a Bezier as a series of integers and is intended for use with pixel coordinates.

Usage

pointsOnBezier(p, n = NULL, method = 'evenly_spaced', t1 = 0, t2 = NULL, 
               deg = NULL, max.dist = NULL, max.dist.factor = 0.1, 
               relative.min.slope = 1e-7, absolute.min.slope = 0, 
               sub.relative.min.slope = 1e-4, sub.absolute.min.slope = 0, 
               print.progress = FALSE)

Arguments

p	control points, input either as vector, matrix or list (see bezier).
n	the number of points to generate along the Bezier. Ignored if method is 'max_dist' or 'adjoining'.
method	the method to be used in generating the points. Either 'evenly_spaced', 'max_dist' or 'adjoining'. Does not need to be specified if max.dist or n are non-NULL.
t1	a parametric value for a Bezier curve or spline at which the points will start.
t2	a parametric value for a Bezier curve or spline at which the points will end. Default is the end of the Bezier curve or spline.
deg	a numeric indicating the degree (or order) of a Bezier spline. For Bezier curves, the degree is computed based on the number of control points.
max.dist	the maximum Euclidean distance (not distance along the curve) between consecutive points for the more rapid routine.
max.dist.factor	a factor used to approximate point position based on maximum distance criteria (see Details). Ignored if max.dist is NULL.
relative.min.slope	parameter passed to bezierArcLength for estimating total arc length. Ignored if max.dist is non-NULL.
absolute.min.slope	parameter passed to bezierArcLength for estimating total arc length. Ignored if max.dist is non-NULL.
sub.relative.min.slope	parameter passed to compareBezierArcLength for estimating total arc length (see compareBezierArcLength). Ignored if max.dist is non-NULL.
sub.absolute.min.slope	parameter passed to compareBezierArcLength for estimating total arc length (see compareBezierArcLength). Ignored if max.dist is non-NULL.
print.progress	logical indicating whether iterations should be printed for tracking function progress.

Details

Points can easily be generated along a Bezier curve or spline using parametric values (provided by the function bezier), however these points are not evenly spaced along the curve. Points generated by parametric values will be closer together in regions with the highest curvature and furthest apart in regions that approach a straight line. This function provides three different functionalities for generating points along a Bezier curve or spline that are more evenly spaced than those generated using parametric values. The 'evenly_spaced' method generates n approximately evenly spaced points along a Bezier, optimizing point position according to specified convergence criteria. The 'max_dist' method places points along a Bezier such that the distance between consecutive points does not exceed a specified Euclidean distance (max.dist). And the 'adjoining' method generates points along a Bezier as a series of integers and is intended for use with pixel coordinates.

The input of the control points p is identical to bezier and can be a vector, matrix or list (see Details in bezier). As with bezier, when control points are input as a list and the number of control points differs for different dimensions, the degree will be elevated so that all dimensions are of uniform degree (see elevateBezierDegree). t1 and t2 are parametric values along the Bezier curve or spline between which points will be generated. The default values for t1 and t2 are the start and end points of the Bezier curve or spline, respectively. For a Bezier spline, if t2 is not specified, it is calculated based on the number of control points and the degree (deg). When using pointsOnBezier for Bezier splines, deg must be specified or else the points will be treated as a single Bezier curve.

If n is non-NULL, pointsOnBezier generates n evenly spaced points along a Bezier curve or spline. This requires accurate approximation of Bezier arc length. An initial estimation of the total arc length between t1 and t2 is made (using bezierArcLength) to determine the interval at which points should be placed to equally subdivide the curve. optim is used to find the optimal position of each point, calling bezierArcLength via compareBezierArcLength, such that the arc length between points is nearly equal to this interval. When positioning each point, the arc length is estimated from t1 (rather than from the previous point) so that errors are not compounded. As a consequence of repeated calls to optim and bezierArcLength, this functionality can be rather slow.

The parameters ending in min.slope are convergence criteria passed to bezierArcLength. The parameters relative.min.slope and absolute.min.slope are the criteria used in the initial arc length estimation, while sub.relative.min.slope and sub.absolute.min.slope are the criteria used to estimate arc length in placing each point along the curve. Larger convergence criteria values will cause pointsOnBezier to run faster but at lower accuracy. For a complete description of the convergence criteria, see Details in bezierArcLength.

pointsOnBezier runs an alternative routine when max.dist is non-NULL. In this case, n and the convergence criteria are ignored, bezierArcLength is not called and pointsOnBezier generates points along a Bezier such that the distance between consecutive points does not exceed the specified Euclidean distance max.dist. The parameter max.dist.factor is a factor that is used to iteratively increase the parametric value to reach the next point without exceeding max.dist. The lower max.dist.factor is, the closer the interpoint Euclidean distance will be to max.dist but the longer pointsOnBezier will take to run (see Examples). If max.dist does not evenly divide the total arc length between t1 and t2, the interval between the second-to-last point and the end point may not be close to max.dist. If max.dist evenly divides the arc length, if max.dist.factor is low and if max.dist is small, the points will be more evenly spaced than with parametric point generation.

When method is 'adjoining', pointsOnBezier will generate points as integers at adjoining positions along the Bezier curve or spline. The arc length is first measured (very roughly) to approximate the first parametric interval at which to find adjoining points. The function adds this initial interval to t1 and finds the position of the next Bezier point, rounded to the nearest integer. The interval is decreased or increased depending on whether the point is too distant or too near until the next point adjoins the previous point. Adjoining is defined as two points whose positions (as integers) differ by one in either or both coordinates. Thus, 2D points adjoining on the diagonal are considered adjoining. For instance, the points [3,5] would be adjoining with [4,5], [3,4] and [4,6] but not [1,3]. The function continues to iterate through the parametric values up to t2, generating points adjoining to the previous point. This method is intended for use with pixel coordinates, such as when Bezier control points are used to trace Bezier curves and splines on an image. Unlike the previous two methods, most of the generated points will not fall exactly on the Bezier curve since they are rounded to the nearest integer. This method currently only works with curves or splines in two dimensions.

In the case of Bezier splines, note that borders between spline segments are not respected and arc lengths are calculated across spline segments. In order to generate points within spline segments, pointsOnBezier should be called separately for each segment.

Value

a list with the following elements:

points	evenly spaced or nearly evenly spaced points along a Bezier curve or spline.
error	an vector of the error for each point along the curve or spline. If the method is 'evenly_spaced', this is the value output from optim for each point estimation. If method is 'max_dist', this is max.dist minus the actual Euclidean distance between consecutive points. If method is 'adjoining', this is the difference between the actual position on the Bezier minus the position to the nearest integer.
t	the parametric values corresponding to each point in points.

Author(s)

Aaron Olsen

See Also

bezier, bezierArcLength, compareBezierArcLength, elevateBezierDegree

Examples

## EVENLY_SPACED METHOD ##
## BEZIER CURVE CONTROL POINTS
p <- matrix(c(3,2, 3,0, 5,5), nrow=3, ncol=2, byrow=TRUE)

## GET PARAMETRIC BEZIER POINTS
bp <- bezier(t=seq(0, 1, length=100), p=p)

## GET EVENLY SPACED POINTS ALONG CURVE
pob <- pointsOnBezier(p=p, n=10, method="evenly_spaced", print.progress=TRUE)

## FUNCTION WILL RUN FASTER BY INCREASING CONVERGENCE CRITERIA
pob_faster <- pointsOnBezier(p=p, n=10, method="evenly_spaced", sub.relative.min.slope=1e-2, 
	print.progress=TRUE)

## PLOT PARAMETRIC BEZIER POINTS
## NOTE THAT THEY ARE NOT EVENLY SPACED ALONG THE CURVE
plot(bp, cex=0.5, asp=1)

## ADD POINTS TO PLOT
## NOTE THAT THESE POINTS ARE EVENLY SPACED ALONG CURVE
points(pob$points, col="red")

## WITH FASTER RUN, SOME DEVIATION BUT POINTS ARE NEARLY IDENTICAL
points(pob_faster$points, col="blue", cex=1.5)


## MAX_DIST METHOD ##
## BEZIER CURVE CONTROL POINTS
p <- matrix(c(3,2, 3,0, 5,5), nrow=3, ncol=2, byrow=TRUE)

## GET PARAMETRIC BEZIER POINTS
bp <- bezier(t=seq(0, 1, length=100), p=p)

## GET POINTS ALONG CURVE WITH INTERPOINT DISTANCE LESS THAN 0.1
pob <- pointsOnBezier(p=p, max.dist=0.1, method="max_dist", print.progress=TRUE)

## PLOT PARAMETRIC BEZIER POINTS
plot(bp, cex=0.5, asp=1)

## ADD POINTS TO PLOT
points(pob$points, col="red")


## ADJOINING METHOD ##
## BEZIER CURVE CONTROL POINTS
p <- matrix(c(300,200, 300,0, 500,500), nrow=3, ncol=2, byrow=TRUE)

## GET PARAMETRIC BEZIER POINTS
bp <- bezier(t=seq(0, 1, length=100), p=p)

## GET POINTS ALONG CURVE WITH ROUNDED POSITIONS AT "PIXEL" SPACING
pob <- pointsOnBezier(p=p, method="adjoining", print.progress=TRUE)

## PLOT PARAMETRIC BEZIER POINTS
plot(bp, cex=0.5, asp=1)

## ADD POINTS TO PLOT
points(pob$points, col="red", cex=0.2, pch=16)

Example output

n of 10: 1 2 3 4 5 6 7 8 9 10

n of 10: 1 2 3 4 5 6 7 8 9 10

bezier documentation built on May 1, 2019, 9:46 p.m.