public final class BinaryCurveApproximationAlgorithm extends Object
The binary curve approximation algorithm is an algorithm designed to approximate a ParametricCurve using as few points as possible but keeping the overall visual appearance of the curve smooth. The number of points used and the visual appearance are not guaranteed, but the results are usually very good.
Users that do not plan on implementing their own ParametricCurves do not need to use this class.
There is one static method called genPts that takes a ParametricCurve, an interval [t_min, t_max], and a MultiPath as parameters. The algorithm uses the ParametricCurve to generate points in the range [t_min, t_max] and append the points in order to the MultiPath. Figure 1 shows the basic idea of how the algorithm works.
The algorithm works by evaluating the parametric midpoint (m) of two points and computing the distance (dist) from the parametric midpoint to line segment formed by the two points. That distance is then compared to the threshold distance, otherwise called the "flatness" of the curve. The algorithm continues to subdivide the curve until dist < flatness is reached. However, that is not all there is to say. Figure 2 illustrates the problem of this approach.
In some cases, the evaluated midpoint is on or near the line segment. To solve this, the idea of a sample limit is used. The sample limit specifies how many additional subdivisions to perform once the condition dist < flatness is reached. If any of the additional subdivisions does not meet the dist < flatness condition, then the algorithm continues from the point that did not meet the condition. The closer the flatness value to 0 and the higher the sample limit both increase the number of points appended to the multi-path.
The idea of a sample limit is adequate for curves that generate points on the curve using a fixed number of control-points in sections. Curves that have this property have a fixed number of inflection points per section. For example, the CubicBSpline generates itself in sections (considering 4 points at a time) but the BSpline with degree 3 only has one section. For curves that do not have this property, the sample-limit can be specified. Note: As the sample limit is increased, it becomes more difficult to produce a point arrangement that causes a problem.
Note: The algorithm is designed so that the first point appended to the multi-path will be eval(t_min) and the last point appended to the multi-path will be eval(t_max). If the result of computing the distance from the line segment to the evaluated point is NaN or Infinity then the algorithm aborts by throwing a RuntimeException.
Curve
,
ParametricCurve
,
MultiPath
Modifier and Type | Method and Description |
---|---|
static void |
genPts(ParametricCurve pc,
double t_min,
double t_max,
MultiPath mp)
Appends a sequence of points to the multi-path using the lineTo method exclusively.
|
public static void genPts(ParametricCurve pc, double t_min, double t_max, MultiPath mp)
IllegalArgumentException
- If t_min > t_max.Copyright © 2016. All rights reserved.