Transition between concentric or tangent circles with a single segment of PH quintic curve

The paper describes a method to join two circles with a C-shaped and an S-shaped transition curve, composed of a Pythagorean hodograph quintic segment, preserving G² continuity. It is considered desirable to have such a curve in satellite path planning, highway or railway route designing, or non-holonomic robot path planning. As an extension of our previous work, we show that a single quintic curve can be used for blending or for a transition curve between two circles, including the previously unsolved cases of concentric and tangential circles.     

Planar G transition between two circles with a fair cubic Bézier curve

Consumer products such as ping-pong paddles, can be designed by blending circles. To be visually pleasing it is desirable that the blend be curvature continuous without extraneous curvature extrema. Transition curves of gradually increasing or decreasing curvature between circles also play an important role in the design of highways and railways. Recently planar cubic and Pythagorean hodograph quintic spiral segments were developed and it was demonstrated how these segments can be composed pairwise to form transition curves that are suitable for G² blending. It is now shown that a single cubic curve can be used for blending or as a transition curve with the guarantee of curvature continuity and fairness. Use of a single curve rather than two segments has the benefit that designers and implementers have fewer entities to be concerned with.     

基于区间分类的螺旋图可视化边绑定方法

在时序数据可视化领域,螺旋图是一种常用的可视化方法,它既能将多个阶段的数据同时展示在一个平面空间内,又能在有限的空间内展示任意时长的数据。针对现有的螺旋图可视化方法在展示大量的时间序列数据时会出现因螺旋线交叉而导致视觉杂乱的问题,研究螺旋图可视化方法意义非凡。首先将状态圆环上的数据点进行分类;然后在相邻的状态圆环之间设置虚拟绑定圆环,通过边绑定的函数将状态圆环上的数据点映射到其对应的虚拟绑定圆环上;最后在状态圆环与其对应的虚拟绑定圆环之间绘制Bézier曲线,在虚拟绑定圆环与虚拟绑定圆环之间绘制螺旋线,从而实现边绑定的效果。实验结果表明,该边绑定算法能够有效地对大规模数据进行可视化,并能有效地缓解视觉杂乱的问题。     

3个控制顶点的类三次Bézier螺线

目的 为了使得过渡曲线的设计更为简单高效。提出基于3个控制顶点的类三次Bézier螺线。方法 通过对基函数的研究首先构造了3条在一定条件下曲率单调递减的类三次Bézier曲线,并由参数的对称性得另3条曲率单调递增的曲线。它们具有端点性、凸包性、几何不变性等三次Bézier曲线的基本性质,特点是只有3个控制顶点。接着严格地证明了此类曲线曲率单调的充分条件。 结果 有两条曲线比三次Bézier曲线的曲率单调条件范围大,且类三次Bézier螺线与三次Bézier螺线存在一定的位置关系。这6条曲线中有4条曲线的一个端点处曲率为零,可组合成4对类三次Bézier螺线来构造两圆弧间半径比例不受限制的S型和C型G²连续过渡曲线;剩下的两条曲线在两圆弧半径相差较大的情况下都可做不含曲率极值点的过渡曲线。最后用实例表明了此类曲线的有效性。结论 在过渡曲线设计中基于3个控制顶点的类三次Bézier螺线比三次Bézier螺线更为简单高效。     

C2 interpolation of spatial data subject to arc-length constraints using Pythagorean–hodograph quintic splines

In order to reconstruct spatial curves from discrete electronic sensor data, two alternative C² Pythagorean–hodograph (PH) quintic spline formulations are proposed, interpolating given spatial data subject to prescribed constraints on the arc length of each spline segment. The first approach is concerned with the interpolation of a sequence of points, while the second addresses the interpolation of derivatives only (without spatial localization). The special structure of PH curves allows the arc-length conditions to be expressed as algebraic constraints on the curve coefficients. The C² PH quintic splines are thus defined through minimization of a quadratic function subject to quadratic constraints, and a close starting approximation to the desired solution is identified in order to facilitate efficient construction by iterative methods. The C² PH spline constructions are illustrated by several computed examples.     

The circlet transform: A robust tool for detecting features with circular shapes

We present a novel method for detecting circles on digital images. This transform is called the circlet transform and can be seen as an extension of classical 1D wavelets to 2D; each basic element is a circle convolved by a 1D oscillating function. In comparison with other circle-detector methods, mainly the Hough transform, the circlet transform takes into account the finite frequency aspect of the data; a circular shape is not restricted to a circle but has a certain width. The transform operates directly on image gradient and does not need further binary segmentation. The implementation is efficient as it consists of a few fast Fourier transforms. The circlet transform is coupled with a soft-thresholding process and applied to a series of real images from different fields: ophthalmology, astronomy and oceanography. The results show the effectiveness of the method to deal with real images with blurry edges.     

G 2 blends of linear segments with cubics and Pythagorean-hodograph quintics

