JP3913832B2

JP3913832B2 - Circular interpolation processing method

Info

Publication number: JP3913832B2
Application number: JP08132697A
Authority: JP
Inventors: 英夫野田
Original assignee: Mutoh Industries Ltd
Current assignee: Mutoh Industries Ltd
Priority date: 1997-03-31
Filing date: 1997-03-31
Publication date: 2007-05-09
Anticipated expiration: 2017-03-31
Also published as: JPH10275240A

Description

【０００１】
【発明の属する技術分野】
この発明は、文字フォント等の曲線部を円弧データによって指定した場合の円弧補間処理方法に関する。
【０００２】
【従来の技術】
文字フォントデータの曲線部は、通常は２次ベジェ曲線や２次スプライン等によって指定されるが、より簡易で高速な方法として、曲線部を円弧データで指定する方法がある。この場合、円弧データは、始点、通過点及び終点で指定される。円弧データは、処理速度を高めるため通常はプロットする直前に線分データに分割される。分割された線分データは、例えば図８に示すように、実際の円弧に対して誤差を生じる。この誤差は、円弧の中心点から円弧の始点及び終点までの線分のなす角度をζとすると、
【０００３】
【数１】
誤差＝ｒ｛１−cos（ζ／２）｝
【０００４】
で表され、この誤差が所定の誤差ｅ以下となるように角度ζが選択される。この角度ζを分割角と呼ぶ。
【０００５】
従来、この分割角ζとその回転方向とを求めるため、次のような処理を行っていた。
即ち、図９に示すように、与えられた始点Ｐ₁、通過点Ｐ₂及び終点Ｐ₃のデータから、円弧の中心点Ｐ₀を求める。次に中心点Ｐ₀と始点Ｐ₁との距離を算出して円弧の半径ｒを求め、求められた半径ｒから分割角ζを求める。更に、中心点Ｐ₀から始点Ｐ₁、通過点Ｐ₂及び終点Ｐ₃にそれぞれ向かうベクトルとのなす角度θ₁，θ₂，θ₃を求める。これらの角度θ₁〜θ₃から回転方向を決定し、分割角ζの符号を決定する。
【０００６】
【発明が解決しようとする課題】
しかし、上述した従来の円弧補間処理方法では、角度θ₁〜θ₃を算出する際に、アークタンジェント演算が必要になる。このアークタンジェント演算は、繰り返しが多いため、処理時間の増大を招くという問題がある。また、アークタンジェント演算をテーブルの参照によって行おうとしても、インデックスが０から無限大まで必要となるので、テーブルの作成も困難であるという問題がある。
【０００７】
この発明は、このような問題点に鑑みなされたもので、高速処理が可能な円弧補間処理方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
この発明に係る円弧補間処理方法は、始点、通過点及び終点の３点で指定される円弧のデータから当該円弧を近似する複数の線分データを生成するための円弧補間処理方法において、前記指定された３点のデータから前記円弧の中心点を算出する中心点算出ステップと、前記３点のデータの少なくとも１つと前記算出された中心点とから前記円弧の半径に対応する値を算出して分割角を決定する分割角決定ステップと、前記始点から前記通過点までのベクトルと前記通過点から前記終点までのベクトルとの外積を求め、その符号に基づいて前記分割角の回転方向を決定する回転方向決定ステップと、前記円弧を前記決定された分割角毎に前記決定された回転方向に分割して線分データを順次生成すると共に、前記線分データの終点が前記円弧の終点を超えたときに前記線分データの生成を終了する線分データ生成ステップとを備え、前記線分データ生成ステップは、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するステップであることを特徴とする。
【０００９】
この発明によれば、円弧のデータとして与えられた始点、通過点及び終点のデータのうち、始点から通過点までのベクトルと通過点から終点までのベクトルとの外積を求め、その符号に基づいて分割角の回転方向を決定するようにしているので、アークタンジェント演算を必要とせず、演算処理は単純な四則演算だけとなるので、処理速度が従来に比べて格段に高速になる。また、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するようにしているので、終了判定も単純な演算で行え、処理速度は更に向上する。
【００１０】
また、与えられた３点のデータの少なくとも一つと中心点とから円弧の半径の２乗値を求め、この半径の２乗値に基づいて分割角を決定するようにすると、平方根演算も不要となるので、処理速度は更に向上する。
【００１１】
【発明の実施の形態】
以下、図面を参照して、この発明の好ましい実施の形態を説明する。
図１は、この発明の実施例に係る円弧補間処理を実現するシステムの機能ブロック図である。
このシステムは、円弧補間処理部１、分割角決定テーブル２及び三角関数テーブルを備えて構成される。
【００１２】
上位システムから与えられた文字コードに基づいて、フォントテーブルから読み出されたフォントデータのうち、曲線の部分は、始点Ｐ₁、通過点Ｐ₂及び終点Ｐ₃により特定される円弧データとなっており、これら３点のデータＰ₁，Ｐ₂，Ｐ₃が円弧補間処理部１に供給されると、図２に示すような円弧補間処理が実行される。
【００１３】
この円弧補間処理は、与えられた３点のデータから中心座標Ｐ₀を決定するステップ（Ｓ１）と、半径の２乗から分割角を決定するステップ（Ｓ２）と、回転方向を決定するステップ（Ｓ３）と、分割角毎に回転方向に沿って分割点列、即ち分割線分を求めるステップ（Ｓ４）と、線分分割を終了するための判定ステップ（Ｓ５）とから構成される。以下、各ステップについて説明する。
【００１４】
（１）中心座標Ｐ₀の決定（Ｓ１）
図３に示すように、Ｐ₀を中心とする円弧上に３点のデータＰ₁，Ｐ₂，Ｐ₃が配置されているとして、中心点Ｐ₀に対して円弧上の点Ｐ₁と点対称の位置に第４の点Ｐ₄を配置した場合、Ｐ₁からＰ₂へのベクトルＶ₂₁と、Ｐ₂からＰ₄へのベクトルＶ₄₂とのなす角度は９０°となり、同じくＰ₁からＰ₃へのベクトルＶ₃₁と、Ｐ₃からＰ₄へのベクトルＶ₄₃とのなす角度も９０°となる。従って、ベクトルＶ₂₁，Ｖ₄₂の内積とベクトルＶ₃₁，Ｖ₄₃の内積は共に０になる。即ち、Ｐ₁，Ｐ₂，Ｐ₃，Ｐ₄の座標をそれぞれ（ｘ₁，ｙ₁），（ｘ₂，ｙ₂），（ｘ₃，ｙ₃），（ｘ₄，ｙ₄）とすると、
【００１５】
【数２】
Ｖ₂₁・Ｖ₄₂
＝（ｘ₂−Ｘ₁）（ｘ₄−ｘ₂）＋（ｙ₂−ｙ₁）（ｙ₄−ｙ₂）
＝０
Ｖ₃₁・Ｖ₄₃
＝（ｘ₃−Ｘ₁）（ｘ₄−ｘ₃）＋（ｙ₃−ｙ₁）（ｙ₄−ｙ₃）
＝０
【００１６】
数２をｘ₄及びｙ₄について解くと、数３のようになる。
【００１７】
【数３】

