JPH08329245A

JPH08329245A - 図形処理方法とその装置

Info

Publication number: JPH08329245A
Application number: JP7139118A
Authority: JP
Inventors: Masaru Kageura; 勝影浦
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1995-06-06
Filing date: 1995-06-06
Publication date: 1996-12-13
Anticipated expiration: 2021-05-17
Also published as: JP3774489B2

Abstract

(57)【要約】【目的】２幾何要素のデータにノイズを含む場合であ
っても、適正にそれらの２幾何要素間の交線を求める図
形処理方法とその装置を提供する。【構成】図形の方程式の係数に基づく所定の判別式を
計算して、前記図形を楕円と判定する第１の判定工程
（Ｓ６、Ｓ７）と、第１の判定工程で前記図形を楕円と
判定したとき、図形の短軸と長軸の長さの差が所定値以
下であれば、前記図形を円と判定する第２の判定工程
（Ｓ９、Ｓ１２）とを備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、図形処理方法とその
装置、特に、２つの図形の交線の算出方法に関するもの
である。

【０００２】

【従来の技術】従来、交線を求めるときに、単純に２幾
何要素の式を連立させて交線の式を代数的・解析的に求
めるという方法があった。また、交線を求めるときに、
２幾何要素の幾何的な特徴を利用して、判別式等を使っ
てあらかじめ交線の種類を決定して、交線の計算を行な
うという方法があった。

【０００３】

【発明が解決しようとする課題】しかしながら、従来の
方法では、２幾何要素の関係の判定等で、桁落ち等によ
る数値的な誤差が少しでも入った場合、統一的かつ実用
的な基準で正しく判定できず、正しい交線が求まらない
ことが多いという問題があった。本発明は、上記従来例
に鑑みてなされたもので、２幾何要素のデータにノイズ
を含む場合であっても、適正にそれらの２幾何要素間の
交線を求める図形処理方法とその装置を提供することを
目的とする。

【０００４】

【課題を解決するための手段】上記目的を達成するた
め、本発明の図形処理方法とその装置は以下の構成を備
える。即ち、図形の方程式の係数に基づく所定の判別式
を計算して、前記図形を楕円と判定する第１の判定工程
と、前記第１の判定工程で前記図形を楕円と判定したと
き、前記図形の短軸と長軸の長さの差が所定値以下であ
れば、前記図形を円と判定する第２の判定工程とを備え
る。

【０００５】また、別の発明は、図形の方程式の係数に
基づく所定の判別式を計算して、前記図形を楕円と判定
する第１の判定手段と、前記第１の判定手段で前記図形
を楕円と判定したとき、前記図形の短軸と長軸の長さの
差が所定値以下であれば、前記図形を円と判定する第２
の判定手段とを備える。

【０００６】

【作用】以上の構成において、図形の方程式の係数に基
づく所定の判別式を計算して、前記図形を楕円と判定
し、前記第１の判定工程で前記図形を楕円と判定したと
き、前記図形の短軸と長軸の長さの差が所定値以下であ
れば、前記図形を円と判定する。

【０００７】また、別の発明は、第１の判定手段が、図
形の方程式の係数に基づく所定の判別式を計算して、前
記図形を楕円と判定し、第２の判定手段が、前記第１の
判定手段で前記図形を楕円と判定したとき、前記図形の
短軸と長軸の長さの差が所定値以下であれば、前記図形
を円と判定する。

【０００８】

【実施例】まず、本発明に係る実施例の図形処理方法の
ポイントの一つは、２つの図形の交線を求める際に、交
線の一般方程式の係数に基づいて、各種判別行列式を計
算することで、おおまかな交線の種類を判別するとい
う、いわゆる代数的判別を行い、その後、おおまかに各
図形種に分類された交線をその複数の幾何的特徴量に基
づいて最終的な交線の分類を決定し、また調整するとい
う、いわゆる幾何学的分類処理を行う構成を有すること
により、ノイズに強く適正な交線を求めることができる
ことにある。（実施例１）図１は、本発明に係る１実施例の図形処理
装置のブロック図であり、バス１（制御線，データ線お
よびアドレス線を含む）には、中央処理装置(ＣＰＵ)
２，リード・オンリー・メモリ(ＲＯＭ)３，ランダム・
アクセス・メモリ(ＲＡＭ)４，入力インターフェース５
を介して入力装置６，ＣＲＴインターフェース７を介し
てＣＲＴ８，外部記憶装置インターフェース９を介し
て、磁気ディスク，磁気テープ等のの外部記憶装置１０
が接続されている。

【０００９】ＲＯＭ３に記憶されたプログラムに応じ、
ＲＡＭ４を一時記憶装置として種々の処理及び制御、例
えば図形入力制御，図形表示表示，ピック処理，隠面処
理，内外判定等を行なう。入力装置６はキーボード，タ
ブレット，マウス等を備え、図形データの入力を行なう
が、この図形データはホスト・コンピュータから受けて
もよい。

