Abstract
在論文當中，我們探討如何以G0或G1連續的多圓弧曲線來對平面曲線作近似。它包括兩大主題：數位化曲線近似的問題及參數曲線轉換的問題，兩者皆採用最大誤差來衡量近似的準確度。數位化曲線是由一連串的點所構成之集合。以數學曲線來近似數位化曲線可在不同應用中，得到緊緻且有效率的表示方法。對於此類的近似問題，我們提出一些以G0或 G1連續的多圓弧來近似數位化曲線的演算法，它主要涵蓋兩種不同的形態︰第一，得到一組最少段的圓弧曲線而其誤差不超過一個限定的容忍值；第二，得到一組誤差最小的多圓弧曲線，而其段數等於一個限定值。首先，我們提出新的演算法來解決單一圓弧及單一雙圓弧的近似問題；接著，我們介紹一些選取接點的演算法，來解決兩種形態的多圓弧近似問題。從高次曲線轉換成低次曲線經常發生在不同資料間的轉換，同時也可用來加速後續的處理。對於此類問題，我們討論參數曲線轉換成G1連續的多圓弧問題；也就是說，給予一參數曲線，我們提出新的演算法來產生一組平滑的多圓弧曲線，其誤差不超過一個限定的容忍值。我們首先利用疊代法來找到最佳的雙圓弧曲線，然後使用“切開及合併”策略來挑選適當的接點。除此之外，我們也提出一些方法，在不增加段數的情形下，加速轉換的速率。For this dissertation, we studied two-dimensional curveapproximation problems by using piecewise circular arcs withgeometry continuity G0 and G1. This study faced two differentkinds of approximation problems: one, approximating digitizedcurves, and two, approximating the conversion of parametriccurves. Both procedures used the maximum norm to measure theaccuracy of the approximation. A digitized curve can beregarded as an ordered set of points. To approximate adigitized curve by mathematical curves often results in acompact and efficient representation for various applications.For this kind of approximation problems, some novel algorithmsare proposed to approximate a given digitized curve by usingpiecewise circular arcs with G0 and G1 continuity. There aretwo types of the piecewise approximation problems, namely, (1)minimizing the number of segments of the approximate curvewhose error is within a specified tolerance E>0, and (2)minimizing the error of the approximate curve whose number ofsegments is equal to a given integer M>0. First, we proposesome new algorithms to solve the best single arc and singlebiarc approximation problems with respect to the maximum norm.Then, based on the results of the single arc and single biarcapproximations, we introduce several knot-selection algorithmswhich can solve both types of approximation problemsefficiently. Approximate conversions from high-order curves tolow-order primitive curves are often required in exchange fordata or to facilitate subsequent processing. For this issue, wediscuss the approximate conversion of parametric curves by G1arc splines. We first used iterative methods to find the bestapproximate biarc of a sub-piece of parametric curve, and laterused the split-and-merge strategy to choose proper knot pointsfor arc splines. Moreover, based on the intrinsic properties ofthe curve, some heuristic methods are proposed to facilitatethe computation of approximate conversions.