【００１８】
ここで変数Ｐ₁，Ｐ₂，Ｐ₃を１６ビット精度とすると、数３のｘ₄，ｙ₄を求める式の分母及びｃ₁，ｃ₂を求める式は、３２ビット整数型で精度を維持することができる。Ｐ₄は、１６ビット整数となる。ｘ₄，ｙ₄を求めるときの最終手順で乗算２回と、除算１回に浮動小数点演算を必要とする。数３より、円弧の中心座標Ｐ₀＝（ｘ₀，ｙ₀）はＰ₁，Ｐ₄の中点として求められるが、切り捨て誤差を防ぐため、数４のように求められる。
【００１９】
【数４】
ｘ₀＝（ｘ₄＋ｘ₁＋１）／２
ｙ₀＝（ｙ₄＋ｙ₁＋１）／２
【００２０】
（２）分割角の決定（Ｓ２）
分割角ζは、数１に基づいて決定するのが理想的であるが、この場合、演算には高い処理能力が要求されるので、ここでは高速処理が可能な次のような手順で分割角を決定する。即ち、半径ｒの２乗値は、数５のように整数演算によって求められる。
【００２１】
【数５】
ｒ²＝（ｘ₁−ｘ₀）²＋（ｙ₁−ｙ₀）²
【００２２】
分割角決定テーブル２には、図４に示すような変換表が予め格納されており、数５で求められた半径の２乗値ｒ²をインデックスとして分割角決定テーブル２から分割角ζを決定する。ここでは誤差ｅを１３ドット程度に設定した。
この方式によれば、▲１▼半径算出のための平方根演算が不要であること、▲２▼逆コサイン変換が不要なこと、から処理時間を大幅に短縮することができる。
【００２３】
（３）回転方向の決定（Ｓ３）
円弧の回転方向は、図５に示すように、始点Ｐ₁から通過点Ｐ₂に延びるベクトルＶ₂₁と、通過点Ｐ₂から終点Ｐ₃に延びるベクトルＶ₃₂とのなす角度θが正であるか負であるかによって決定することができる。即ち、図５（ａ）のように、Ｖ₂₁とＶ₃₂とのなす角度θが正である場合には反時計回りであり、同図（ｂ）のように、Ｖ₂₁とＶ₃₂とのなす角度θが負である場合には時計回りである。２本のベクトルＶ₂₁，Ｖ₃₂の外積は、数６のように求められる。
【００２４】
【数６】
Ｖ₂₁×Ｖ₃₂
＝｜Ｖ₂₁｜｜Ｖ₃₂｜sinθ
＝（ｘ₂−ｘ₁）（ｙ₃−ｙ₂）−（ｙ₂−ｙ₁）（ｘ₃−ｘ₂）
【００２５】
この値の正負の符号をそのまま分割角ζの回転方向とする。この演算も整数処理のみで行える。
【００２６】
（４）線分への分割処理（Ｓ４）
円弧の中心点Ｐ₀と符号付き分割角ζとが求まったら、図６に示すように、線分への分割処理を繰り返して、各分割点をＰ_d1，Ｐ_d2，…求めていく。これにより分割ベクトルＶ_d1，Ｖ_d2，…が求められる。いま、円弧の中心点Ｐ₀から分割点Ｐ_dn-1，Ｐ_dnへ延びるベクトルをそれぞれＶ_rn-1，Ｖ_rnとすると、
【００２７】
【数７】

