図面情報の品質評価方法
【課題】クリアランスを考慮した全件自動検査を可能にすること。
【解決手段】(1)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成し、(2)表Ａで「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成し、(3)表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得、(4)図形１と図形２とを入れ換えて上記(1)〜(3)を繰り返し、図形２から見た判定結果を得、(5)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する。
【解決手段】(1)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成し、(2)表Ａで「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成し、(3)表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得、(4)図形１と図形２とを入れ換えて上記(1)〜(3)を繰り返し、図形２から見た判定結果を得、(5)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地理空間情報等図面情報の品質評価方法に関する。
【背景技術】
【０００２】
ＪＳＧＩ（Japanese Standards for Geographic Information（地理情報標準）に基づく、地理空間情報の論理一貫性位相の「ねじれ（交差）」品質評価検査の実施は、クリアランスと呼ばれる許容誤差を認めているが、従来システムでは、完全交差（クリアランスを考慮しない）による全件検査、もしくは目視による検査が実施されており、クリアランスを考慮した全件自動検査は困難であった。なお、先行技術文献として非特許文献１がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】渡邉孝三・岡部篤行・中村秀至（２００８）：ＧＩＳデータの位相検査の交差判定ツールの開発とその適用による有効性の検討．「ＧＩＳ−理論と応用」１６（１）．５９−６８
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記の点にかんがみ、地理空間情報のみに限定されず広く図面情報に適用可能であって、クリアランスを考慮した全件自動検査を可能にする図面情報の品質評価方法を提供することを目的とする。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の図面情報の品質評価方法は、
図形１と図形２とからなる図面情報をコンピュータからなる検査装置に入力し、該検査装置において、品質評価検査を行って検査結果データを出力する図面情報の品質評価方法であって、少なくとも下記工程(a)〜(c)を実行し、
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)前記工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
前記工程(b)及び(c)は、それぞれ、下記工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)前記工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、前記工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)前記工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、前記工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
前記第１条件が成立しない場合、「交差あり」と判定し、
一方、前記第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
前記第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
前記次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、前記次の隣接線分ＮＬＬがある場合、前記次の隣接線分ＮＮＬで前記第１条件が成立するか否かの判定に戻り、
一方、前記第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
前記第３条件が成立しない場合、「交差あり」と判定し、
一方、前記第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
前記第１条件は、「図形Ａが判定円Ｃ内を通過すること」、前記第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、前記第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、前記「図形Ａ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤの始点Ｐｓから、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、前記「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、前記「図形Ｂ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤにおいて、前記図形Ａと前記隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）
ことを特徴とする。
【０００６】
本発明の図面情報の品質評価方法によると、検査装置（コンピュータ）上で「クリアランスを超えた交差」かどうかの判定が正しく行われるようになり、地理空間情報の品質評価を自動で行い、クリアランスを考慮した全件検査が可能となる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態に係る図面情報の品質評価方法を実施するシステムの構成図である。
【図２】品質評価方法の内容を示すフローチャートである。
【図３】交点Ｐの求め方を示す説明図である。
【図４】同じく、交点Ｐの求め方を示す説明図である。
【図５】図形及び線分のクリアランス境界の説明図である。
【図６】クリアランス境界の求め方を示す
【図７】図形と線分のクリアランス境界との交差判定の説明図である。
【図８】線分と円弧の交差判定の説明図である。
【図９】交点がクリアランス境界内にあるかどうかの判定方法の説明図である。
【図１０】図形が円内を通過するかどうかの判定方法の説明図である。
【図１１】線分と円の交差判定の説明図である。
【図１２】円周上の点が円弧上にあるかどうかの判定方法の説明図である。
【図１３】図２図示ステップＳ２の具体的内容を示すフローチャートである。
【図１４】図形１と図形２との交差判定を具体的に説明するための図形図である。
【図１５】図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１６】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１７】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１８】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１９】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図２０】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図２１】図１４図示の図形に対する交差判定方法により得られた表Ａの構成図である。
【図２２】「交差なし」と判定される図形例の構成図である。
【図２３】図形Ａが判定円Ｃ内を通過しない図形例の構成図である。
【図２４】次の隣接線分ＮＮＬで再度条件判定を行うかどうかの判定方法を説明するための図形例の構成図である。
【図２５】同じく、次の隣接線分ＮＮＬで再度条件判定を行うかどうかの判定方法を説明するための図形例の構成図である。
【図２６】隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続するかどうかの判定方法を説明するための図形例の構成図である。
【図２７】変更後の部分図形ＰＤの説明図である。
【図２８】図形と線分のクリアランス境界との交差判定の具体例を示す図である。
【図２９】同じく、図形と線分のクリアランス境界との交差判定の具体例を示す図であり、前半部分の説明図である。
【図３０】図２９に続く後半部分の説明図である。
【図３１】交差判定の結果が「端側と交差」になった場合の説明図である。
【図３２】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３３】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３４】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３５】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３６】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３７】表Ｂの作成方法の説明図である。
【図３８】同じく、表Ｂの作成方法の説明図である。
【図３９】始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４０】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４１】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４２】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４３】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４４】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４５】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４６】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４７】同じく始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４８】図形の具体例による交差判定結果を示す図である。
【図４９】同じく、図形の具体例による交差判定結果を示す図である。
【図５０】同じく、図形の具体例による交差判定結果を示す図である。
【図５１】同じく、図形の具体例による交差判定結果を示す図である。
【図５２】同じく、図形の具体例による交差判定結果を示す図である。
【図５３】同じく、図形の具体例による交差判定結果を示す図である。
【図５４】同じく、図形の具体例による交差判定結果を示す図である。
【図５５】表Ｃの内容から最終的に「クリアランスを超えた交差」かどうかを判定する方法についての説明図である。
【図５６】図形１から見た判定結果と図形２から見た判定結果から最終的に交差判定を行う方法についての説明図である。
【図５７】本実施形態の効果を説明するための説明図である。
【図５８】同じく本実施形態の効果を説明するための説明図である。
【図５９】同じく本実施形態の効果を説明するための説明図である。
【図６０】同じく本実施形態の効果を説明するための説明図である。
【図６１】同じく本実施形態の効果を説明するための説明図である。
【図６２】同じく本実施形態の効果を説明するための説明図である。
【発明を実施するための形態】
【０００８】
図１は、本発明の一実施形態に係る図面情報の品質評価方法を実施するシステムの構成を示し、コンピュータからなる検査装置１は、地理空間情報を入力し、入力した地理空間情報に対して品質評価検査を行って、検査結果データを出力する。
【０００９】
検査装置１は、地理空間情報が図形１と図形２とからなる地理空間情報である場合、品質評価検査を図２に示す手順で行う。なお、以下の説明は、数学座標系を使用している。
【００１０】
図２において、まず、クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める（ステップＳ１）。
【００１１】
次に、「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成する（ステップＳ２）。
【００１２】
次に、ステップＳ２で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成する（ステップＳ３）。
【００１３】
次に、表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る（ステップＳ４）。
【００１４】
次に、図形１と図形２とを入れ換えてステップＳ２〜Ｓ４を繰り返し、図形２から見た判定結果を得る（ステップＳ５）。
【００１５】
最後に、「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する（ステップＳ６）。
【００１６】
以下、ステップＳ１〜Ｓ６の具体的内容を順に説明する。
【００１７】
Ａ． ステップＳ１
ステップＳ１では、クリアランスを考慮せずに、図形１と図形２との交差判定を行い、交点Ｐを求める（図１４参照。図１４に示すＰ１が交点Ｐである。なお、図１４に示すＣＢは、図形２のクリアランス境界である。）。
【００１８】
図３に示すように、図形１がｍ個の線分１−１、１−２、…、１−ｍからなり、また、図形２がｎ個の線分２−１、２−２、…、２−ｎからなる場合、図形１の線分１−１と図形２の各線分２−１、２−２、…、２−ｎとの交差判定、図形１の線分１−２と図形２の各線分２−１、２−２、…、２−ｎとの交差判定、…、図形１の線分１−ｍと図形２の各線分２−１、２−２、…、２−ｎとの交差判定を行い、交点Ｐを求める。
【００１９】
交点Ｐを求めるに当たっては、図４に示すように、図形１の線分Ａの端点を（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、図形２の線分Ｂの端点を（ｘ３，ｙ３）、（ｘ４，ｙ４）とした場合、最初に、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と２点（ｘ３，ｙ３）、（ｘ４，ｙ４）を通る直線との交点（ｘ，ｙ）を求める。そして、求めた交点（ｘ，ｙ）が、線分Ａ上にあり、かつ、線分Ｂ上にあるとき、線分Ａと線分Ｂが交点（ｘ，ｙ）で交差すると判定する。
【００２０】
Ｂ． ステップＳ２
ステップＳ２では、「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成する。
【００２１】
a) 図形１の交点Ｐ１間の部分図形ＰＤ
図形１の交点Ｐ１間の部分図形ＰＤは、基本的には、例えば図１５（Ｂ）に太線で示すように、図形１において始点側の交点Ｐ１（Ｐ1b）と終点側の交点Ｐ１（Ｐ1a）との間の図形であるが、後述するように、交点Ｐ１から前の交点までの図形、及び、交点Ｐ１から次の交点までの図形により構成される。
【００２２】
b) クリアランス境界ＣＢ
クリアランス境界ＣＢとは、図形又は線分からの距離がクリアランス以内となる領域（クリアランス領域）の境界線であり、図形のクリアランス境界ＣＢは、図５（Ａ）に示すように、図形を取り囲む閉ループ線で表され、線分のクリアランス境界ＣＢは、図５（Ｂ）に示すように、線分を取り囲む閉ループ線で表される。
【００２３】
そして、図形のクリアランス境界ＣＢは、図５（Ａ）に示すように、図形の始点から終点に向かう方向を基準として、始点側の端側、左側、右側及び終点側の端側により構成され、また、線分のクリアランス境界ＣＢは、図５（Ｂ）に示すように、線分の始点から終点に向かう方向を基準として、始点側の端側、左側、右側及び終点側の端側により構成される。
【００２４】
線分のクリアランス境界ＣＢを求めるに当たっては、図６に示すように、線分の始点（ｘ１，ｙ１）及び終点（ｘ２，ｙ２）を線分（ｘ１，ｙ１）―（ｘ２，ｙ２）に対して垂直方向へｃｌ（クリアランス）だけ移動した点Ａ（ｘａ，ｙａ）、点Ｂ（ｘｂ，ｙｂ）、点Ｃ（ｘｃ，ｙｃ）、点Ｄ（ｘｄ，ｙｄ）を求め、点Ａと点Ｂとを結んだ線分と、点Ｃと点Ｄとを結んだ線分と、終点（ｘ２，ｙ２）を中心点とし、半径がｃｌで、点Ｂで始まり点Ｃで終わる右回りの円弧と、始点（ｘ１，ｙ１）を中心点とし、半径がｃｌで、点Ｄで始まり点Ａで終わる右回りの円弧とにより構成する。
【００２５】
c) 「図形」と「線分のクリアランス境界」との交差判定
「図形」と「線分のクリアランス境界」との交差判定は、図形を構成する線分とクリアランス境界の構成要素ごとに、全ての組合せで交差判定を行う。例えば、図７に示すように、図形がｍ個の線分１−１、１−２、…、１−ｍで構成され、線分のクリアランス境界が線分２−１、２−２及び円弧２−１、２−２で構成される場合、線分１−１と線分２−１との交差判定、線分１−１と線分２−２との交差判定、線分１−１と円弧２−１との交差判定、線分１−１と円弧２−２との交差判定、線分１−２と線分２−１との交差判定、線分１−２と線分２−２との交差判定、線分１−２と円弧２−１との交差判定、線分１−２と円弧２−２との交差判定、…、線分１−ｍと線分２−１との交差判定、線分１−ｍと線分２−２との交差判定、線分１−ｍと円弧２−１との交差判定、線分１−ｍと円弧２−２との交差判定を行う。
【００２６】
線分と円弧との交差判定は、図８に示すように、線分の端点を（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、円弧の中心点を（ｘｃ，ｙｃ）、半径をｒ、開始角をθ１、終了角をθ２とした場合、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と、中心点（ｘｃ，ｙｃ）、半径ｒの円との交点（ｘ，ｙ）を求める。そして、交点（ｘ，ｙ）が線分上にあり、かつ、円弧上にあれば、線分と円弧が交点（ｘ，ｙ）で交差すると判定する。
【００２７】
円周上の点が円弧上にあるかどうかの判定は、図１２に示すように、円周上の点を（ｘ，ｙ）とし、円弧の中心点を（ｘｃ，ｙｃ）、半径をｒ、開始角をθ１、終了角をθ２とし、点（ｘｃ，ｙｃ）から点（ｘ，ｙ）への方向角θ３を求め、θ３がθ１とθ２との間にあるときに、点が円弧上にあると判定する。
【００２８】
d) ステップＳ２の具体的内容（図１３）
次に、ステップＳ２の具体的内容を図１３に基づいて説明する。
【００２９】
d-1.
まず、図形１の交点Ｐ１から前（始点寄り）の交点（前の交点が無い場合は始点）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点寄り）の交点（次の交点が無い場合は終点）までの部分図形ＰＤａとを設定する（ステップＳ２１）。
【００３０】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）、（Ｂ）に示すように、交点Ｐ１ｂについての部分図形ＰＤｂ及び部分図形ＰＤａは、それぞれ、交点Ｐ１ｂから始点ＰSTまでの太線で表した図形、及び、交点Ｐ１ｂから次の交点Ｐ１ａまでの太線で表した図形となり、また、図１６（Ａ）、（Ｂ）に示すように、交点Ｐ１ａについての部分図形ＰＤｂ及び部分図形ＰＤａは、それぞれ、交点Ｐ１ａから交点Ｐ１ｂまでの太線で表した図形、及び、交点Ｐ１ａから終点ＰENまでの太線で表した図形となる。
【００３１】
d-2.
次に、図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢ（ＣＢｂ）を設定する（ステップＳ２２）。
【００３２】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）、（Ｂ）に示すように、交点Ｐ１ｂのある線分ＢＬについてのクリアランス境界ＣＢｂは、破線で表した図形となり、また、図１６（Ａ）、（Ｂ）に示すように、交点Ｐ１ａのある線分ＢＬについてのクリアランス境界ＣＢｂは、破線で表した図形となる。
【００３３】
d-3.
次に、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行う（ステップＳ２３）。
【００３４】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）に示すように、交点Ｐ１ｂについての部分図形ＰＤｂは、クリアランス境界ＣＢｂの右側と交差すると判定し、図１５（Ｂ）に示すように、交点Ｐ１ｂについての部分図形ＰＤａは、クリアランス境界ＣＢｂの左側と交差すると判定し、また、図１６（Ａ）に示すように、交点Ｐ１ａについての部分図形ＰＤｂは、クリアランス境界ＣＢｂの左側と交差すると判定し、図１６（Ｂ）に示すように、交点Ｐ１ａについての部分図形ＰＤａは、クリアランス境界ＣＢｂの右側と交差すると判定する。
【００３５】
d-4.
次に、「交差あり」か否かを判定する（ステップＳ２４）。
【００３６】
d-4-a.
「交差なし」の場合、「交差なし」と判定する（ステップＳ２５）。
【００３７】
例えば図２２に示す図形１及び図形２の場合、部分図形ＰＤは線分ＢＬのクリアランス境界ＣＢｂ内にあるため、ステップＳ２４の判定結果は「ＮＯ」となり、「交差なし」と判定され（ステップＳ２５）、表Ａが作成される。
【００３８】
d-4-b.
一方、「交差あり」の場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を継続するか否かを判定する（ステップＳ２６）。
【００３９】
例えば図１４に示す図形１及び図形２の場合、上述したように、交点Ｐ１ｂについての部分図形ＰＤｂ及び部分図形ＰＤａのいずれも「交差あり」となり、また、交点Ｐ１ａについての部分図形ＰＤｂ及び部分図形ＰＤａのいずれも「交差あり」となるため、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続するか否かを判定することになる。
【００４０】
この隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する条件として３つの条件（第１条件、第２条件、第３条件）がある。第１条件は、「図形Ａが判定円Ｃ内を通過すること（ステップＳ２６ａ）」である。第２条件は、「最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること（ステップＳ２６ｂ）」である。第３条件は、「図形Ｂが判定円Ｃ内を通過すること（ステップＳ２６ｃ）」である。第１条件の判定ステップＳ２６ａの判定結果、第２条件の判定ステップＳ２６ｂの判定結果及び第３条件の判定ステップＳ２６ｃの判定結果が全て「ＹＥＳ」の場合のみ、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する。第１条件の判定ステップＳ２６ａの判定結果は「ＹＥＳ」であっても第２条件の判定ステップＳ２６ｂの判定結果が「ＮＯ」である場合、次の隣接線分ＮＮＬがあるか否かを判定し（ステップＳ２６ｄ）、ステップＳ２６ｄの判定結果が「ＹＥＳ」の場合、ステップＳ２６ａへ移行し、次の隣接線分ＮＮＬで再度条件判定を行う。
【００４１】
点（ｘ，ｙ）がクリアランス境界内にあるかどうかの判定は、図９に示すように、点（ｘ，ｙ）から２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線へ下ろした垂線の足（ｘｆ，ｙｆ）を求めた上で、点（ｘ，ｙ）から線分までの距離ｄを求める。そして、ｄ≦ｃｌのとき、点（ｘ，ｙ）がクリアランス境界内にあると判定する。
【００４２】
図形が円内を通過するかどうかの判定は、図形を構成する線分ごとに円との交差判定を行い、円と交差する線分が存在したら円内を通過すると判定する。例えば、図１０に示すように、図形がｍ個の線分で構成されている場合、線分１と円の交差判定、線分２と円の交差判定、…、線分ｍと円の交差判定を行う。
【００４３】
線分と円の交差判定は、図１１に示すように、線分の端点をそれぞれ（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、円の中心点を（ｘｃ，ｙｃ）、半径をｒとし、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と円との交点（ｘａ，ｙａ）、（ｘｂ，ｙｂ）を求める。そして、交点（ｘａ，ｙａ）、（ｘｂ，ｙｂ）のどちらか一方でも線分上にあれば、線分と円とが交差すると判定する。
【００４４】
（第１条件）
第１条件は、上記のように、「図形Ａが判定円Ｃ内を通過すること」である。
【００４５】
・図形Ａ
図形Ａとは、部分図形ＰＤの始点Ｐｓから、部分図形ＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいう。
【００４６】
例えば図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての部分図形ＰＤｂ及び線分ＢＬのクリアランス境界ＣＢｂは図１７（Ａ）に示すようになるため、部分図形ＰＤｂにおける図形Ａは図１７（Ｂ）に示すようになる。また、交点Ｐ１ｂについての部分図形ＰＤａ及び線分ＢＬのクリアランス境界ＣＢｂは図１８（Ａ）に示すようになるため、部分図形ＰＤａにおける図形Ａは図１８（Ｂ）に示すようになる。また、交点Ｐ１ａについての部分図形ＰＤｂ及び線分ＢＬのクリアランス境界ＣＢｂは図１９（Ａ）に示すようになるため、部分図形ＰＤｂにおける図形Ａは図１９（Ｂ）に示すようになる。また、交点Ｐ１ａについての部分図形ＰＤａ及び線分ＢＬのクリアランス境界ＣＢｂは図２０（Ａ）に示すようになるため、部分図形ＰＤａにおける図形Ａは図２０（Ｂ）に示すようになる。
【００４７】
・判定円Ｃ
判定円Ｃとは、線分（現在の線分）ＢＬに隣接する隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいう。
【００４８】
例えば図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての現在の線分ＢＬ、隣接線分ＮＬ及び隣接線分ＮＬのクリアランス境界ＣＢｎは図１７及び図１８に示すようになるため、判定円Ｃは図１７及び図１８に示すようになる。また、交点Ｐ１ａについての現在の線分ＢＬ、隣接線分ＮＬ及び隣接線分ＮＬのクリアランス境界ＣＢｎは図１９及び図２０に示すようになるため、判定円Ｃは図１９及び図２０に示すようになる。
【００４９】
・第１条件の判定結果（第１条件が成立しない場合）
図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての図形Ａ、及び、交点Ｐ１ａについての図形Ａは、図１７（Ｂ）、図１８（Ｂ）、図１９（Ｂ）及び図２０（Ｂ）に示すように、いずれも判定円Ｃを通過していないため、第１条件は成立しないことになり、判定ステップＳ２６ａの判定結果は「ＮＯ」となり、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続せず、「交差あり」と判定し（ステップＳ２７）、表Ａを作成することになる。
【００５０】
したがって、図１４に示す図形１及び図形２の場合、ステップＳ２において表Ａが作成されることになり、表Ａは、図２１に示す内容となる。図２１において、表Ａの第１行目には、「図形１の交点Ｐ１ｂから始点ＰSTまでの部分図形ＰＤｂ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第２行目には、図形１の交点Ｐ１ｂが書き込まれ、表Ａの第３行目には、「図形１の交点Ｐ１ｂから次の交点Ｐ１ａまでの部分図形ＰＤａ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第４行目には、「図形１の交点Ｐ１ａから前の交点Ｐ１ｂまでの部分図形ＰＤｂ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第５行目には、図形１の交点Ｐ１ａが書き込まれ、表Ａの第６行目には、「図形１の交点Ｐ１ａから終点ＰENまでの部分図形ＰＤａ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、この結果、表Ａの第１行目、第３行目には、それぞれ、「右側と交差」、「左側と交差」が書き込まれ、第４行目、第６行目には、それぞれ、「左側と交差」、「右側と交差」が書き込まれる。
【００５１】
また、図２３に示す図形１及び図形２の場合、図形Ａが判定円Ｃ内を通過しないため、表Ａに、「交差あり（左側と交差）」と書き込まれる。
【００５２】
・第１条件の判定結果（第１条件が成立する場合）
図形１及び図形２が図２４に示す場合、図形１の部分図形ＰＤにおける図形Ａは判定円Ｃ内を通過することになるため、ステップＳ２６ａの判定結果は「ＹＥＳ」となり、次に、第２条件が成立するか否かが判定される（ステップＳ２６ｂ）。
【００５３】
（第２条件）
第２条件は、上記のように、「最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」である。
【００５４】
・第２条件の判定結果（第２条件が成立しない場合）
図２４に示す図形１及び図形２の場合、最初の交点Ｐｆは、隣接線分ＮＬのクリアランス境界ＣＢｎの外にあるため、第２条件は成立しないことになる。
【００５５】
第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否か判定する（ステップＳ２６ｄ）。
【００５６】
・次の隣接線分ＮＮＬがない場合
次の隣接線分ＮＮＬがない場合、「交差あり」と判定し（ステップＳ２７）、表Ａを作成する。図２４の例の場合、隣接線分ＮＮＬがないことから、「交差あり（左側と交差）」と判定し（ステップＳ２７）、表Ａを作成することになる。
【００５７】
・次の隣接線分ＮＮＬがある場合
次の隣接線分ＮＮＬがある場合、ステップＳ２６ａへ移行し、図形Ａが判定円Ｃ（このときの判定円Ｃは、次の隣接線分ＮＮＬの、隣接線分ＮＬ寄りの端点Ｐｓｔ、を中心とする円Ｃｎとなる。）を通過するか否かを判定する。
【００５８】
図２５に示す図形１及び図形２の場合、次の隣接線分ＮＮＬがあることから、図形Ａが判定円Ｃｎ内を通過かするか否か判定され（ステップＳ２６ａ）、この判定結果は「ＮＯ」となり、「交差あり（左側と交差）」と判定され（ステップＳ２７）、表Ａが作成されることになる。
【００５９】
・第２条件の判定結果（第２条件が成立する場合）
図２６に示す図形１及び図形２の場合、最初の交点Ｐｆは、隣接線分ＮＬのクリアランス境界ＣＢｎ内にあることから、ステップＳ２６ｂの判定結果は「ＹＥＳ」となり、次に、第３条件が成立するか否かが判定される（ステップＳ２６ｃ）。
【００６０】
（第３条件）
第３条件は、上記のように、「図形Ｂが判定円Ｃ内を通過すること」である。
【００６１】
・図形Ｂ
図形Ｂとは、部分図形ＰＤにおいて、図形Ａと隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう。但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。
【００６２】
例えば図２６（Ａ）に示す図形１及び図形２の場合、最初の交点Ｐｆ及び最後の交点Ｐｌは図２６（Ａ）に示すようになるため、図形Ｂは、図２６（Ｂ）に示すようになる。
【００６３】
・第３条件の判定結果（第３条件が成立しない場合）
例えば図２８に示す図形１及び図形２の場合、図２８（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過しないため、ステップＳ２６ｃの判定結果は「ＮＯ」となり、「交差あり（左側と交差）」と判定し（ステップＳ２７）、表Ａを作成する。
【００６４】
・第３条件の判定結果（第３条件が成立する場合）
例えば図２６に示す図形１及び図形２の場合、図２６（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過するため、ステップＳ２６ｃの判定結果は「ＹＥＳ」となり、次に、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する（ステップＳ２８）。
【００６５】
＜隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定＞
隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定においては、図形Ａが隣接線分ＮＬのクリアランス境界ＣＢｎ内にある場合を除き、部分図形ＰＤの変更を行う。変更後の部分図形ＰＤの始点は、変更前の部分図形ＰＤの始点Ｐｓから最初の交点Ｐｆまでの部分と、隣接線分ＮＬのクリアランス境界ＣＢｎと、の最後の交点Ｐｌになる。
【００６６】
例えば図２６（Ａ）に示す図形１及び図形２の場合、図２７（Ａ）に示すように、変更前の部分図形ＰＤにおいて、部分図形ＰＤの始点Ｐｓから最初の交点Ｐｆまでの部分は図２７（Ａ）において太線で示すものとなり、変更後の部分図形ＰＤは、図２７（Ｂ）において太線で示す図形となる。図２７（Ｂ）に示す部分図形ＰＤの場合、現在の線分ＢＬ（元の隣接線分ＮＬ）のクリアランス境界ＣＢｂ（元のクリアランス境界ＣＢｎ）内にあるため、表Ａに「交差なし」と書き込まれる。
【００６７】
ｅ) 「部分図形」と「線分のクリアランス境界」との交差判定の具体例
・図２８に示す図形１及び図形２の場合、図２８（Ａ）に示すように、部分図形ＰＤが線分ＢＬのクリアランス境界ＣＢｂと交差しており、図形Ａが判定円Ｃ内を通過しており、最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあり、図２８（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過しないため、表Ａに「交差あり（左側と交差）」と書き込まれる。
【００６８】
・図２９に示す図形１及び図形２の場合、図２９に示すように、部分図形ＰＤが線分ＢＬのクリアランス境界ＣＢｂと交差しており、図形Ａが判定円Ｃ内を通過しており、最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にないため、次の隣接線分ＮＮＬを使用して再度条件判定が行われ、再度の条件判定において、図３０（Ａ）に示すように、図形Ａが次の隣接線分ＮＮＬの判定円Ｃｎ内を通過しており、最初の交点Ｐｆが次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあり、図３０（Ｂ）に示すように、図形Ｂが判定円Ｃｎ内を通過するため、次の隣接線分ＮＮＬを使用して交差判定を継続する。次の隣接線分ＮＮＬを使用した交差判定においては、更新後の部分図形ＰＤとして、更新前の部分図形ＰＤのうち最後の交点Ｐｌを始点とする図形が使用され、この更新後の部分図形ＰＤは次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあるため、表Ａに「交差なし」と書き込まれる。
【００６９】
f) 交差判定の結果が「端側と交差」になった場合
図３１に示すように、図形２の最初の線分のクリアランス境界の始点側の端側、又は、最後の線分のクリアランス境界の終点側の端側と交差しているときには、その端側は、図形のクリアランス境界の端側と一致するので、図形のクリアランス境界の端側と交差していることになり、交差判定の結果は、「端側と交差」になる。
【００７０】
図３２に示すように、図形２の線分のクリアランス境界の上記以外の端側と交差しているときには、その端側は、図形のクリアランス境界の左側又は右側の一部分であり、図形のクリアランス境界の左側又は右側と交差していることになるので、どちら側と交差しているかの判定を行う。点が直線に対してどちら側にあるかの判定は、図３５に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線のどちら側にあるか判定する。この判定にあたっては、座標法により、三角形（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）の面積Ｓを計算する（２Ｓ＝（ｙ２−ｙ１）（ｘ３−ｘ１）−（ｘ２−ｘ１）（ｙ３−ｙ１））。座標法では、面積の符号が、図３６（Ａ）に示すように、三角形が右回りのときには正になり、図３６（Ｂ）に示すように、三角形が左回りのときは負になるので、面積が正のときは、「点は直線の右側にある」と判定し、面積が負のときは、「点は直線の左側にある」と判定する。
【００７１】
図３３に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線の（進行方向に対して）左側にあるときには、線分のクリアランス境界の端側と交差して外に出たならば、図形のクリアランス境界の右側と交差して外に出たことになるので、交差判定の結果は、「右側と交差」になる。
【００７２】
図３４に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線の（進行方向に対して）右側にあるときには、線分のクリアランス境界の端側と交差して外に出たならば、図形のクリアランス境界の左側と交差して外に出たことになるので、交差判定の結果は、「左側と交差」になる。
【００７３】
Ｃ． ステップＳ３
ステップＳ３では、ステップＳ２で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成する。
【００７４】
a) 拡張部分図形ＥＰＤ
例えば図３７（Ａ）に示す図形１及び図形２の場合、表Ａは、図３７（Ｂ）に示すようになり、第３行目及び第４行目の判定結果は「交差なし」となる。
【００７５】
このような場合、表Ｂを作成する。表Ｂを作成するに当たっては、拡張部分図形ＥＰＤが使用され、上述した表Ａを作成する手順と同様な手順により、拡張部分図形ＥＰＤとクリアランス境界ＣＢとの交差判定を行い、表Ｂを作成する。
【００７６】
図３７（Ａ）に示す図形１及び図形２の場合、図３８（Ａ）に示すように、交点Ｐ１ｂについての拡張部分図形ＥＰＤａは、交点Ｐ１ｂから終点ＰENまでの部分図形となり、交点Ｐ１ａについての拡張部分図形ＥＰＤｂは、交点Ｐ１ａから始点ＰSTまでの部分図形となり、判定結果である表Ｂは、図３８（Ｃ）に示すようになる。
【００７７】
＜具体例（図３９〜図４７）＞
図３９に示す図形１及び図形２の場合、部分図形ＰＤと現在の線分ＢＬのクリアランス境界ＣＢｂとの交差判定の結果は、図３９に示すように、「左側と交差」になる。
【００７８】
このため、まず、始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓとの交差判定を継続するか否かを判定することになる。
【００７９】
図４０に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓ内にあり、また、図形Ａとクリアランス境界ＣＢｎｓとの交点がないため、図形Ｂは図形Ａと同じになり、図形Ｂは判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００８０】
このため、隣接線分ＮＬｓのクリアランス境界ＣＢｎｓを使用した交差判定を継続することになる。
【００８１】
この隣接線分ＮＬｓのクリアランス境界ＣＢｎｓを使用した交差判定においては、図形Ａがクリアランス境界ＣＢｎｓ内にあるため、部分図形ＰＤの変更は行わず、図４１に示すように、上述したクリアランス境界ＣＢｂとの交差判定に使用された部分図形ＰＤと同じ部分図形が使用される。
【００８２】
この交差判定の結果は、図４１に示すように、「（始点側の）端側と交差」になる。
【００８３】
このため、次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎとの交差判定を継続するか否かを判定することになる。
【００８４】
図４２に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあり、また、図形Ｂは、図４３に示すように、判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００８５】
このため、次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎを使用した交差判定を継続することになる。
【００８６】
この次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎを使用した交差判定においては、部分図形ＰＤが変更され、図４４に示す部分図形ＰＤが使用される。
【００８７】
この交差判定の結果は、図４４に示すように、「左側と交差」になる。そして、次の次の隣接線分がないため、始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓとの交差判定の結果は、「左側と交差」ということになる。
【００８８】
次に、終点方向の隣接線分ＮＬｅのクリアランス境界ＣＢｎｅとの交差判定を継続するか否かを判定することになる。
【００８９】
図４５に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは終点方向の隣接線分ＮＬｅのクリアランス境界ＣＢｎｅ内にあり、また、図形Ａとクリアランス境界ＣＢｎｅとの交点がないため、図形Ｂは図形Ａと同じになり、図形Ｂは判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００９０】
このため、隣接線分ＮＬｅのクリアランス境界ＣＢｎｅを使用した交差判定を継続することになる。
【００９１】
この隣接線分ＮＬｅのクリアランス境界ＣＢｎｅを使用した交差判定においては、図形Ａがクリアランス境界ＣＢｎｅ内にあるため、部分図形ＰＤの変更は行わず、図４６に示すように、上述したクリアランス境界ＣＢｂとの交差判定に使用された部分図形ＰＤと同じ部分図形が使用される。
【００９２】
この交差判定の結果は、図４６に示すように、「交差なし」になる。
【００９３】
したがって、始点方向の隣接線分ＮＬｓ側の交差判定の結果は「左側と交差」になり、終点方向の隣接線分ＮＬｅ側の交差判定の結果は「交差なし」になる。
【００９４】
このように始点方向と終点方向とで交差判定の結果が一致せず、いずれか一方の判定結果に「交差なし」がある場合、交差判定の結果は「交差なし」とされ、表Ａに「交差なし」を書き込む。
【００９５】
次に、拡張部分図形ＥＰＤを使用して、上述した部分図形ＰＤを使用した交差判定と同様に交差判定を行う。
【００９６】
この交差判定においては、始点方向の判定結果は、部分図形ＰＤを使用した交差判定と同じく「左側と交差」になり、一方、終点方向の判定結果は、図４７に示すように、「右側と交差」になる。
【００９７】
このような場合、交差判定の結果は「両側と交差」とし、表Ｂに「両側と交差」を書き込む。
【００９８】
なお、図示しないが、図形１がループ状の図形の場合、始点が存在しないので、一周して元の交点までの部分図形を拡張部分図形ＥＰＤとして使用する。
【００９９】
Ｄ． ステップＳ４
ステップＳ４では、表Ａと表Ｂから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうか判定し、図形１から見た判定結果を得る。
【０１００】
（具体例その１（図４８））
図４８（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図４８（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果となっているのに対し、表Ｂでは「右側と交差」、「（始点）の端側と交差」となっている。
【０１０１】
このような場合、表Ａにおいて交点ＰAの次の行の判定結果が「交差なし」のときに、表Ｂにおける同じ行の判定結果及び次の交点ＰBの次の行の判定結果が「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）のときには、変更条件が成立しているとし、表Ｃの判定結果を「交差なし」とする。
【０１０２】
同様に、表Ａにおいて交点ＰBの前の行の判定結果が「交差なし」のときに、表Ｂにおける同じ行の判定結果及び前の交点ＰAの前の行の判定結果が「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）のときには、表Ｃの判定結果を「交差なし」とする。
【０１０３】
（具体例その２（図４９））
図４９（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図４９（Ｂ）に示すようになる。すなわち、表Ａの第３行目、第４行目、第６行目及び第７行目では「交差なし」の判定結果となっているのに対し、表Ｂでは「左側と交差」、「右側と交差」、「左側と交差」、「右側と交差」となっている。
【０１０４】
したがって、上記変更条件が成立しているため、表Ｃにおいては、上記各行に「交差なし」が書き込まれる。
【０１０５】
（具体例その３（図５０））
図５０（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５０（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果になっているのに対し、表Ｂでは「左側と交差」、「左側と交差」となっている。
【０１０６】
したがって、上記変更条件が成立していない。このような場合、表Ｃには、表Ｂと同じ内容が書き込まれる。
【０１０７】
（具体例その４（図５１））
図５１（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５１（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果になっているのに対し、表Ｂでは「両側と交差」、「右側と交差」となっている。
【０１０８】
このように、「両側と交差」と「右側（左側）と交差」の組合せのときは、「同じ側で交差」とみなす。
【０１０９】
このため、上記変更条件が成立することなり、表Ｃには、「交差なし」が書き込まれる。
【０１１０】
（具体例その５（図５２））
図５２（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５２（Ｂ）に示すようになる。表Ｂにおいて、第３行目及び第４行目の判定結果は、それぞれ「交差なし」及び「左側と交差」となっている。このように、表Ｂにおいて、交点ＰA、ＰBに挟まれた２つの判定結果のどちらか一方でも「交差なし」となっている場合、表Ｃの判定結果は「交差なし」に変更する。
【０１１１】
（具体例その６（図５３））
図５３（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５３（Ｂ）に示すようになる。交点ＰA、ＰBに挟まれた２つの行で、表Ａの判定結果が片方だけ「交差なし」で、表Ｂの判定結果が「左側と交差」と「右側と交差」の組合せになっている場合、表Ｃでは、共に「交差なし」に変更する。
【０１１２】
（具体例その７（図５４））
図５４（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５４（Ｂ）に示すようになる。
【０１１３】
表Ｃには、図５５（Ａ）に示すように、各交点ＰA、ＰBごとに最終的な判定結果が書き込まれる。
【０１１４】
表Ｃの中で、図５５（Ｂ）に示すように、交点Ｐの上下の行の判定結果が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、また、図５５（Ｃ）に示すように、それ以外の組合せのときは「交差なし」と判定する。
【０１１５】
表Ｃにおいて、交点ＰAと交点ＰBとで挟まれた２つの行には、「交差なし」が書き込まれる。「クリアランスを超えて交差した」かどうかの判定時には、表Ｃ中の「交差なし」は無視して考えるため、表Ｃ中の「交差なし」を削除すると、図５４（Ｃ）に示すようになる。
【０１１６】
Ｅ． ステップＳ５
ステップＳ５では、図形１と図形２を入れ換えてステップＳ２〜Ｓ４を繰り返し、図形２から見た判定結果を得る。
【０１１７】
Ｆ． ステップＳ６
ステップＳ６では、「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する。
【０１１８】
図５６（Ａ）、（Ｃ）に示す図形１及び図形２の場合、図形１から見た判定結果は図５６（Ｂ）に示すようになり、「クリアランスを超えた交差」と判定されるが、図形２から見た判定結果は図５６（Ｄ）に示すようになり、「交差なし」と判定される。このため、最終的に「交差なし」と判定される。
【０１１９】
以上説明したように、本実施形態に係る図面情報の品質評価方法は、
図形１と図形２とからなる地理空間情報（図面情報）をコンピュータからなる検査装置１に入力し、検査装置１において、品質評価検査を行って検査結果データを出力する地理空間情報（図面情報）の品質評価方法であって、工程(a)〜(c)
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
を実行し、
工程(b)及び(c)は、それぞれ、工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
第１条件が成立しない場合、「交差あり」と判定し、
一方、第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、次の隣接線分ＮＬＬがある場合、次の隣接線分ＮＮＬで第１条件が成立するか否かの判定に戻り、
一方、第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
第３条件が成立しない場合、「交差あり」と判定し、
一方、第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
第１条件は、「図形Ａが判定円Ｃ内を通過すること」、第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、「図形Ａ」とは、部分図形ＰＤ又は拡張部分図形ＥＰＤの始点Ｐｓから、部分図形ＰＤ又は拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、「図形Ｂ」とは、部分図形ＰＤ又は拡張部分図形ＥＰＤにおいて、図形Ａと隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）。
【０１２０】
そして、工程(b)の交差判定により表Ａが作成され、工程(c)の交差判定により表Ｂが作成され、
表Ａ及び表Ｂには、それぞれ、各交点Ｐ１が書き込まれ、各交点Ｐ１の上の行に、交点Ｐ１についての部分図形ＰＤｂ又は拡張部分図形ＥＰＤｂとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれ、各交点Ｐ１の下の行に、交点Ｐ１についての部分図形ＰＤａ又は拡張部分図形ＥＰＤａとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれる。
【０１２１】
そして、工程(a)〜(c)の実行後、工程(d)〜(f)
(d)表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る
(e)図形１と図形２とを入れ換えて工程(b)〜(d)を繰り返し、図形２から見た判定結果を得る
(f)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する
を実行する。
【０１２２】
本実施形態によると、下記の効果が奏される。
【０１２３】
本実施形態のように線分のクリアランス境界を使用して表Ａ及び表Ｂを作成する代わりに、図５７（Ａ）に示すように、図形のクリアランス境界を使用して表Ａ及び表Ｂを作成する場合、表Ａ及び表Ｂは図５７（Ｂ）に示すようになり、最終的に「交差なし」と判定されるが、図５８（Ａ）に示すように、線分のクリアランス境界を使用して表Ａ及び表Ｂを作成する場合、表Ａ及び表Ｂは図５８（Ｂ）に示すようになり、最終的に交点ＰAとＰBでそれぞれ「クリアランスを超えて交差する」と正しく判定されるようになる。
【０１２４】
また、図５９（Ａ）に示す図形の場合、表Ａは図５９（Ｂ）に示すようになり、一方、図６０（Ａ）に示す図形の場合、表Ａは図６０（Ｂ）に示すようになり、表Ａは互いに一致した内容となる。しかし、図５９（Ｂ）と図６０（Ｂ）の表Ｂの内容は一致していないため、表Ｂの内容を参照することにより正しい判定を行うことができるようになる。
【０１２５】
また、図６１（Ａ）に示す図形の場合、表Ｂは図６１（Ｂ）に示すようになり、一方、図６２（Ａ）に示す図形の場合、表Ｂは図６２（Ｂ）に示すようになり、表Ｂは互いに一致した内容となる。しかし、図６１（Ｂ）と図６２（Ｂ）の表Ａの内容は一致していないため、表Ａの内容を参照することにより正しい判定を行うことができるようになる。
【０１２６】
また、本実施形態では、工程(d)において、
1) 表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
2) 表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、また、
表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、
3) 表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行のどちらか一方でも「交差なし」となっている場合、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
4) 表Ａにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行の片方だけ「交差なし」であり、かつ、表Ｂにおいて、前記交点Ｐ１の下の行と前記次の交点Ｐ１の上の行が「左側と交差」と「右側と交差」の組合せになっている場合、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
5) 表Ｃにおいて、交点Ｐの上下の行が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、それ以外の組合せのときは「交差なし」と判定する
ようにしたため、複雑な図形や複雑に交差している場合でも、正しく判定することが可能になる。
【０１２７】
したがって、本実施形態によると、検査装置（コンピュータ）上で「クリアランスを超えた交差」かどうかの判定が正しく行われるようになり、地理空間情報（図面情報）の品質評価を自動で行い、クリアランスを考慮した全件検査が可能となる。
【符号の説明】
【０１２８】
１ 検査装置（コンピュータ）
【技術分野】
【０００１】
本発明は、地理空間情報等図面情報の品質評価方法に関する。
【背景技術】
【０００２】
ＪＳＧＩ（Japanese Standards for Geographic Information（地理情報標準）に基づく、地理空間情報の論理一貫性位相の「ねじれ（交差）」品質評価検査の実施は、クリアランスと呼ばれる許容誤差を認めているが、従来システムでは、完全交差（クリアランスを考慮しない）による全件検査、もしくは目視による検査が実施されており、クリアランスを考慮した全件自動検査は困難であった。なお、先行技術文献として非特許文献１がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】渡邉孝三・岡部篤行・中村秀至（２００８）：ＧＩＳデータの位相検査の交差判定ツールの開発とその適用による有効性の検討．「ＧＩＳ−理論と応用」１６（１）．５９−６８
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記の点にかんがみ、地理空間情報のみに限定されず広く図面情報に適用可能であって、クリアランスを考慮した全件自動検査を可能にする図面情報の品質評価方法を提供することを目的とする。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の図面情報の品質評価方法は、
図形１と図形２とからなる図面情報をコンピュータからなる検査装置に入力し、該検査装置において、品質評価検査を行って検査結果データを出力する図面情報の品質評価方法であって、少なくとも下記工程(a)〜(c)を実行し、
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)前記工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
前記工程(b)及び(c)は、それぞれ、下記工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)前記工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、前記工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)前記工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、前記工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
前記第１条件が成立しない場合、「交差あり」と判定し、
一方、前記第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
前記第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
前記次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、前記次の隣接線分ＮＬＬがある場合、前記次の隣接線分ＮＮＬで前記第１条件が成立するか否かの判定に戻り、
一方、前記第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
前記第３条件が成立しない場合、「交差あり」と判定し、
一方、前記第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
前記第１条件は、「図形Ａが判定円Ｃ内を通過すること」、前記第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、前記第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、前記「図形Ａ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤの始点Ｐｓから、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、前記「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、前記「図形Ｂ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤにおいて、前記図形Ａと前記隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）
ことを特徴とする。
【０００６】
本発明の図面情報の品質評価方法によると、検査装置（コンピュータ）上で「クリアランスを超えた交差」かどうかの判定が正しく行われるようになり、地理空間情報の品質評価を自動で行い、クリアランスを考慮した全件検査が可能となる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態に係る図面情報の品質評価方法を実施するシステムの構成図である。
【図２】品質評価方法の内容を示すフローチャートである。
【図３】交点Ｐの求め方を示す説明図である。
【図４】同じく、交点Ｐの求め方を示す説明図である。
【図５】図形及び線分のクリアランス境界の説明図である。
【図６】クリアランス境界の求め方を示す
【図７】図形と線分のクリアランス境界との交差判定の説明図である。
【図８】線分と円弧の交差判定の説明図である。
【図９】交点がクリアランス境界内にあるかどうかの判定方法の説明図である。
【図１０】図形が円内を通過するかどうかの判定方法の説明図である。
【図１１】線分と円の交差判定の説明図である。
【図１２】円周上の点が円弧上にあるかどうかの判定方法の説明図である。
【図１３】図２図示ステップＳ２の具体的内容を示すフローチャートである。
【図１４】図形１と図形２との交差判定を具体的に説明するための図形図である。
【図１５】図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１６】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１７】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１８】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図１９】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図２０】同じく、図１４図示の図形に対する交差判定方法を説明するための説明図である。
【図２１】図１４図示の図形に対する交差判定方法により得られた表Ａの構成図である。
【図２２】「交差なし」と判定される図形例の構成図である。
【図２３】図形Ａが判定円Ｃ内を通過しない図形例の構成図である。
【図２４】次の隣接線分ＮＮＬで再度条件判定を行うかどうかの判定方法を説明するための図形例の構成図である。
【図２５】同じく、次の隣接線分ＮＮＬで再度条件判定を行うかどうかの判定方法を説明するための図形例の構成図である。
【図２６】隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続するかどうかの判定方法を説明するための図形例の構成図である。
【図２７】変更後の部分図形ＰＤの説明図である。
【図２８】図形と線分のクリアランス境界との交差判定の具体例を示す図である。
【図２９】同じく、図形と線分のクリアランス境界との交差判定の具体例を示す図であり、前半部分の説明図である。
【図３０】図２９に続く後半部分の説明図である。
【図３１】交差判定の結果が「端側と交差」になった場合の説明図である。
【図３２】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３３】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３４】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３５】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３６】同じく、交差判定の結果が「端側と交差」になった場合の説明図である。
【図３７】表Ｂの作成方法の説明図である。
【図３８】同じく、表Ｂの作成方法の説明図である。
【図３９】始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４０】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４１】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４２】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４３】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４４】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４５】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４６】同じく、始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４７】同じく始点側と終点側の両方で隣接線分のクリアランス境界との交差判定を行う場合の判定方法の説明図である。
【図４８】図形の具体例による交差判定結果を示す図である。
【図４９】同じく、図形の具体例による交差判定結果を示す図である。
【図５０】同じく、図形の具体例による交差判定結果を示す図である。
【図５１】同じく、図形の具体例による交差判定結果を示す図である。
【図５２】同じく、図形の具体例による交差判定結果を示す図である。
【図５３】同じく、図形の具体例による交差判定結果を示す図である。
【図５４】同じく、図形の具体例による交差判定結果を示す図である。
【図５５】表Ｃの内容から最終的に「クリアランスを超えた交差」かどうかを判定する方法についての説明図である。
【図５６】図形１から見た判定結果と図形２から見た判定結果から最終的に交差判定を行う方法についての説明図である。
【図５７】本実施形態の効果を説明するための説明図である。
【図５８】同じく本実施形態の効果を説明するための説明図である。
【図５９】同じく本実施形態の効果を説明するための説明図である。
【図６０】同じく本実施形態の効果を説明するための説明図である。
【図６１】同じく本実施形態の効果を説明するための説明図である。
【図６２】同じく本実施形態の効果を説明するための説明図である。
【発明を実施するための形態】
【０００８】
図１は、本発明の一実施形態に係る図面情報の品質評価方法を実施するシステムの構成を示し、コンピュータからなる検査装置１は、地理空間情報を入力し、入力した地理空間情報に対して品質評価検査を行って、検査結果データを出力する。
【０００９】
検査装置１は、地理空間情報が図形１と図形２とからなる地理空間情報である場合、品質評価検査を図２に示す手順で行う。なお、以下の説明は、数学座標系を使用している。
【００１０】
図２において、まず、クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める（ステップＳ１）。
【００１１】
次に、「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成する（ステップＳ２）。
【００１２】
次に、ステップＳ２で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成する（ステップＳ３）。
【００１３】
次に、表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る（ステップＳ４）。
【００１４】
次に、図形１と図形２とを入れ換えてステップＳ２〜Ｓ４を繰り返し、図形２から見た判定結果を得る（ステップＳ５）。
【００１５】
最後に、「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する（ステップＳ６）。
【００１６】
以下、ステップＳ１〜Ｓ６の具体的内容を順に説明する。
【００１７】
Ａ． ステップＳ１
ステップＳ１では、クリアランスを考慮せずに、図形１と図形２との交差判定を行い、交点Ｐを求める（図１４参照。図１４に示すＰ１が交点Ｐである。なお、図１４に示すＣＢは、図形２のクリアランス境界である。）。
【００１８】
図３に示すように、図形１がｍ個の線分１−１、１−２、…、１−ｍからなり、また、図形２がｎ個の線分２−１、２−２、…、２−ｎからなる場合、図形１の線分１−１と図形２の各線分２−１、２−２、…、２−ｎとの交差判定、図形１の線分１−２と図形２の各線分２−１、２−２、…、２−ｎとの交差判定、…、図形１の線分１−ｍと図形２の各線分２−１、２−２、…、２−ｎとの交差判定を行い、交点Ｐを求める。
【００１９】
交点Ｐを求めるに当たっては、図４に示すように、図形１の線分Ａの端点を（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、図形２の線分Ｂの端点を（ｘ３，ｙ３）、（ｘ４，ｙ４）とした場合、最初に、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と２点（ｘ３，ｙ３）、（ｘ４，ｙ４）を通る直線との交点（ｘ，ｙ）を求める。そして、求めた交点（ｘ，ｙ）が、線分Ａ上にあり、かつ、線分Ｂ上にあるとき、線分Ａと線分Ｂが交点（ｘ，ｙ）で交差すると判定する。
【００２０】
Ｂ． ステップＳ２
ステップＳ２では、「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ａを作成する。
【００２１】
a) 図形１の交点Ｐ１間の部分図形ＰＤ
図形１の交点Ｐ１間の部分図形ＰＤは、基本的には、例えば図１５（Ｂ）に太線で示すように、図形１において始点側の交点Ｐ１（Ｐ1b）と終点側の交点Ｐ１（Ｐ1a）との間の図形であるが、後述するように、交点Ｐ１から前の交点までの図形、及び、交点Ｐ１から次の交点までの図形により構成される。
【００２２】
b) クリアランス境界ＣＢ
クリアランス境界ＣＢとは、図形又は線分からの距離がクリアランス以内となる領域（クリアランス領域）の境界線であり、図形のクリアランス境界ＣＢは、図５（Ａ）に示すように、図形を取り囲む閉ループ線で表され、線分のクリアランス境界ＣＢは、図５（Ｂ）に示すように、線分を取り囲む閉ループ線で表される。
【００２３】
そして、図形のクリアランス境界ＣＢは、図５（Ａ）に示すように、図形の始点から終点に向かう方向を基準として、始点側の端側、左側、右側及び終点側の端側により構成され、また、線分のクリアランス境界ＣＢは、図５（Ｂ）に示すように、線分の始点から終点に向かう方向を基準として、始点側の端側、左側、右側及び終点側の端側により構成される。
【００２４】
線分のクリアランス境界ＣＢを求めるに当たっては、図６に示すように、線分の始点（ｘ１，ｙ１）及び終点（ｘ２，ｙ２）を線分（ｘ１，ｙ１）―（ｘ２，ｙ２）に対して垂直方向へｃｌ（クリアランス）だけ移動した点Ａ（ｘａ，ｙａ）、点Ｂ（ｘｂ，ｙｂ）、点Ｃ（ｘｃ，ｙｃ）、点Ｄ（ｘｄ，ｙｄ）を求め、点Ａと点Ｂとを結んだ線分と、点Ｃと点Ｄとを結んだ線分と、終点（ｘ２，ｙ２）を中心点とし、半径がｃｌで、点Ｂで始まり点Ｃで終わる右回りの円弧と、始点（ｘ１，ｙ１）を中心点とし、半径がｃｌで、点Ｄで始まり点Ａで終わる右回りの円弧とにより構成する。
【００２５】
c) 「図形」と「線分のクリアランス境界」との交差判定
「図形」と「線分のクリアランス境界」との交差判定は、図形を構成する線分とクリアランス境界の構成要素ごとに、全ての組合せで交差判定を行う。例えば、図７に示すように、図形がｍ個の線分１−１、１−２、…、１−ｍで構成され、線分のクリアランス境界が線分２−１、２−２及び円弧２−１、２−２で構成される場合、線分１−１と線分２−１との交差判定、線分１−１と線分２−２との交差判定、線分１−１と円弧２−１との交差判定、線分１−１と円弧２−２との交差判定、線分１−２と線分２−１との交差判定、線分１−２と線分２−２との交差判定、線分１−２と円弧２−１との交差判定、線分１−２と円弧２−２との交差判定、…、線分１−ｍと線分２−１との交差判定、線分１−ｍと線分２−２との交差判定、線分１−ｍと円弧２−１との交差判定、線分１−ｍと円弧２−２との交差判定を行う。
【００２６】
線分と円弧との交差判定は、図８に示すように、線分の端点を（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、円弧の中心点を（ｘｃ，ｙｃ）、半径をｒ、開始角をθ１、終了角をθ２とした場合、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と、中心点（ｘｃ，ｙｃ）、半径ｒの円との交点（ｘ，ｙ）を求める。そして、交点（ｘ，ｙ）が線分上にあり、かつ、円弧上にあれば、線分と円弧が交点（ｘ，ｙ）で交差すると判定する。
【００２７】
円周上の点が円弧上にあるかどうかの判定は、図１２に示すように、円周上の点を（ｘ，ｙ）とし、円弧の中心点を（ｘｃ，ｙｃ）、半径をｒ、開始角をθ１、終了角をθ２とし、点（ｘｃ，ｙｃ）から点（ｘ，ｙ）への方向角θ３を求め、θ３がθ１とθ２との間にあるときに、点が円弧上にあると判定する。
【００２８】
d) ステップＳ２の具体的内容（図１３）
次に、ステップＳ２の具体的内容を図１３に基づいて説明する。
【００２９】
d-1.
まず、図形１の交点Ｐ１から前（始点寄り）の交点（前の交点が無い場合は始点）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点寄り）の交点（次の交点が無い場合は終点）までの部分図形ＰＤａとを設定する（ステップＳ２１）。
【００３０】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）、（Ｂ）に示すように、交点Ｐ１ｂについての部分図形ＰＤｂ及び部分図形ＰＤａは、それぞれ、交点Ｐ１ｂから始点ＰSTまでの太線で表した図形、及び、交点Ｐ１ｂから次の交点Ｐ１ａまでの太線で表した図形となり、また、図１６（Ａ）、（Ｂ）に示すように、交点Ｐ１ａについての部分図形ＰＤｂ及び部分図形ＰＤａは、それぞれ、交点Ｐ１ａから交点Ｐ１ｂまでの太線で表した図形、及び、交点Ｐ１ａから終点ＰENまでの太線で表した図形となる。
【００３１】
d-2.
次に、図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢ（ＣＢｂ）を設定する（ステップＳ２２）。
【００３２】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）、（Ｂ）に示すように、交点Ｐ１ｂのある線分ＢＬについてのクリアランス境界ＣＢｂは、破線で表した図形となり、また、図１６（Ａ）、（Ｂ）に示すように、交点Ｐ１ａのある線分ＢＬについてのクリアランス境界ＣＢｂは、破線で表した図形となる。
【００３３】
d-3.
次に、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行う（ステップＳ２３）。
【００３４】
例えば図１４に示す図形１及び図形２の場合、図１５（Ａ）に示すように、交点Ｐ１ｂについての部分図形ＰＤｂは、クリアランス境界ＣＢｂの右側と交差すると判定し、図１５（Ｂ）に示すように、交点Ｐ１ｂについての部分図形ＰＤａは、クリアランス境界ＣＢｂの左側と交差すると判定し、また、図１６（Ａ）に示すように、交点Ｐ１ａについての部分図形ＰＤｂは、クリアランス境界ＣＢｂの左側と交差すると判定し、図１６（Ｂ）に示すように、交点Ｐ１ａについての部分図形ＰＤａは、クリアランス境界ＣＢｂの右側と交差すると判定する。
【００３５】
d-4.
次に、「交差あり」か否かを判定する（ステップＳ２４）。
【００３６】
d-4-a.
「交差なし」の場合、「交差なし」と判定する（ステップＳ２５）。
【００３７】
例えば図２２に示す図形１及び図形２の場合、部分図形ＰＤは線分ＢＬのクリアランス境界ＣＢｂ内にあるため、ステップＳ２４の判定結果は「ＮＯ」となり、「交差なし」と判定され（ステップＳ２５）、表Ａが作成される。
【００３８】
d-4-b.
一方、「交差あり」の場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を継続するか否かを判定する（ステップＳ２６）。
【００３９】
例えば図１４に示す図形１及び図形２の場合、上述したように、交点Ｐ１ｂについての部分図形ＰＤｂ及び部分図形ＰＤａのいずれも「交差あり」となり、また、交点Ｐ１ａについての部分図形ＰＤｂ及び部分図形ＰＤａのいずれも「交差あり」となるため、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続するか否かを判定することになる。
【００４０】
この隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する条件として３つの条件（第１条件、第２条件、第３条件）がある。第１条件は、「図形Ａが判定円Ｃ内を通過すること（ステップＳ２６ａ）」である。第２条件は、「最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること（ステップＳ２６ｂ）」である。第３条件は、「図形Ｂが判定円Ｃ内を通過すること（ステップＳ２６ｃ）」である。第１条件の判定ステップＳ２６ａの判定結果、第２条件の判定ステップＳ２６ｂの判定結果及び第３条件の判定ステップＳ２６ｃの判定結果が全て「ＹＥＳ」の場合のみ、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する。第１条件の判定ステップＳ２６ａの判定結果は「ＹＥＳ」であっても第２条件の判定ステップＳ２６ｂの判定結果が「ＮＯ」である場合、次の隣接線分ＮＮＬがあるか否かを判定し（ステップＳ２６ｄ）、ステップＳ２６ｄの判定結果が「ＹＥＳ」の場合、ステップＳ２６ａへ移行し、次の隣接線分ＮＮＬで再度条件判定を行う。
【００４１】
点（ｘ，ｙ）がクリアランス境界内にあるかどうかの判定は、図９に示すように、点（ｘ，ｙ）から２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線へ下ろした垂線の足（ｘｆ，ｙｆ）を求めた上で、点（ｘ，ｙ）から線分までの距離ｄを求める。そして、ｄ≦ｃｌのとき、点（ｘ，ｙ）がクリアランス境界内にあると判定する。
【００４２】
図形が円内を通過するかどうかの判定は、図形を構成する線分ごとに円との交差判定を行い、円と交差する線分が存在したら円内を通過すると判定する。例えば、図１０に示すように、図形がｍ個の線分で構成されている場合、線分１と円の交差判定、線分２と円の交差判定、…、線分ｍと円の交差判定を行う。
【００４３】
線分と円の交差判定は、図１１に示すように、線分の端点をそれぞれ（ｘ１，ｙ１）、（ｘ２，ｙ２）とし、円の中心点を（ｘｃ，ｙｃ）、半径をｒとし、２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線と円との交点（ｘａ，ｙａ）、（ｘｂ，ｙｂ）を求める。そして、交点（ｘａ，ｙａ）、（ｘｂ，ｙｂ）のどちらか一方でも線分上にあれば、線分と円とが交差すると判定する。
【００４４】
（第１条件）
第１条件は、上記のように、「図形Ａが判定円Ｃ内を通過すること」である。
【００４５】
・図形Ａ
図形Ａとは、部分図形ＰＤの始点Ｐｓから、部分図形ＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいう。
【００４６】
例えば図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての部分図形ＰＤｂ及び線分ＢＬのクリアランス境界ＣＢｂは図１７（Ａ）に示すようになるため、部分図形ＰＤｂにおける図形Ａは図１７（Ｂ）に示すようになる。また、交点Ｐ１ｂについての部分図形ＰＤａ及び線分ＢＬのクリアランス境界ＣＢｂは図１８（Ａ）に示すようになるため、部分図形ＰＤａにおける図形Ａは図１８（Ｂ）に示すようになる。また、交点Ｐ１ａについての部分図形ＰＤｂ及び線分ＢＬのクリアランス境界ＣＢｂは図１９（Ａ）に示すようになるため、部分図形ＰＤｂにおける図形Ａは図１９（Ｂ）に示すようになる。また、交点Ｐ１ａについての部分図形ＰＤａ及び線分ＢＬのクリアランス境界ＣＢｂは図２０（Ａ）に示すようになるため、部分図形ＰＤａにおける図形Ａは図２０（Ｂ）に示すようになる。
【００４７】
・判定円Ｃ
判定円Ｃとは、線分（現在の線分）ＢＬに隣接する隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいう。
【００４８】
例えば図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての現在の線分ＢＬ、隣接線分ＮＬ及び隣接線分ＮＬのクリアランス境界ＣＢｎは図１７及び図１８に示すようになるため、判定円Ｃは図１７及び図１８に示すようになる。また、交点Ｐ１ａについての現在の線分ＢＬ、隣接線分ＮＬ及び隣接線分ＮＬのクリアランス境界ＣＢｎは図１９及び図２０に示すようになるため、判定円Ｃは図１９及び図２０に示すようになる。
【００４９】
・第１条件の判定結果（第１条件が成立しない場合）
図１４に示す図形１及び図形２の場合、交点Ｐ１ｂについての図形Ａ、及び、交点Ｐ１ａについての図形Ａは、図１７（Ｂ）、図１８（Ｂ）、図１９（Ｂ）及び図２０（Ｂ）に示すように、いずれも判定円Ｃを通過していないため、第１条件は成立しないことになり、判定ステップＳ２６ａの判定結果は「ＮＯ」となり、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続せず、「交差あり」と判定し（ステップＳ２７）、表Ａを作成することになる。
【００５０】
したがって、図１４に示す図形１及び図形２の場合、ステップＳ２において表Ａが作成されることになり、表Ａは、図２１に示す内容となる。図２１において、表Ａの第１行目には、「図形１の交点Ｐ１ｂから始点ＰSTまでの部分図形ＰＤｂ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第２行目には、図形１の交点Ｐ１ｂが書き込まれ、表Ａの第３行目には、「図形１の交点Ｐ１ｂから次の交点Ｐ１ａまでの部分図形ＰＤａ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第４行目には、「図形１の交点Ｐ１ａから前の交点Ｐ１ｂまでの部分図形ＰＤｂ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、表Ａの第５行目には、図形１の交点Ｐ１ａが書き込まれ、表Ａの第６行目には、「図形１の交点Ｐ１ａから終点ＰENまでの部分図形ＰＤａ」と「図形２のクリアランス境界ＣＢｂ」との交差判定の結果が書き込まれ、この結果、表Ａの第１行目、第３行目には、それぞれ、「右側と交差」、「左側と交差」が書き込まれ、第４行目、第６行目には、それぞれ、「左側と交差」、「右側と交差」が書き込まれる。
【００５１】
また、図２３に示す図形１及び図形２の場合、図形Ａが判定円Ｃ内を通過しないため、表Ａに、「交差あり（左側と交差）」と書き込まれる。
【００５２】
・第１条件の判定結果（第１条件が成立する場合）
図形１及び図形２が図２４に示す場合、図形１の部分図形ＰＤにおける図形Ａは判定円Ｃ内を通過することになるため、ステップＳ２６ａの判定結果は「ＹＥＳ」となり、次に、第２条件が成立するか否かが判定される（ステップＳ２６ｂ）。
【００５３】
（第２条件）
第２条件は、上記のように、「最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」である。
【００５４】
・第２条件の判定結果（第２条件が成立しない場合）
図２４に示す図形１及び図形２の場合、最初の交点Ｐｆは、隣接線分ＮＬのクリアランス境界ＣＢｎの外にあるため、第２条件は成立しないことになる。
【００５５】
第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否か判定する（ステップＳ２６ｄ）。
【００５６】
・次の隣接線分ＮＮＬがない場合
次の隣接線分ＮＮＬがない場合、「交差あり」と判定し（ステップＳ２７）、表Ａを作成する。図２４の例の場合、隣接線分ＮＮＬがないことから、「交差あり（左側と交差）」と判定し（ステップＳ２７）、表Ａを作成することになる。
【００５７】
・次の隣接線分ＮＮＬがある場合
次の隣接線分ＮＮＬがある場合、ステップＳ２６ａへ移行し、図形Ａが判定円Ｃ（このときの判定円Ｃは、次の隣接線分ＮＮＬの、隣接線分ＮＬ寄りの端点Ｐｓｔ、を中心とする円Ｃｎとなる。）を通過するか否かを判定する。
【００５８】
図２５に示す図形１及び図形２の場合、次の隣接線分ＮＮＬがあることから、図形Ａが判定円Ｃｎ内を通過かするか否か判定され（ステップＳ２６ａ）、この判定結果は「ＮＯ」となり、「交差あり（左側と交差）」と判定され（ステップＳ２７）、表Ａが作成されることになる。
【００５９】
・第２条件の判定結果（第２条件が成立する場合）
図２６に示す図形１及び図形２の場合、最初の交点Ｐｆは、隣接線分ＮＬのクリアランス境界ＣＢｎ内にあることから、ステップＳ２６ｂの判定結果は「ＹＥＳ」となり、次に、第３条件が成立するか否かが判定される（ステップＳ２６ｃ）。
【００６０】
（第３条件）
第３条件は、上記のように、「図形Ｂが判定円Ｃ内を通過すること」である。
【００６１】
・図形Ｂ
図形Ｂとは、部分図形ＰＤにおいて、図形Ａと隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう。但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。
【００６２】
例えば図２６（Ａ）に示す図形１及び図形２の場合、最初の交点Ｐｆ及び最後の交点Ｐｌは図２６（Ａ）に示すようになるため、図形Ｂは、図２６（Ｂ）に示すようになる。
【００６３】
・第３条件の判定結果（第３条件が成立しない場合）
例えば図２８に示す図形１及び図形２の場合、図２８（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過しないため、ステップＳ２６ｃの判定結果は「ＮＯ」となり、「交差あり（左側と交差）」と判定し（ステップＳ２７）、表Ａを作成する。
【００６４】
・第３条件の判定結果（第３条件が成立する場合）
例えば図２６に示す図形１及び図形２の場合、図２６（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過するため、ステップＳ２６ｃの判定結果は「ＹＥＳ」となり、次に、隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定を継続する（ステップＳ２８）。
【００６５】
＜隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定＞
隣接線分ＮＬのクリアランス境界ＣＢｎを使用した交差判定においては、図形Ａが隣接線分ＮＬのクリアランス境界ＣＢｎ内にある場合を除き、部分図形ＰＤの変更を行う。変更後の部分図形ＰＤの始点は、変更前の部分図形ＰＤの始点Ｐｓから最初の交点Ｐｆまでの部分と、隣接線分ＮＬのクリアランス境界ＣＢｎと、の最後の交点Ｐｌになる。
【００６６】
例えば図２６（Ａ）に示す図形１及び図形２の場合、図２７（Ａ）に示すように、変更前の部分図形ＰＤにおいて、部分図形ＰＤの始点Ｐｓから最初の交点Ｐｆまでの部分は図２７（Ａ）において太線で示すものとなり、変更後の部分図形ＰＤは、図２７（Ｂ）において太線で示す図形となる。図２７（Ｂ）に示す部分図形ＰＤの場合、現在の線分ＢＬ（元の隣接線分ＮＬ）のクリアランス境界ＣＢｂ（元のクリアランス境界ＣＢｎ）内にあるため、表Ａに「交差なし」と書き込まれる。
【００６７】
ｅ) 「部分図形」と「線分のクリアランス境界」との交差判定の具体例
・図２８に示す図形１及び図形２の場合、図２８（Ａ）に示すように、部分図形ＰＤが線分ＢＬのクリアランス境界ＣＢｂと交差しており、図形Ａが判定円Ｃ内を通過しており、最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にあり、図２８（Ｂ）に示すように、図形Ｂが判定円Ｃ内を通過しないため、表Ａに「交差あり（左側と交差）」と書き込まれる。
【００６８】
・図２９に示す図形１及び図形２の場合、図２９に示すように、部分図形ＰＤが線分ＢＬのクリアランス境界ＣＢｂと交差しており、図形Ａが判定円Ｃ内を通過しており、最初の交点Ｐｆが隣接線分ＮＬのクリアランス境界ＣＢｎ内にないため、次の隣接線分ＮＮＬを使用して再度条件判定が行われ、再度の条件判定において、図３０（Ａ）に示すように、図形Ａが次の隣接線分ＮＮＬの判定円Ｃｎ内を通過しており、最初の交点Ｐｆが次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあり、図３０（Ｂ）に示すように、図形Ｂが判定円Ｃｎ内を通過するため、次の隣接線分ＮＮＬを使用して交差判定を継続する。次の隣接線分ＮＮＬを使用した交差判定においては、更新後の部分図形ＰＤとして、更新前の部分図形ＰＤのうち最後の交点Ｐｌを始点とする図形が使用され、この更新後の部分図形ＰＤは次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあるため、表Ａに「交差なし」と書き込まれる。
【００６９】
f) 交差判定の結果が「端側と交差」になった場合
図３１に示すように、図形２の最初の線分のクリアランス境界の始点側の端側、又は、最後の線分のクリアランス境界の終点側の端側と交差しているときには、その端側は、図形のクリアランス境界の端側と一致するので、図形のクリアランス境界の端側と交差していることになり、交差判定の結果は、「端側と交差」になる。
【００７０】
図３２に示すように、図形２の線分のクリアランス境界の上記以外の端側と交差しているときには、その端側は、図形のクリアランス境界の左側又は右側の一部分であり、図形のクリアランス境界の左側又は右側と交差していることになるので、どちら側と交差しているかの判定を行う。点が直線に対してどちら側にあるかの判定は、図３５に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線のどちら側にあるか判定する。この判定にあたっては、座標法により、三角形（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）の面積Ｓを計算する（２Ｓ＝（ｙ２−ｙ１）（ｘ３−ｘ１）−（ｘ２−ｘ１）（ｙ３−ｙ１））。座標法では、面積の符号が、図３６（Ａ）に示すように、三角形が右回りのときには正になり、図３６（Ｂ）に示すように、三角形が左回りのときは負になるので、面積が正のときは、「点は直線の右側にある」と判定し、面積が負のときは、「点は直線の左側にある」と判定する。
【００７１】
図３３に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線の（進行方向に対して）左側にあるときには、線分のクリアランス境界の端側と交差して外に出たならば、図形のクリアランス境界の右側と交差して外に出たことになるので、交差判定の結果は、「右側と交差」になる。
【００７２】
図３４に示すように、点（ｘ３，ｙ３）が２点（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線の（進行方向に対して）右側にあるときには、線分のクリアランス境界の端側と交差して外に出たならば、図形のクリアランス境界の左側と交差して外に出たことになるので、交差判定の結果は、「左側と交差」になる。
【００７３】
Ｃ． ステップＳ３
ステップＳ３では、ステップＳ２で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行い、表Ｂを作成する。
【００７４】
a) 拡張部分図形ＥＰＤ
例えば図３７（Ａ）に示す図形１及び図形２の場合、表Ａは、図３７（Ｂ）に示すようになり、第３行目及び第４行目の判定結果は「交差なし」となる。
【００７５】
このような場合、表Ｂを作成する。表Ｂを作成するに当たっては、拡張部分図形ＥＰＤが使用され、上述した表Ａを作成する手順と同様な手順により、拡張部分図形ＥＰＤとクリアランス境界ＣＢとの交差判定を行い、表Ｂを作成する。
【００７６】
図３７（Ａ）に示す図形１及び図形２の場合、図３８（Ａ）に示すように、交点Ｐ１ｂについての拡張部分図形ＥＰＤａは、交点Ｐ１ｂから終点ＰENまでの部分図形となり、交点Ｐ１ａについての拡張部分図形ＥＰＤｂは、交点Ｐ１ａから始点ＰSTまでの部分図形となり、判定結果である表Ｂは、図３８（Ｃ）に示すようになる。
【００７７】
＜具体例（図３９〜図４７）＞
図３９に示す図形１及び図形２の場合、部分図形ＰＤと現在の線分ＢＬのクリアランス境界ＣＢｂとの交差判定の結果は、図３９に示すように、「左側と交差」になる。
【００７８】
このため、まず、始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓとの交差判定を継続するか否かを判定することになる。
【００７９】
図４０に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓ内にあり、また、図形Ａとクリアランス境界ＣＢｎｓとの交点がないため、図形Ｂは図形Ａと同じになり、図形Ｂは判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００８０】
このため、隣接線分ＮＬｓのクリアランス境界ＣＢｎｓを使用した交差判定を継続することになる。
【００８１】
この隣接線分ＮＬｓのクリアランス境界ＣＢｎｓを使用した交差判定においては、図形Ａがクリアランス境界ＣＢｎｓ内にあるため、部分図形ＰＤの変更は行わず、図４１に示すように、上述したクリアランス境界ＣＢｂとの交差判定に使用された部分図形ＰＤと同じ部分図形が使用される。
【００８２】
この交差判定の結果は、図４１に示すように、「（始点側の）端側と交差」になる。
【００８３】
このため、次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎとの交差判定を継続するか否かを判定することになる。
【００８４】
図４２に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎ内にあり、また、図形Ｂは、図４３に示すように、判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００８５】
このため、次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎを使用した交差判定を継続することになる。
【００８６】
この次の隣接線分ＮＮＬのクリアランス境界ＣＢｎｎを使用した交差判定においては、部分図形ＰＤが変更され、図４４に示す部分図形ＰＤが使用される。
【００８７】
この交差判定の結果は、図４４に示すように、「左側と交差」になる。そして、次の次の隣接線分がないため、始点方向の隣接線分ＮＬｓのクリアランス境界ＣＢｎｓとの交差判定の結果は、「左側と交差」ということになる。
【００８８】
次に、終点方向の隣接線分ＮＬｅのクリアランス境界ＣＢｎｅとの交差判定を継続するか否かを判定することになる。
【００８９】
図４５に示すように、図形Ａは判定円Ｃ内を通過しており、また、最初の交点Ｐｆは終点方向の隣接線分ＮＬｅのクリアランス境界ＣＢｎｅ内にあり、また、図形Ａとクリアランス境界ＣＢｎｅとの交点がないため、図形Ｂは図形Ａと同じになり、図形Ｂは判定円Ｃ内を通過しているため、上記の第１条件、第２条件、第３条件の全てが成立している。
【００９０】
このため、隣接線分ＮＬｅのクリアランス境界ＣＢｎｅを使用した交差判定を継続することになる。
【００９１】
この隣接線分ＮＬｅのクリアランス境界ＣＢｎｅを使用した交差判定においては、図形Ａがクリアランス境界ＣＢｎｅ内にあるため、部分図形ＰＤの変更は行わず、図４６に示すように、上述したクリアランス境界ＣＢｂとの交差判定に使用された部分図形ＰＤと同じ部分図形が使用される。
【００９２】
この交差判定の結果は、図４６に示すように、「交差なし」になる。
【００９３】
したがって、始点方向の隣接線分ＮＬｓ側の交差判定の結果は「左側と交差」になり、終点方向の隣接線分ＮＬｅ側の交差判定の結果は「交差なし」になる。
【００９４】
このように始点方向と終点方向とで交差判定の結果が一致せず、いずれか一方の判定結果に「交差なし」がある場合、交差判定の結果は「交差なし」とされ、表Ａに「交差なし」を書き込む。
【００９５】
次に、拡張部分図形ＥＰＤを使用して、上述した部分図形ＰＤを使用した交差判定と同様に交差判定を行う。
【００９６】
この交差判定においては、始点方向の判定結果は、部分図形ＰＤを使用した交差判定と同じく「左側と交差」になり、一方、終点方向の判定結果は、図４７に示すように、「右側と交差」になる。
【００９７】
このような場合、交差判定の結果は「両側と交差」とし、表Ｂに「両側と交差」を書き込む。
【００９８】
なお、図示しないが、図形１がループ状の図形の場合、始点が存在しないので、一周して元の交点までの部分図形を拡張部分図形ＥＰＤとして使用する。
【００９９】
Ｄ． ステップＳ４
ステップＳ４では、表Ａと表Ｂから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうか判定し、図形１から見た判定結果を得る。
【０１００】
（具体例その１（図４８））
図４８（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図４８（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果となっているのに対し、表Ｂでは「右側と交差」、「（始点）の端側と交差」となっている。
【０１０１】
このような場合、表Ａにおいて交点ＰAの次の行の判定結果が「交差なし」のときに、表Ｂにおける同じ行の判定結果及び次の交点ＰBの次の行の判定結果が「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）のときには、変更条件が成立しているとし、表Ｃの判定結果を「交差なし」とする。
【０１０２】
同様に、表Ａにおいて交点ＰBの前の行の判定結果が「交差なし」のときに、表Ｂにおける同じ行の判定結果及び前の交点ＰAの前の行の判定結果が「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）のときには、表Ｃの判定結果を「交差なし」とする。
【０１０３】
（具体例その２（図４９））
図４９（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図４９（Ｂ）に示すようになる。すなわち、表Ａの第３行目、第４行目、第６行目及び第７行目では「交差なし」の判定結果となっているのに対し、表Ｂでは「左側と交差」、「右側と交差」、「左側と交差」、「右側と交差」となっている。
【０１０４】
したがって、上記変更条件が成立しているため、表Ｃにおいては、上記各行に「交差なし」が書き込まれる。
【０１０５】
（具体例その３（図５０））
図５０（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５０（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果になっているのに対し、表Ｂでは「左側と交差」、「左側と交差」となっている。
【０１０６】
したがって、上記変更条件が成立していない。このような場合、表Ｃには、表Ｂと同じ内容が書き込まれる。
【０１０７】
（具体例その４（図５１））
図５１（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５１（Ｂ）に示すようになる。すなわち、表Ａの第３行目及び第４行目では「交差なし」の判定結果になっているのに対し、表Ｂでは「両側と交差」、「右側と交差」となっている。
【０１０８】
このように、「両側と交差」と「右側（左側）と交差」の組合せのときは、「同じ側で交差」とみなす。
【０１０９】
このため、上記変更条件が成立することなり、表Ｃには、「交差なし」が書き込まれる。
【０１１０】
（具体例その５（図５２））
図５２（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５２（Ｂ）に示すようになる。表Ｂにおいて、第３行目及び第４行目の判定結果は、それぞれ「交差なし」及び「左側と交差」となっている。このように、表Ｂにおいて、交点ＰA、ＰBに挟まれた２つの判定結果のどちらか一方でも「交差なし」となっている場合、表Ｃの判定結果は「交差なし」に変更する。
【０１１１】
（具体例その６（図５３））
図５３（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５３（Ｂ）に示すようになる。交点ＰA、ＰBに挟まれた２つの行で、表Ａの判定結果が片方だけ「交差なし」で、表Ｂの判定結果が「左側と交差」と「右側と交差」の組合せになっている場合、表Ｃでは、共に「交差なし」に変更する。
【０１１２】
（具体例その７（図５４））
図５４（Ａ）に示す図形１及び図形２の場合、表Ａ及び表Ｂは図５４（Ｂ）に示すようになる。
【０１１３】
表Ｃには、図５５（Ａ）に示すように、各交点ＰA、ＰBごとに最終的な判定結果が書き込まれる。
【０１１４】
表Ｃの中で、図５５（Ｂ）に示すように、交点Ｐの上下の行の判定結果が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、また、図５５（Ｃ）に示すように、それ以外の組合せのときは「交差なし」と判定する。
【０１１５】
表Ｃにおいて、交点ＰAと交点ＰBとで挟まれた２つの行には、「交差なし」が書き込まれる。「クリアランスを超えて交差した」かどうかの判定時には、表Ｃ中の「交差なし」は無視して考えるため、表Ｃ中の「交差なし」を削除すると、図５４（Ｃ）に示すようになる。
【０１１６】
Ｅ． ステップＳ５
ステップＳ５では、図形１と図形２を入れ換えてステップＳ２〜Ｓ４を繰り返し、図形２から見た判定結果を得る。
【０１１７】
Ｆ． ステップＳ６
ステップＳ６では、「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する。
【０１１８】
図５６（Ａ）、（Ｃ）に示す図形１及び図形２の場合、図形１から見た判定結果は図５６（Ｂ）に示すようになり、「クリアランスを超えた交差」と判定されるが、図形２から見た判定結果は図５６（Ｄ）に示すようになり、「交差なし」と判定される。このため、最終的に「交差なし」と判定される。
【０１１９】
以上説明したように、本実施形態に係る図面情報の品質評価方法は、
図形１と図形２とからなる地理空間情報（図面情報）をコンピュータからなる検査装置１に入力し、検査装置１において、品質評価検査を行って検査結果データを出力する地理空間情報（図面情報）の品質評価方法であって、工程(a)〜(c)
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
を実行し、
工程(b)及び(c)は、それぞれ、工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
第１条件が成立しない場合、「交差あり」と判定し、
一方、第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、次の隣接線分ＮＬＬがある場合、次の隣接線分ＮＮＬで第１条件が成立するか否かの判定に戻り、
一方、第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
第３条件が成立しない場合、「交差あり」と判定し、
一方、第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
第１条件は、「図形Ａが判定円Ｃ内を通過すること」、第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、「図形Ａ」とは、部分図形ＰＤ又は拡張部分図形ＥＰＤの始点Ｐｓから、部分図形ＰＤ又は拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、「図形Ｂ」とは、部分図形ＰＤ又は拡張部分図形ＥＰＤにおいて、図形Ａと隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）。
【０１２０】
そして、工程(b)の交差判定により表Ａが作成され、工程(c)の交差判定により表Ｂが作成され、
表Ａ及び表Ｂには、それぞれ、各交点Ｐ１が書き込まれ、各交点Ｐ１の上の行に、交点Ｐ１についての部分図形ＰＤｂ又は拡張部分図形ＥＰＤｂとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれ、各交点Ｐ１の下の行に、交点Ｐ１についての部分図形ＰＤａ又は拡張部分図形ＥＰＤａとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれる。
【０１２１】
そして、工程(a)〜(c)の実行後、工程(d)〜(f)
(d)表Ａと表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る
(e)図形１と図形２とを入れ換えて工程(b)〜(d)を繰り返し、図形２から見た判定結果を得る
(f)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する
を実行する。
【０１２２】
本実施形態によると、下記の効果が奏される。
【０１２３】
本実施形態のように線分のクリアランス境界を使用して表Ａ及び表Ｂを作成する代わりに、図５７（Ａ）に示すように、図形のクリアランス境界を使用して表Ａ及び表Ｂを作成する場合、表Ａ及び表Ｂは図５７（Ｂ）に示すようになり、最終的に「交差なし」と判定されるが、図５８（Ａ）に示すように、線分のクリアランス境界を使用して表Ａ及び表Ｂを作成する場合、表Ａ及び表Ｂは図５８（Ｂ）に示すようになり、最終的に交点ＰAとＰBでそれぞれ「クリアランスを超えて交差する」と正しく判定されるようになる。
【０１２４】
また、図５９（Ａ）に示す図形の場合、表Ａは図５９（Ｂ）に示すようになり、一方、図６０（Ａ）に示す図形の場合、表Ａは図６０（Ｂ）に示すようになり、表Ａは互いに一致した内容となる。しかし、図５９（Ｂ）と図６０（Ｂ）の表Ｂの内容は一致していないため、表Ｂの内容を参照することにより正しい判定を行うことができるようになる。
【０１２５】
また、図６１（Ａ）に示す図形の場合、表Ｂは図６１（Ｂ）に示すようになり、一方、図６２（Ａ）に示す図形の場合、表Ｂは図６２（Ｂ）に示すようになり、表Ｂは互いに一致した内容となる。しかし、図６１（Ｂ）と図６２（Ｂ）の表Ａの内容は一致していないため、表Ａの内容を参照することにより正しい判定を行うことができるようになる。
【０１２６】
また、本実施形態では、工程(d)において、
1) 表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
2) 表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、また、
表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、
3) 表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行のどちらか一方でも「交差なし」となっている場合、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
4) 表Ａにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行の片方だけ「交差なし」であり、かつ、表Ｂにおいて、前記交点Ｐ１の下の行と前記次の交点Ｐ１の上の行が「左側と交差」と「右側と交差」の組合せになっている場合、表Ｂの内容を変更して表Ｃに「交差なし」と書き込み、
5) 表Ｃにおいて、交点Ｐの上下の行が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、それ以外の組合せのときは「交差なし」と判定する
ようにしたため、複雑な図形や複雑に交差している場合でも、正しく判定することが可能になる。
【０１２７】
したがって、本実施形態によると、検査装置（コンピュータ）上で「クリアランスを超えた交差」かどうかの判定が正しく行われるようになり、地理空間情報（図面情報）の品質評価を自動で行い、クリアランスを考慮した全件検査が可能となる。
【符号の説明】
【０１２８】
１ 検査装置（コンピュータ）
【特許請求の範囲】
【請求項１】
図形１と図形２とからなる図面情報をコンピュータからなる検査装置に入力し、該検査装置において、品質評価検査を行って検査結果データを出力する図面情報の品質評価方法であって、少なくとも下記工程(a)〜(c)を実行し、
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)前記工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
前記工程(b)及び(c)は、それぞれ、下記工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)前記工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、前記工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)前記工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、前記工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
前記第１条件が成立しない場合、「交差あり」と判定し、
一方、前記第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
前記第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
前記次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、前記次の隣接線分ＮＬＬがある場合、前記次の隣接線分ＮＮＬで前記第１条件が成立するか否かの判定に戻り、
一方、前記第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
前記第３条件が成立しない場合、「交差あり」と判定し、
一方、前記第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
前記第１条件は、「図形Ａが判定円Ｃ内を通過すること」、前記第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、前記第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、前記「図形Ａ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤの始点Ｐｓから、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、前記「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、前記「図形Ｂ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤにおいて、前記図形Ａと前記隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）
ことを特徴とする図面情報の品質評価方法。
【請求項２】
前記工程(b)の交差判定により表Ａが作成され、前記工程(c)の交差判定により表Ｂが作成され、
前記表Ａ及び前記表Ｂには、それぞれ、各交点Ｐ１が書き込まれ、各交点Ｐ１の上の行に、交点Ｐ１についての部分図形ＰＤｂ又は拡張部分図形ＥＰＤｂとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれ、各交点Ｐ１の下の行に、交点Ｐ１についての部分図形ＰＤａ又は拡張部分図形ＥＰＤａとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれる
ことを特徴とする請求項１に記載の図面情報の品質評価方法。
【請求項３】
前記工程(a)〜(c)の実行後、下記工程(d)〜(f)を実行する
(d)前記表Ａと前記表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る
(e)図形１と図形２とを入れ換えて前記工程(b)〜(d)を繰り返し、図形２から見た判定結果を得る
(f)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する
ことを特徴とする請求項２に記載の図面情報の品質評価方法。
【請求項４】
前記工程(d)において、
前記表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込み、
前記表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項３に記載の図面情報の品質評価方法。
【請求項５】
前記表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、また、
前記表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなす
ことを特徴とする請求項４に記載の図面情報の品質評価方法。
【請求項６】
前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行のどちらか一方でも「交差なし」となっている場合、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項５に記載の図面情報の品質評価方法。
【請求項７】
前記表Ａにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行の片方だけ「交差なし」であり、かつ、前記表Ｂにおいて、前記交点Ｐ１の下の行と前記次の交点Ｐ１の上の行が「左側と交差」と「右側と交差」の組合せになっている場合、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項６に記載の図面情報の品質評価方法。
【請求項８】
前記表Ｃにおいて、交点Ｐの上下の行が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、それ以外の組合せのときは「交差なし」と判定する
ことを特徴とする請求項７に記載の図面情報の品質評価方法。
【請求項９】
前記表Ｃにおいて、「交差なし」の行が存在したとき、「交差なし」の行を削除した前記表Ｃにおいて、複数の連続する交点の上下の行が「左側と交差」、「右側と交差」の組合せのとき、この複数の連続する交点が１つの交差区間を形成し、その交差区間で「クリアランスを超えて交差した」と判定する
ことを特徴とする請求項８に記載の図面情報の品質評価方法。
【請求項１】
図形１と図形２とからなる図面情報をコンピュータからなる検査装置に入力し、該検査装置において、品質評価検査を行って検査結果データを出力する図面情報の品質評価方法であって、少なくとも下記工程(a)〜(c)を実行し、
(a)クリアランスを考慮せずに、図形１と図形２の交差判定を行い、交点Ｐを求める
(b)「図形１の交点Ｐ１間の部分図形ＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
(c)前記工程(b)で「交差なし」と判定されたものについて、「図形１の交点Ｐ１間の部分図形ＰＤを拡張した拡張部分図形ＥＰＤ」と「図形２のクリアランス境界ＣＢ」との交差判定を行う
前記工程(b)及び(c)は、それぞれ、下記工程(g-1)〜(g-4)及び(g-5-a)又は(g-5-b)
(g-1)前記工程(b)の場合、図形１の交点Ｐ１から前（始点ＰST寄り）の交点Ｐ１（前の交点Ｐ１が無い場合は始点ＰST）までの部分図形ＰＤｂと、図形１の交点Ｐ１から次（終点ＰEN寄り）の交点Ｐ１（次の交点Ｐ１が無い場合は終点ＰEN）までの部分図形ＰＤａとを設定し、一方、前記工程(c)の場合、図形１の交点Ｐ１から始点ＰSTまでの拡張部分図形ＥＰＤｂ、又は、図形１の交点Ｐ１から終点ＰENまでの拡張部分図形ＥＰＤａを設定する
(g-2)図形２を構成する線分群のうち、図形１の交点Ｐ１のある線分ＢＬについてのクリアランス境界ＣＢｂを設定する
(g-3)前記工程(b)の場合、部分図形ＰＤｂとクリアランス境界ＣＢｂとの交差判定、及び、部分図形ＰＤａとクリアランス境界ＣＢｂとの交差判定を行い、一方、前記工程(c)の場合、拡張部分図形ＥＰＤｂとクリアランス境界ＣＢｂとの交差判定、又は、拡張部分図形ＥＰＤａとクリアランス境界ＣＢｂとの交差判定を行う
(g-4)「交差あり」か否かを判定する
(g-5-a)「交差なし」の場合、「交差なし」と判定する
(g-5-b)一方、「交差あり」の場合、所定の第１条件が成立するか否かを判定し、
前記第１条件が成立しない場合、「交差あり」と判定し、
一方、前記第１条件が成立する場合、所定の第２条件が成立するか否かを判定し、
前記第２条件が成立しない場合、次の隣接線分ＮＮＬがあるか否かを判定し、
前記次の隣接線分ＮＮＬがない場合、「交差あり」と判定し、一方、前記次の隣接線分ＮＬＬがある場合、前記次の隣接線分ＮＮＬで前記第１条件が成立するか否かの判定に戻り、
一方、前記第２条件が成立する場合、所定の第３条件が成立するか否かを判定し、
前記第３条件が成立しない場合、「交差あり」と判定し、
一方、前記第３条件が成立する場合、隣接線分ＮＬのクリアランス境界ＣＢ（ＣＢｎ）を使用した交差判定を行う
からなり、
前記第１条件は、「図形Ａが判定円Ｃ内を通過すること」、前記第２条件は、「最初の交点Ｐｆが線分（現在の線分）ＢＬに隣接する隣接線分ＮＬのクリアランス境界ＣＢｎ内にあること」、前記第３条件は、「図形Ｂが判定円Ｃ内を通過すること」であり、前記「図形Ａ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤの始点Ｐｓから、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤとクリアランス境界ＣＢとの最初の交点Ｐｆまでの図形をいい、前記「判定円Ｃ」とは、隣接線分ＮＬの線分ＢＬ側の端点Ｐｅを中心とする半径クリアランスの円をいい、前記「図形Ｂ」とは、前記部分図形ＰＤ又は前記拡張部分図形ＥＰＤにおいて、前記図形Ａと前記隣接線分ＮＬのクリアランス境界ＣＢｎとの最後の交点Ｐｌから最初の交点Ｐｆまでの図形をいう（但し、最後の交点Ｐｌがない場合、図形Ｂは図形Ａと同じになる。）
ことを特徴とする図面情報の品質評価方法。
【請求項２】
前記工程(b)の交差判定により表Ａが作成され、前記工程(c)の交差判定により表Ｂが作成され、
前記表Ａ及び前記表Ｂには、それぞれ、各交点Ｐ１が書き込まれ、各交点Ｐ１の上の行に、交点Ｐ１についての部分図形ＰＤｂ又は拡張部分図形ＥＰＤｂとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれ、各交点Ｐ１の下の行に、交点Ｐ１についての部分図形ＰＤａ又は拡張部分図形ＥＰＤａとクリアランス境界ＣＢとの交差判定の判定結果が書き込まれる
ことを特徴とする請求項１に記載の図面情報の品質評価方法。
【請求項３】
前記工程(a)〜(c)の実行後、下記工程(d)〜(f)を実行する
(d)前記表Ａと前記表Ｂとから表Ｃを作成し、それぞれの交差が「クリアランスを超えた交差」かどうかを判定し、図形１から見た判定結果を得る
(e)図形１と図形２とを入れ換えて前記工程(b)〜(d)を繰り返し、図形２から見た判定結果を得る
(f)「図形１から見た判定結果」と「図形２から見た判定結果」の両方で「クリアランスを超えた交差」と判定された交差のみを、最終的に「クリアランスを超えた交差」と判定する
ことを特徴とする請求項２に記載の図面情報の品質評価方法。
【請求項４】
前記工程(d)において、
前記表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込み、
前記表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに「同じ側で交差」（「左側と交差」、「右側と交差」又は「端側と交差」）が書き込まれているとき、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項３に記載の図面情報の品質評価方法。
【請求項５】
前記表Ａにおいて、交点Ｐ１の上の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の上の行と前の交点Ｐ１の上の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなし、また、
前記表Ａにおいて、交点Ｐ１の下の行に「交差なし」が書き込まれており、かつ、前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の下の行とに、「両側と交差」と「右側（左側）と交差」の組合せが書き込まれているとき、「同じ側で交差」とみなす
ことを特徴とする請求項４に記載の図面情報の品質評価方法。
【請求項６】
前記表Ｂにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行のどちらか一方でも「交差なし」となっている場合、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項５に記載の図面情報の品質評価方法。
【請求項７】
前記表Ａにおいて、交点Ｐ１の下の行と次の交点Ｐ１の上の行の片方だけ「交差なし」であり、かつ、前記表Ｂにおいて、前記交点Ｐ１の下の行と前記次の交点Ｐ１の上の行が「左側と交差」と「右側と交差」の組合せになっている場合、前記表Ｂの内容を変更して前記表Ｃに「交差なし」と書き込む
ことを特徴とする請求項６に記載の図面情報の品質評価方法。
【請求項８】
前記表Ｃにおいて、交点Ｐの上下の行が「左側と交差」、「右側と交差」の組合せのときに、その交点Ｐで「クリアランスを超えて交差した」と判定し、それ以外の組合せのときは「交差なし」と判定する
ことを特徴とする請求項７に記載の図面情報の品質評価方法。
【請求項９】
前記表Ｃにおいて、「交差なし」の行が存在したとき、「交差なし」の行を削除した前記表Ｃにおいて、複数の連続する交点の上下の行が「左側と交差」、「右側と交差」の組合せのとき、この複数の連続する交点が１つの交差区間を形成し、その交差区間で「クリアランスを超えて交差した」と判定する
ことを特徴とする請求項８に記載の図面情報の品質評価方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【図５２】
【図５３】
【図５４】
【図５５】
【図５６】
【図５７】
【図５８】
【図５９】
【図６０】
【図６１】
【図６２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【図５２】
【図５３】
【図５４】
【図５５】
【図５６】
【図５７】
【図５８】
【図５９】
【図６０】
【図６１】
【図６２】
【公開番号】特開２０１１−１７０５５８（Ｐ２０１１−１７０５５８Ａ）
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願番号】特願２０１０−３２９０７（Ｐ２０１０−３２９０７）
【出願日】平成２２年２月１７日（２０１０．２．１７）
【出願人】（５９３１５４４３６）アイサンテクノロジー株式会社 (1)
【Ｆターム（参考）】
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願日】平成２２年２月１７日（２０１０．２．１７）
【出願人】（５９３１５４４３６）アイサンテクノロジー株式会社 (1)
【Ｆターム（参考）】
[ Back to top ]