pointsOnBezier {bezier} R Documentation

## Generates points along a Bezier curve or spline

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

`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)

## 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)

points(pob\$points, col="red")

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