【００２８】
で表せる。従って、ｎ番目の分割点Ｐ_dnの座標（ｘ_dn，ｙ_dn）は、次のように求められる。
【００２９】
【数８】
ｘ_dn＝（ｘ_dn-1−ｘ₀）cosζ−（ｙ_dn-1−ｙ₀）sinζ＋ｘ₀
ｙ_dn＝（ｘ_dn-1−ｘ₀）sinζ＋（ｙ_dn-1−ｙ₀）cosζ＋ｙ₀
【００３０】
このとき、sinζ及びcosζは、三角関数テーブル３を参照することにより求める。分割角としては０°から１８０°までを想定しておけば充分であるが、図４に示すような分割角決定テーブル２を用いた場合には、２°から１５°までの１４通りの配列を用意しておけば足りる。sinζ及びcosζは、線分分割時に一度求めておけば良く、数８の演算も単純であるから、高速処理が可能になる。
【００３１】
（５）分割終了判定（Ｓ５）
分割処理の終了は、分割点が円弧の終点Ｐ₃を超えたかどうかにより判定する。
図７に示すように、分割点Ｐ_dn-1から終了点Ｐ₃に延びるベクトルをＶ₁とし、次の分割点Ｐ_dnから終了点Ｐ₃に延びるベクトルをＶ₂とすると、同図（ａ）のように、分割点Ｐ_dnが終了点Ｐ₃の手前に存在する場合には、ベクトルＶ₁とベクトルＶ₂とのなす角度は９０°以下となるが、同図（ｂ）のように、分割点Ｐ_dnが終了点Ｐ₃を超えた場合には、ベクトルＶ₁とベクトルＶ₂とのなす角度は９０°を超える。従って、ベクトルＶ１，Ｖ２の内積を求め、その符号が負になったことをもって分割点_Pdnが終了点Ｐ₃を超えたと判断することができる。即ち、
【００３２】
【数９】
Ｖ₁・Ｖ₂
＝（ｘ₃−ｘ_dn-1）（ｘ₃−ｘ_dn）＋（ｙ₃−ｙ_dn-1）（ｙ₃−ｙ_dn）≦０
【００３３】
を検出したら、分割線分Ｖ_dnは使用せずに、終点Ｐ₃に至る線分Ｖ₁を最終線分とする。
以上の処理により、円弧補間処理の速度を大幅に向上させることができる。
【００３４】
【発明の効果】
以上述べたように、この発明によれば、円弧のデータとして与えられた始点、通過点及び終点のデータのうち、始点から通過点までのベクトルと通過点から終点までのベクトルとの外積を求め、その符号に基づいて分割角の回転方向を決定するようにしているので、アークタンジェント演算を必要とせず、演算処理は四則演算だけとなるので、処理速度が従来に比べて格段に高速になるという効果を奏する。また、線分データを生成する毎にその線分データの始点から円弧の終点へ延びるベクトルと線分データの終点から円弧の終点へ延びるベクトルとの内積を求め、その符号に基づいて線分データの生成を終了するようにしているので、終了判定も単純な演算で行え、処理速度は更に向上するという効果を奏する。
【図面の簡単な説明】
【図１】この発明の一実施例に係る円弧補間処理を実現するシステムの機能ブロック図である。
【図２】同円弧補間処理のフローチャートである。
【図３】同処理における円弧の中心点座標の算出手順を説明するための図である。
【図４】同処理における分割角の決定手順に用いられる分割角決定テーブルの一例を示す図である。
【図５】同処理における分割角の回転方向決定手順を説明するための図である。
【図６】同処理における線分分割手順を説明するための図である。
【図７】同処理における線分分割終了判定手順を説明するための図である。
【図８】円弧の線分分割角度と誤差との関係を示す図である。
【図９】従来の円弧補間処理方法を説明するための図である。
【符号の説明】
１…円弧補間処理部、２…分割角決定テーブル、３…三角関数テーブル。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a circular interpolation processing method when a curved portion such as a character font is designated by circular arc data.
[0002]
[Prior art]
The curved portion of the character font data is normally designated by a quadratic Bezier curve, a quadratic spline, or the like. As a simpler and faster method, there is a method of designating the curved portion by arc data. In this case, the arc data is designated by a start point, a passing point, and an end point. Arc data is usually divided into line segment data immediately before plotting in order to increase the processing speed. The divided line segment data causes an error with respect to an actual arc as shown in FIG. This error is given by ζ as the angle formed by the line segment from the center point of the arc to the start point and end point of the arc.
[0003]
[Expression 1]
Error = r {1-cos (ζ / 2)}
[0004]
The angle ζ is selected so that this error is equal to or less than a predetermined error e. This angle ζ is called a split angle.
[0005]
Conventionally, in order to obtain the division angle ζ and the rotation direction, the following processing has been performed.
That is, as shown in FIG. 9, the center point P _{0 of the} arc is obtained from the given data of the start point P ₁ , the passing point P ₂ and the end point P ₃ . Next, the distance between the center point P ₀ and the start point P ₁ is calculated to obtain the radius r of the arc, and the division angle ζ is obtained from the obtained radius r. Further, angles θ ₁ , θ ₂ , and θ ₃ formed by vectors from the center point P ₀ to the start point P ₁ , the passing point P _2, and the end point P ₃ are obtained. The rotation direction is determined from these angles θ _{1 to} θ _3, and the sign of the division angle ζ is determined.
[0006]
[Problems to be solved by the invention]
However, in the conventional circular interpolation processing method described above, arc tangent calculation is required when calculating the angles θ _{1 to} θ ₃ . This arc tangent calculation has a problem of increasing the processing time because it is frequently repeated. In addition, even if the arctangent calculation is performed by referring to the table, since the index is required from 0 to infinity, it is difficult to create the table.
[0007]
The present invention has been made in view of such problems, and an object thereof is to provide a circular interpolation processing method capable of high-speed processing.
[0008]
[Means for Solving the Problems]
The circular interpolation processing method according to the present invention is the circular interpolation processing method for generating a plurality of line segment data approximating the circular arc from the circular arc data specified by the start point, the passing point, and the end point. A center point calculating step for calculating the center point of the arc from the three data points, and calculating a value corresponding to the radius of the arc from at least one of the three point data and the calculated center point; A division angle determination step for determining a division angle, and an outer product of a vector from the start point to the passing point and a vector from the passing point to the end point are determined, and the rotation direction of the division angle is determined based on the sign. A rotation direction determining step, and sequentially generating line segment data by dividing the arc into the determined rotation direction for each determined division angle, and an end point of the line segment data is the arc And a said line segment data generating step of terminating the generation of the line segment data when exceeding the end point, the line segment data generating step, from the starting point of the line segment data each time generating the segment data arc end point And calculating the inner product of the vector extending to the end point of the arc from the end point of the line segment data to the end point of the arc, and ending the generation of the line segment data based on the sign .
[0009]
According to the present invention, the cross product of the vector from the start point to the pass point and the vector from the pass point to the end point is obtained from the start point, pass point and end point data given as the arc data, and based on the sign Since the rotation direction of the split angle is determined, the arctangent calculation is not required, and the calculation process is only a simple four-rule calculation, so that the processing speed is remarkably higher than the conventional one. Each time line data is generated, an inner product of a vector extending from the start point of the line segment data to the end point of the arc and a vector extending from the end point of the line segment data to the end point of the arc is obtained, and the line segment data is calculated based on the sign. Therefore, the end determination can be performed by a simple calculation, and the processing speed is further improved.
[0010]
Further, if the square value of the radius of the arc is obtained from at least one of the given three points data and the center point, and the division angle is determined based on the square value of the radius, the square root calculation is not required. Therefore, the processing speed is further improved .
[0011]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, preferred embodiments of the present invention will be described with reference to the drawings.
FIG. 1 is a functional block diagram of a system for realizing circular interpolation processing according to an embodiment of the present invention.
This system includes an arc interpolation processing unit 1, a split angle determination table 2, and a trigonometric function table.
[0012]
Of the font data read from the font table based on the character code given from the host system, the curve portion is arc data specified by the start point P ₁ , the passing point P ₂ and the end point P _3. When these three points of data P ₁ , P ₂ , and P ₃ are supplied to the circular interpolation processing unit 1, circular interpolation processing as shown in FIG. 2 is executed.
[0013]
This circular interpolation processing includes a step of determining the center coordinate P ₀ from the given three points data (S1), a step of determining a split angle from the square of the radius (S2), and a step of determining the rotation direction ( S3), a step (S4) for obtaining a division point sequence, that is, a division line segment, along the rotation direction for each division angle, and a determination step (S5) for ending the line segment division. Hereinafter, each step will be described.
[0014]
(1) Determination of center coordinate P ₀ (S1)
As shown in FIG. 3, as the data P ₁ at three points on an arc centered on the P _0, P _2, P ₃ is located, a point P ₁ and the point on the arc relative to the center point P ₀ If a fourth point P ₄ of and placed symmetrically, the vector V ₂₁ from P ₁ to P _2, the angle is 90 ° next to the vector V ₄₂ from P ₂ to P _4, as well from P ₁ a vector V ₃₁ to P _3, the angle also 90 ° between the vector V ₄₃ from P ₃ to P _4. Accordingly, the inner product of the vectors V ₂₁ and V _{42 and} the inner product of the vectors V ₃₁ and V ₄₃ are both zero. That is, if the coordinates of P ₁ , P ₂ , P ₃ , and P ₄ are (x ₁ , y ₁ ), (x ₂ , y ₂ ), (x ₃ , y ₃ ), and (x ₄ , y ₄ ), respectively. ,
[0015]
[Expression 2]
V ₂₁ · V ₄₂
_{_{= (X 2 -X 1) (}} x 4 -x 2) + (y 2 -y 1) (y 4 -y 2)
= 0
V ₃₁・ V ₄₃
= (X ₃ -X ₁ ) (x ₄ -x ₃ ) + (y ₃ -y ₁ ) (y ₄ -y ₃ )
= 0
[0016]
Solving Equation 2 for x ₄ and y ₄ gives Equation 3.
[0017]
[Equation 3]