【００１０】ＣＲＴ８は、必要に応じて複数のビット・
マップ・プレーン等を含んでおり、図形を表示する。次
に、本実施例の理解を容易にするために、図２に示すよ
うな円筒と平面による交線を求める方法、即ち、交線が
楕円または円である場合での交線計算方法を一例として
以下説明する。

【００１１】図３は、本発明の一実施例の図形処理の流
れを説明するフローチャートである。ここで、以下に述
べる処理に対応する処理プログラムはＲＯＭ３に格納さ
れており、ＣＰＵ２がこのプログラムを読み出して、解
釈し、実行する。以下、フローチャートを説明する前
に、説明に必要となる用語の定義を行う。＜平面、および、円筒面等の記号および用語の定義＞平
面および円筒面に関する記号を図８に示すように定義す
る。

【００１２】Ｐ０：平面上の基準点ｎ０：平面の法線ベクトル（単位ベクトルとする）ｃ０：円筒面の軸上の基準点ｒ：円筒面の半径ｎ１：円筒面の軸ベクトル（単位ベクトルとする）次の２つは図４には示されていないが、詳細は後述す
る。

【００１３】ＥＰＳ：幾何学的許容長さＥＰＳＡ：幾何学的許容角度《用語》・円筒面の基準面：ｃ０を通り円筒面の軸に垂直な平面
を円筒面の基準面という。

【００１４】・幾何学的特徴値：図形の中心，半径，長
径，短径等の幾何学的な特徴を表す値。次に、図３を参照して、本発明の一実施例の図形処理の
流れを説明する。尚、上述した変数名が以下の記述に表
れるが、それらの変数名は、ランダムアクセスメモリ４
に割り当てられているものとする。

【００１５】まず、ステップＳ６では、交線の式から交
線の種類・特徴量を算出する。ここで、対象となる平
面，円筒面のデータはすでに外部記憶装置またはランダ
ムアクセスメモリに予め格納されているものとし、そこ
から対象となる平面，円筒面のデータ取り出す。また、
対象となる平面は、所定のｘｙ平面と平行になるように
座標変換が既にかけられており、交線の式として２次曲
線の一般形ａ・ｘ²＋２ｈ・ｘｙ＋ｂ・ｙ²＋２ｇ・ｘ＋２ｆ・ｙ＋ｃ＝
０ここで、ａ，ｂ，ｃ，ｆ，ｇは定数。の形式で既に求められており、ランダムアクセスメモリ
４にそのデータが格納されているものとする。

【００１６】上述の座標変換は、例えば、前記対象とな
る平面の各座標と所定の変換マトリクスＭ（所定のｘｙ
平面と元座標空間での対象となる平面の角度をパラメー
タとする）の積を取ることで実現できる。また、逆に、
変換された平面の各座標と前記変換マトリクスＭの逆行
列Ｍ’の積を取ることにより、元の対象となる平面を求
めることができる。

【００１７】以下、本ステップでの詳細な処理内容を説
明する。まず、上の２次曲線の種類を判別するための行
列式を算出し、ランダムアクセスメモリ４に格納する。そし
て、Ｄ＝０であるならば上の２次曲線を直線として分類
する。

【００１８】次に、上の２次曲線の種類を判別するため
の別な行列式を計算し、ランダムアクセスメモリ４に格納する。そし
て、△＝０ならば上の２次曲線を放物線として分類す
る。

【００１９】次に、ｘ０＝（ｒｆｈ−ｂｇ）／△ ｙ０＝（ｒｈｇ−ａｆ）／△ を計算し、ランダムアクセスメモリ４に格納する。そし
て、Ｘ０＝（ｘ０，ｙ０）を計算し、ランダムアクセスメモリ４に格納する。

【００２０】次に、ａとｂの関係によって、以下の式 θ＝π／４：（もし、ａ＝ｂならば） θ＝（１／２）ａｔａｎ（２ｈ／(ａ−ｂ)）：（もし、ａ≠ｂならば）を計算し、ランダムアクセスメモリ４に格納する。

【００２１】次に、ｔ²−(ａ＋ｂ)ｔ＋ａｂ＝０ここで、ａ，ｂは定数の解ｔ１，ｔ２を計算し、ランダムアクセスメモリ４に
格納する。

【００２２】次に、ｈ＝０ならば、ａ，ｂをそれぞれａ
２、ｂ２に代入、即ち、ａ２＝ａ，ｂ２＝ｂの代入を行って、ランダムアクセスメモリ４に格納す
る。

【００２３】また、ｈ＞０ならば、ａ２＝ｍａｘ(ｔ１，ｔ２) ｂ２＝ｍｉｎ(ｔ１，ｔ２) ここで、ｍａｘ（ｘ１，ｘ２）：ｘ１とｘ２のうちの
大きい方を選択
する関数。