Fillets, also known as blend arcs, are used in CNC machining to round corners. Fillets are normally circular arcs, which have G ¹ contact with the straight line segments to which they are joined. Recent advances in machining technology allow NURBS, including Pythagorean-hodograph (PH) curve segments, to be incorporated in CNC tool paths. This article examines the use of cubic and PH quintic Bézier curve segments that have a single curvature extremum, and which have G ² contact with the straight line segments to which they are joined, as fillets. It is shown how the extreme circle of curvature can be determined. The point of curvature extremum and the corresponding value of the curvature can be changed by adjusting the joining points of the blending curve with the neighbouring straight lines. These blending curves can also be incorporated in computer-aided design packages for curve or surface design.     

A sweepline algorithm for Euclidean Voronoi diagram of circles

Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others.The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed.The worst-case time complexity of the proposed algorithm is O((n+m)log n), where n is the number of input circles, and m is the number of intersection points among circles. As m can be O(n²), the presented algorithm is optimal with O(n² log n) worst-case time complexity.     

A new approximation algorithm for labeling points with circle pairs

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in time and O(n) space and achieves an approximation factor of (≈1.486+ε), which improves the previous best bound of 1.491+ε.     

On a circle placement problem

We consider the following circle placement problem: given a set of pointsp _i ,i=1,2, ...,n, each of weightw _i , in the plane, and a fixed disk of radiusr, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a setS ofn circles,D _i ,i=1,2, ...,n, of the same radiusr, each of weightw _i , find a subset ofS whose common intersection is nonempty and whose total weight is maximum. AnO (n ²) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs inO (n ² logn) time.     

Fair, G- and C-continuous circle splines for the interpolation of sparse data points

This paper presents a carefully chosen curve blending scheme between circles, which is based on angles, rather than point positions. The result is a class of circle splines that robustly produce fair-looking G²-continuous curves without any cusps or kinks, even through rather challenging, sparse sets of interpolation points. With a simple reparameterization the curves can also be made C²-continuous. The same method is usable in the plane, on the sphere, and in 3D space.     

Hermite interpolation with Tschirnhausen cubic spirals

A method to create planar G¹ curves by joining spiral segments is described. The spiral segments are either spirals taken from the Tschirnhausen cubic curve or spirals created by joining circular arcs to segments of the Tschirnhausen cubic in a G³ fashion. The above mentioned spirals can match geometric Hermite data in all cases where that data can be matched with a general spiral. The use of spirals gives the designer excellent control over the shape of curve that is produced because there are no internal curvature maxima, curvature minima, inflection points, loops, or cusps in a spiral segment.     

Curvature continuous interpolation of curve meshes

This paper presents a method for local construction of a curvature continuous (GC²) piecewise polynomial surface which interpolates a given rectangular curvature continuous quintic curve mesh. First, we create a C² quintic basic curve mesh, which interpolates the same grid points, preserves the tangent slopes and curvatures but not derivative vectors at the grid points. After estimating twist and higher order mixed partial derivatives for each grid point, we generate locally the so-called C² biquintic basic patches, which serve to compute the first and second order cross-derivative functions of the final interpolation surface. In order to match the tangents and second order derivative vectors of the original boundary curves at the grid points, these basic patches are reparametrized by 5 × 3 and 3 × 5 functions, which lead to vector-valued first and second order cross-derivative functions of degrees 7 and 9 of the final surface patches, and eventually lead to a GC² piecewise polynomial surface of degree 9 × 9, which is then converted to a GC² Bézier composite surface. By arranging the surface patches in a chess-board fashion, the degrees of the final surface patches can be 9 × 5 and 5 × 9. An example for the construction of a GC² ship hull, together with its color-coded curvature maps, is given to illustrate the method. This method is attractive because the final surface has a much lower degree than other similar methods, it allows flexible local modification of the original curve mesh and local editing of the interpolation surface, and it is easily integrated into state-of-the-art geometric modeling systems.     

Möbius变换下四次有理抛物-PH曲线的C2 Hermite插值

目的 曲线插值问题在机器人设计、机械工业、航天工业等诸多现代工业领域都有广泛的应用，而已知端点数据的Hermite插值是计算机辅助几何设计中一种常用的曲线构造方法，本文讨论了一种偶数次有理等距曲线，即四次抛物-PH曲线的C² Hermite插值问题。方法 基于M bius变换引入参数，利用复分析的方法构造了四次有理抛物-PH曲线的C² Hermite插值，给出了具体插值算法及相应的Bézier曲线表示和控制顶点的表达式。结果 通过给出"合理"的端点插值数据，以数值实例表明了该算法的有效性，所得12条插值曲线中，结合最小绝对旋转数和弹性弯曲能量最小化两种准则给出了判定满足插值条件最优曲线的选择方法，并以具体实例说明了与其他插值方法的对比分析结果。结论 本文构造了M bius变换下的四次有理抛物-PH曲线的C² Hermite插值，在保证曲线次数较低的情况下，达到了连续性更高的插值条件，计算更为简单，插值效果明显，较之传统奇数次PH曲线具有更加自然的几何形状，对偶数次PH曲线的相关研究具有一定意义。     