[0018]
Here, assuming that the variables P ₁ , P ₂ , and P ₃ are 16-bit precision, the denominator of the expression for obtaining x ₄ and y ₄ of Equation ₃ and the expression for obtaining c ₁ and c ₂ are 32-bit integer types and maintain precision. can do. P ₄ is a 16-bit integer. In the final procedure for obtaining x ₄ and y ₄ , a floating point operation is required twice for multiplication and once for division. From Equation 3, the center coordinates P ₀ = (x ₀ , y ₀ ) of the arc are obtained as the midpoints of P ₁ and P ₄ , but are obtained as in Equation 4 in order to prevent truncation errors.
[0019]
[Expression 4]
x ₀ = (x ₄ + x ₁ +1) / 2
y ₀ = (y ₄ + y ₁ +1) / 2
[0020]
(2) Determination of split angle (S2)
Ideally, the division angle ζ is determined based on Equation 1, but in this case, since a high processing capacity is required for the calculation, here, the division angle ζ is performed by the following procedure capable of high-speed processing. To decide. That is, the square value of the radius r is obtained by integer calculation as shown in Equation 5.
[0021]
[Equation 5]
r ² = (x ₁ −x ₀ ) ² + (y ₁ −y ₀ ) ²
[0022]
A conversion table as shown in FIG. 4 is stored in advance in the split angle determination table 2, and the split angle ζ is determined from the split angle determination table 2 using the squared value r ² of the radius obtained in Equation 5 as an index. To do. Here, the error e is set to about 13 dots.
According to this method, (1) the square root calculation for calculating the radius is unnecessary, and (2) the inverse cosine transform is unnecessary, so that the processing time can be greatly shortened.
[0023]
(3) Determination of rotation direction (S3)
As shown in FIG. 5, the rotation direction of the arc is positive when the angle θ formed by the vector V ₂₁ extending from the start point P ₁ to the passing point P ₂ and the vector V ₃₂ extending from the passing point P ₂ to the end point P ₃ is positive. Can be determined by whether it is negative or negative. That is, as shown in FIG. 5 (a), the in the case where the angle between V ₂₁ and V ₃₂ theta is positive is counterclockwise, as shown in FIG. (B), the V ₂₁ and V ₃₂ When the formed angle θ is negative, it is clockwise. The outer product of the two vectors V ₂₁ and V ₃₂ is obtained as shown in Equation 6.
[0024]
[Formula 6]
V ₂₁ × V ₃₂
_{_{= | V 21 || V 32 |}} sinθ
_{_{= (X 2 -x 1) (}} y 3 -y 2) - (y 2 -y 1) (x 3 -x 2)
[0025]
The sign of this value is directly used as the rotation direction of the dividing angle ζ. This operation can also be performed only by integer processing.
[0026]
(4) Dividing process into line segments (S4)
When the arc center point P ₀ and the signed division angle ζ are obtained, the division processing into line segments is repeated as shown in FIG. 6 to obtain the division points P _d1 , P _d2,. Thereby, divided vectors V _d1 , V _d2 ,... _Are obtained. Now, let V _rn-1 and V _rn be vectors extending from the center point P _{0 of the} arc to the dividing points P _dn-1 and P _dn , respectively.
[0027]
[Expression 7]