【００２４】ｍｉｎ（ｘ１，ｘ２）：ｘ１とｘ２のう
ちの小さい方を選択する関数。を計算し、ランダムアクセスメモリ４に格納する。ま
た、ｈ＜０ならば、ａ２＝ｍｉｎ(ｔ１，ｔ２) ｂ２＝ｍａｘ(ｔ１，ｔ２) を計算し、ランダムアクセスメモリ４に格納する。

【００２５】次に、△＞０とならば、円，楕円，点楕
円，虚楕円のいずれかであるとしてその結果（それらの
種類を識別する所定のコード）をランダムアクセスメモ
リ４に格納する。次に、ａ／ｃを計算して、ａ／ｃ＞０ならば、点，虚楕円として、その結果（それらの種類を
識別する所定のコード）をランダムアクセスメモリ４に
格納する。

【００２６】ａ／ｃ＞０が成立しなければ、円または楕
円として、その結果（それらの種類を識別する所定のコ
ード）をランダムアクセスメモリ４に格納する。次に、ｒ１＝√(−ｃ／ａ２) ｒ２＝√(−ｃ／ｂ２）ここで、√(ｘ)：ｘのルートを演算する関数。を計算し、ランダムアクセスメモリ４に格納する。

【００２７】ここで、ｒ１−ｒ２＝０ならば円と判定
し、それ以外ならば楕円判定し、その結果（それらの種
類を識別する所定のコード）をランダムアクセスメモリ
４に格納する。上述の処理で円と判定されたならば、半
径ｒｍｉｎ＝ｒ１＝ｒ２となる。また、その中心はＸ０
である。これらのデータを、ランダムアクセスメモリ４
に格納する。

【００２８】また、上述の処理で楕円と判定されたとき
で、ｒ１＞ｒ２ならば、長軸ベクトル：(ｒ１,０,０)を半時計周りにθ回転した
ベクトル短軸ベクトル：(０,ｒ２,０)を半時計周りにθ回転した
ベクトル中心：Ｘ０としてそれらのデータをランダムアクセスメモリ４に格
納する。

【００２９】以上説明した判定条件を満足しない、即
ち、円か楕円以外に分類されたときは、処理を終了す
る。逆に、円か楕円に分類されたときは、ステップＳ７
へ進む。ステップＳ７では、ステップＳ６で分類された
交線が楕円であるかチェックして、楕円であればステッ
プＳ８へ進む。逆に、円であればステップＳ１１へ進
む。

【００３０】ステップＳ８では、長軸または短軸の長さ
が、所定の幾何学的許容長さであるＥＰＳ以下であるか
を判定する。ここでの処理は、ステップＳ６で求めた楕
円の特徴値である長軸，短軸ベクトルからそれらの大き
さ（長さ）を計算して、その長軸または短軸の長さがＥ
ＰＳ以下かどうかを判定する。そして、長軸または短軸
の長さがＥＰＳ以下であれば、ステップＳ１３からのス
テップを行なう。逆に、その長軸または短軸の長さがＥ
ＰＳ以下でなければ、ステップＳ９からの処理を行な
う。

【００３１】ステップＳ９では、長軸と短軸の長さの差
がＥＰＳ以下かどうかを判定する。ここでは、その差が
幾何学的許容長さであるＥＰＳ以下ならば近似的に円と
見なし、ステップＳ１２からの処理を行なう。逆に、そ
の差が幾何学的許容長さＥＰＳ以下でなければ楕円と見
なし、ステップＳ１０からの処理を行なう。ステップＳ
１０では、楕円として交線を出力する。具体的には、ス
テップＳ６で求めた中心座標，長軸ベクトル，短軸ベク
トルを、元の座標空間に逆座標変換し、楕円の法線ベク
トルを元の平面の法線ベクトルと同一にしたものを、楕
円の特徴値として出力して、それらの変換された特徴値
をランダムアクセスメモリ４または、外部記憶装置１０
に格納する。

【００３２】ステップＳ１１では半径がＥＰＳ以下かど
うかを判定する。具体的には、交線が円と判定されたと
きであって、その半径が微小であったり、桁落ち等の数
値的誤差等で、幾何学的許容誤差ＥＰＳ以下であると判
定された時は、ステップＳ１３からの処理を行なう。逆
に、ＥＰＳ以上であると判定された時は、ステップＳ１
２からの処理を行なう。

【００３３】ステップＳ１２では、交線を円として出力
する。具体的には、交線が円であると判定し、ステップ
Ｓ９から本ステップにきた場合、言い換えれば、ステッ
プＳ６の代数的判定で楕円と判定された場合は、長軸と
短軸があるので、ここでは、長軸と短軸の大きさの平均
を円の半径とする。尚、ここでの半径の求め方は、今、
長軸と短軸の大きさの平均としたが、長軸あるいは短軸
のいづれかの長さを円の半径として設定してもよい。

【００３４】そして、所定のｘｙ平面と平行である求め
られた円を元の対象平面上に座標変換するために、逆行
列Ｍ’とこの求められた円の各座標との積をとることに
より座標変換する。このようにして、元の対象の法線ベ
クトルと同一の法線ベクトルを持つ円の中心と半径等の
特徴値をＣＲＴ８に出力する。ステップＳ１３では、交
線が点に縮退したと判定して、この判定状態をメッセー
ジでＣＲＴ８に出力するが、交線に関するデータのＣＲ
Ｔ８への出力は行わず、処理を終了する。

【００３５】以上説明したように、本実施例によれば、
交線の一般式の係数に基づいて代数的形状判別を行い、
その結果を用いて、短軸や長軸や半径などの幾何学的特
徴量での第２次の形状判別を行い、形状を調整すること
により、適正な交線形状を求めることができる。（実施例２）実施例２の図形処理装置のハードウエア構
成は図１と同様であるが、交線算出方法が異なる。

【００３６】以下、図４のフローチャートを参照して、
実施例２での交線算出処理手順を説明する。ただし、図
４のステップＳ６〜ステップＳ１３は実施例１のステッ
プＳ６からステップＳ１３の処理と同様であるので説明
を省略する。また説明で使用する用語等も実施例１と同
様である。

【００３７】まず、ステップＳ１では平面と円筒面との
関係を判定する。具体的には、平面の法線ベクトルと円
筒の軸との関係判定を行ない、交線の種類を推定する。
具体的には、平面の法線ベクトルｎ０と円筒の軸ベクト
ルｎ１間の内積に基づく相関値を以下の式で計算する。ａ＝ｎ０・ｎ１／(|ｎ０|・|ｎ１|) そして、その結果ａをランダムアクセスメモリ４に格納
する。次に、その結果ａの絶対値が次式を満足するか判
定し、１.０−ＥＰＳＡ≦|ａ|≦１.０＋ＥＰＳＡを満足するとき、平面と円筒軸は垂直と判定する。ま
た、 |ａ|≦ＥＰＳＡを満足するとき、平面と円筒軸は平行であると判定す
る。そして、それらの結果をランダムアクセスメモリ４
に格納する。

【００３８】ステップＳ２では、ステップＳ１における
判定結果をランダムアクセスメモリより取り出し、平面
と円が垂直であればステップＳ１４へ進む。逆に、垂直
でなければステップＳ３へ進む。ステップＳ１４では、
円筒軸と平面の交点を算出する。ステップＳ１５では、
円としての交線をＣＲＴ８に出力する。具体的には、ス
テップＳ１４で求めた交点をランダムアクセスメモリ４
より取り出し、その交点を円の中心とし、半径は円筒面
の半径ｒと同じ円を交線として、それらのデータをラン
ダムアクセスメモリ４や外部記憶装置１０に格納する
か、またはＣＲＴ８にその図形を出力する（図２参
照）。そして、処理を終了する。

【００３９】ステップＳ３では、平面と円筒軸が平行か
どうかを判定する。具体的には、ステップＳ１における
判定結果をランダムアクセスメモリ４より取り出し、平
面と円筒軸が平行という結果になっているかどうかチェ
ックし、平面と円筒軸が平行であればステップＳ１６へ
進み、そうでなければステップＳ４へ進む。ステップＳ
１６では、交線は直線であるとして、その直線を求める
計算を行なう。具体的には、交線は、０本から２本の直
線（図２の（ｂ）、（ｃ）、（ｄ）参照）であり、その
計算を行い、その直線のデータをランダムアクセスメモ
リ４または外部記憶装置１０またはＣＲＴ８に出力する
（図２参照）。そして、処理を終了する。

【００４０】ステップＳ４では、平面がｘｙ平面に平行
になるように、平面，円筒面を座標変換する。具体的に
は、平面がｘｙ平面と平行になるように、平面，円筒面
の各特徴値に対して座標変換を行う。ステップＳ５で
は、変換後の平面のＺ座標値（ＸＹ平面に直交する軸を
Ｚ軸として、そのＺ軸方向でのその平面の座標値）Ｚ０
を円筒面の式に代入し、交線の式を算出する。具体的に
は、以下の処理を行う。即ち、ステップＳ４の座標変換
の結果、平面の式が、Ｚ＝Ｚ０になったとする。また平面，円筒面の各特徴値である、
平面上の基準点Ｐ０、円筒面の軸上の基準点Ｃ０、円筒
面の軸ベクトルｎ１がそれぞれ、Ｐ０ --＞Ｐ01 Ｃ０ --＞Ｃ01 ｎ１ --＞ｎ11 になったとする。この時、変換後の円筒面の式は、 (Ｘ−Ｃ01)・(Ｘ−Ｃ０)＝｛(Ｘ−Ｃ01)・ｎ01}²＋ｒ² この式に、Ｘ＝(ｘ,ｙ,Ｚ０）を代入し、展開した式
が、交線の式として求められる。そして、求められた交
線の式のパラメータをランダムアクセスメモリ４に格納
する。

【００４１】次に、実施例１で説明したステップＳ６以
下の処理に進も、交線を楕円か円と判定すればそれをＣ
ＲＴ８等に出力し、点として判定されれば、その主旨を
ＣＲＴ等に表示して処理を終了する。以上説明したよう
に、本実施例によれば、はじめに、平面と円筒面の位置
関係の代数的判定、より具体的には、平面と円筒が直交
しているか平行になっているかを代数的に判定して、そ
れらのいずれかであると判定すると、それぞれ交線が
円、直線と見なし、それらに対して、ステップＳ６以下
の幾何学的処理を行なう必要がなく、より高速に図形処
理を実行できる。このように、上述の代数的処理と幾何
学的処理を巧妙に結びつけることにより、高速にかつ、
適正な交線形状を求めることができる。（実施例３）本実施例では、円筒面の軸と平面が平行と
判定され、交線が直線である場合（図４(ｂ),(ｃ),(ｄ)
参照）での平面と円筒面の交線計算処理方法を説明す
る。

【００４２】尚、以下に示すフローチャートに対応する
プログラムは、ＲＯＭ３に予め格納されており、ＣＰＵ
２がこのプログラムを参照し、解釈して実行する。図５
は、本実施例の平面と円筒面の交線計算処理方法を説明
するフローチャートであり、このフローチャートを参照
して、各ステップ毎にその処理内容を説明する。ここ
で、説明に使用する用語等は実施例１と同様である。

【００４３】ステップＳ１００では、円筒の軸と平面が
平行な場合での円筒面の軸と平面の距離ｒ２を算出し
て、ランダムアクセスメモリ４に格納する。算出方法
は、円筒の軸上の任意の１点と平面の距離を求めればよ
い。ステップＳ１７では、円筒面と平面の最短距離ｄ
(符号付き)、即ち、ｄ＝ｒ２−ｒを求め、その結果をランダムアクセスメモリ４に格納す
る。

【００４４】ステップＳ１８では、ステップＳ１７で求
められた円筒面と平面の最短距離ｄが、次不等式ｄ ≦ ＥＰＳを満足するかどうかを判定する。そして、満足すれば、
ステップＳ２２へ進み、満足しなければステップＳ１９
からの処理を行なう。

【００４５】ステップＳ２２では、円筒面と平面が接し
ていると判定して、ランダムアクセスメモリに４その判
定結果を格納する（図２(ｃ)参照）。ステップＳ２３で
は、接している稜線を交線として算出する。具体的に
は、Ｃ０から平面におろした垂線の足の点をＰ３とする
と、Ｐ３を通り円筒面の軸方向ベクトルを方向ベクトル
とする直線が接している稜線（交線）であるとして、算
出する。そして、その結果をＣＲＴ８に表示して処理を
終了する。

【００４６】ステップＳ１９では、円筒面と平面の最短
距離ｄが次の不等式ｄ＞ＥＰＳを満足するかどうか判定する。そして、満足すれば、ス
テップＳ２４から処理を行ない、満足しなければステッ
プＳ２０からの処理を行なう。

【００４７】ステップＳ２４では、交線を持たないと判
定（図４(ｂ)参照）、即ち、平面と円筒面は離れている
と判定し、その結果をＣＲＴ８に表示して処理を終了す
る。ステップＳ２０では、２本の直線が交線であるとし
てこれらの直線を求め、ランダムアクセスメモリ４に格
納する（図４(ｄ)参照）。具体的には、円筒面の基準点
を中心とし、半径を円筒面の半径ｒとした円の法線が円
筒面の軸方向ベクトルであるその円と、平面との交点、
Ｐ１，Ｐ２を求める。そして、Ｐ１，Ｐ２を通り、円筒
面の軸方向ベクトルを方向ベクトルとする直線を交線と
する。

【００４８】ステップＳ２１では、Ｐ１とＰ２の距離が
ＥＰＳ以内かどうか判定して、ＥＰＳ以内であれば、２
本の交線距離がＥＰＳ以内と判定して、その結果をラン
ダムアクセスメモリ４に格納し、ステップＳ２５へ進
む。逆に、ＥＰＳ以内でなければ、その結果をＣＲＴ８
に表示して処理を終了する。ステップＳ２５では、２本
の交線を一つにまとめる処理を行う。具体的には、２本
の交線は近似的に同一であると判定し、ステップＳ２０
で求めた直線上の点Ｐ１，Ｐ２のいずれかを通り、円筒
面の軸方向ベクトルを方向ベクトルとする直線を求め、
それを唯一の交線としてランダムアクセスメモリ４また
は外部記憶装置１０またはＣＲＴ８に出力する。

【００４９】以上説明したように、本実施例では、円筒
面の軸と平面が平行と判定され、交線が直線である場合
に、円筒面の軸と平面間の距離と所定の閾値との大小関
係によって、図２に示したように、円筒面と平面が離れ
ているか、接しているか（１本の交線を持つ）、２本の
交線を持つかを判定でき、特に、２本の交線を持つと判
定された場合、それらの距離が所定の閾値以内であれ
ば、１本の直線に修正することで、ノイズに強く適正な
交線を求めることができる。（実施例４）本実施例では、図４の交線処理と、図５の
交線が直線である場合の交線処理を組み合わせた処理
（図６、図７参照）を説明する。本実施例での交線処理
でのポイントは、図４のステップＳ１６で交線としての
直線が求められた後、図５のステップＳ１００からの処
理を行って、その交線を調整することで、ノイズに強い
交線処理方法を提供する。

【００５０】尚、図６、図７に示すフローチャートに対
応するプログラムは、ＲＯＭ３に予め格納されており、
ＣＰＵ２がこのプログラムを参照し、解釈して実行す
る。図６、図７は、図４と図５を組み合わせた本実施例
の平面と円筒面の交線計算処理方法を説明するフローチ
ャートである。このフローチャートで、各ステップ番号
は図４と図５のステップ番号と同じものを用いており、
これは、図４と図５の対応するステップでの処理内容が
同じであることを意味する。

【００５１】即ち、図６、図７におけるステップＳ１〜
ステップＳ１５は、図４のステップＳ１〜ステップＳ１
５の処理，また、図６、図７におけるステップＳ１６〜
ステップＳ２５は図５のステップＳ１６〜ステップＳ２
５の処理と同様である。従って、全体のステップで説明
を省略する。以上説明したように、本実施例によれば、
図４の交線処理と、図５の交線が直線である場合の交線
処理を組み合わせて、交線を調整することで、ノイズに
強い交線処理方法を提供する。（他の実施例）以上、平面と円筒の関係においてその交
線計算方法を説明したが、平面と，円筒面，円錐面，球
や，その他の面要素間の交線計算においても適用できる
ことは言うまでもない。

【００５２】尚、本発明は、複数の機器から構成される
システムに適用しても、１つの機器から成る装置に適用
しても良い。また、本発明はシステム或は装置にプログ
ラムを供給することによって達成される場合にも適用で
きることはいうまでもない。以上説明したように、本発
明に係る実施例では、２幾何要素の交線を求める時に、
あらかじめ幾何的に意味のある誤差基準によって、２幾
何要素が接している場合等の特殊ケースの処理を行な
い、また代数的な一般的な手法で求めた交線の解を、幾
何的に意味のある誤差基準を使って補正することによっ
て、実用的な基準で正しく交線の解を安定的に求めるこ
とができ、かつノイズにも強いという効果がある。

【００５３】

【発明の効果】以上説明したように本発明によれば、２
幾何要素のデータにノイズを含む場合であっても、適正
にそれらの２幾何要素間の交線を求めることができる。

【図面の簡単な説明】

【図１】本発明に係る１実施例の図形処理装置のブロッ
ク図である。

【図２】平面と円筒面の位置関係に対応する交線の様子
を説明する図である。

【図３】本発明の第１の実施例の交線処理を示す流れ図
である。

【図４】本発明の第２の実施例の交線処理を示す流れ図
である。

【図５】本発明の第３の実施例の交線処理を示す流れ図
である。

【図６】本発明の第４の実施例の交線処理を示す流れ図
である。

【図７】本発明の第４の実施例の交線処理を示す流れ図
である。

【図８】各実施例での処理を説明するための、用語など
の定義を示す図である。

Claims

【特許請求の範囲】

【請求項１】図形の方程式の係数に基づく所定の判別
式を計算して、前記図形を楕円と判定する第１の判定工
程と、前記第１の判定工程で前記図形を楕円と判定したとき、
前記図形の短軸と長軸の長さの差が所定値以下であれ
ば、前記図形を円と判定する第２の判定工程とを備える
ことを特徴とする図形処理方法。
【請求項２】前記第２の判定工程で前記図形を円と判
定したとき、前記長軸の長さと前記短軸の長さの平均値
を前記円の半径の長さとすることを特徴とする請求項１
に記載の図形処理方法。
【請求項３】前記第２の判定工程で前記図形を円と判
定したとき、前記長軸の長さを前記円の半径の長さとす
ることを特徴とする請求項１に記載の図形処理方法。
【請求項４】前記第２の判定工程で前記図形を円と判
定したとき、前記短軸の長さを前記円の半径とすること
を特徴とする請求項１に記載の図形処理方法。
【請求項５】前記図形の方程式は、ｘ，ｙを変数とす
るａｘ²＋２ｈｘｙ＋ｂｙ²＋２ｇｘ＋２ｆｙ＋ｃ＝０で
表現され、ａ，ｈ，ｂ，ｇ，ｆ，ｃは所定の係数である
ことを特徴とする請求項１に記載の図形処理方法。
【請求項６】前記第１の判定工程は、ａｂ−ｈ²＞０、かつ、ａ／ｃ≦０、かつ、ｔを変数と
する２次方程式ｔ²−(ａ＋ｂ)ｔ＋ａｂ＝０の解t1,t2
に関して、ａ２、ｂ２をｈ＝０ならば、ａ２＝ａ，ｂ２＝ｂｈ＞０ならば、ａ２＝max(t1,t2)，ｂ２＝min(t1,t2) ｈ＜０ならば、ａ２＝min(t1,t2)，ｂ２＝max(t1,t2) と設定し、−ｃ／ａ２のルート演算の結果をｒ１、−ｃ
／ｂ２のルート演算の結果をｒ２とするとき、ｒ１≒ｒ
２ならば、前記図形を楕円と判定することを特徴とする
ことを特徴とする請求項５に記載の図形処理方法。
【請求項７】前記図形の短軸または長軸のいづれか一
方の長さが所定値以下であれば、前記図形を点と判定す
る工程をさらに備えることを特徴とする請求項１に記載
の図形処理方法。
【請求項８】前記第１の判定工程で前記図形を楕円と
判定したとき、前記図形の短軸と長軸の長さの差が所定
値以下でなければ、前記図形を楕円と判定する第３の判
定工程をさらに備えることを特徴とする請求項１に記載
の図形処理方法。
【請求項９】前記第２の判定工程で円と判定された図
形を表示する工程をさらに備えることを特徴とする請求
項１に記載の図形処理方法。
【請求項１０】前記第３の判定工程で楕円と判定され
た図形を表示する工程をさらに備えることを特徴とする
請求項８に記載の図形処理方法。
【請求項１１】前記図形は、所定の平面と所定の円筒
面の交線の図形であることを特徴とする請求項１に記載
の図形処理方法。
【請求項１２】前記図形は、所定の平面と所定の円錐
面の交線の図形であることを特徴とする請求項１に記載
の図形処理方法。
【請求項１３】前記図形は、所定の平面と所定の球面
の交線の図形であることを特徴とする請求項１に記載の
図形処理方法。
【請求項１４】前記第１の判定工程の前に、前記平面
の放線ベクトルと前記円筒面の軸ベクトルとの内積に基
づく相関係数を求め、前記相関係数が所定の範囲値内で
あれば、前記図形を円と判定する第４の判定工程を備
え、前記第４の判定工程で前記図形が円と判定されたなら
ば、前記第１の判定工程以下の処理を行わないことを特
徴とする請求項８に記載の図形処理方法。
【請求項１５】前記第１の判定工程の前に、前記平面
の放線ベクトルと前記円筒面の軸ベクトルとの内積に基
づく相関係数を求め、前記相関係数が所定の閾値以下で
あれば、前記図形を直線と判定する第５の判定工程を備
え、前記第５の判定工程で前記図形が直線と判定されたなら
ば、前記第１の判定工程以下の処理を行わないことを特
徴とする請求項８に記載の図形処理方法。
【請求項１６】前記第５の判定工程で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の範囲値内であれば、前記平面と前記円筒面は接して
いると判定し、接している稜線を交線とする第６の判定
工程を有することを特徴とする請求項１５に記載の図形
処理方法。
【請求項１７】前記第５の判定工程で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の閾値以上であれば、前記平面と前記円筒面は交線を
持たないと判定する第７の判定工程を有することを特徴
とする請求項１５に記載の図形処理方法。
【請求項１８】前記第５の判定工程で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の範囲値内になく、かつ、前記平面と前記円筒面間の
距離が所定の閾値以上でなければ、前記平面と前記円筒
面は２本の直線の交線を有すると判定する第８の判定工
程を有することを特徴とする請求項１５に記載の図形処
理方法。
【請求項１９】前記第８の判定工程で、前記平面と前
記円筒面は２本の直線の交線を有すると判定された場合
で、前記２本の直線間の距離が所定の閾値より小さけれ
ば、前記２本の直線の中心線を唯一の交線とすることを
特徴とする請求項１８に記載の図形処理方法。
【請求項２０】前記第８の判定工程で、前記平面と前
記円筒面は２本の直線の交線を有すると判定された場合
で、前記２本の直線間の距離が所定の閾値より小さけれ
ば、前記２本の直線のいづれか一方の直線を唯一の交線
とすることを特徴とする請求項１８に記載の図形処理方
法。
【請求項２１】図形の方程式の係数に基づく所定の判
別式を計算して、前記図形を楕円と判定する第１の判定
手段と、前記第１の判定手段で前記図形を楕円と判定したとき、
前記図形の短軸と長軸の長さの差が所定値以下であれ
ば、前記図形を円と判定する第２の判定手段とを備える
ことを特徴とする図形処理装置。
【請求項２２】前記第２の判定手段で前記図形を円と
判定したとき、前記長軸の長さと前記短軸の長さの平均
値を前記円の半径の長さとすることを特徴とする請求項
２１に記載の図形処理装置。
【請求項２３】前記第２の判定手段で前記図形を円と
判定したとき、前記長軸の長さを前記円の半径の長さと
することを特徴とする請求項２１に記載の図形処理装
置。
【請求項２４】前記第２の判定手段で前記図形を円と
判定したとき、前記短軸の長さを前記円の半径とするこ
とを特徴とする請求項２１に記載の図形処理装置。
【請求項２５】前記図形の方程式は、ｘ，ｙを変数と
するａｘ²＋２ｈｘｙ＋ｂｙ²＋２ｇｘ＋２ｆｙ＋ｃ＝０
で表現され、ａ，ｈ，ｂ，ｇ，ｆ，ｃは所定の係数であ
ることを特徴とする請求項２１に記載の図形処理装置。
【請求項２６】前記第１の判定手段は、ａｂ−ｈ²＞０、かつ、ａ／ｃ≦０、かつ、ｔを変数と
する２次方程式ｔ²−(ａ＋ｂ)ｔ＋ａｂ＝０の解t1,t2
に関して、ａ２、ｂ２をｈ＝０ならば、ａ２＝ａ，ｂ２＝ｂｈ＞０ならば、ａ２＝max(t1,t2)，ｂ２＝min(t1,t2) ｈ＜０ならば、ａ２＝min(t1,t2)，ｂ２＝max(t1,t2) と設定し、−ｃ／ａ２のルート演算の結果をｒ１、−ｃ
／ｂ２のルート演算の結果をｒ２とするとき、ｒ１≒ｒ
２ならば、前記図形を楕円と判定することを特徴とする
ことを特徴とする請求項２５に記載の図形処理装置。
【請求項２７】前記図形の短軸または長軸のいづれか
一方の長さが所定値以下であれば、前記図形を点と判定
する手段をさらに備えることを特徴とする請求項２１に
記載の図形処理装置。
【請求項２８】前記第１の判定手段で前記図形を楕円
と判定したとき、前記図形の短軸と長軸の長さの差が所
定値以下でなければ、前記図形を楕円と判定する第３の
判定手段をさらに備えることを特徴とする請求項２１に
記載の図形処理装置。
【請求項２９】前記第２の判定手段で円と判定された
図形を表示する手段をさらに備えることを特徴とする請
求項２１に記載の図形処理装置。
【請求項３０】前記第３の判定手段で楕円と判定され
た図形を表示する手段をさらに備えることを特徴とする
請求項２８に記載の図形処理装置。
【請求項３１】前記図形は、所定の平面と所定の円筒
面の交線の図形であることを特徴とする請求項２１に記
載の図形処理装置。
【請求項３２】前記図形は、所定の平面と所定の円錐
面の交線の図形であることを特徴とする請求項２１に記
載の図形処理装置。
【請求項３３】前記図形は、所定の平面と所定の球面
の交線の図形であることを特徴とする請求項２１に記載
の図形処理装置。
【請求項３４】前記第１の判定手段の前に、前記平面
の放線ベクトルと前記円筒面の軸ベクトルとの内積に基
づく相関係数を求め、前記相関係数が所定の範囲値内で
あれば、前記図形を円と判定する第４の判定手段を備
え、前記第４の判定手段で前記図形が円と判定されたなら
ば、前記第１の判定手段以下の処理を行わないことを特
徴とする請求項２８に記載の図形処理装置。
【請求項３５】前記第１の判定手段の前に、前記平面
の放線ベクトルと前記円筒面の軸ベクトルとの内積に基
づく相関係数を求め、前記相関係数が所定の閾値以下で
あれば、前記図形を直線と判定する第５の判定手段を備
え、前記第５の判定手段で前記図形が直線と判定されたなら
ば、前記第１の判定手段以下の処理を行わないことを特
徴とする請求項２８に記載の図形処理装置。
【請求項３６】前記第５の判定手段で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の範囲値内であれば、前記平面と前記円筒面は接して
いると判定し、接している稜線を交線とする第６の判定
手段を有することを特徴とする請求項３５に記載の図形
処理装置。
【請求項３７】前記第５の判定手段で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の閾値以上であれば、前記平面と前記円筒面は交線を
持たないと判定する第７の判定手段を有することを特徴
とする請求項３５に記載の図形処理装置。
【請求項３８】前記第５の判定手段で、前記図形を直
線と判定した場合、前記平面と前記円筒面間の距離が所
定の範囲値内になく、かつ、前記平面と前記円筒面間の
距離が所定の閾値以上でなければ、前記平面と前記円筒
面は２本の直線の交線を有すると判定する第８の判定手
段を有することを特徴とする請求項３５に記載の図形処
理装置。
【請求項３９】前記第８の判定手段で、前記平面と前
記円筒面は２本の直線の交線を有すると判定された場合
で、前記２本の直線間の距離が所定の閾値より小さけれ
ば、前記２本の直線の中心線を唯一の交線とすることを
特徴とする請求項３８に記載の図形処理装置。
【請求項４０】前記第８の判定手段で、前記平面と前
記円筒面は２本の直線の交線を有すると判定された場合
で、前記２本の直線間の距離が所定の閾値より小さけれ
ば、前記２本の直線のいづれか一方の直線を唯一の交線
とすることを特徴とする請求項３８に記載の図形処理装
置。