曲線近似装置及び方法
【目的】本発明の目的は、処理時間を増大させることなく、滑らかな折線近似が得られる曲線近似方法及び装置を提供することにある。
【構成】曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ線分と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有する。
【効果】処理時間を増大させることなく、滑らかな折線近似が得られる曲線近似方法及び装置を構成出来る。
【構成】曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ線分と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有する。
【効果】処理時間を増大させることなく、滑らかな折線近似が得られる曲線近似方法及び装置を構成出来る。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、曲線を例えば表示装置又は印刷装置等に出力する曲線近似装置に係る。
【０００２】
【従来の技術】一般に、曲線を直接ドット列として発生させようとすると複雑な処理を必要とするため、複数の連続した線分からなる折線で近似して表示する。線分を発生するには、例えば、ＤＤＡ(Digital Differential Analizer）を用いる方法がある。
【０００３】即ち、曲線の折線近似は、曲線上に適当なＮ(≧１)個の分割点を採り（一般に、分割点の座標値は実数値になるが、四捨五入等によって尤も近くの整数値に丸める）、始点と第１番目の分割点、第１番目の分割点と第２番目の分割点、……、第Ｎ−１番目の分割点と第Ｎ番目の分割点、第Ｎ番目の分割点と終点とを線分で結ぶことによってなされる。
【０００４】従来、曲線上の分割点の求め方としては、次のようなものがあった。
【０００５】第一の例としては、曲線の各座標がパラメータによる数式で表現されている場合に、パラメータの値を始点から終点までで等分し、各パラメータの値における点を分割点とする方法である。
【０００６】第二の例としては、特開平2−10476公報に記載のように、曲線上の適当な一点を分割点として求め、曲線の始点と終点とを結ぶ直線と分割点との距離を計算し、その距離が所定値以上の場合には、分割されたそれぞれの部分曲線に対しこの処理を繰り返し、所定値未満になった場合には、上記のようにして得られた部分曲線の始点及び終点を分割点とする方法である。
【０００７】
【発明が解決しようとする課題】上記従来技術の第一の例では、曲線の曲率が大きい箇所も小さな箇所も一律に処理するため、滑らかな折線近似を得ようとする場合、曲率の大きな箇所に合わせると分割点の個数を多く必要とし、又、曲率の小さな箇所には過剰の分割となり、処理時間の増大及び近似精度に問題があった。
【０００８】上記第二の例では、例えば図７のような曲線Ｐ(0)Ｐ(1)に対し、分割点として点Ｐ（線分Ｐ(0)Ｐ(1)上にあるものとする）を採れば、直線Ｐ(0)Ｐ(1)と点Ｐとの距離は０なので所定値未満となり、故に曲線Ｐ(0)Ｐ(1)の近似として線分Ｐ(0)Ｐ(1)が得られる。然し乍ら、線分Ｐ(0)Ｐ(1)から尤も離れた曲線Ｐ(0)Ｐ(1)上の点Ｐ(2)又は点Ｐ(3)までの距離ｄ(2)又はｄ(3)が大きい場合には、線分Ｐ(0)Ｐ(1)は曲線Ｐ(0)Ｐ(1)の近似とは言い難い。又、図７のような場合には、曲線Ｐ(0)Ｐ(1)を二つの曲線Ｐ(0)Ｐ及び曲線ＰＰ(1)に分けてから処理する方法が考えられる。然し乍ら、一般に、線分Ｐ(0)Ｐ(1)と交わる曲線Ｐ(0)Ｐ(1)上の点Ｐが存在すること及び座標を求めることは複雑な計算を必要とする。
【０００９】従って、本発明の目的は、処理時間を増大させることなく、又、図７のような曲線に対しても滑らかな折線近似が得られる曲線近似方法及び装置を提供することにある。
【００１０】
【問題を解決するための手段】上記課題は、曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ直線と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有することによって達成される。
【００１１】
【作用】上記曲線分割手段によって曲線上の一つ以上の分割点を求め、上記距離計算手段によって曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し上記曲線分割手段及び上記距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を上記線分発生手段によって発生することによって曲線を折線で近似する。ここで、上記曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とする。
【００１２】
【実施例】以下、本発明の一実施例について述べる。
【００１３】図１は、本発明の構成図の一例である。図１R>１において、１０１は曲線分割手段であり曲線上の一つ以上の分割点を求めるために使用し、１０２は距離計算手段であり曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算するために使用し、１０３は線分発生手段であり始点と終点とを結ぶ線分を発生するために使用する。
【００１４】図２は、本発明のフローチャートの一例である。先ず、曲線を分割するための分割点を求め（曲線分割処理、ステップ２０１）、次に、曲線の始点及びステップ２０１で求めた分割点及び曲線の終点を隣合う順番毎に線分で結ぶ（折線発生処理、ステップ２０２）。
【００１５】図３は、図２におけるステップ２０１の曲線分割処理のフローチャートの一例である。先ず、曲線分割手段１０１によって曲線の始点Ｐ(0)と終点Ｐ(1)とを結ぶ直線Ｐ(0)Ｐ(1)に平行な接線を有する点Ｑ(k)(k=1, 2, …, M)を総て求め、分割点とする（ステップ３０１）。次に、距離計算手段１０２によって直線Ｐ(0)Ｐ(1)とそれぞれの分割点との距離の最大値を求める(ステップ３０２）。次に、ステップ３０２で求めた距離の最大値が所定値未満であれば処理を終了し、所定値以上であれば繰返し処理（ステップ３０４）を実行する（判定３０３）。
【００１６】図４は、図３におけるステップ３０４の繰返し処理のフローチャートの一例である。曲線分割処理に入力される曲線の始点をＱ(0)、分割点をＱ(k)(k＝1, 2,…, M)、曲線の終点をＱ(M＋1)とする。先ず、ループカウンタLCにM＋1を代入する（ステップ４０１）。次に、始点をＱ(M+1-LC)、終点をＱ(M−LC)とする部分曲線に対し図２におけるステップ２０１の曲線分割処理を行う（ステップ４０２、ステップ４０３）。次に、LCをデクリメントし（ステップ４０４）、０であれば繰返し処理を終了し、正数であれば再びステップ４０２に戻る（判定４０５）。
【００１７】図５は、図２におけるステップ２０２の折線発生処理のフローチャートの一例である。図２におけるステップ２０１の曲線分割処理によって求めた分割点をＲ(k)(k＝1, 2, …, N)、曲線の始点をＲ(0)、終点をＲ(N＋1)とする。先ず、ループカウンタLCにN＋1を代入する（ステップ５０１）。次に、線分発生手段１０３によって始点をＲ(N＋1−LC)、終点をＲ(N−LC)とする線分を発生する（ステップ５０２）。次に、LCをデクリメントし（ステップ５０３）、０であれば折線発生処理を終了し、正数であれば再びステップ５０２に戻る（判定５０４）。
【００１８】図６は、本発明の上記実施例を用いて曲線の折線近似を行った場合の一例である。
【００１９】図６（ａ）は、曲線分割手段１０１によって、曲線Ｐ(0)Ｐ(1)に対して、直線Ｐ(0)Ｐ(1)に平行な接線を有する点Ｐ(2)及び点Ｐ(3)を求めるようすを示す図である。
【００２０】例えば、曲線Ｐ(0)Ｐ(1)が
【００２１】
【数１】Ｐ=Ｐ(t) (0≦t≦1)のようにパラメータによる数式で表現されている場合を考える。この場合には、直線Ｐ(0)Ｐ(1)に平行な接線を有する分割点の求め方は次のようにする。即ち、曲線Ｐ(0)Ｐ(1)のt(0≦t≦1)における接線の勾配ベクトルはＰ'(t)で与えられ（'は微分を表す）、又、直線Ｐ(0)Ｐ(1)の方向ベクトルはＰ(1)−Ｐ(0)で与えられるので、両ベクトルの方向が一致するための値tを求めればよい。それには、tとαの連立方程式
【００２２】
【数２】Ｐ'(t)=α(Ｐ(1)−Ｐ(0)) (0≦t≦1)を解く方法、又は、tについての方程式(Ｐ(1)−Ｐ(0))×Ｐ'(t)=０ (0≦t≦1)を解く方法等がある（×は外積を表す）。これらは、どちらからも同じ解が得られ、微積分学の平均値の定理により少なくとも一つの解が存在する。又、三次のBezier曲線のようにＰ(t)が高々三次の多項式で表される場合には、二次方程式を解けばよいことになり、二次方程式の解の公式により容易に解を求めることができる。又、Ｐ(t)が円弧の一部として与えられる場合には、逆正接テーブルのようなテーブルを用いることで容易に解を求めることができる。以上のようにして求めたt＝t(1), t(2), …, t(N)によって分割点Ｐ(t(1)), Ｐ(t(2)), …, Ｐ(t(N))を求めることができる。
【００２３】次に、距離計算手段１０２によって、直線Ｐ(0)Ｐ(1)と点Ｐ(2)及び点Ｐ(3)との距離ｄ(2)及びｄ(3)を求める。距離の求め方は、一般に、直線の方程式を
【００２４】
【数３】aX＋bY＋c＝0とするとき、点Ｐ(X, Y)からこの直線までの距離ｄは
【００２５】
【数４】ｄ＝|aX＋bY＋c|/√(a×a＋b×b)で与えられる（×は積演算を表す）。又、線分と点との距離の求め方は、特開平2-10476公報に記載のように、線分の中点と点との距離を求めるようにしてもよい。この例では、max(ｄ(2), ｄ(3))が所定値以上になるものとする。
【００２６】図６（ｂ）は、max(ｄ(2), ｄ(3))が所定値以上になるため、曲線分割手段１０１によって、部分曲線Ｐ(0)Ｐ(2)に対し分割点Ｐ(4)を、部分曲線Ｐ(2)Ｐ（３）に対し分割点Ｐ（５）及びＰ(6)を、部分曲線Ｐ(3)Ｐ(1)に対し分割点Ｐ(7)を求め、距離計算手段１０２によって、直線Ｐ(0)Ｐ(2)と点Ｐ(4)との距離ｄ(4)を、直線Ｐ(2)Ｐ(3)と点Ｐ(5)及び点Ｐ(6)との距離ｄ(5)及びｄ(6)を、直線Ｐ(3)Ｐ(1)と点Ｐ(7)との距離ｄ(7)を求めるようすを示す図である。この例では、ｄ(4)のみ所定値以上になるものとする。
【００２７】図６(ｃ）は、ｄ(4)が所定値以上になるため、曲線分割手段１０１によって、部分曲線Ｐ(0)Ｐ(4)に対し分割点Ｐ(8)を、部分曲線Ｐ(4)Ｐ(2)に対し分割点Ｐ(9)を求め、距離計算手段１０２によって、直線Ｐ(0)Ｐ(4)と点Ｐ(8)との距離ｄ(8)を、直線Ｐ(4)Ｐ(2)と点Ｐ(9)との距離ｄ(9)を求めるようすを示す図である。この例では、max(ｄ(8), ｄ(9))が所定値未満となるものとする。
【００２８】図６（ｄ）は、総ての距離が所定値未満となったため、線分発生手段１０３によって、線分(0)Ｐ(4)及び線分Ｐ(4)Ｐ(2)及び線分Ｐ(2)Ｐ(3)及び線分Ｐ(3)Ｐ(1)を結び、折線を発生するようすを示した図である。
【００２９】
【発明の効果】本発明によれば、曲線分割手段によって曲線上の一つ以上の分割点を求め、距離計算手段によって曲線の始点と終点を結ぶ線分と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し曲線分割手段及び距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を線分発生手段によって発生することによって曲線を折線で近似する。ここで、曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とする。
【００３０】従って、処理時間を増大させることなく、又、図７のような曲線に対しても滑らかな折線近似が得られる曲線近似方法及び装置を構成出来る。
【図面の簡単な説明】
【図１】本発明の構成図である。
【図２】本発明のフローチャートである。
【図３】曲線分割処理のフローチャートである。
【図４】繰返し処理のフローチャートである。
【図５】折線発生処理のフローチャートである。
【図６】曲線の折線近似を行った場合の一例を示す図である。
【図７】曲線の折線近似の従来例を示す図である。
【符号の説明】
１０１…曲線分割手段、
１０２…距離計算手段、
１０３…線分発生手段。
【０００１】
【産業上の利用分野】本発明は、曲線を例えば表示装置又は印刷装置等に出力する曲線近似装置に係る。
【０００２】
【従来の技術】一般に、曲線を直接ドット列として発生させようとすると複雑な処理を必要とするため、複数の連続した線分からなる折線で近似して表示する。線分を発生するには、例えば、ＤＤＡ(Digital Differential Analizer）を用いる方法がある。
【０００３】即ち、曲線の折線近似は、曲線上に適当なＮ(≧１)個の分割点を採り（一般に、分割点の座標値は実数値になるが、四捨五入等によって尤も近くの整数値に丸める）、始点と第１番目の分割点、第１番目の分割点と第２番目の分割点、……、第Ｎ−１番目の分割点と第Ｎ番目の分割点、第Ｎ番目の分割点と終点とを線分で結ぶことによってなされる。
【０００４】従来、曲線上の分割点の求め方としては、次のようなものがあった。
【０００５】第一の例としては、曲線の各座標がパラメータによる数式で表現されている場合に、パラメータの値を始点から終点までで等分し、各パラメータの値における点を分割点とする方法である。
【０００６】第二の例としては、特開平2−10476公報に記載のように、曲線上の適当な一点を分割点として求め、曲線の始点と終点とを結ぶ直線と分割点との距離を計算し、その距離が所定値以上の場合には、分割されたそれぞれの部分曲線に対しこの処理を繰り返し、所定値未満になった場合には、上記のようにして得られた部分曲線の始点及び終点を分割点とする方法である。
【０００７】
【発明が解決しようとする課題】上記従来技術の第一の例では、曲線の曲率が大きい箇所も小さな箇所も一律に処理するため、滑らかな折線近似を得ようとする場合、曲率の大きな箇所に合わせると分割点の個数を多く必要とし、又、曲率の小さな箇所には過剰の分割となり、処理時間の増大及び近似精度に問題があった。
【０００８】上記第二の例では、例えば図７のような曲線Ｐ(0)Ｐ(1)に対し、分割点として点Ｐ（線分Ｐ(0)Ｐ(1)上にあるものとする）を採れば、直線Ｐ(0)Ｐ(1)と点Ｐとの距離は０なので所定値未満となり、故に曲線Ｐ(0)Ｐ(1)の近似として線分Ｐ(0)Ｐ(1)が得られる。然し乍ら、線分Ｐ(0)Ｐ(1)から尤も離れた曲線Ｐ(0)Ｐ(1)上の点Ｐ(2)又は点Ｐ(3)までの距離ｄ(2)又はｄ(3)が大きい場合には、線分Ｐ(0)Ｐ(1)は曲線Ｐ(0)Ｐ(1)の近似とは言い難い。又、図７のような場合には、曲線Ｐ(0)Ｐ(1)を二つの曲線Ｐ(0)Ｐ及び曲線ＰＰ(1)に分けてから処理する方法が考えられる。然し乍ら、一般に、線分Ｐ(0)Ｐ(1)と交わる曲線Ｐ(0)Ｐ(1)上の点Ｐが存在すること及び座標を求めることは複雑な計算を必要とする。
【０００９】従って、本発明の目的は、処理時間を増大させることなく、又、図７のような曲線に対しても滑らかな折線近似が得られる曲線近似方法及び装置を提供することにある。
【００１０】
【問題を解決するための手段】上記課題は、曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ直線と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有することによって達成される。
【００１１】
【作用】上記曲線分割手段によって曲線上の一つ以上の分割点を求め、上記距離計算手段によって曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し上記曲線分割手段及び上記距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を上記線分発生手段によって発生することによって曲線を折線で近似する。ここで、上記曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とする。
【００１２】
【実施例】以下、本発明の一実施例について述べる。
【００１３】図１は、本発明の構成図の一例である。図１R>１において、１０１は曲線分割手段であり曲線上の一つ以上の分割点を求めるために使用し、１０２は距離計算手段であり曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算するために使用し、１０３は線分発生手段であり始点と終点とを結ぶ線分を発生するために使用する。
【００１４】図２は、本発明のフローチャートの一例である。先ず、曲線を分割するための分割点を求め（曲線分割処理、ステップ２０１）、次に、曲線の始点及びステップ２０１で求めた分割点及び曲線の終点を隣合う順番毎に線分で結ぶ（折線発生処理、ステップ２０２）。
【００１５】図３は、図２におけるステップ２０１の曲線分割処理のフローチャートの一例である。先ず、曲線分割手段１０１によって曲線の始点Ｐ(0)と終点Ｐ(1)とを結ぶ直線Ｐ(0)Ｐ(1)に平行な接線を有する点Ｑ(k)(k=1, 2, …, M)を総て求め、分割点とする（ステップ３０１）。次に、距離計算手段１０２によって直線Ｐ(0)Ｐ(1)とそれぞれの分割点との距離の最大値を求める(ステップ３０２）。次に、ステップ３０２で求めた距離の最大値が所定値未満であれば処理を終了し、所定値以上であれば繰返し処理（ステップ３０４）を実行する（判定３０３）。
【００１６】図４は、図３におけるステップ３０４の繰返し処理のフローチャートの一例である。曲線分割処理に入力される曲線の始点をＱ(0)、分割点をＱ(k)(k＝1, 2,…, M)、曲線の終点をＱ(M＋1)とする。先ず、ループカウンタLCにM＋1を代入する（ステップ４０１）。次に、始点をＱ(M+1-LC)、終点をＱ(M−LC)とする部分曲線に対し図２におけるステップ２０１の曲線分割処理を行う（ステップ４０２、ステップ４０３）。次に、LCをデクリメントし（ステップ４０４）、０であれば繰返し処理を終了し、正数であれば再びステップ４０２に戻る（判定４０５）。
【００１７】図５は、図２におけるステップ２０２の折線発生処理のフローチャートの一例である。図２におけるステップ２０１の曲線分割処理によって求めた分割点をＲ(k)(k＝1, 2, …, N)、曲線の始点をＲ(0)、終点をＲ(N＋1)とする。先ず、ループカウンタLCにN＋1を代入する（ステップ５０１）。次に、線分発生手段１０３によって始点をＲ(N＋1−LC)、終点をＲ(N−LC)とする線分を発生する（ステップ５０２）。次に、LCをデクリメントし（ステップ５０３）、０であれば折線発生処理を終了し、正数であれば再びステップ５０２に戻る（判定５０４）。
【００１８】図６は、本発明の上記実施例を用いて曲線の折線近似を行った場合の一例である。
【００１９】図６（ａ）は、曲線分割手段１０１によって、曲線Ｐ(0)Ｐ(1)に対して、直線Ｐ(0)Ｐ(1)に平行な接線を有する点Ｐ(2)及び点Ｐ(3)を求めるようすを示す図である。
【００２０】例えば、曲線Ｐ(0)Ｐ(1)が
【００２１】
【数１】Ｐ=Ｐ(t) (0≦t≦1)のようにパラメータによる数式で表現されている場合を考える。この場合には、直線Ｐ(0)Ｐ(1)に平行な接線を有する分割点の求め方は次のようにする。即ち、曲線Ｐ(0)Ｐ(1)のt(0≦t≦1)における接線の勾配ベクトルはＰ'(t)で与えられ（'は微分を表す）、又、直線Ｐ(0)Ｐ(1)の方向ベクトルはＰ(1)−Ｐ(0)で与えられるので、両ベクトルの方向が一致するための値tを求めればよい。それには、tとαの連立方程式
【００２２】
【数２】Ｐ'(t)=α(Ｐ(1)−Ｐ(0)) (0≦t≦1)を解く方法、又は、tについての方程式(Ｐ(1)−Ｐ(0))×Ｐ'(t)=０ (0≦t≦1)を解く方法等がある（×は外積を表す）。これらは、どちらからも同じ解が得られ、微積分学の平均値の定理により少なくとも一つの解が存在する。又、三次のBezier曲線のようにＰ(t)が高々三次の多項式で表される場合には、二次方程式を解けばよいことになり、二次方程式の解の公式により容易に解を求めることができる。又、Ｐ(t)が円弧の一部として与えられる場合には、逆正接テーブルのようなテーブルを用いることで容易に解を求めることができる。以上のようにして求めたt＝t(1), t(2), …, t(N)によって分割点Ｐ(t(1)), Ｐ(t(2)), …, Ｐ(t(N))を求めることができる。
【００２３】次に、距離計算手段１０２によって、直線Ｐ(0)Ｐ(1)と点Ｐ(2)及び点Ｐ(3)との距離ｄ(2)及びｄ(3)を求める。距離の求め方は、一般に、直線の方程式を
【００２４】
【数３】aX＋bY＋c＝0とするとき、点Ｐ(X, Y)からこの直線までの距離ｄは
【００２５】
【数４】ｄ＝|aX＋bY＋c|/√(a×a＋b×b)で与えられる（×は積演算を表す）。又、線分と点との距離の求め方は、特開平2-10476公報に記載のように、線分の中点と点との距離を求めるようにしてもよい。この例では、max(ｄ(2), ｄ(3))が所定値以上になるものとする。
【００２６】図６（ｂ）は、max(ｄ(2), ｄ(3))が所定値以上になるため、曲線分割手段１０１によって、部分曲線Ｐ(0)Ｐ(2)に対し分割点Ｐ(4)を、部分曲線Ｐ(2)Ｐ（３）に対し分割点Ｐ（５）及びＰ(6)を、部分曲線Ｐ(3)Ｐ(1)に対し分割点Ｐ(7)を求め、距離計算手段１０２によって、直線Ｐ(0)Ｐ(2)と点Ｐ(4)との距離ｄ(4)を、直線Ｐ(2)Ｐ(3)と点Ｐ(5)及び点Ｐ(6)との距離ｄ(5)及びｄ(6)を、直線Ｐ(3)Ｐ(1)と点Ｐ(7)との距離ｄ(7)を求めるようすを示す図である。この例では、ｄ(4)のみ所定値以上になるものとする。
【００２７】図６(ｃ）は、ｄ(4)が所定値以上になるため、曲線分割手段１０１によって、部分曲線Ｐ(0)Ｐ(4)に対し分割点Ｐ(8)を、部分曲線Ｐ(4)Ｐ(2)に対し分割点Ｐ(9)を求め、距離計算手段１０２によって、直線Ｐ(0)Ｐ(4)と点Ｐ(8)との距離ｄ(8)を、直線Ｐ(4)Ｐ(2)と点Ｐ(9)との距離ｄ(9)を求めるようすを示す図である。この例では、max(ｄ(8), ｄ(9))が所定値未満となるものとする。
【００２８】図６（ｄ）は、総ての距離が所定値未満となったため、線分発生手段１０３によって、線分(0)Ｐ(4)及び線分Ｐ(4)Ｐ(2)及び線分Ｐ(2)Ｐ(3)及び線分Ｐ(3)Ｐ(1)を結び、折線を発生するようすを示した図である。
【００２９】
【発明の効果】本発明によれば、曲線分割手段によって曲線上の一つ以上の分割点を求め、距離計算手段によって曲線の始点と終点を結ぶ線分と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し曲線分割手段及び距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を線分発生手段によって発生することによって曲線を折線で近似する。ここで、曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とする。
【００３０】従って、処理時間を増大させることなく、又、図７のような曲線に対しても滑らかな折線近似が得られる曲線近似方法及び装置を構成出来る。
【図面の簡単な説明】
【図１】本発明の構成図である。
【図２】本発明のフローチャートである。
【図３】曲線分割処理のフローチャートである。
【図４】繰返し処理のフローチャートである。
【図５】折線発生処理のフローチャートである。
【図６】曲線の折線近似を行った場合の一例を示す図である。
【図７】曲線の折線近似の従来例を示す図である。
【符号の説明】
１０１…曲線分割手段、
１０２…距離計算手段、
１０３…線分発生手段。
【特許請求の範囲】
【請求項１】曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ直線と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有することを特徴とする曲線近似装置。
【請求項２】請求項１記載の曲線近似装置において、上記曲線分割手段によって曲線上の一つ以上の分割点を求め、上記距離計算手段によって曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し上記曲線分割手段及び上記距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を上記線分発生手段によって発生することによって曲線を折線で近似することを特徴とする曲線近似方法。
【請求項３】請求項１記載の曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とすることを特徴とする曲線近似装置。
【請求項１】曲線上の一つ以上の分割点を求め複数の曲線に分割する曲線分割手段と、曲線の始点と終点とを結ぶ直線と曲線上の一点との距離を計算する距離計算手段と、二点を結ぶ線分を発生する線分発生手段を有することを特徴とする曲線近似装置。
【請求項２】請求項１記載の曲線近似装置において、上記曲線分割手段によって曲線上の一つ以上の分割点を求め、上記距離計算手段によって曲線の始点と終点を結ぶ直線と該分割点との距離の最大値を計算し、該距離の最大値が所定値以上の場合には分割されたそれぞれの部分曲線に対し上記曲線分割手段及び上記距離計算手段によって上記処理を繰り返し、所定値未満となった部分曲線の場合には上記処理の繰り返しを行なわず該部分曲線の始点と終点とを結ぶ線分を上記線分発生手段によって発生することによって曲線を折線で近似することを特徴とする曲線近似方法。
【請求項３】請求項１記載の曲線分割手段は、曲線の始点と終点とを結ぶ直線と平行な接線を有する点を分割点とすることを特徴とする曲線近似装置。
【図１】
【図２】
【図６】
【図７】
【図３】
【図４】
【図５】
【図２】
【図６】
【図７】
【図３】
【図４】
【図５】
【公開番号】特開平５−２０５０４１
【公開日】平成５年（１９９３）８月１３日
【国際特許分類】
【出願番号】特願平４−１４７３５
【出願日】平成４年（１９９２）１月３０日
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【公開日】平成５年（１９９３）８月１３日
【国際特許分類】
【出願日】平成４年（１９９２）１月３０日
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
[ Back to top ]