[0028]
It can be expressed as Accordingly, the coordinates (x _dn , y _dn ) of the nth division point P _dn are obtained as follows.
[0029]
[Equation 8]
x _dn = (x _dn-1 -x ₀ ) cosζ- (y _dn-1 -y ₀ ) sinζ + x ₀
y _dn = (x _dn-1 -x ₀ ) sinζ + (y _dn-1 -y ₀ ) cosζ + y ₀
[0030]
At this time, sinζ and cosζ are obtained by referring to the trigonometric function table 3. Assuming that the division angle is from 0 ° to 180 °, it is sufficient, but when the division angle determination table 2 as shown in FIG. 4 is used, 14 arrangements from 2 ° to 15 ° are provided. It is enough if you have prepared. sinζ and cosζ may be obtained once at the time of dividing the line segment, and since the calculation of Expression 8 is simple, high-speed processing is possible.
[0031]
(5) Determination of division end (S5)
End of division processing is checked by whether the division point exceeds the arc end point P _3.
As shown in FIG. 7, when a vector extending from the dividing point P _dn-1 to the end point P ₃ is V ₁ and a vector extending from the next dividing point P _dn to the end point P ₃ is V ₂ , ), When the dividing point P _dn exists before the end point P ₃ , the angle formed by the vector V ₁ and the vector V ₂ is 90 ° or less, as shown in FIG. When the dividing point P _dn exceeds the end point P ₃ , the angle formed by the vector V ₁ and the vector V ₂ exceeds 90 °. Therefore, it can be determined that the calculated inner product of vectors V1, V2, dividing points _Pdn with a that the sign becomes negative has exceeded the end point P _3. That is,
[0032]
[Equation 9]
V ₁・ V ₂
= (X ₃ −x _dn−1 ) (x ₃ −x _dn ) + (y ₃ −y _dn−1 ) (y ₃ −y _dn ) ≦ 0
[0033]
Is detected, the segment V ₁ that reaches the end point P ₃ is determined as the final segment without using the segment segment V _dn .
With the above processing, the speed of the circular interpolation processing can be greatly improved.
[0034]
【The invention's effect】
As described above, according to the present invention, the cross product of the vector from the start point to the pass point and the vector from the pass point to the end point is obtained from the start point, pass point and end point data given as the arc data. Since the rotation direction of the split angle is determined based on the sign, the arc tangent calculation is not required, and the arithmetic processing is only four arithmetic operations. Therefore, the processing speed is remarkably higher than the conventional one. There is an effect. Each time line data is generated, an inner product of a vector extending from the start point of the line segment data to the end point of the arc and a vector extending from the end point of the line segment data to the end point of the arc is obtained, and the line segment data is based on the sign. Therefore, the end determination can be performed by a simple calculation, and the processing speed is further improved.
[Brief description of the drawings]
FIG. 1 is a functional block diagram of a system for realizing circular interpolation processing according to an embodiment of the present invention.
FIG. 2 is a flowchart of the circular interpolation process.
FIG. 3 is a diagram for explaining a calculation procedure of a center point coordinate of an arc in the same processing.
FIG. 4 is a diagram showing an example of a split angle determination table used in a split angle determination procedure in the same process.
FIG. 5 is a diagram for explaining a procedure for determining a rotation direction of a split angle in the same process.
FIG. 6 is a diagram for explaining a line segment dividing procedure in the same processing;
FIG. 7 is a diagram for explaining a line segment division end determination procedure in the same process;
FIG. 8 is a diagram illustrating a relationship between an arc segment dividing angle and an error.
FIG. 9 is a diagram for explaining a conventional circular interpolation processing method;
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... Circular interpolation process part, 2 ... Division angle determination table, 3 ... Trigonometric function table.

Claims

In the circular interpolation processing method for generating a plurality of line segment data approximating the arc from the arc data designated by the start point, the passing point, and the end point,
A center point calculating step of calculating a center point of the arc from the specified three points of data;
A split angle determining step of determining a split angle by calculating a value corresponding to the radius of the arc from at least one of the data of the three points and the calculated center point;
A rotation direction determining step for obtaining a cross product of a vector from the start point to the passing point and a vector from the passing point to the end point, and determining a rotation direction of the split angle based on the sign;
The line segment data is sequentially generated by dividing the arc in the determined rotation direction at the determined division angles, and the line segment data is generated when the end point of the line segment data exceeds the end point of the arc. and a line segment data generating step of terminating the generation of,
The line segment data generation step calculates an inner product of a vector extending from the start point of the line segment data to the end point of the arc and a vector extending from the end point of the line segment data to the end point of the arc every time the line segment data is generated. A circular interpolation processing method characterized in that it is a step of obtaining and ending generation of the line segment data based on the sign .

The division angle determining step is a step of obtaining a square value of the radius of the arc from at least one of the data of the three points and the center point, and determining a division angle based on the square value of the radius. The circular interpolation processing method according to claim 1.