(57)【要約】【課題】  ２次元或いは３次元図形のデータを統一的に記録するデータ構造で、データ量が少なく処理効率の優れたデータ構造とこれを読み書きするプログラムを提供する。【解決手段】本発明によるデータ構造は、図形を表現する幾何学形状の線の端点として当該図形を構成する各点に図形を表現するために必要な情報を保持させた点データのみの集合体で図形データを構成して当該図形の表現を可能とし、前記図形を構成する各点の点データは、そのデータ領域に一定の規則に従って順番に記録される当該点と線で結ばれている複数の隣接点の点データ領域のアドレスと、当該点のアドレスが一定の規則で隣接点の各点データ領域に記録された順番が何番目であるかを示す数値とから構成され、当該点データは様々な属性、履歴情報を持つことが出来る。  またこれを実現するプログラムは、本発明の特有の規則に従って前記各点データの入出力を行うプログラム（関数）で構成される。【選択図】    図２８
2006114007.tif 000002
【特許請求の範囲】
【請求項１】
図形データやこれを処理するプログラムを記憶する手段と、前記図形データを処理する演算手段を備えたコンピュータによって描かれた２次元および３次元図形を、再現可能にコンピュータのメモリに記録するための手段であって、当該図形を表現する幾何学形状の線の端点として当該図形を構成する各点に図形を表現するために必要な情報を保持させた点データのみの集合体で図形データを構成し、当該図形の表現を可能とするデータ構造において、前記各構成点のそれぞれの点データを記録する点データ領域に固有のアドレスを割り当てたとき、前記図形を構成する点の点データ領域に、当該点と線で結ばれている複数の隣接点の、点データ領域のアドレスを示すアドレスが、あらかじめ決められた規則に従って順番に記録されることを特徴とする、コンピュータに２次元およびは３次元図形を記憶させるデータ構造。
【請求項２】
請求項１に記載のデータ構造において当該点の点データ領域のアドレスが当該点と線で結ばれた隣接点の各点データ領域に記録された順番はそれぞれ何番目であるかを示す数値が、当該点の点データ領域に記録されることを特徴とするデータ構造
【請求項３】
請求項第１項に記載の、あらかじめ決められた規則とは、２次元図形においては時計回り、又は反時計回りであり、３次元図形においては頂点を図形の外側から見て時計回り、又は反時計回りであること特徴とするデータ構造
【請求項４】
請求項１に記載のデータ構造において、前記点データは属性情報を保持していることを特徴とするデータ構造
【請求項５】
請求項４に記載のデータ構造において、前記点データの属性情報は、当該点Pの座標値又は座標値が記録されている領域のアドレスへのポインター、点の種類を表すためにあらかじめ定められた数値又は文字データ、点の色を表すあらかじめ定められた数値又は文字データ、点に関する処理の種類を表すあらかじめ定められた数値又は文字データ、他の図形データの記録されている領域或いは点に保持させる事象のデータを記録した領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）、又はB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線のいずれかの制御点であることを表すあらかじめ定められた数値又は文字データから選ばれる１又は２以上の属性情報であることを特徴とするデータ構造
【請求項６】
請求項４に記載のデータ構造において、前記点データの属性情報は当該点とその隣接点との間に引かれる線に関する属性情報であることを特徴とするデータ構造
【請求項７】
請求項６に記載のデータ構造において、前記線に関する属性情報は線の種類を表すあらかじめ定められた数値又は文字データ、線の色を表すあらかじめ定められた数値又は文字データ、線が曲線の場合には曲線の定義式データ又は曲線の定義式を記憶している領域のアドレスへのポインター、係数及び変数の定義域データ又は定義域を記憶している領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）、又はB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線のいずれかの種類であることを表すあらかじめ定められた数値又は文字データから選ばれる１又は２以上の属性情報であることを特徴とするデータ構造
【請求項８】
請求項１に記載のデータ構造において、当該対象図形を構成する１個あるいは複数個の点の移動、削除、新たな点の作成、属性の変更又は隣接点の変更により変形する場合、前記変更の行われた各点の点データに、移動、削除、新たに作成された点、属性変更又は隣接点変更の行われた点であることを示す情報と、その変形が当該対象図形の何度目の変形であるかを示す変形回数値が、履歴情報として記録されることを特徴とするデータ構造
【請求項９】
請求項８に記載のデータ構造において、変形が行われた場合その履歴情報としての変形回数値は変形毎に変形回数を１として順次変形回数が加算記録されるものであり、図形の変形が、点の削除によるものの場合は、前記変形回数値にその変形が点の削除によるものであることを示す記号を付記するものであることを特徴とするデータ構造
【請求項１０】
請求項８に記載のデータ構造において、当該対象図形を構成する点の移動、削除、属性変更、又は隣接点変更により図形の変形がなされる場合、各点データには当該点の移動前、削除前、属性変更前、又は隣接点変更前の点データと、移動後、削除後、属性変更後、又は隣接点変更後の点データとが履歴情報として記録されることを特徴とするデータ構造
【請求項１１】
請求項８に記載のデータ構造において、当該対象図形が当該図形を構成する新たな点の作成により変形する場合、当該点の点データはその変形時点における変形回数値を履歴情報として持った新しい点データとして作成され、記録されることを特徴とするデータ構造
【請求項１２】
請求項８に記載のデータ構造において、点の移動、削除、新たな生成、属性の変更、又は隣接点の変更により変形が行われた場合、当該対象図形のデータは各点データと別にその都度、変形回数を１として加算記録した当該対象図形の変更記録を保持していることを特徴とするデータ構造
【請求項１３】
図形データやこれを処理するプログラムを記憶する手段と、前記図形データを処理する演算手段を備えたコンピュータによって描かれた２次元および３次元図形を、再現可能にコンピュータのメモリに記録するとき、当該図形を表現する幾何学形状の線の端点として当該図形を構成する各点に当該図形を表現するために必要な情報を保持させた点データのみの集合体で当該図形データを構成して当該図形の表現を可能とするように、当該図形を構成する前記点の点データをメモリに書き込んだり読み出したりするプログラムであって、
前記各点のデータの記録される領域を確保する命令及び利用目的に従って当該領域のアドレスを読み出す命令と、
当該図形を構成する点と線で結ばれた複数の隣接点の、各点データ領域のアドレスを、あらかじめ決められた規則に従って順番に当該点の点データ領域に書き込む命令及び、利用目的に従って同領域から読み出す命令
を含むことを特徴とするプログラム。
【請求項１４】
請求項１３に記載のプログラムであって、当該点の点データ領域のアドレスが、複数の隣接点の各点データ領域に記録された順番はそれぞれ何番目であるかを示す数値を当該点の点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム。
【請求項１５】
請求項第１３項に記載の、あらかじめ決められた規則とは、２次元図形においては時計回り、又は反時計回りであり、３次元図形においては頂点を図形の外側から見て時計回り、又は反時計回りであること特徴とするプログラム
【請求項１６】
請求項１３に記載のプログラムであって、請求項４に記載の属性情報を前記点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム
【請求項１７】
請求項１３に記載のプログラムであって、請求項８に記載の履歴情報を前記点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム
【請求項１８】
請求項１３に記載のプログラムを用いて２次元図形処理、３次元図形処理、又は２次元と３次元図形の混在する図形の処理をコンピュータで行うことを可能とすることを特徴とするプログラム
【請求項１９】
請求項１３〜１８のいずれか１項に記載のコンピュータプログラムを記録したコンピュータで読みとり可能な記録媒体
【請求項２０】
請求項１３〜１８のいずれか１項に記載のコンピュータプログラムを利用して作成された図形データを記録してデータベース化し、利用可能にしたコンピュータで読みとり可能な記録媒体
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は図形データやこれを処理するプログラムを記憶する手段と、前記図形データを処理する演算手段を備えたコンピュータによって描かれた２次元および３次元図形を、再現可能にコンピュータのメモリに記録するためのデータ構造、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
近年、コンピュータで２次元又は３次元のオブジェクトの形状モデルとして図形処理を行い、処理されたその２次元又は３次元図形のデータを構造化してメモリに記録したり、メモリに記録されている図形データを読み出して様々な処理を行うことはCAD/CAMのように設計や生産に関わる作業ばかりでなく、ロボットの環境認識機構にかかる分野や、科学的シミュレーションの分野、コンピュータ・グラフィックスの分野など広範な分野において大変重要な要素を占めている。
そして特にCAD/CAMの分野においては処理した３次元図形をコンピュータのメモリに記録する方法として様々な方式が提案され利用されている。
初期のCADシステムにおいては、多面体のデータとして頂点と稜線の情報のみを与える方式のデータ構造が多用されてきたが、コンピュータのメモリの大容量化に伴って、より多くの情報を与えることが出来、必要とされる処理がより容易に且つ短時間で可能となる、データに冗長度を持たせたアプリケーション・オリエンテッド方式のデータ構造が採用され、利用されるようになってきた。
【０００３】
今日、CADシステムの基礎的なデータ構造として最も広く採用されているのは、B.  G.  Baumgart によって提案されたデータ構造である「ウィングド・エッジ構造」がより使いやすく改良された「ハーフエッジ構造」と呼ばれるデータ構造である。  前記ハーフエッジ構造は多面体に対する多様な処理操作に柔軟に対応できるデータ構造である。
図３６は従来技術である「ハーフエッジ構造」の説明図である。多面体はその稜線を外部から見たとき、稜線、稜線に隣接する頂点と面の接続関係を示す図３６(a)のようになる。図中、eは稜線、稜線eの下側の頂点はpv、上側の頂点はnv、左上に出る稜線はpccw、左下に出る稜線はpcw、右上に出る稜線はncw、右下に出る稜線はnccw、そして、稜線eに対し左の面はpf、右の面はnfである。
多面体の稜線eは図３６(a)に示すようにそれぞれ２つの面pfとnfが隣接しており、ハーフエッジ構造は多面体の稜線eを左側の面pfに共有される稜線eと右側の面nfに共有される稜線e'の２つに分けて考えるものである。
すなわち、ハーフエッジ構造によるデータ構造では、左側の稜線eに対しては、図３６(b)に示すように稜線eに上側方向に方向を与えて、始点の頂点pvと終点の頂点nv、反時計まわりに入ってくる左側の面の稜線pcw、反時計まわりに出て行く左側の面の稜線pccw、及び左側の面pfに関する情報を与える。そして、更に同じ稜線でありながら方向が反対になっている稜線e'に関する情報も付加する。右側の稜線e'ついても同様に６種類の情報（始点の頂点pv'、終点の頂点nv'、稜線pcw'、稜線pccw'、右の面pf'、稜線eに関する情報）が与えられる。
この構造はデータの冗長度は高いが、対話的な立体形状の変形や、形状演算などCADを利用した形状設計を行う場合に必要とされる各種の処理操作を効率よく実行できると共に、プログラム作成に要する時間の短縮に寄与するとされ、広く使われている。
【非特許文献１】「CAD/CAMシステムの基礎と実際」  古川進、向井伸治著                  ２００２年９月２５日  共立出版株式会社発行  ２２頁
【０００４】
しかし、上記データ構造を持ってしても平面と曲面によって構成される立体図形の場合には、平面と曲面のデータの取り扱い方が異なるため、平面と曲面の接続部分においてデータの整合性をとることが極めて難しく、プログラム作成に要する労力も大きく、また、プログラム自体が必要とする記憶容量の増大と共にデータの必要とする記憶容量も膨大なものになっている。
また、平面と曲面を正確に接続することはあきらめて、画面表示の時にあたかも正確に接続されているかのように表示するための工夫をしているCADシステムも存在する。
しかし、これでは図形の形状は正確に記述されてはいないので、たとえば数値制御工作機械用に工具経路を作成する場合や、積層造形装置に送るデータの作成などの作業時において著しい不都合が生じている。
【０００５】
また図形における曲面に関するデータの取り扱い方は非常に複雑である。２次曲面のように数式で定義される場合には特に幾何情報を取り扱う必要はないが、数式と変数の定義域をデータとして持たせる必要がある。
またSPLINE  (splinecurve)、NURBS（Non-Uniform Rational B-Splines）、B-SPLINE（B-splinecurve）、などの場合は、通過点あるいは制御点の座標値を表の形で持たせる方法が一般的である。更に、３角形パッチなどのように、点がｍ×ｎ個のような縦横の個数のかけ算で表せない場合には、特別なデータ構造を用意しておく必要がある。
このように図形における曲面を表現するためのデータの取り扱いについては、統一的な方法が無く、データ量の多寡や処理効率について議論できるレベルには至っていない。
【０００６】
一方、図形処理において、図形の形状を変更する際の変更履歴を保持する手段に関しては、対話的な形状生成作業において、誤った操作の取り消しや取り消しの取り消しをしたい場合には、コマンドの履歴を別のデータとして保持して、取り消しの命令を実行するときには、与えられた命令をコマンド履歴に従って、最初から実行し直すか、直前の命令が可逆的なものである場合には逆操作を行って操作の取り消しと同等の効果を得る、と言う手段が多く採用されている。また形状の変更の履歴を、同一データ構造内に蓄積しておく方法も考案されているが、この方法では多くの形状データを同一データ構造内に記憶させるため、処理効率の低下を招き、実際のCADシステムで利用されることは少ない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
２次元や３次元のオブジェクトの形状モデルとしての２次元や３次元図形のデータをコンピュータのメモリに記録した後、そのデータを読み出してはその図形に対して様々な処理を行うに当たっては、上記のように、図形の形状によって、複雑な異なるデータ構造で必要とされる処理に対処せざるを得ず、作業量も多く、データ量も膨大となり、処理効率の低下を免れない。また、上記のような稜線を基準としたデータ構造の他、面を基準としたデータ構造も提案されているが、現段階においては、曲面に優れたデータ構造はなく、多くの曲面を複雑に組み合わせて構成される立体図形や、平面と曲面が混在するような立体図形の場合には、平面と曲面、或いは曲面間の関係を統一的に記憶できるデータ構造がないために不都合が多く、曲面処理の難しさの克服が大きな課題になっている。
さらに、図形の形状を変形する際の変形履歴を保持する手段に関して見れば、上記手段では、幾何データが膨大になり、図形の変形の度にそのデータ量が大幅に増加して処理効率が非常に悪くなる問題が大きな課題の１つとなっている。
そこで本発明においては、あらゆる図形のデータを、同一の形式で統一的メモリに記録するための、且つ煩雑な処理が必要とされず作業量の少ない、さらにはデータ量を従来より大幅に削減できる処理効率の優れたデータ構造及び同データ構造で記録されるデータを読み書きする命令を含むプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は上記課題を解決するものであり、コンピュータで処理された２次元および３次元図形を、下記の構成に基づいて再現可能にコンピュータのメモリに記録するためのデータタ構造、プログラム、及び記録媒体を提供するものである。
［１］図形データやこれを処理するプログラムを記憶する手段と、前記図形データを処理する演算手段を備えたコンピュータによって描かれた２次元および３次元図形を、再現可能にコンピュータのメモリに記録するための手段であって、当該図形を表現する幾何学形状の線の端点として当該図形を構成する各点に図形を表現するために必要な情報を保持させた点データのみの集合体で図形データを構成し、当該図形の表現を可能とするデータ構造において、前記各構成点のそれぞれの点データを記録する点データ領域に固有のアドレスを割り当てたとき、前記図形を構成する点の点データ領域に、当該点と線で結ばれている複数の隣接点の、点データ領域のアドレスを示すアドレスが、あらかじめ決められた規則に従って順番に記録されることを特徴とする、コンピュータのメモリに２次元およびは３次元図形のデータを記録するデータ構造。  前記データ領域に記録されるアドレスは領域が確保されるとコンピュータが自動的に割り当てたアドレスそのものを示す数値或いは該アドレスを指し示す記号または文字列（ポインター）であることが出来る。
【０００９】
［２］前記［１］項に記載のデータ構造において当該点の点データ領域のアドレスが当該点と線で結ばれた隣接点の各点データ領域に記録された順番はそれぞれ何番目であるかを示す数値が、当該点の点データ領域に記録されることを特徴とするデータ構造
［３］前記［１］項に記載の、あらかじめ決められた規則とは、２次元図形においては時計回り、又は反時計回りであり、３次元図形においては頂点を図形の外側から見て時計回り、又は反時計回りであること特徴とするデータ構造
【００１０】
［４］前記［１］項に記載のデータ構造において、前記点データは属性情報を保持していることを特徴とするデータ構造
［５］前記［４］項に記載のデータ構造において、前記点データの属性情報は、当該点Pの座標値或いは座標値が記録されている領域のアドレスへのポインター、点の種類を表すあらかじめ定められた数値又は文字データ、点の色を表すあらかじめ定められた数値又は文字データ、点に関する処理の種類を表すあらかじめ定められた数値又は文字データ、他の図形データを記録した領域或いは点に保持させる事象のデータを記録した領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）、又はB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線のいずれかの制御点であるかを表すあらかじめ定められた数値又は文字データから選ばれる１又は２以上の属性であることを特徴とするデータ構造
［６］前記［４項］に記載のデータ構造において、前記点データの属性情報は当該点とその隣接点との間に引かれる線に関する属性情報であることを特徴とするデータ構造
［７］前記［６］項に記載のデータ構造において、前記線に関する属性情報は線の種類を表すあらかじめ定められた数値又は文字データ、線の色を表すあらかじめ定められた数値又は文字データ、線が曲線の場合には曲線の定義式データ又は曲線の定義式を記憶している領域のアドレスへのポインター、係数及び変数の定義域データ又は定義域を記憶している領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）又はB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線、のいずれの種類であるかを表すあらかじめ定められた数値又は文字データから選ばれる１又は２以上の属性であることを特徴とするデータ構造
【００１１】
［８］前記［１］項に記載のデータ構造において、当該対象図形を構成する１個あるいは複数個の点の移動、削除、新たな点の作成、属性の変更又は隣接点の変更により変形する場合、前記変更の行われた各点の点データに、移動、削除、新たに作成された点、属性変更又は隣接点変更の行われた点であることを示す情報と、その変形が当該対象図形の何度目の変形であるかを示す変形回数値が、履歴情報として記録されることを特徴とするデータ構造
［９］前記［８］項に記載のデータ構造において、変形が行われた場合その履歴情報としての変形回数値は変形毎に変形回数を１として順次変形回数が加算記録されるものであり、図形の変形が、点の削除によるものの場合は、前記変形回数値にその変形が点の削除によるものであることを示す記号を付記するものであることを特徴とするデータ構造
［１０］前記［８］項に記載のデータ構造において、当該対象図形を構成する点の移動、削除、属性変更、又は隣接点変更により図形の変形がなされる場合、各点データには当該点の移動前、削除前、属性変更前、又は隣接点変更前の点データと、移動後、削除後、属性変更後、又は隣接点変更後の点データとが履歴情報として記録されることを特徴とするデータ構造
［１１］前記［８］項に記載のデータ構造において、当該対象図形が当該図形を構成する新たな点の作成により変形する場合、当該点の点データはその変形時点における変形回数値を履歴情報として持った新しい点データとして作成され、記録されることを特徴とするデータ構造  
［１２］  前記［８］項に記載のデータ構造において、点の移動、削除、新たな生成、属性の変更、又は隣接点の変更により変形が行われた場合、当該対象図形のデータは各点データと別にその都度、変形回数を１として加算記録した当該対象図形の変更記録を保持していることを特徴とするデータ構造
【００１２】
［１３］図形データやこれを処理するプログラムを記憶する手段と、前記図形データを処理する演算手段を備えたコンピュータによって描かれた２次元および３次元図形を、再現可能にコンピュータのメモリに記録するとき、当該図形を表現する幾何学形状の線の端点として当該図形を構成する各点に当該図形を表現するために必要な情報を保持させた点データのみの集合体で当該図形データを構成して当該図形の表現を可能とするように、当該図形を構成する前記点の点データをメモリに書き込んだり読み出したりするプログラムであって、（１）前記各点のデータの記録される領域を確保する命令及び利用目的に従って当該領域のアドレスを読み出す命令と、（２）前記図形を構成する点と線で結ばれた複数の隣接点の、各点データ領域のアドレスを示すアドレスを、あらかじめ決められた規則に従って順番に当該点の点データ領域に書き込む命令及び、利用目的に従って同領域から読み出す命令とを含むことを特徴とするプログラム。
【００１３】
［１４］前記［１３］項に記載のプログラムであって、当該点の点データ領域のアドレスが、複数の隣接点の各点データ領域に記録された順番はそれぞれ何番目であるかを示す数値を当該点の点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム。
［１５］前記［１３］項に記載の、あらかじめ決められた規則とは、２次元図形においては時計回り、又は反時計回りであり、３次元図形においては頂点を図形の外側から見て時計回り、又は反時計回りであること特徴とするプログラム
【００１４】
［１６］前記［１３］項に記載のプログラムであって、前記［４］項に記載の属性情報を前記点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム
［１７］前記［１３］項に記載のプログラムであって、前記［８］項に記載の履歴情報を前記点データ領域に書き込む命令と利用目的に従って同領域から読み出す命令を含むことを特徴とするプログラム
【００１５】
［１８］前記［１３］項に記載のプログラムを用いて２次元図形処理、３次元図形処理、又は２次元と３次元図形の混在する図形の処理をコンピュータで行うことを可能にすることを特徴とするプログラム
［１９］前記［１３］〜［１８］項のいずれか１項に記載のコンピュータプログラムを記録したコンピュータで読みとり可能な記録媒体
［２０］前記［１３］〜［１８］のいずれか１項に記載のコンピュータプログラムを利用して作成された図形データを記録してデータベース化し、利用可能にしたコンピュータで読みとり可能な記録媒体
【発明の効果】
【００１６】
本発明のコンピュータのメモリに２次元および３次元の図形データを記録するデータ構造によれば、すべての図形のデータは、それぞれが図形の表現のために必用な情報を保持した点データのみの集合体で構成されるのでデータ量が非常に少なく、コンピュータによる処理効率は格段に向上する。
そして、前記当該図形を構成する各点のデータは、互いに隣接点との関係を情報として持っているので煩雑な処理をすることなく目的に応じて、図形上の必要な点を取り出したり、各点の接続関係を導き出したりすることが出来る。
更に、当該図形を構成する各点のデータは当該点或いは当該点と隣接点との間に引かれる直線や曲線などの属性情報を保持することが出来るので、２次元図形、３次元図形、特に平面と曲面の混在する３次元図形においても、全く同一の形式で統一的にデータ構造を構築でき、当該図形データは２次元、３次元の区別が無くメモリに記録可能となる。
また、前記点データに保持される属性情報は、あらかじめ定められた数値又は文字データ又は他の図形へのポインターとして記録されるので、仮にたくさんの属性が記述されたとしても点データ自体のデータ量はさほど増加することはなく、従って図形データの全体量も増加することなくコンピュータにおける処理効率は低下しない。
【００１７】
更に図形を構成する点の点データに図形の変形にかかる情報を変更履歴情報として記憶させておき、図形の変形毎に変形に関係した点データには変形回数値を記憶させることが出来るので、やり直し作業が極めて容易である。
例えば直前に行った行為を取り消す場合には、履歴レベルを１だけ減らした情報をたどれば良く、５段階前の形状に戻りたい場合には、履歴レベルを5減らした情報をたどれば良い。また前記履歴情報を見れば現段階の変形が何回目の変更によるものであるかを容易に知ることが出来るので、本発明のデータ構造による図形データは変形回数が増加しても整然と履歴管理が出来、何回でも戻ったり修正したりの変更ができる作業性の高い図形データとなる。
【００１８】
そして、本発明のデータ構造に記録されているデータを読み書きするプログラムはコンピュータで作成された図形データを本発明のデータ構造に準拠してメモリに記録したり、処理の目的に応じてメモリから読み出したりするプログラムであるので、このプログラムを含む図形処理プログラムは、煩雑なデータ記憶のためのルーチンを必要とせず、データ量の少ないコンパクトな図形データを作成し、処理速度の速い、あらゆる図形を効率的に且つ容易に処理することが出来るプログラムとなる。
また、本発明のデータ構造に準拠すれば、２次元、３次元の図形が同一のデータ構造で扱えるので、これに基づいた２次元、３次元の図形を処理する機能を実現するプログラムは従来にない新しいユニークな図形ソフトの世界を開くプログラムとなる。
また前記コンピュータプログラムを記録したコンピュータ読みとり可能な記録媒体は前記データ構造を活用するコンピュータプログラムを広く容易に提供することを可能とする。
更に、前記プログラムによって作成されたデータベースは、誰でも容易に活用でき、複雑な図形を書く場合の基礎データとして活用可能であり、汎用的で互換性と利便性の高いデータベースとなる。
【発明を実施するための最良の形態】
【００１９】
本発明は、コンピュータで処理されたあらゆる図形をメモリに記憶させるためのデータ構造であり、前記データ構造に準拠してコンピュータのメモリに書き込んだり、利用目的に従ってそのデータの全部又は一部を読み出したりする命令を含むプログラムであり、前記プログラム、或いはそのプログラムによって作成された図形データを記録した、コンピュータで読みとり可能な記録媒体である。
本発明が対象とする図形は、図形化しようとする事象や対象物の形状の如何を問わず、コンピュータ上で直線や曲線の接続として構成される図形、平面のみで構成される図形、平面と曲面で構成される図形、曲面のみで構成される図形など、あらゆる２次元、３次元の図形である。
そして、本発明のデータ構造は、幾何形状を扱うすべての分野において活用されるものである。例えば、機械系CAD/CAMシステムにおける基本的なデータ構造、建築用CADシステムにおけるデータ構造、立体形状データを利用して，積層造形する際のSTLデータへの変換に係るデータ構造、ロボットの環境認識機構において，ロボットの頭脳に当たるコンピュータ内の形状モデルに係るデータ構造、データベースシステムにおいて形状を基本にして類似形状のものを検索する時のデータ構造、原子や分子などの構造解析時のデータ構造、CGやベクトル図形を扱うドロー系ソフトのデータ構造、カーナビや地図情報などにおける図形データのデータ構造、ゲームなどの娯楽産業や教育産業におけるアニメーションシステムのデータ構造、ヴァーチャルリアリティ(VR)による手術ナビゲーション，手術シミュレーションなどの医療応用システムのデータ構造、フライトシミュレータ，天文宇宙シミュレータ，科学理論のイメージ化のためのデータ構造、家電・セキュリティ機器，健康機器その他画面表示機能のある機器において図形データを扱う場合のデータ構造に利用できるものである。
【００２０】
本発明によるデータ構造を図に基づいて説明する。
図１は本発明の、コンピュータで処理された２次元図形をメモリに記録するデータ構造を説明するための２次元図形の例を示し、図２は３次元図形の例を示す。図３〜６は前記図形をメモリに記録するときのデータ構造の概念を示す構成説明図である。
図中、図形Aは２次元図形、図形Bは３次元図形であり、点P、Q、R、Sはそれぞれ対象とする図形の構成点である。図形を構成する点は無数にあるが、ここで言う図形の構成点とは、対象図形をコンピュータで幾何学形状として扱う場合に図形を表現するすべての線の端点を意味するものであり、また１つの端点と線で結ばれる１つ又は複数の端点はすべて隣接点として扱われる。
【００２１】
本発明のデータ構造によれば、対象図形のデータは点データのみの集合体で構成され、各点はそれぞれ図形を表現するために必用な情報を保持した点データとして記録されている。各点データは隣接点との関係を基本としたものであり、複数の隣接点のアドレスを一定の規則に従って配列した表形式で概念的に表現されるので以後隣接点表と呼ぶことにする。
【００２２】
図３に示すデータ構造の概念説明図は２次元の対象図形Ａを構成する点Pが複数の隣接点Q、Rを有する場合の例であり、図４に示すデータ構造の概念説明図は３次元の対象図形Bを構成する点Pが複数の隣接点Q、R、Sを有する場合の例である。
図形Aを再現可能にメモリに記録するための本発明のデータ構造においては、点Ｐ、Ｑ、Ｒには当該点P、Ｑ、Ｒのデータが記録される各点データ領域のアドレス（以後P、Ｑ、Ｒのアドレスと称する）を確保したとき、Ｐの点データ領域にはあらかじめ決められた規則に従って順番に、同点Pと隣接する複数の隣接点Q、Rの、各点のアドレスが点データとして記録される。ここで言う各点のアドレスはコンピュータが割り当てた数値であるが、各点のデータ領域に点データとして記録されるアドレスは以下の説明においてはアドレスと同一の符号を使用しているが、アドレスそのものの数値であっても各アドレスを示す記号又は文字列などのポインターであっても良い。
図形Aの点Pの点データを例示するＰの隣接点表では（１）当該点PのアドレスがP1であり、（２）あらかじめ決められた規則に従って順番に当該点Pのデータ領域に記録される、同点Pと隣接する複数の隣接点Q、Rの各々のアドレスが、Q1、R1である。
同様にQの点データを例示するＱの隣接点表では（１）当該点QのアドレスがQ1であり、（２）あらかじめ決められた規則に従って順番に当該点Qのデータ領域に記録される、同点Qと隣接する複数の隣接点R、Pの各々のアドレスがR1、P1である。
また同様にRの点データを例示するＲの隣接点表では（１）当該点RのアドレスがR1であり、（２）あらかじめ決められた規則に従って順番に当該点Rのデータ領域に記録される、同点Rと隣接する複数の隣接点P、Qの各々のアドレスが、P1、Q1である。
なお図においては隣接点を記録する順序の規則である「あらかじめ決められた規則」は反時計回りであり、以下の説明でも反時計回りとして記述しているが、時計回りとすることも出来る。
【００２３】
図形Ｂをメモリに記録するための本発明のデータ構造においては、点Ｐ、Ｑ、Ｒ、Ｓには当該点P、Ｑ、Ｒ、Ｓのデータが記録される各点データ領域のアドレス（以後P、Ｑ、Ｒ、Ｓのアドレスと称する）が割り当てられると、Ｐの点データ領域にはあらかじめ決められた規則に従って順番に、同点Pと隣接する複数の隣接点Q、R、Ｓの、各点のアドレスが記録される。前記と同様データ領域に記録されるアドレスはアドレスそのものの数値の他に記号や文字列などのポインターであっても良い。
図形Bの点Pの隣接点表では（１）当該点PのアドレスがP1であり、（２）あらかじめ決められた規則に従って順番に当該点Pのデータ領域に記録される、同点Pと隣接する複数の隣接点Q、R、Sの各々のアドレス（ポインター）が、Q1、R1、S1である。
同様にQの隣接点表では（１）当該点QのアドレスがQ1であり、（２）あらかじめ決められた規則に従って順番に当該点Qのデータ領域に記録される、同点Qと隣接する複数の隣接点R、P、Sの各々のアドレスが、R1、P1、S1である。
また同様にRの隣接点表では（１）当該点RのアドレスがR1であり、（２）あらかじめ決められた規則に従って順番に当該点Rのデータ領域に記録される、同点Rと隣接する複数の隣接点S、P、Qの各々のアドレスが、S1、P1、Q1である。
さらに同様にSの隣接点表では（１）当該点SのアドレスがS1であり、（２）あらかじめ決められた規則に従って順番に当該点Sのデータ領域に記録される、同点Sと隣接する複数の隣接点P、R、Qの各々のアドレスが、P1、R1、Q1である。
【００２４】
図５に示すデータ構造は、前記図形Aのデータ構造を示す図３に、当該点Pのアドレスが隣接点Q、Rの各隣接点表の中に記録された順番は何番目であるかを示す数値（以後配置数値と称する）が、追加されて構成される。
同様にQのデータには当該点Qのアドレスが、隣接点R、Pの各隣接点表中に記録された順番は何番目であるかを示す数値（配置数値）が追加されて構成される。
さらにRのデータには当該点Rのアドレスが、隣接点P、Qの各隣接点表中に記録された順番は何番目であるかを示す数値（配置数値）が追加されて構成される。
図中点Pの隣接点表では、当該点Pの配置数値は隣接点Qでは２であり隣接点Rでは１である。同様にQの隣接点表では、当該点Qの配置数値が隣接点Rでは２であり隣接点Pでは１である。また同様にRの隣接点表では、当該点Rの配置数値が隣接点Pでは２であり隣接点Qでは１である。
各隣接点表の中に記録されたアドレスの左側に記入されている数値は、単に各アドレスが記録された順番を示すもので、各隣接点表の構成を説明するために便宜上記入してあるが実際の点データには含まれないので省略しても良い。
【００２５】
図６に示すデータ構造は、前記図形Ｂのデータ構造を示す図４に、当該点Pのアドレスが隣接点Q、R、Ｓの各点データの中に記録された順番は何番目であるかを示す数値（配置数値）が、追加されて構成される
すなわち前記Pの点データに当該点Pの配置数値が追加される。
同様にQのデータには当該点Qの配置数値が追加される。
また、Rのデータには当該点Rの配置数値が追加される。
さらにSのデータには当該点Sの配置数値が追加される。
図中点Pの点データでは、当該点Pの配置数値は隣接点Qでは２であり、隣接点Rでは２であり、隣接点Sでは１である。
同様にQの点データでは、当該点Qの配置数値は隣接点Rでは３であり、隣接点Pでは１であり、隣接点Sでは３である。
同様にRの点データでは、当該点Rの配置数値は隣接点Sでは２であり、隣接点Pでは２であり、隣接点Qでは１である
さらにSの点データでは、当該点Sの配置数値は隣接点Pでは３であり、隣接点Rでは１であり、隣接点Qでは３である
前記同様各点データの中に記録されたアドレスの左側に記入されている数値は、単に各アドレスが記録された順番を示すもので、各点データの構成を説明するために便宜上記入してあるが実際の点データには含まれないので省略しても良い。
【００２６】
図７、図８は本発明の前記データ構造の図４、図５に属性情報を記録する場合の例を示す構成概念図である。  
図形を構成する点Ｐのデータに含まれる属性情報には、点の性質や他図形との関係を規定する点自身に関する属性情報pa1,pa2・・・と、隣接点との間に引かれる線に関する属性情報pb1、pb2・・・とがある。
点Ｑ、Ｒ、Ｓについても同様に点自身および隣接点との間に引かれる線に関する属性情報qa1,qa2・・・qb1,qb2・・・、ra1,ra2・・・rb1,rb2・・・、sa1,sa2・・・sb1,sb2・・・とがある。
【００２７】
前記点自身に関する属性情報としては、当該点Ｐの座標値又は座標値の記録されている領域のアドレスへのポインター、点の種類を表すあらかじめ定められた数値又は文字データ、点の色を表すあらかじめ定められた数値又は文字データ、点に関する処理の種類を表すあらかじめ定められた数値又は文字データ、他の図形データの記録されている領域或いは点に保持させる事象のデータを記録した領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）、及びB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線のいずれかの制御点であることを表すあらかじめ定められた数値又は文字データなどがあり、これらの属性の１又は２以上の情報が図のように当該点Ｐのデータとして記載される。
【００２８】
前記線に関する属性情報は線の種類を表すあらかじめ定められた数値又は文字データ、線の色を表すあらかじめ定められた数値又は文字データ、線が曲線の場合には曲線の定義式データ又は曲線の定義式を記憶している領域のアドレスへのポインター、係数及び変数の定義域データ又は定義域を記憶している領域のアドレスへのポインター、及びスプライン曲線（Spline Curve）、B-スプライン曲線（B-spline Curve）、ベジェ曲線（Bezier Curve）、NURBS曲線（Non-Uniform Rational B-Spline Curve）、細分化曲線（Subdivision Curve）、及びB-スプライン曲線、ベジェ曲線、NURBS曲線以外の自由曲線のいずれかの種類であることを表すあらかじめ定められた数値又は文字データであり、これらの１又は２以上の情報が線の属性情報として記載される。
【００２９】
前記点データに記録される属性情報は、実務上はあらかじめ属性の種類に従って数値を定めておくことが好ましい。例えば図７、図８における点Ｐの隣接点表で隣接点Ｑのアドレスの横pb1の欄に、線に関する属性情報として割り当てた番号を記録しておく。
以下に代表的な、点と隣接点との間に引かれる線に関する属性情報の例を示す。もちろん割り当てた属性情報番号はプログラムによって任意に選択することが出来る。
属性情報番号      処理の内容
１０００      平面を規定する直線
２１００      平面と曲面の境界で曲面はベジェ曲面
２２００      平面と曲面の境界で曲面はＢスプライン  
２３１０      平面と曲面の境界で曲面は細分化曲面（Ｓ曲面）
２３２０      平面と曲面の境界で曲面は細分化曲面（カットマル・クラーク曲面）
２４００      平面と曲面の境界で曲面はスプライン補間曲面
２５００      平面と曲面の境界で曲面はＮＵＲＢＳ、重みは別に定める
２６００      平面と曲面の境界で曲面は２次曲面、条件は別に定める
３１１０      曲面の制御点（ベジェ曲面で４角形パッチ）
３１２０      曲面の制御点（ベジェ曲面で３角形パッチ）
３１３０      曲面の制御点（ベジェ曲面で５角形パッチ）
３２１０      曲面の制御点（Ｂスプライン曲面で４角形パッチ）
・
・
・
【００３０】
これら記載された数値によって処理の仕方は異なる。また例えば属性を１６ビットで表すとすると、６５，５３６種類の異なる属性の処理を行うことが出来る。
このように属性情報をあらかじめ定められた数値又は文字列で与えておき、各点データにはその数値又は文字列を記録しておけばよいので、本発明のデータ構造は点データ自体のデータ量をさほど増やす事なく、すべての点の特性や、隣接点との間に引かれる線について詳しい表現を可能としている。また本発明のデータ構造は、２次元の図形であっても３次元の図形であっても全く同一の形式で取り扱いが可能なので、平面曲面の混在するモデルの取り扱いをも容易にするものである。
【００３１】
本発明によるデータ構造においては、図形の変形が、対象図形を構成する点の移動、削除、追加、属性の変更、又は隣接点の変更によってなされた場合には、その変更は変更履歴情報として各点データに記録保存される。
当該対象図形を構成する１個あるいは複数個の点の移動、削除、新たな点の作成、属性の変更、又は隣接点の変更により変形する場合、変更の行われた各点データに、変更の行われた点であることを示す情報とその変形が当該対象図形の何度目の変形であるかを記す変形回数値が時系列に数値で履歴情報として記録される。
変形が行われた場合その履歴情報には変形毎に変形回数を１として順次変形回数値が加算記録され、図形の変形が、点の削除によるものの場合は、前記変形回数値にその変形が点の削除によるものであることを記す記号を付記する。
このように本発明のデータ構造は、各点のデータ自身に図形の変更に係る情報が記録される構造であり、コンピュータでの処理作業を終了して図形データをファイルに保存した後、再度読み込んで処理作業をする場合にも、従来の図形データの様な履歴にコマンド依存の部分がないので、履歴情報に従って過去の変更のいかなる段階のデータでも自在に取り出すことが出来、作業の効率化に大きく寄与するものである。
【００３２】
対象図形の変形に係る情報を保持するために、本発明のデータ構造では各点のデータに変更前の情報が保持されている。
例えば、当該対象図形を構成する点の移動、削除、属性変更、又は隣接点変更により変形するにあたり、当該点Pの移動前、削除前、属性変更前、又は隣接点変更前の変形回数値iの点をPiとし移動後、削除後、属性変更後又は隣接点変更後の点をP(i＋１)とする場合、当該点Pの点データには移動前、削除前、属性変更前又は隣接点変更前の点Piの点データと移動後、削除後、属性変更後、又は隣接点変更後の点P(i＋１)の点データが記録される。そして、当該対象図形が当該図形を構成する新たな点の作成により変形するにあたり、当該点Qのデータは、図形の変形回数値ｉの時点においては点データQiとして作成される。
このように本発明のデータ構造は図形の変形により変更のあった場合でも、変更前の情報を記憶していて他の情報の参照等を必要とせず、且つトータルのデータ量の増加を最小限に抑えられる整然としたデータ構造である。
また、本発明のデータ構造によれば図形データは図形を構成する点データの集合体で構成されるものであるが、各点データの他に変更記録データを持つことが出来る。
【００３３】
図９〜１２は、本発明のデータ構造における変更履歴に係る概念説明図である。
図９(a)は第１回の変形である履歴レベル１の図形（原図）であり、図９(b)は第２回目の変形である履歴レベル２の図形であり、図９(c)は第３回目の変形である履歴レベル３の図形である。図９において１０は、履歴レベル１における図形、２０は履歴レベル２における図形、３０は履歴レベル３における図形であり、図１０〜１２において１０a、１０b、２０a、２０b、３０a、３０bは点データ、１０c、２０c、３０cは変形回数値で、４０は変更記録データである。
まず第１回の変形による履歴レベル１における図形１０は、図１０に示すように４つの点Ｐ、Ｑ、Ｒ、Ｓの点データで構成される。この場合４つの点Ｐ、Ｑ、Ｒ、Ｓのデータとしてそれぞれ新規に作成された点データＰ１、Ｑ１、Ｒ１、Ｓ１が記録される。すなわち、点Ｐ、Ｑ、Ｒ、Ｓのそれぞれの点データ１０a内には作成されたＰ１、Ｑ１、Ｒ１、Ｓ１の各点データ１０ｂが記録される。
そして前記作成された点Ｐ１、Ｑ１、Ｒ１、Ｓ１の点データ１０b内には図形の変形が何度目の変形であるかを示す変形回数値１０cが記録される。ここでは１回目の変形なので「１」がそれぞれ記録されている。
なお図中、作成された点Ｐ１、Ｑ１、Ｒ１、Ｓ１の点データ１０b内にＮＵＬＬとあるのは、点Ｐ１、Ｑ１、Ｒ１、Ｓ１が点Ｐ、Ｑ、Ｒ、Ｓの最初のデータとして作成されたものであり、それ以前に当該点に係る変形は無いと言うことを情報として記憶していることを示している。
また変更記録データ４０には、第１回の変形であることを示す数値１が記録される。
【００３４】
次に図９(b)に示す図形２０は図９(a)の図形１０の点ＰとＱの間に点Ｔが新規に追加作成されたもので、これによる前記図形の変形は２回目であり履歴レベルは２となる。この場合新規に作成される点はＴであり、点Ｔの作成により点データの内容に変更を生ずるのは点ＰとＱである。
図１１において点Ｔのデータとして新たに作成された点Ｔ1が記録され、同点Ｔのデータ２０a内には作成された点Ｔ1の点データ２０bが記録される。そして作成された、前記Ｔ1の点データ２０b内には、図形の変形が何度目の変形であるかを示す、変形回数値２０cが記録される。ここでは２回目の変形なので「２」が記録されている。
また点ＰとＱの点データは、点Ｔが作成されたことにより隣接点の関係が変更される。そこで点ＰとＱの点データ２０aには変更前の点であるＰ1、Ｑ1の点データ１０bと変更後の点であるＰ2、Ｑ2の点データ２０bが記録され、２回目の変形により作成されたことを示す変更回数値２０cが記録される。ここでは変形回数値は「２」である。
このように点ＰとＱの点データ２０aには、隣接点の関係の変更により、新たに点Ｐ2、Ｑ2が作成されているが、点の移動や属性の変更による変形の場合も同様である。
また変更記録データ４０には、第２回の変形であることを示す数値２が記録される。
【００３５】
そして図９（ｃ）に示す、第３回目の変形による履歴レベル３における図形３０は、図９(b)の図形２０の点Ｓと点Ｑの間に配置されていた点Ｒが削除されて構成されている。この場合削除される点はＲであり、点Ｒの削除により、点データに変更があるのが、点Ｑと点Ｓになる。点Ｒが削除されるに当たり、点Ｒ2のデータが作成され、図１２に示すように同点Ｒの点データ３０a内には削除される前の点Ｒ１の点データ１０ｂと、削除後の点Ｒ2の点データ３０bが記録される。
そして削除された点Ｒ2の点データ３０b内には当該削除が図形の何度目の変形として行われたかを示す変形回数値３０cが記録される。ここでは３回目の変形なので「３」が記録され、その変形が削除されたものであるので、削除による変形であることを示す記号、ここでは「−」が付記される。
また点Ｑの点データ３０aには、変更前の点Ｑ1の点データ１０b、Ｑ2の点データ２０b及び変更後の点Ｑ3の点データ３０b、そして点Ｓの点データ３０aには、変更前の点Ｓ1の点データ１０bと変更後の点Ｓ2の点データ３０bが記録され、３回目の変形により作成されたことを示す変形回数値３０cがともに記録される。ここでの変形回数値は「３」である。
さらに変更記録データ４０には３回目の変形であることを示す数字３が記録される。
【００３６】
そして図形データは、点の移動、削除、新たな生成、属性の変更、又は隣接点の変更により変形が行われるとその都度、変形回数を１として図１０〜１２に示すように当該対象図形の変更記録データ４０に順次変形回数を加算記録して保持し、変更履歴を管理可能とする。そして変形前に戻る場合には何段回前であっても変形記録データの数値を指定することにより変更過程の任意の時点に戻っての編集を可能とする。
前記変更記録データ４０は、戻り操作をした場合、現段階の図形が変更過程のどの段階にあるかを各点データに知らせる。
例えば変形が３０回されたとすると、変更記録データ４０には３０が記録される。そして、その後５段階前の変更過程に飛ぶ戻り操作がされた場合、変更記録データ４０は２５を記録する。
すなわち前記変更記録データ４０に記録されている数値が、現段階の図形であり、各点データは、変形回数２５以下の最新の情報で図形を表現する。すなわち２６、２７、２８、２９、３０回目の変形による情報は現段階の図形に係る情報でないことを、各点データは変更記録データ４０の数値で認識する。
【００３７】
前記のように、図形を構成するすべての点のデータに図形の変形に係る情報を記録しておき、各点のデータには変更回数値を記録し、さらに対象図形に変更記録データ４０を記録しておくことにより、例えば直前に行った行為を取り消す場合、履歴レベルを１だけ減らした情報をたどれば良く、また変更記録データ４０に、現在編集中の図形が何回目の変更のものであるかが記録されているので、変形回数が増加しても点データの交錯はなく、整然と履歴が管理され、何回でもどの段階へでも自在に戻ることが出来る作業性の高い図形データを本発明は提供するものである。
【００３８】
本発明のデータ構造の入出力を受け持つプログラムは、ＣＤ−ＲＯＭ、半導体やＩＣなどの記録媒体に書き込んで実現することが出来る。
同プログラムは図形の各点データの新規作成、削除、変更など各段階で前記データ構造になるようにメモリに書き込んだり、目的に応じて本データ構造特有の規則に従って読み出したりするものであり、本プログラムを含むアプリケーションプログラムは、２次元、３次元の平面・曲面の混在する図形を簡単に処理出来る画期的なものである。
【００３９】
図１３は図２に示す図形Ｂを作成するプログラム（関数）のフローチャートを示す。
まず、３つの隣接点を有する点Ｐのデータ領域を確保し、この領域内に属性情報として点Ｐの座標値を書き込む。
次に３つの隣接点を有する点Ｑのデータ領域を確保し、この領域内に属性情報として点Ｑの座標値を書き込む。
次に３つの隣接点を有する点Ｒのデータ領域を確保し、この領域内に属性情報として点Ｒの座標値を書き込む
次に３つの隣接点を有する点Ｓのデータ領域を確保し、この領域内に属性情報として点Ｓの座標値を書き込む
次に点Ｐの隣接点表の１番目に点Ｑ（のアドレス）と配置数値２を書き込み、２番目に点Ｒ（のアドレス）と配置数値２を書き込み、３番目に点Ｓ（のアドレス）と配置数値１を書き込む。
同様に点Ｑの隣接点表の１番目に点Ｒと配置数値３を書き込み、２番目に点Ｐと配置数値１を書き込み、３番目に点Ｓと配置数値３を書き込む。
次に点Ｒの隣接点表の１番目に点Ｓと配置数値２を書き込み、２番目に点Ｐと配置数値２を書き込み、３番目に点Ｑと配置数値１を書き込む。
次に点Ｓの隣接点表の１番目に点Ｐと配置数値３を書き込み、２番目に点Ｒと配置数値１を書き込み、３番目に点Ｑと配置数値３を書き込む。
以上のプログラム（関数）により点Ｐ、Ｑ、Ｒ、Ｓによって構成される図形Ｂが作成されるが、属性情報として座標値を書き込まない場合には各点データは隣接点との相互の関係だけを規定するものであり、目視できる図形を表現するものではないが、例えば脳細胞のような相互の関連だけを重視する抽象的な事象に対する解析データとして活用できる。
【００４０】
図１４から図２２に前記図形を表現する点データの入出力に関するプログラムの例をフローチャートによって示す。
ここではフローチャートを説明する都合上、隣接点表中に記載される隣接点アドレスの記録される順番は表の行の順序と同一と見なしｉ行、ｊ行（ｉ,ｊ＝１，２，３・・・）はｉ番目、ｊ番目にデータが記録されることを意味するものとする。
図１４はＮ個の隣接点を有する新しい点Ｐを生成して隣接点関係をデータ領域に書き込むプログラム（関数）のフローチャートである。
図においてまずＮ個の隣接点を有する点の情報を格納する記憶領域即ち当該点の点データ領域を確保し、当該点をＰとして点Ｐの属性及び隣接点数Ｎを書き込む。ここでＮ＝０の場合は分岐して終了するが、Ｎ＝０でなければつぎのステップへ進む。
Ｐの隣接点Ｐ１に対してＰｉを反時計回りにたどって記録する場合のｉ番目（ｉ=1）の隣接点ＰｉのアドレスＰｉをＰの隣接点表（Ｐの点データ）のｉ行目（ｉ番目）に書き込む。
次に点ＰのアドレスをPｉの隣接点表の中に、隣接点Ｐｉから見て反時計回りにj番目の行位置（記録順番）に追記する。
次に点Pｉの隣接点表のｊ行目（ｊ番目）に行番号ｉ（配置数値ｉ）を書き込む。
次に点Ｐの隣接点表のｉ行目（ｉ番目）に隣接点Ｐのアドレスが追記された行番号（配置数値）ｊを書き込む。
次に点Ｐｉの隣接点表において点Ｐの追記によって記憶位置（記録順番）の変わった隣接点の隣接点表において点Ｐｉの記憶位置の行番号（配置数値）を１つ増やす。
ｉ＝Ｎでない場合にはｉ＝ｉ＋１として２番目の隣接点Ｐ２に対して前記のステップを繰り返す。ｉ＝Ｎになった時点でこのプログラム（関数）の実行を終了する。
【００４１】
図１５は図形データから点Ｐを削除するプログラム（関数）のフローチャートである。
まず点Ｐの隣接点数ｎを読み出す。
ｎ＝０の場合は分岐して、点Ｐの情報を格納している記憶領域（点Ｐのデータ領域）を開放して終了する。
ｎ＝０でない場合には、点Ｐの隣接点表のｉ行目（ｉ番目）の点Ｐｉの隣接点表から、点Ｐのアドレスが記憶されている行を削除する。
次に点Ｐｉの隣接点数を１つ減らす。
次に点Ｐｉの隣接点表において削除により記録位置が変わった隣接点の隣接点表における点Ｐｉの記憶位置の配置数値を１つ減らす。
ｉ＝ｎになるまでこの動作を繰り返し、ｉ＝ｎになった時点で点Ｐのデータ領域を開放してプログラム（関数）の実行を終了する。
【００４２】
図１６は点Ｐ１と点Ｐ２を接続するプログラム（関数）のフローチャートである。
まず点Ｐ２を点Ｐ１の隣接点表で反時計回りに記録する順番の行位置ｍに追加する。
次にＰ１の隣接点数を１つ増やす。
次に点Ｐ１の隣接点表において追加によって記憶位置が変わった隣接点の隣接点表において点Ｐ１の記憶位置の配置数値を１つ増やす。
次に点Ｐ１を点Ｐ２の隣接点表で反時計回りに記録する順番の行位置ｎに追加する。
次にＰ２の隣接点数を１つ増やす。
次に点Ｐ２の隣接点表において追加によって記憶位置が変わった隣接点の隣接点表において点Ｐ２の記憶位置の配置数値を１つ増やす。
次にＰ１の隣接点表のｍ行目に行番号ｎを書き込む。
最後にＰ２の隣接点表のｎ行目に行番号ｍを書き込む。
以上で２点Ｐ１とＰ２の接続がなされ隣接点としての関係が生ずる。
【００４３】
図１７は点Ｐ１とＰ２の接続を削除し、２点の隣接点関係を解消するプログラム（関数）のフローチャートを示す。
まず点Ｐ１の隣接点表から点Ｐ２のアドレスが記録されている行を削除する。
次に点Ｐ１の隣接点数を１つ減らす。
次に点Ｐ１の隣接点表において、削除により記録位置が変わった隣接点の隣接点表における点Ｐ１の記録位置の行番号を１つ減らす。
次に点Ｐ２の隣接点表から点Ｐ１が記録されている行を削除する。
次に点Ｐ２の隣接点数を１つ減らす。
最後に点Ｐ２の隣接点表において、削除により記録位置が変わった隣接点の隣接点表における点Ｐ２の記録位置の配置数値を１つ減らす。
以上により点Ｐ１とＰ２との接続は削除され、点Ｐ１とＰ２の隣接点関係は無くなる。
【００４４】
図１８は点Ｐ１と点Ｐ２から反時計回りにＫ番目の隣接点を取り出すプログラム（関数）のフローチャートを示す。
まず点Ｐ１の隣接点表で点Ｐ２の記録位置の行番号ｍを読み出す。
次に点Ｐ２の隣接点数ｎを読み出す。
次に点Ｐ２の隣接点表の（ｍ＋ｎ−Ｋ−１）ｍｏｄ ｎ）＋１行目の隣接点を読み出す。
以上で反時計回りのＫ番目の隣接点を取り出すことが出来るが、時計回りにＫ番目の隣接点を取り出す場合は図１９のフローチャートに示すプログラム（関数）となる。
まず点Ｐ１の隣接点表で点Ｐ２の記録位置の行番号ｍを読み出す。
次に点Ｐ２の隣接点数ｎを読み出す。
次に点Ｐ２の隣接点表の（ｍ＋ｎ＋Ｋ−１）ｍｏｄ ｎ）+１行目の隣接点を読み出す。
【００４５】
図２０は点Ｐ１と点Ｐ２の間に新しい点Ｐ３を生成するプログラム（関数）のフローチャートを示す。
まず２個の隣接点を持つ点Ｐ３のデータ領域を確保する。
次に点Ｐ３の座標値、属性及び隣接点数２を書き込む。
次に点Ｐ１の隣接点表で点Ｐ２の記録位置（記録順番）ｍと行番号（配置数値）ｎを読み出す。
次に点Ｐ３の隣接点表の１行目に点Ｐ１のアドレスと行番号（配置数値）ｍを書き込む。
次に点Ｐ３の隣接点表の２行目に点Ｐ２のアドレスと行番号（配置数値）ｎを書き込む
次に点Ｐ１の隣接点表のｍ行目に点Ｐ３のアドレスと行番号（配置数値）１を書き込む
次に点Ｐ２の隣接点表のｎ行目に点Ｐ３のアドレスと行番号（配置数値）２を書き込む。
以上によって点Ｐ１と点Ｐ２の隣接点関係は解消され新たにＰ１とＰ３、Ｐ３とＰ２との間に隣接点関係が生まれる。
【００４６】
図２１は点Ｐ１と点Ｐ２の左側の面を構成する点列を反時計回りに取り出すプログラム（関数）のフローチャートを示す。
まず点Ｐ１のアドレスを点ＰＡに代入し、同様に点Ｐ２についても点ＰＢに代入する。
次に点ＰＡの隣接点表で点ＰＢの記録位置の行番号ｍを読み出す。
次に点ＰＢの隣接点数ｎを読み出す。
次に点ＰＢの隣接点表の  （（ｍ＋ｎ−２）ｍｏｄ  ｎ）＋１行目の隣接点を面の構成点として読み出すとともに、点ＰＣにも代入する。
点ＰＣが点Ｐ１のアドレスと一致するまで、点ＰＢを点ＰＡに代入し、点ＰＣを点ＰＢに代入し上記処理を繰り返す。
以上のプログラム（関数）によって点Ｐ１、Ｐ２、Ｐ３・・・で囲まれた面を反時回りに取り出すことが出来るが、これを時計回りに取り出したい場合は上記プログラム（関数）の式を
（（ｍ＋ｎ）ｍｏｄ  ｎ）＋１とすればよい。
このプログラム（関数）のフローチャートを図２２に示す。
【００４７】
次に図２３に履歴管理を行う場合のプログラム（関数）のフローチャートの例を示す。
点Ｐに変更が生じて図形が変形する場合には、
まず、点Ｐの履歴レベルと現在の履歴レベルを比較し、
これが異なる場合には点Ｐと同じ大きさの点データ領域を確保する。
次に新しいデータ領域に点Ｐのデータを複写する。
次にデータの複写された新しいデータ領域に現在の履歴レベルを書き込む（上書き）。
次にデータの複写された新しいデータ領域に点Ｐの変更前のアドレスを書き込み変更前のデータとの関係を維持し、変更後のアドレスを点Ｐのアドレスとする。
一方、前記点Ｐの履歴レベルと現在の履歴レベルを比較したとき履歴レベルが同じ場合には前記ステップをとばして次のステップへ進む。
そして点Ｐのデータ領域に隣接点のアドレス、配置数値、座標値その他の属性など必要なデータを書き込む（上書き）。
以上のプログラム（関数）によって、点Ｐに変更が生じた場合の履歴管理が可能となる。
【実施例１】
【００４８】
本発明によるデータ構造の実施例を以下に詳述する。
図２４は本発明によるデータ構造の実施例の説明用２次元図形を示す図である。
図中１は２次元図形で、点Ｖ0、Ｖ1、Ｖ2、Ｖ3、Ｖ4、Ｖ5、Ｖ6、Ｖ7、Ｖ8、Ｖ9、Ｖ10、Ｖ11、Ｖ12、Ｖ13、Ｖ14は２次元図形１を構成する点である。
同図形をメモリに記録するためのデータ構造は、同図を構成する複数の点データの集まりであり、各点データはそれぞれ図形の表現に必用な情報を保持している。
図２４において、まずＶ0の隣接点はＶ0と線で結ばれている点はＶ1、Ｖ3、Ｖ6、Ｖ7であるので、点Ｖ0の点データには隣接点を反時計回りに点Ｖ1、Ｖ3、Ｖ6、Ｖ7の順に各点のアドレスＶ1、Ｖ3、Ｖ6、Ｖ7が順番に記録される。また各隣接点Ｖ1、Ｖ3、Ｖ6、Ｖ7も同様な形で記録されており、各隣接点の中で、点Ｖ0のアドレスが何番目に記録されているかを示す数値が、Ｖ0の点データ中に記録される。ここでは隣接点を反時計回り（Counter Clockwise）の規則の順に記録しているが、時計回り（Clockwise）の規則に従っても良い。
【００４９】
図２５は前記図形を構成する点Ｖ0の点データの構成概念を示すＶ0の隣接点表である。
図中２はＶ0のアドレスであり、３は隣接点のアドレス、４は各隣接点のデータ（隣接点表）において点Ｖ0のアドレスが記録されている順番が何番目かを示す数値（配置数値）、５は隣接点のアドレスが記録される順番でありここでは説明上順番を示すために数値が記入されているが実際のデータにはこの数値は含まれない。６は属性情報である。なお隣接点はあらかじめ決められた規則に従って順番に記録されるものであり、前記においては反時計回りと言う規則に従っており、隣接点のアドレス３はここでは反時計回りに５に示す順番で記録される。
【００５０】
図２６は前記図形のすべての点についての点データを一覧表形式で表示したものでありこの点データのみの集合体（隣接点表の一覧表）で図形データは構成される。
図２６のデータ構造から図２4に示す領域Ａを抽出する方法について説明する。領域Ａは点Ｖ0を出発点としてＶ3、Ｖ5、Ｖ9、Ｖ6を経てＶ0に戻る線で囲まれている。ここでは配置数値に１を加算或いは減算した場合に、参照隣接点表に配置数値に１を加算或いは減算した数値（記録順番）がない場合は、例えば、配置数値が３で、１の加算により参照隣接点表の４番目を参照しなければならないが当該隣接点表に４番目が無い場合は１番目に戻るようにし、配置数値が１で１の減算により参照数値が０となる場合は最後の数値を参照するものとする（隣接点表の順番の循環）。
まず図２６において、点Ｖ0の隣接点表では、点Ｖ3のアドレスＶ3は２番目であり、前記Ｖ3の隣接点表において点Ｖ0のアドレスが何番目に記録されているかを示す数値（配置数値）は３となっている。
次に前記Ｖ3の配置数値３から１を引くと２となるので、点Ｖ3の隣接点表の２番目が導かれる。点Ｖ3の隣接点表の２番目を見ると点Ｖ5のアドレスＶ5があり、Ｖ5の配置数値は１であることがわかる。
そして前記Ｖ5の配置数値１から１を引く。配置数値１から１を引くと０となり隣接点表には０の場所がないので、点Ｖ5の隣接点表で最後の数値を参照する。すると点Ｖ9が記録されているアドレスＶ9があり、配置数値は１である。
同様にＶ9の配置数値１から１を引くと０となるので点Ｖ9の隣接点表で最後の数値を参照する。するとＶ6のアドレスＶ6があり、配置数値は２である。
同様に配置数値２から１を引くと１になるので、点Ｖ6の隣接点表の１番目を参照する。するとＶ0のアドレスＶ0が導き出される。
すなわち領域Ａに沿って１周したことになり、領域Ａが抽出されたことになる。
前記において配置数値から１を引く操作は領域を反時計回りにたどることを意味し、もし時計回りにたどる場合には配置数値に１を足す操作をすればよい。
【００５１】
なお以下に、点Ｖiの隣接点表のj番目に書かれている点Ｖmのアドレスへ移る動作を記号Eを使って、
Vm  ＝  E［Vi（j）］
と書くことにする。
ここでVi（j）は点Ｖiの隣接点表のj番目に書かれている点Ｖmのアドレスで、Ｅが実際にＶmに移る動作を表している。この記号Ｅを使い、Ｐjを点Ｖiの隣接点表のj番目に書かれている点Ｖmの配置数値欄の数、点Ｖｉの隣接点の個数をＫ、ＸｍｏｄＫを、ＸをＫで割った余りとすると、点Ｖi、Ｖmの反時計回りに移る作業は
Ｖn  ＝  Ｅ［Ｖm（（（Ｐj−１＋Ｋ−１）ｍｏｄＫ）＋１）］  （５１−１）
と表される。００５０における説明では「配置数値に１を加算或いは減算した場合に、参照隣接点表に配置数値に１を加算或いは減算した数値（記録順番）がない場合は、例えば、配置数値が３で、１の加算により参照隣接点表の４番目を参照しなければならないが当該隣接点表に４番目が無い場合は１番目に戻るようにし、配置数値が１で１の減算により参照数値が０となる場合は最後の数値を参照する」と定めたが、前記の式（５１−１）ではこのことを考慮しなくても良い。
【００５２】
前述の図２４において、領域Ａは点Ｖ0、Ｖ3、Ｖ5、Ｖ9、Ｖ6によって構成される５角形領域なので、領域Ａの面積は以下のようにして容易に求めることが出来る。
まず、適当な位置に点Ｏを配置し、△ＯＶ0Ｖ3の面積を計算する。同様に△ＯＶ3Ｖ5、△ＯＶ5Ｖ9、△ＯＶ9Ｖ6、△ＯＶ6Ｖ0の面積を計算して、すべて足しあわせれば領域Ａの面積が求められる。隣接点間を結ぶ線が曲線の場合であっても領域ＯＶ0Ｖ3、ＯＶ3Ｖ5、ＯＶ5Ｖ9、ＯＶ9Ｖ6、ＯＶ6Ｖ0の面積が計算できれば全く同様に領域Ａの面積が計算できる。また、前記曲線の計算が複雑になってしまって正確な面積が求めにくいような場合でも、上記手段によれば近似的な面積の計算は可能である。
【００５３】
図２７は前記図形データに属性として高さ情報を記録したものである。各点の属性としての高さ情報はここでは各点データ（隣接点表）の一番下に表示されている。
ここでは図２７に示す隣接点表即ち図形データから以下の方法で近似的に等高線を求める。
例えば高さ１００ｍの所を探したいときには、高さ０の点とその隣接点の高さを比較する。すなわち、高さ０と隣接点の高さとの差が１００ｍ以上ある場合には、その中間に１００ｍの点があることになる。点Ｖ0とＶ3はそれぞれ０ｍと５００ｍの高さなのでこれら２点が直線で結ばれている場合には点Ｖ0とＶ3を結んだ線の点Ｖ0から５分の１の点Ｐ１００を高さ１００ｍの点とする。（図２４）
同様の計算をして  、点Ｖ0とＶ6の間の点Ｑ１００を１００ｍの高さとする。さらに点Ｖ1、Ｖ2・・・Ｖ7について同様な計算を行うと、高さ１００ｍの点列が得られる。これらの点を結ぶことによって高さ１００ｍの近似的な等高線を引くことが出来る。高さがすべて直線的に変化し、かつ隣接点を結ぶ線が直線の場合には正確な等高線が得られる。
【００５４】
このようにして等高線が得られれば山の稜線や谷線なども表示でき、また雨が降ったときにどこが最も急流になるのかなども予測できる。天気図と組み合わせることによって、局所的な大雨の時にどこが危険か、安全なところはどこかなどと言った情報が自動的に得られる事になる。
また隣接点を結ぶ線が道路である場合には、各点を交差点とし、この点における交通量を属性として記憶しておけば、交通情報も容易に得られる。道路の総延長距離やその他の道路に関する様々な情報も得られる。
前記図形のデータを組合せ、さらに別の図形データを組み合わせることにより詳細な地図とともに、我々の生活に必要とされる各種の情報が求められる。
このように本発明のデータ構造は図形を構成するそれぞれの点に、様々な角度から必要な多くの属性を持たせることが出来るので、その用途は幅広く、応用範囲の広いデータ構造である。しかも、図形は点データのみの構成であり、各点データも中身は単純な数値やポインターなどで構成されているのでデータ量は少なくコンピュータの処理速度も速い。
【実施例２】
【００５５】
次に本発明の３次元図形における実施例を詳述する。
図２８は３次元図形を示すもので、点Ｖ0、Ｖ1、Ｖ2、Ｖ3、Ｖ4、Ｖ5、Ｖ6、Ｖ7は当該図形７を構成する点である。
本発明のデータ構造においては、前記各点がそれぞれ図形を表現するのに必用な情報を保持した点データとして記録されている。
図２８の図形７においては、まずＶ0の隣接点はＶ0と直線で結ばれている点Ｖ1、Ｖ3、Ｖ4であるので、点Ｖ0の点データには隣接点を反時計回りに点Ｖ1、Ｖ3、Ｖ4の順に各点のアドレスＶ1、Ｖ3、Ｖ4が順番に記録される。また各隣接点Ｖ1、Ｖ3、Ｖ4も同様な形で記録されており、各隣接点の中で、点Ｖ0のアドレスが何番目に記録されているかを示す配置数値が、Ｖ0の点データ中に記録される。
ここでは隣接点を反時計回り（Counter Clockwise）の規則の順に記録しているが、時計回り（Clockwise）の規則に従っても良い。
【００５６】
３次元図形７を表現する図形データも、前述の２次元図形の実施例で説明したのと同様な点データの集合体で構成され一覧表形式で表現される。
図２９は３次元図形７のデータ構造を示す図であり、図形７を構成する各点データを隣接点表の形式で表したものである。
図２９に基づいて３次元図形７の任意の面を描く方法を説明する。
点Ｖ0は点Ｖ1、Ｖ3、Ｖ4の３つの隣接点を有している。前記隣接点の内、例えば隣接点Ｖ3との関係で描く図形を導き出すとする。
点Ｖ0の隣接点表で、隣接点Ｖ3は２番目の隣接点として記録されている。そして前記隣接点Ｖ3のアドレスはＶ3であり、配置数値は１であることが分かる。そこで、Ｖ3の配置数値１に１を加算、或いは減算する。すなわちＶ0の隣接点から時計方向に回る場合は配置数値に＋１、反時計方向に回る場合には配置数値に−１を加える。
本実施例においては、時計回りを選択しＶ3の配置位置１に１を加えると、２となるのでＶ3の隣接点表中で２番目の隣接点へ導かれる。Ｖ3の隣接点表中で２番目にあるのはＶ2である。そしてＶ2の配置数値は１である。
Ｖ2の配置数値１に１を加えると２となり、Ｖ2の隣接点表中の２番目に記録されたＶ1に導かれ、その配置数値は１である。
そこでこれに１を足すと２なので点Ｖ1の隣接点表の２番目を見ると、点Ｖ0であり、これは出発点であるので□Ｖ0Ｖ3Ｖ2Ｖ1を導き出すことが出来る。
【００５７】
３次元の図形においても、点Ｖiの隣接点表のj番目に書かれている点Ｖmのアドレスへ移る動作を記号Eを使って、
Vm  ＝  E［Vi（j）］
と書くことが出来る。
ここでVi（j）は点Ｖiの隣接点表のj番目に書かれている点Ｖmのアドレスで、Ｅが実際にＶmに移る動作を表している。この記号Ｅを使い、Ｐjを点Ｖiの隣接点表のj番目に書かれている点Ｖmの配置数値欄の数、点Ｖｉの隣接点の個数をＫ、ＸｍｏｄＫを、ＸをＫで割った余りとすると、点Ｖi、Ｖmを結ぶ線の左側の面に対して反時計回りに点Ｖnを導き出す作業は
Ｖn  ＝  Ｅ［Ｖm（（（Ｐj−１＋Ｋ−１）ｍｏｄＫ）＋１）］    （５７−１）
と表される。
また右側の面に対して時計回りに点Ｖnを導き出す作業は
Ｖn  ＝  Ｅ［Ｖm（（（Ｐj＋１＋Ｋ−１）ｍｏｄＫ）＋１）］  （５７−２）
と表される。
【実施例３】
【００５８】
図３０は閉じた領域を有する３次元図形８aと閉じた領域を持たない図形８bが点Ｖ１を共有している、いわゆる非多様体の図形８の例である。図形８aの点Ｖ１以外の点データに対する取り扱いは前記と同様である。但し、図形８ｂは閉じた領域を有していないので、外から見て時計回り又は反時計回りになるように隣接点の順序を決めることができないので、点Ｖ１における隣接点の順序はたとえば、Ｖ１０、Ｖ１２、Ｖ１４と定める。Ｖ１０、Ｖ１４、Ｖ１２の順序でも良い。
点Ｖ１の隣接点の順序をＶ１０、Ｖ１２、Ｖ１４と定めると、図形８bの面Ｆ１を矢印の方向から見て、面Ｆ１の構成頂点を反時計回りに取り出すときには、前記の式（５７−１）が利用できる。ただし、式（５７−１）の式中に現れる数Ｋは面Ｆ１の構成頂点の数とする。
図３０の図形８a及び８bの点Ｖ１の点データは図３１のように構成する。点Ｖ１の点データを図形８ａの隣接点データと図形８ｂの隣接点データに分け、図形８ａの隣接点データを表の上に、図形８ｂの隣接点データを表の下に記憶させる。点Ｖ１に対する図形８ｂの隣接点がＶ１０、Ｖ１２、Ｖ１４と順序付けられていれば、図３０の面Ｆ１を矢印の方向から見たとき、面Ｆ１のＶ１、Ｖ１０の次の構成点Ｖ１１を反時計回りに取り出す計算は
Ｖ１１＝Ｅ［Ｖ１０（（（Ｐj−１＋Ｋ２−１）ｍｏｄＫ２）＋Ｋ１＋１）］  （５８−１）
と表される。ただし、Ｋ１は点Ｖ１の図形８ａに属する隣接点の数であり、Ｋ２は図形８ｂに属する隣接点の数である。また、Ｐｊは点Ｖ１の隣接点Ｖ１０に対する配置数値である。面Ｆ１を矢印の方向から見たとき、面Ｆ１の構成点を反時計まわりに取り出すときには、すべて式（５８−１）と同様な計算を行うことにすれば、図３０の点Ｖ１１・Ｖ１２・・・の隣接点の順序は自動的に決まる。
【実施例４】
【００５９】
図３２は別の実施例を示す説明図で点Ｃ0〜Ｃ11の点列を示している。
例えばＣ1を出発点としてＣ4、Ｃ7、Ｃ10を順次取り出すときには図３３に示す隣接点表の配置数値に２を加算或いは減算する。なお配置数値に２を加算或いは減算した時に、隣接点表にその加算された数値の順番が無い場合、例えば配置数値が３で２の加算により隣接点表の５番目を参照しなければならないが、隣接点表に１つ下の４番目までしかデータが無い場合は５番目の代わりに１番目に戻るようにし、また配置数値が４で２の加算により隣接点表の６番目を参照しなければならないが、隣接点表に２つ下の４番目までしかデータが無い場合は６番目の代わりに２番目に戻るようにする。そして２を減算した数値が０になる場合は隣接点表の最後を参照し、−１になる場合は最後から２番目を参照する。
図３２のような格子状に与えられた点列を縦方向或いは横方向にたどって順次点列を取り出す作業は曲面の生成の際に常に行われるものである。
【実施例５】
【００６０】
本発明のデータ構造において図３４に示す円筒面を有する３次元図形Ｃを形成する方法を示す。点Ｖ１，Ｖ２，Ｖ５，Ｖ６以外の、図形Ａの点の取り扱いについては、前記の方法を適用する。点Ｖ１，Ｖ２に関する本発明によるデータ構造の点データの一部を図３５に示す。点Ｖ１とＶ２を結ぶ線を描くためには、まず、点Ｖ１の点データ領域で点Ｖ２のアドレスが書かれている欄の右端の属性値Ｐをみて、アドレスＰに記憶されているデータを参照する。アドレスＰの属性値を参照すると円弧であることが分かる。また、円弧は平面
ａｘ＋ｖｙ＋ｃｚ＝ｄ
の上にあり、中心が（ｘ０，ｙ０，ｚ０），半径ｒ、円弧の開始点が角度０度、終点が角度３０度であることが分かる。
【００６１】
隣接点を持たない円又は球の単体のような数式で表される図形では、図形上に任意の点Ｐを定めれば、当該点Ｐの点データは数式を記憶している場所へのポインタを属性として記述するだけで、特に隣接点に関する情報を記述する必用はない。
【００６２】
ここで本発明により多面体を表現する場合のデータ量と、従来の代表技術であるハーフエッジ構造によって多面体を表現する場合のデータ量の比較を行う。
なお以下では理論的に必要とする最小限の記憶容量で計算する。
最初にハーフエッジ構造で必要とされるデータの種類と大きさについて考える。
ハーフエッジ構造ではウィングドエッジ構造の図３６(a) を稜線eで分割し、図３６(ｂ)に示されるように１本の稜線ｅに対して、片側で６種類（pccw, pcw, pf, pv, nv, e'）の情報を記憶させる。反対側も同じデータ量が記憶されるので合計で１２種類の情報をデータとして記憶させている。これらはすべて点の情報が記録されているアドレスへのポインターであるから１ポインタ当たり４バイトのメモリが必要として、全稜線を記憶するのに必要なメモリ容量Ｎｅは
Ｎｅ＝４×１２ｎｅ＝４８ｎｅ
となる。ここでneは多面体を構成する稜線の数である。
頂点データに必要な記憶容量
頂点の３次元座標値は（ｘ、ｙ、ｚ）の組合せで表現される。またこれらの座標値は浮動小数点数であるから、それぞれ４バイト必要である。多面体の構成頂点の数をｎｖとすると必要なメモリ容量Ｎｖは
Ｎｖ＝４×３×ｎｖ＝１２ｎｖ
で表される。上記のデータの他に通常は面及び稜線へのポインタを持たせるようにプログラムするが、ここでは最小限のメモリを考えているのでこれらは無視する。
面データに必用な記憶容量
面からその構成稜線の１本を参照するポインタが必要なので、必要なメモリ容量Ｎｆは
Ｎｆ＝４×ｎｆ
である。ここでｎｆは多面体を構成する面の数である。
上記１．２．３を総合すると多面体を記憶するために必用な全記憶容量Ｎｈは
Ｎｈ＝４８ｎｅ＋１２ｎｖ＋４ｎｆ
で表される。
【００６３】
ところで、穴のない多面体の頂点、稜線、面の数の間には次の関係が成り立つことが知られている（オイラー標数）。
ｎｖ＋ｎｆ−ｎｅ＝２
多面体の面、稜線、頂点の数が多くなると、それらに比較して上式の右辺の定数２は無視しうる程度の微少量と見なすことが出来るので、近似的に次の式が成り立つ。
ｎｅ＝ｎｖ＋ｎｆ                        ・・・・・・（１）
頂点の数と面の数の関係は解析的には求めることが出来ないので、正確には記述できないが、仮に
ｎｆ＝１．５ｎｖ
と概算することにすると、必要なデータ量は、
Ｎｈ＝４８ｎｅ＋１２ｎｖ＋４×１．５ｎｖ＝４８ｎｅ＋１８ｎｖ
となる。式（１）を利用すると、
Ｎｈ＝４８ｎｅ＋７．２ｎｅ＝５５．２ｎｅ  ・・・・・（２）
が得られる。
つまり穴のない多面体をハーフエッジ構造で記憶するために必要なメモリ容量は最低でも５５．２ｎｅバイト必要と言うことが分かる。
【００６４】
本発明によるデータ構造で座標値以外の属性情報を持たない場合について考える。
頂点の座標値を記憶するためのメモリ容量はハーフエッジ構造と同じである。つまり、頂点の座標値を記憶するために必要な容量Ｎｖは
Ｎｖ＝１２ｎｖ                            ・・・・・（３）
バイトである。
隣接点表のために必要なメモリについて考察する。
隣接点の数は稜線数のちょうど２倍だけあり、また各要素は４バイトのメモリを必要とするので、隣接点表のために必用なメモリＮｎは
隣接点表に記載のデータは共有する稜線数のちょうど２倍だけあり、また表の各データ領域は４バイトのメモリを必要とするので、隣接点表のために必要なメモリＮｎは
Ｎｎ＝２ｎｅｘ４＝８ｎｅ                  ・・・・・（４）
バイトである。一つの頂点に隣接する頂点の数が２５６以下である場合には、各隣接点のアドレスへのポインタに対応する配置数値の記憶には１バイトのメモリで十分なので、この配置数値の記憶のためのメモリＮｐは  
Ｎｐ＝２ｎｅ                              ・・・・・（５）
バイトで済むことになる。
式（３）、（４）、（５）をまとめると必要な記憶容量Ｎｃは
Ｎｃ＝１２ｎｖ＋８ｎｅ＋２ｎｅ＝１４．８ｎｅ  ・・・（６）
バイトで済むことが分かる。
【００６５】
式（２）と（６）を比較すると本発明に係るデータ構造が必要とするメモリ容量は、ハーフエッジ構造と比較して２７％弱であることが分かる。
１つの点に２５６点以上の点が接続される場合に、例えば６５，５３６点以下である場合には隣接点表の配置数の記憶には２バイト必要なので式（５）のＮｐを計算し直すと
Ｎｐ＝４ｎｅ
バイトとなる。この場合にはハーフエッジ構造の３３％程度になる。
１つの頂点に６５，５３６点以上が隣接するような多面体は通常生成されないので、より多くの頂点が隣接する場合の記憶容量の計算は省略する。
前記の比較は、理論的に最小のメモリ容量を概算したものであり、実際にプログラムを組むときには両者ともある程度の冗長度を持たせるので、コンピュータに実装した場合の比較も行う必要がある。ハーフエッジ構造と本発明に係るデータ構造をそれぞれコンピュータ上に実装して比較を行ったところ、本発明に係るデータ構造で立体を記述した場合のデータ量はハーフエッジ構造の場合に比較して約１／３であった。
【実施例６】
【００６６】
次に本発明によるデータ構造を利用して、図形の変形に係る履歴情報をすべて記憶させた場合にどの程度記憶容量が増加するかについて、実際にプログラムを作成し、図３７に示すような３次元図形作成の履歴を記憶させて必要なメモリを調べる。
図３７は本発明のデータ構造で記憶された３次元図形の１例で、図３８はこの図形が作成される過程を示す。各過程を操作レベル１〜９に分け、途中で戻り操作を行って次のステップに進むという一連の作業の流れを図示したものである。
図３７に示す３次元図形Ｄは、次のような工程で作成される。
最初に図３８（１）に示すような２次元図形を生成し（操作レベル１）、この面を掃引して３次元図形を生成する（操作レベル２）。さらに、上面に突起を生成する（操作レベル３）。
次に操作レベル３を取り消して、操作レベル２に戻り底面の凹部を生成する（操作レベル４）。そして次に、上面に凹部の生成と穴の形成を行う（操作レベル５）。さらに、上面の他の部分に凹部の生成と穴の形成を行う（操作レベル６）。
別の穴を形成する（操作レベル７）。そして、操作レベル７の穴の形成を取り消して、操作レベル６に戻り、上面に凹部を生成する（操作レベル８）。
そして最後に、穴の形成を行い（操作レベル９）、上部の凹部の部分を曲面化して、３次元図形Ｄを作成する。
【００６７】
上記操作レベル１から９までの工程では、操作レベル１の図形から操作レベル２、操作レベル３・・・・というように変形が行われていることになる。
すなわち各操作レベルの流れを示す図３８の様に、＜１＞→＜２＞→＜３＞と変形した後、＜３＞を取り消し、＜２＞に戻り、＜２＞→＜４＞→＜５＞→＜６＞→＜７＞と変形し、今度は＜７＞を取り消して＜６＞にもどり、＜６＞→＜８＞→＜９＞へと変形している。
この操作レベル１から９までの変形において、その変更履歴情報をすべて記憶した場合の記憶容量の推移を記録した結果を、図３９に示す。
図３９に示すグラフにおいて、横軸は変形を行った回数（操作レベル１〜９を履歴レベル１〜９として表現してある）、縦軸は実際にメモリを使用した記憶容量及び図形Ｄの頂点数を表す。前記グラフにおける△点は図形Ｄの頂点数の変化を示している。
また前記グラフで、棒グラフのａは、操作レベルの各段階において生成された図形を記憶するのに必要な記憶容量を、棒グラフのｂはその操作レベルで生成される図形に至るまでのすべての変形履歴（全変更履歴）を記憶するのに要した記憶容量を、棒グラフのｃは、その操作レベルの段階までの各操作レベル（例えば、履歴レベル５の場合は履歴レベル１〜５までの各履歴レベル）におけるすべての図形を記憶するのに必要とされる記憶容量の合計を表している。
【００６８】
図３９に示すグラフによれば、全変形履歴を記憶するのに必要な記憶量（棒グラフｂ）は、図形一つを記憶するのに必要なメモリ（棒グラフａ）のほぼ１．３〜１．５倍の間で推移していることが分かる。倍率が高くなっている時は、図形生成後に作業の取り消しを行った時である。
なお比較のために、ハーフエッジ構造によって図３８の操作レベル９に示す図形単体を記憶するのに必要な記憶容量の概算を行った。その結果、操作レベル９に示す図形単体を記憶するのに必要な記憶量は、本発明のデータ構造を使って全操作レベルの変更履歴を記憶するのに必要な記憶量の倍以上であることが分かった。
【実施例７】
【００６９】
本発明による図形の変更履歴とメモリの使用量の関係をより詳細に比較するために、図４０に示す図形Ｅに対して、前記と同様の調査を行った。
その結果が図４１に示す１００回の変更履歴と消費メモリ量の関係を示すグラフである。
この例においては、図形の変形回数が１００回なので計測は１０回ごとに行った。  １つの図形を記憶するのに必要なメモリ量は、形状が複雑になるにつれて増加するが、全変更履歴を保持するのに必要なメモリ量は相対的に低いことが分かる。
前記グラフにおいて、棒グラフＡは各操作を行った後に図形１つを記憶するのに必要とする全メモリ量を、棒グラフＢはそれまでの全変形履歴を記憶するのに必要なメモリ量を表している。グラフの△印は１つの図形を記憶するのに必要なメモリ量と全変形履歴を記憶するのに要したメモリ量の比の推移を表している。
前記の調査からも図形の変更履歴をすべてデータ中に記憶させておいても、その記憶量は小さく、ハーフエッジ構造で作成された図形を記憶する場合と比較して、大幅にメモリ使用量が少なくて良いことが分かる。すなわちハーフエッジ構造による１つの図形データの必要とするメモリ量以下で、本発明のデータ構造では全変更履歴をもった図形データが作成できる。
【００７０】
前記記載の内容のまとめとして、本発明のデータ構造で図形を保存する場合と、従来技術のハーフエッジ構造で図形を保存する場合の違いを図４２の比較表に示す。
【図面の簡単な説明】
【００７１】
【図１】本発明のデータ構造を説明するための２次元図形
【図２】本発明のデータ構造を説明するための３次元図形
【図３】本発明のデータ構造により２次元図形を表現する点データの基本構成概念説明図
【図４】本発明のデータ構造により３次元図形を表現する点データの基本構成概念説明図
【図５】本発明のデータ構造により２次元図形を表現する点データの付加機能概念説明図
【図６】本発明のデータ構造により３次元図形を表現する点データの付加機能概念説明図
【図７】本発明のデータ構造において各点データが保持する属性情報に関する概念説明図
【図８】本発明のデータ構造において各点データが保持する属性情報に関する別の説明図
【図９】本発明における変更履歴について説明するための変更過程を示す図
【図１０】前記変更過程の履歴レベル１に於ける本発明のデータ構造の概念説明図
【図１１】前記変更過程の履歴レベル２に於ける本発明のデータ構造の概念説明図
【図１２】前記変更過程の履歴レベル３に於ける本発明のデータ構造の概念説明図
【図１３】本発明のデータ構造で図形を作成するプログラムのフローチャート
【図１４】本発明のデータ構造により新しい点の点データを生成し、メモリに書き込むプログラムのフローチャート
【図１５】本発明のデータ構造による図形の点データを削除するプログラムのフローチャート
【図１６】本発明のデータ構造による図形の点を他の点の隣接点とするプログラムのフローチャート
【図１７】本発明のデータ構造による図形の点の隣接点情報を削除するプログラムのフローチャート
【図１８】本発明のデータ構造によってメモリに記録された図形のデータから反時計回りにＫ番目の隣接点を取り出すプログラムのフローチャート
【図１９】本発明のデータ構造によってメモリに記録された図形のデータから時計回りにＫ番目の隣接点を取り出すプログラムのフローチャート
【図２０】本発明のデータ構造による図形の点とその隣接点の間に新しい点を生成するプログラムのフローチャート
【図２１】本発明のデータ構造によってメモリに記録された図形の面の構成点を反時計回りに取り出すプログラムのフローチャート
【図２２】本発明のデータ構造によってメモリに記録された図形の面の構成点を時計回りに取り出すプログラムのフローチャート
【図２３】本発明のデータ構造による履歴管理を行う場合の点データ領域への書き込み処理を行うプログラムのフローチャート
【図２４】本発明のデータ構造の実施例説明用２次元図形を示す図
【図２５】前記図２４に於いて点Ｖ0を例とした点データを示す図（点Ｖ0の隣接点表）
【図２６】前記図２４の２次元図形を表現する本発明のデータ構造の概念図
【図２７】前記図２４の２次元図形で高さの情報を保持する本発明のデータ構造の概念図
【図２８】本発明のデータ構造の実施例説明用３次元図形を示す図
【図２９】前記図２８の３次元図形を表現する本発明のデータ構造の概念図
【図３０】本発明のデータ構造の実施例を説明するための非多様体の図
【図３１】前記図３０の非多様体に対する本発明のデータ構造の概念図
【図３２】本発明の説明のため、格子状の点列を示す図
【図３３】格子状の点列において、本発明のデータ構造の各点データから１つの点列を取り出すための説明用点データ図
【図３４】本発明の実施例を説明するための円筒面を有する３次元図形Ｃを示す図
【図３５】円筒面を有する３次元図形において平面と曲面の境界上にある構成点の、本発明による点データの例を示す図
【図３６】従来技術であるウィングドエッジ構造及びハーフエッジ構造の説明図
【図３７】本発明のデータ構造で記録された図形データの操作過程の説明用３次元図形Ｄを示す図
【図３８】前記図３７の３次元図形Ｄの各操作レベルの流れを示す図
【図３９】前記３次元図形Ｄの作成における変形履歴と記憶量の関係を示すグラフ
【図４０】本発明のデータ構造で記録された図形データにおいて、変更履歴と使用メモリ量の関係を調べるための３次元図形Ｅを示す図
【図４１】前記３次元図形Ｅの作成過程１００回の変形履歴とメモリ量の関係を示すグラフ
【図４２】従来技術のハーフエッジ構造と本発明のデータ構造との比較表
【符号の説明】
【００７２】
１    ２次元図形
２    点V０の（データ領域の）アドレス
３    隣接点のアドレス
４    各隣接点のデータの中でV0のアドレスが何番目に記憶されているかを示す数値（配置数値）
５    隣接点のアドレスが記憶される順番
６    属性
７    ３次元図形
８    ３次元非多様体図形
【図１】
2006114007.tif 000003
【図２】
2006114007.tif 000004
【図３】
2006114007.tif 000005
【図４】
2006114007.tif 000006
【図５】
2006114007.tif 000007
【図６】
2006114007.tif 000008
【図７】
2006114007.tif 000009
【図８】
2006114007.tif 000010
【図９】
2006114007.tif 000011
【図１０】
2006114007.tif 000012
【図１１】
2006114007.tif 000013
【図１２】
2006114007.tif 000014
【図１３】
2006114007.tif 000015
【図１４】
2006114007.tif 000016
【図１５】
2006114007.tif 000017
【図１６】
2006114007.tif 000018
【図１７】
2006114007.tif 000019
【図１８】
2006114007.tif 000020
【図１９】
2006114007.tif 000021
【図２０】
2006114007.tif 000022
【図２１】
2006114007.tif 000023
【図２２】
2006114007.tif 000024
【図２３】
2006114007.tif 000025
【図２４】
2006114007.tif 000026
【図２５】
2006114007.tif 000027
【図２６】
2006114007.tif 000028
【図２７】
2006114007.tif 000029
【図２８】
2006114007.tif 000030
【図２９】
2006114007.tif 000031
【図３０】
2006114007.tif 000032
【図３１】
2006114007.tif 000033
【図３２】
2006114007.tif 000034
【図３３】
2006114007.tif 000035
【図３４】
2006114007.tif 000036
【図３５】
2006114007.tif 000037
【図３６】
2006114007.tif 000038
【図３７】
2006114007.tif 000039
【図３８】
2006114007.tif 000040
【図３９】
2006114007.tif 000041
【図４０】
2006114007.tif 000042
【図４１】
2006114007.tif 000043
【図４２】
2006114007.tif 000044