Transportation Distances on the Circle

This paper is devoted to the study of the Monge-Kantorovich theory of optimal mass transport, in the special case of one-dimensional and circular distributions. More precisely, we study the Monge-Kantorovich problem between discrete distributions on the unit circle S ¹, in the case where the ground distance between two points x and y is defined as h(d(x,y)), where d is the geodesic distance on the circle and h a convex and increasing function. This study complements previous results in the literature, holding only for a ground distance equal to the geodesic distance d. We first prove that computing a Monge-Kantorovich distance between two given sets of pairwise different points boils down to cut the circle at a well chosen point and to compute the same distance on the real line. This result is then used to obtain a dissimilarity measure between 1-D and circular discrete histograms. In a last part, a study is conducted to compare the advantages and drawbacks of transportation distances relying on convex or concave cost functions, and of the classical L ¹ distance. Simple retrieval experiments based on the hue component of color images are shown to illustrate the interest of circular distances. The framework is eventually applied to the problem of color transfer between images.     

The circle as a smoothly joined BR-curve on [0, 1]

The full circle as an image of [0, 1] is represented as a BR-curve with five massic vectors (i.e., weighted points or pure vectors). In order to obtain C^k smoothly joined circles, we determine different one-to-one rational changes of parameter. They lead to control polygons consisting in five (respectively seven, nine) massic vectors for k = 1 (respectively k = 3, k = 5). This study is completed by an algorithm and solutions with only positively weighted points.     

Motion design with Euler–Rodrigues frames of quintic Pythagorean-hodograph curves

The paper presents an interpolation scheme for G¹ Hermite motion data, i.e., interpolation of data points and rotations at the points, with spatial quintic Pythagorean-hodograph curves so that the Euler–Rodrigues frame of the curve coincides with the rotations at the points. The interpolant is expressed in a closed form with three free parameters, which are computed based on minimizing the rotations of the normal plane vectors around the tangent and on controlling the length of the curve. The proposed choice of parameters is supported with the asymptotic analysis. The approximation error is of order four and the Euler–Rodrigues frame differs from the ideal rotation minimizing frame with the order three. The scheme is used for rigid body motions and swept surface construction.     

Equivalence of distinct characterizations for rational rotation-minimizing frames on quintic space curves

A rotation-minimizing frame on a space curve r(t) is an orthonormal basis (f₁,f₂,f₃) for R³, where f₁=r^′/|r^′| is the curve tangent, and the normal-plane vectors f₂,f₃ exhibit no instantaneous rotation about f₁. Such frames are useful in spatial path planning, swept surface design, computer animation, robotics, and related applications. The simplest curves that have rational rotation-minimizing frames (RRMF curves) comprise a subset of the quintic Pythagorean-hodograph (PH) curves, and two quite different characterizations of them are currently known: (a) through constraints on the PH curve coefficients; and (b) through a certain polynomial divisibility condition. Although (a) is better suited to the formulation of constructive algorithms, (b) has the advantage of remaining valid for curves of any degree. A proof of the equivalence of these two different criteria is presented for PH quintics, together with comments on the generalization to higher-order curves. Although (a) and (b) are both sufficient and necessary criteria for a PH quintic to be an RRMF curve, the (non-obvious) proof presented here helps to clarify the subtle relationships between them.     

Global G3 continuity toolpath smoothing for a 5-DoF machining robot with parallel kinematics

Toolpath smoothing is an important approach to improve robots’ operational stability and machining quality. Nowadays, the corner rounding smoothing and curve fitting smoothing algorithms are usually adopted to process the linear toolpath segments to improve its continuity. But the high order continuity between the fitted curve and its adjacent curves is difficult to be guaranteed. For parallel machining robots (PMRs), the tangential, curvature and curvature derivative discontinuities at the junction may lead to the self-excited vibration of mechanical structure, consequently the machining efficiency and quality are decreased. Under this consideration, a global G³ continuity toolpath smoothing method for five degrees of freedom (5-DoF) PMRs is proposed. The linear segments toolpath generated by the Computer-Aided Manufacturing (CAM) system is first divided into long linear segments (LLSs) and short linear segments groups (SLSGs) through breakpoint searching. At the junction point, a B-spline transition curve is inserted to blend adjacent toolpaths. For the SLSG, the quintic B-spline is adopted to fit the discrete data points, constraint equations about the derivatives at the start and end points are established to achieve G³ continuity with the adjacent transition curves. Based on the proposed method, the smoothing for two test toolpaths is carried out, and experiments on a 5-DoF PMR are conducted to show the validity of the method in motion smoothness.