Algorithm 952 Dong, Bohan; Farouki, Rida T.
ACM transactions on mathematical software,
10/2015, Letnik:
41, Številka:
4
Journal Article
Recenzirano
The implementation of a library of basic functions for the construction and analysis of planar quintic Pythagorean-hodograph (PH) curves is presented using the complex representation. The special ...algebraic structure of PH curves permits exact algorithms for the computation of key properties, such as arc length, elastic bending energy, and offset (parallel) curves. Single planar PH quintic segments are constructed as interpolants to first-order Hermite data (end points and derivatives), and this construction is then extended to open or closed
C
2
PH quintic spline curves interpolating a sequence of points in the plane. The nonlinear nature of PH curves incurs a multiplicity of formal solutions to such interpolation problems, and a key aspect of the algorithms is to efficiently single out the unique “good” interpolant among them.
A comprehensive analysis of the morphology of the solution space for a special type of quadratic quaternion equation is presented. This equation, which arises in a surface construction problem, ...incorporates linear terms in a quaternion variable and its conjugate with right and left quaternion coefficients, while the quadratic term has a quaternion coefficient placed between the variable and its conjugate. It is proved that, for generic coefficients, the equation has two, one, or no solutions, but in certain special instances the solution set may comprise a circle or a 3-sphere in the quaternion space H. The analysis yields solutions for each case, and intuitive interpretations of them in terms of the four-dimensional geometry of the quaternion space H.
The existence of rational rotation-minimizing frames on polynomial space curves is characterized by the satisfaction of a certain identity among rational functions. Part 2 of Remark 5.1 in the ...original paper states an inequality among the degrees of the denominators of these rational functions, but the proof given therein was incomplete. A formal proof of this inequality, which is essential to the complete categorization of rational rotation-minimizing frames on polynomial space curves, appears to be a rather formidable task. Since all known examples and special cases suggest that the inequality is correct, it is restated here as a conjecture rather than a definitive result, and some preliminary steps towards the proof are presented.
A method for constructing rational Pythagorean-hodograph (PH) curves in
R
3
is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first ...derivative, defines the orientation of the curve
osculating planes. Augmenting this orientation information with a rational
support function, that specifies the distance of each osculating plane from the origin, then completely defines a one-parameter family of osculating planes, whose envelope is a developable ruled surface. The rational PH space curve is identified as the
edge of regression (or
cuspidal edge) of this developable surface. Such curves have rational parametric speed, and also rational adapted frames that satisfy the same conditions as polynomial PH curves in order to be
rotation-minimizing with respect to the tangent. The key properties of such
rational PH space curves are derived and illustrated by examples, and simple algorithms for their practical construction by geometric Hermite interpolation are also proposed.
► Rational PH space curves defined by vector field and scalar function. ► Curve is specified as edge of regression of tangent developable. ► Geometric Hermite interpolation by solution of linear equations. ► Conditions for existence of rational rotation-minimizing frames.
A Pythagorean-hodograph (PH) curver(t)=(x(t),y(t),z(t)) has the distinctive property that the components of its derivative r′(t) satisfy x′2(t)+y′2(t)+z′2(t)=σ2(t) for some polynomial σ(t). ...Consequently, the PH curves admit many exact computations that otherwise require approximations. The Pythagorean structure is achieved by specifying x′(t),y′(t),z′(t) in terms of polynomials u(t),v(t),p(t),q(t) through a construct that can be interpreted as a mapping from R4 to R3 defined by a quaternion product or the Hopf map. Under this map, r′(t) is the image of a ringed surface S(t,ϕ) in R4, whose geometrical properties are investigated herein. The generation of S(t,ϕ) through a family of four-dimensional rotations of a “base curve” is described, and the first fundamental form, Gaussian curvature, total area, and total curvature of S(t,ϕ) are derived. Furthermore, if r′(t) is non-degenerate, S(t,ϕ) is not developable (a non-trivial fact in R4). It is also shown that the pre-images of spatial PH curves equipped with a rotation-minimizing orthonormal frame (comprising the tangent and normal-plane vectors with no instantaneous rotation about the tangent) are geodesics on the surface S(t,ϕ). Finally, a geometrical interpretation of the algebraic condition characterizing the simplest non-trivial instances of rational rotation-minimizing frames on polynomial space curves is derived.
An adapted orthonormal frame
(
f
1
,
f
2
,
f
3
)
on a space curve
r
(
t
)
, where
f
1
=
r
′
/
|
r
′
|
is the curve tangent, is
rotation-minimizing if its angular velocity satisfies
ω
⋅
f
1
≡
0
, ...i.e., the normal-plane vectors
f
2
,
f
3
exhibit no instantaneous rotation about
f
1
. The simplest space curves with
rational rotation-minimizing frames (RRMF curves) form a subset of the quintic spatial
Pythagorean-hodograph (PH)
curves, identified by certain non-linear constraints on the curve coefficients. Such curves are useful in motion planning, swept surface constructions, computer animation, robotics, and related fields. The condition that identifies the RRMF quintics as a subset of the spatial PH quintics requires a rational expression in four quadratic polynomials
u
(
t
)
,
v
(
t
)
,
p
(
t
)
,
q
(
t
)
and their derivatives to be reducible to an analogous expression in just two polynomials
a
(
t
)
,
b
(
t
)
. This condition has been analyzed, thus far, in the case where
a
(
t
)
,
b
(
t
)
are also quadratic, the corresponding solutions being called
Class I RRMF quintics. The present study extends these prior results to provide a complete categorization of all possible PH quintic solutions to the RRMF condition. A family of
Class II RRMF quintics is thereby newly identified, that correspond to the case where
a
(
t
)
,
b
(
t
)
are linear. Modulo scaling/rotation transformations, Class II curves have five degrees of freedom, as with the Class I curves. Although Class II curves have rational RMFs that are only of degree 6–as compared to degree 8 for Class I curves–their algebraic characterization is more involved than for the latter. Computed examples are used to illustrate the construction and properties of this new class of RRMF quintics. A novel approach for generating RRMF quintics, based on the sum-of-four-squares decomposition of positive real polynomials, is also introduced and briefly discussed.
A characterization for spatial Pythagorean-hodograph (PH) curves of degree 7 with rotation-minimizing Euler–Rodrigues frames (ERFs) is determined, in terms of one real and two complex constraints on ...the curve coefficients. These curves can interpolate initial/final positions pi and pf and orientational frames (ti,ui,vi) and (tf,uf,vf) so as to define a rational rotation-minimizing rigid body motion. Two residual free parameters, that determine the magnitudes of the end derivatives, are available for optimizing shape properties of the interpolant. This improves upon existing algorithms for quintic PH curves with rational rotation-minimizing frames (RRMF quintics), which offer no residual freedoms. Moreover, the degree 7 PH curves with rotation-minimizing ERFs are capable of interpolating motion data for which the RRMF quintics do not admit real solutions. Although these interpolants are of higher degree than the RRMF quintics, their rotation-minimizing frames are actually of lower degree (6 versus 8), since they coincide with the ERF. This novel construction of rational rotation-minimizing motions may prove useful in applications such as computer animation, geometric sweep operations, and robot trajectory planning.
•A characterization of degree 7 PH curves with rotation-minimizing Euler–Rodrigues frames is developed.•The characterization is used to formulate a system of equations for interpolating initial/final positions and orientations of a rigid body by a rational rotation-minimizing motion.•The system incorporates two free parameters for shape optimization of the solutions.•Solutions exist for data sets that admit no RRMF quintic interpolants.•Although these curves are of slightly higher degree, their rational rotation-minimizing frames are of lower degree than for RRMF quintics.
This paper compares two techniques for the approximation of the offsets to a given planar curve. The two methods are based on approximate conversion of the planar curve into circular splines and ...Pythagorean hodograph (PH) splines, respectively. The circular splines are obtained using a novel variant of biarc interpolation, while the PH splines are constructed via Hermite interpolation of
C
1 boundary data.
We analyze the approximation order of both conversion procedures. As a new result, the
C
1 Hermite interpolation with PH quintics is shown to have approximation order 4 with respect to the original curve, and 3 with respect to its offsets. In addition, we study the resulting data volume, both for the original curve and for its offsets. It is shown that PH splines outperform the circular splines for increasing accuracy, due to the higher approximation order.
A rotation-minimizing adapted frame on a space curve
r
(
t
)
is an orthonormal basis
(
f
1
,
f
2
,
f
3
)
for
R
3
such that
f
1
is coincident with the curve tangent
t
=
r
′
/
|
r
′
|
at each point and ...the normal-plane vectors
f
2
,
f
3
exhibit no instantaneous rotation about
f
1
. Such frames are of interest in applications such as spatial path planning, computer animation, robotics, and swept surface constructions. Polynomial curves with
rational rotation-minimizing frames (RRMF curves) are necessarily Pythagorean-hodograph (PH) curves–since only the PH curves possess rational unit tangents–and they may be characterized by the fact that a rational expression in the four polynomials
u
(
t
)
,
v
(
t
)
,
p
(
t
)
,
q
(
t
)
that define the quaternion or Hopf map form of spatial PH curves can be written in terms of just two polynomials
a
(
t
)
,
b
(
t
)
. As a generalization of prior characterizations for RRMF cubics and quintics, a sufficient and necessary condition for a spatial PH curve of arbitrary degree to be an RRMF curve is derived herein for the generic case satisfying
u
2
(
t
)
+
v
2
(
t
)
+
p
2
(
t
)
+
q
2
(
t
)
=
a
2
(
t
)
+
b
2
(
t
)
. This RRMF condition amounts to a divisibility property for certain polynomials defined in terms of
u
(
t
)
,
v
(
t
)
,
p
(
t
)
,
q
(
t
)
and their derivatives.
This paper presents a methodology based on a variation of the Rapidly-exploring Random Trees (RRTs) that generates feasible trajectories for a team of autonomous aerial vehicles with holonomic ...constraints in environments with obstacles. Our approach uses Pythagorean Hodograph (PH) curves to connect vertices of the tree, which makes it possible to generate paths for which the main kinematic constraints of the vehicle are not violated. These paths are converted into trajectories based on feasible speed profiles of the robot. The smoothness of the acceleration profile of the vehicle is indirectly guaranteed between two vertices of the RRT tree. The proposed algorithm provides fast convergence to the final trajectory. We still utilize the properties of the RRT to avoid collisions with static, environment bound obstacles and dynamic obstacles, such as other vehicles in the multi-vehicle planning scenario. We show results for a set of small unmanned aerial vehicles in environments with different configurations.
PDF
