(57)【特許請求の範囲】
【請求項１】
第１多角形と第２多角形の多角形重なり部分を求めるためのコンピュータ処理ユニットの実行方法であって、
前記第１多角形を表す第１データであって、前記第１多角形の境界を共に表す複数のリンクを有している第１データを受け取り、
前記第２多角形を表す第２データであって、前記第２多角形の境界を共に表す複数のリンクを有している第２データを受け取り、
前記第１多角形の第１最小境界矩形を計算し、
前記第２多角形の第２最小境界矩形を計算し、
前記第１及び第２最小境界矩形の重なり部分としての重なり矩形を計算し、
前記重なり矩形内に完全に含まれる前記第１及び第２多角形のリンクと関係するノードのノード・リンク・マップを作成し、
該ノード・リンク・マップ内のノードから、３つ以上のリンクと関係するスタートノードを識別し、
前記スタートノードから始めて、前記スタートノードからスタートノードに戻るリンクをたどることによって、重なり多角形の境界を共に表すリンクを識別し、
前記重なり多角形を表す第３のデータであって、前記重なり多角形の境界を共に表すものとして識別される前記リンクを含む前記第３データを格納し、
前記重なり多角形の前記境界状のノードを前記ノード・リンク・マップから取り除き、  そして、
もし、該取り除いた後に、前記ノード・リンク・マップが３つ以上のリンクと関係するノードを含んでいる場合には、第２スタートノードとして前記ノードを用い、かつ上記手順を反復して第２重なり多角形を識別して格納する段階とを備えたことを特徴とする方法。
【請求項２】
前記第１多角形の境界を表す前記リンクが、時計回り又は逆時計回りのいずれかの方向に一貫して順番に並べられることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１多角形に位置する穴の境界が複数のリンクによって表され、前記穴の境界を表すリンクが前記第１多角形の境界を表すリンクの並びの順番の方向とは反対の方向に順番に並んでいることを特徴とする請求項２に記載の方法。
【請求項４】
前記第１多角形と第２多角形が２次元の幾何学的特徴を表していることを特徴とする請求項１に記載の方法。
【請求項５】
重なり多角形の境界を共に表すリンクを識別する段階が、
前記スタートノードに関連するリンクの中から、前記第１多角形の境界内にあるリンクであって、前記第２多角形内に位置するリンクを選択することによって第１リンクを識別し、
最後に識別されたリンクと関連するリンクを選択することによってそれぞれ後続のリンクを識別し、
該最後に識別されたリンクのノードと関連する複数のリンクがある場合には、前記最後に識別されたリンクとの間で最小角度をもつリンクを選択する段階とを備えたことを特徴とする請求項１に記載の方法。
【請求項６】
第１多角形と第２多角形の多角形重なり部分を求めるためのコンピュータ処理ユニットの実行方法を遂行するためのコンピュータ実行可能命令を含むコンピュータ読み取り可能媒体であって、
前記方法が
前記第１多角形を表す第１データであって、前記第１多角形の境界を共に表す複数のリンクを有している第１データを受け取り、
前記第２多角形を表す第２データであって、前記第２多角形の境界を共に表す複数のリンクを有している第２データを受け取り、
前記第１多角形の第１最小境界矩形を計算し、
前記第２多角形の第２最小境界矩形を計算し、
前記第１及び第２最小境界矩形の重なり部分としての重なり矩形を計算し、
前記重なり矩形内に完全に含まれる前記第１及び第２多角形のリンクと関係するノードのノード・リンク・マップを作成し、
該ノード・リンク・マップ内のノードから、３つ以上のリンクと関係するスタートノードを識別し、
前記スタートノードから始めて、前記スタートノードからスタートノードに戻るリンクをたどることによって、重なり多角形の境界を共に表すリンクを識別し、
前記重なり多角形を表す第３データであって、前記重なり多角形の境界を共に表すものとして識別される前記リンクを含む前記第３データを格納し、
前記重なり多角形の前記境界状のノードを前記ノード・リンク・マップから取り除き、  そして、
もし、該取り除いた後に、前記ノード・リンク・マップが３つ以上のリンクと関係するノードを含んでいる場合には、第２スタートノードとして前記ノードを用い、かつ上記手順を反復して第２重なり多角形を識別して格納する段階とを備えたことを特徴とするコンピュータ読み取り可能媒体。
【請求項７】
第１多角形と第２多角形の多角形和集合を求めるためのコンピュータ処理ユニットの実行方法であって、
前記第１多角形を表す第１データであって、前記第１多角形の境界を共に表す複数のリンクを有している第１データを受け取り、
前記第２多角形を表す第２データであって、前記第２多角形の境界を共に表す複数のリンクを有している第２データを受け取り、
前記第１多角形の第１最小境界矩形を計算し、
前記第２多角形の第２最小境界矩形を計算し、
前記第１及び第２最小境界矩形の重なり部分としての重なり矩形を計算し、
前記重なり矩形内に完全に含まれる前記第１及び第２多角形のリンクと関係するノードのノード・リンク・マップを作成し、
該ノード・リンク・マップ内のノードから、３つ以上のリンクと関係するスタートノードを識別し、
前記スタートノードから始めて、前記スタートノードからスタートノードに戻るリンクをたどることによって、和集合多角形の境界を共に表すリンクを識別し、
前記和集合多角形を表す第３データであって、前記和集合多角形の境界を共に表すものとして識別される前記リンクを含む前記第３データを格納し、
前記和集合多角形の前記境界状のノードを前記ノード・リンク・マップから取り除き、  そして、
もし、該取り除いた後に、前記ノード・リンク・マップが３つ以上のリンクと関係するノードを含んでいる場合には、第２スタートノードとして前記ノードを用い、かつ上記手順を反復して第２和集合多角形を識別して格納する段階とを備えたことを特徴とする方法。
【請求項８】
前記第１多角形の境界を表す前記リンクが、時計回り又は逆時計回りのいずれかの方向に一貫して順番に並べられることを特徴とする請求項７に記載の方法。
【請求項９】
前記第１多角形に位置する穴の境界が複数のリンクによって表され、前記穴の境界を表すリンクが前記第１多角形の境界を表すリンクの並びの順番の方向とは反対の方向に順番に並んでいることを特徴とする請求項８に記載の方法。
【請求項１０】
前記第１多角形と第２多角形が２次元の幾何学的特徴を表していることを特徴とする請求項７に記載の方法。
【請求項１１】
和集合多角形の境界を共に表すリンクを識別する段階が、
前記スタートノードに関連するリンクの中から、前記第１多角形の境界内にあるリンクであって、前記第２多角形内に位置するリンクを選択することによって第１リンクを識別し、
最後に識別されたリンクと関連するリンクを選択することによってそれぞれ後続のリンクを識別し、
該最後に識別されたリンクのノードと関連する複数のリンクがある場合には、前記最後に識別されたリンクとの間で最小角度をもつリンクを選択する段階とを備えたことを特徴とする請求項７に記載の方法。
【請求項１２】
第１多角形と第２多角形の多角形和集合を求めるためのコンピュータ処理ユニットの実行方法を遂行するためのコンピュータ実行可能命令を含むコンピュータ読み取り可能媒体であって、
前記方法が
前記第１多角形を表す第１データであって、前記第１多角形の境界を共に表す複数のリンクを有している第１データを受け取り、
前記第２多角形を表す第２データであって、前記第２多角形の境界を共に表す複数のリンクを有している第２データを受け取り、
前記第１多角形の第１最小境界矩形を計算し、
前記第２多角形の第２最小境界矩形を計算し、
前記第１及び第２最小境界矩形の重なり部分としての重なり矩形を計算し、
前記重なり矩形内に完全に含まれる前記第１及び第２多角形のリンクと関係するノードのノード・リンク・マップを作成し、
該ノード・リンク・マップ内のノードから、３つ以上のリンクと関係するスタートノードを識別し、
前記スタートノードから始めて、前記スタートノードからスタートノードに戻るリンクをたどることによって、和集合多角形の境界を共に表すリンクを識別し、
前記和集合多角形を表す第３データであって、前記和集合多角形の境界を共に表すものとして識別される前記リンクを含む前記第３データを格納し、
前記和集合多角形の前記境界状のノードを前記ノード・リンク・マップから取り除き、  そして、
もし、該取り除いた後に、前記ノード・リンク・マップが３つ以上のリンクと関係するノードを含んでいる場合には、第２スタートノードとして前記ノードを用い、かつ上記手順を反復して第２和集合多角形を識別して格納する段階とを備えたことを特徴とするコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２つの多角形の重なり部分又は和集合を求める方法に関し、具体的には地理的特徴を表す２つの多角形の重なり部分又は和集合を求めることに関する。
【０００２】
【従来の技術】
地理データベースにおいて、多角形は、例えば湖、レクリエーション公園、市、郡、州、ゴルフコースなどのような二次元領域を表すために使用される。地理データベースの幾つかの種類において、多角形は、互いに連結されて多角形の囲まれた境界を形成する一連のリンクにより表される。
【０００３】
地理データベースを用いて実行される一般に必要とされる機能は、ある二次元の地理的特徴（例えば市、郡、州等）の中に位置する別の二次元の地理的特徴（湖、レクリエーション公園など）の部分を見つけることである。二次元の地理的特徴を表すために用いられる多角形の重なり部分を求めることによって、この解法を見つけることができる。
多角形の重なり部分を求めるための従来の方法がある。多角形の重なり部分を求めるための公知のアルゴリズムは、「計算幾何学」（Ｊｏｓｅｐｈ  Ｏ’Ｒｏｕｒｋｅ著。１９９８年、ケンブリッジ大学出版、第２版）において説明されている。このアルゴリズムは、２つの多角形から全ての形状点を取り出し、それらをｙ座標値によって分類し、各々の形状点において線分を完全に掃引探索する。その線分が両方の多角形に位置する場合には、それが重なり部分境界である。この従来のアルゴリズムを用いて、２つの多角形内にｎ個の形状点がある場合、全体の複雑さはｎ＊ｌｏｇ（ｎ）である。このように、この従来のアルゴリズムは十分に機能するが、計算を多く必要とするため、結果を得るのに比較的長い時間がかかる。
【０００４】
地理データベースを使用して実行される一般に必要とされる別の機能は、２つの二次元の地理的特徴の和集合を見つけることである。二次元の地理的特徴を表すために用いられる多角形の和集合を求めることによって、この解法を見つけることができる。多角形の和集合を求める従来の方法がある。しかしながら、従来の方法は計算を多く必要とするため、結果を得るのに比較的長い時間がかかる。
【０００５】
【発明が解決しようとする課題】
従って、２つの多角形の重なり部分又は和集合をより早く求める方法への必要性がある。
【０００６】
【課題を解決するための手段】
これら及び他の目的に対処するため、本発明は、第１多角形と第２多角形の多角形重なり部分を求める方法を含む。第１多角形の境界の第２多角形の境界との重なり部分は、多角形の境界の少なくとも３つの部分（即ち、リンク）が延びるノードを見つけることによって求められる。このノードから、第２多角形内に位置する第１多角形の境界部分を識別することによって、多角形重なり部分の境界の第１部分が求められる。（１）多角形重なり部分の境界の現在部分の先端に連結し、（２）多角形重なり部分の境界の該現在部分と最小角度を形成する第１多角形又は第２多角形のいずれかの境界部分を選択することによって、多角形重なり部分の境界の次の部分の各々が求められる。
【０００７】
開示された本発明の更に別の態様によると、重なり合った穴又は島が両方の多角形内にあれば、これら穴又は島が求められる。
本発明の別の態様によると、第１多角形と第２多角形の多角形和集合を求める方法が開示される。第１多角形の境界の第２多角形の境界の重なり部分が、多角形の境界の少なくとも３つの部分（即ち、リンク）が延びるノードを見つけることによって求められる。このノードから、第２多角形の外に位置する第１多角形の境界部分を識別することによって、多角形和集合の境界の第１部分が求められる。（１）多角形和集合の境界の現在部分の先端に連結し、（２）多角形和集合の境界の該現在部分と最大角度を形成する第１多角形又は第２多角形のいずれかの境界部分を選択することによって、多角形和集合の境界の次の部分の各々が求められる。
開示された本発明の更に別の態様は、第１多角形内に含まれるが第２多角形内には含まれない穴又は島、及び第２多角形内に含まれるが第１多角形内には含まれない穴又は島について説明する。
【０００８】
【発明の実施の形態】
Ｉ．地理データベース
図１を参照すると、地理データベース１００が、対象とされた領域１０８内に位置する特徴を表すデータ１０４を含む。例えば、地理データベース１００は、道路１１２及び所定の点１１６を表すデータを含むことができる。地理データベース１００はまた、二次元の特徴即ち事物１２４を表すデータ１２０を含む。地理データベース１００において表すことができる異なる種類の二次元の特徴の一部には、地形（例えば、山脈）、水域（例えば、湖、池、沼地、湿地）、レクリエーション地域（例えば、ゴルフコース、公園、屋外競技場、保安林）、ビジネス街、工業団地、及び行政管理地域（例えば、市、町、州、郡区、自治体、郡、学区）、並びに他の種の地域が含まれる。
図２を参照すると、地理データベース１００において、多角形を用いて二次元の特徴が表される。言い換えると、地理データベース１００において、二次元の特徴を表すために用いられるデータは、これらの特徴を多角形として表している。地理データベース１００において、多角形の境界は、表される二次元特徴の境界に対応する。
【０００９】
以下の用語を地理データベース１００における二次元特徴を表すために用いる。
「ノード」−リンクの端となる点。
「線分」−２点を結ぶ直線。
「リンク」（すなわち「辺」）−各端部がノードで終端する一つ又はそれ以上の線分の、連続した無分枝のストリング。
「形状点」−２つのノード間のリンクに沿った点。
「配向リンク」−開始ノード（「基準ノード」と呼ばれる）と終了ノード（「非基準ノード」と呼ばれる）を有するリンク。
「単純多角形」−一つのノードで始まりかつ終わる一連の配向リンクによって形成された外部境界内の内部領域。（単純多角形は、自己内で交わらない。）
「多角形」−外部境界に囲まれた領域、及び０又は少なくとも１つの内部境界（例えば、穴又は島）。多角形は、１つの外部単純多角形と０又は少なくとも１つの内部単純多角形から構成される。多角形は、一つの単純多角形だけからなる場合は、単純多角形であり、或いは少なくとも一つの内部単純多角形を有する場合は複雑多角形である。
【００１０】
地理データベース１００は、一定のきまりに従う。例えば、リンクはリンク同志が交わることがなく、ノード以外では互いに交わらない。また、形状点、ノード或いはリンクの重なり合いはない。互いに連結する２つのリンクは、共通のノードを有する。地理データベース１００において、重なり合う二次元の地理的特徴は、重なり合う多角形によって表される。多角形が重なり合うとき、一方の多角形の境界は、他方の多角形の境界と交わる。地理データベース１００において、一方の多角形の境界が他方の多角形の境界と交わる位置は、ノードによって表される。（多角形の境界が別の多角形の境界と交わる位置以外に、多角形の境界に沿った他の位置を表すためにノードを用いることができる。）形状点は、多角形の境界が別の多角形の境界と交わる点を表すためには用いられない。
地理データベース１００において、二次元の特徴を表す多角形のデータ表現１３２は、多角形の境界を形成する各配向リンクを識別するリスト１３６を含む。地理データベースにおいて用いられるきまりによると、リスト１３６は、配向リンクを時計回りの順序で識別する。多角形が穴（即ち、第１多角形の内部に完全に位置する第２多角形）を有する場合、その穴は逆時計回りの順序でリスト表示された配向リンクのリストによって識別される。
【００１１】
ＩＩ．多角形の重なり部分を求める方法
上述のように、地理データベースを使用するアプリケーションを用いて、２つの二次元特徴が重なり合うかどうかを判断し、重なり合う場合には、その２つの二次元領域の重なり部分（即ち、重複部分）を形成する二次元領域を求める必要があることもある。これらの二次元特徴を表すために用いられる多角形については、多角形の重なり部分を求めることの必要性がある。
多角形の重なり部分を求める方法が、図３から図１０までに関連して説明される。図３を参照すると、この方法は、図１及び図２に関連して説明された多角形のデータ表現を含む地理データベース１００を使用するソフトウェアプログラム２００によって実行される。ソフトウェアプログラム２００は、２つの多角形のデータ表現を入力として受け取る。（２つの多角形のデータ表現は、図２で述べられたものに従う。）ソフトウェアプログラム２００は、入力として提供された２つの多角形のデータ表現のうちの多角形重なり部分を表す各多角形のデータ表現を、出力として提供する。或いは、ソフトウェアプログラム２００は、入力として提供された２つの多角形のデータ表現の重なり部分がないことを示す出力を提供する。
【００１２】
このソフトウェアプログラム２００は、乗物の運転者にナビゲーション関連の特徴を提供する地理データベースを使用するナビゲーションシステム２１０にインストールすることができる。ソフトウェアプログラム２００を地理データベースを使用するサーバ上にインストールして、乗物の運転者、運転者でない人、携帯情報端末（ＰＤＡ）のユーザ、携帯電話のユーザなどを含む様々な種類のユーザにナビゲーション関連のサービスを提供することもできる。地理データベースを使用するサーバを、インターネット又は他の通信ネットワークに接続することができる。地理データベースをコンパイルするとき、即ち原始データベースから得られたデータベース製品を生成するために、ソフトウェアプログラム２００を使用することもできる。様々なナビゲーション関連、地図関連或いは他の種の特徴を提供するために、ソフトウェアプログラム２００を地理データベースを使用する独立型のコンピュータで使用することもできる。
これらの異なるシステムのいずれにおいても、必要に応じてソフトウェアプログラム２００をコンピュータ読み取り可能な媒体上に格納し、該媒体からシステムのメモリにロードし、実行することができる。
【００１３】
２つの多角形の多角形重なり部分の割り出しについて、図４から図１０に関連して説明される。図４は、Ｐ（Ａ）及びＰ（Ｂ）と表記された２つの多角形を示す。開示された実施形態を用いて、多角形Ｐ（Ａ）とＰ（Ｂ）の重なり部分Ｐ（Ｉ）が求められる。
図５Ａから図５Ｃまでは、多角形Ｐ（Ａ）とＰ（Ｂ）の重なり部分を求めるためのソフトウェアプログラム２００によって実行されるプロセス２２０における段階を示す。プロセス２２０は、２つの多角形のデータ表現を受け取る段階から始まる（段階２２４）。プロセス２２０は、２つの多角形Ｐ（Ａ）及びＰ（Ｂ）に対する最小境界４角形を形成する段階を含む（段階２２８）。図６は、それぞれＭＢＲ（Ａ）及びＭＢＲ（Ｂ）と表記された、これらＰ（Ａ）及びＰ（Ｂ）に対する最小境界４角形の構成を示す。最小境界４角形ＭＢＲ（Ａ）とＭＢＲ（Ｂ）が重なり合うかどうかを判断するために、これらを比較する（段階２３２）。多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形が重なり合わない場合、多角形Ｐ（Ａ）とＰ（Ｂ）は重なり合わず、否定的な結果が戻される（段階２３６）。最小境界４角形ＭＢＲ（Ａ）とＭＢＲ（Ｂ）が重なる場合、多角形Ｐ（Ａ）とＰ（Ｂ）は重なり合っていることになり、プロセス２２０が継続する。
【００１４】
このプロセスは、ノード・リンク・マップを形成することで継続する。ノード・リンク・マップは、多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の多角形重なり部分ＭＢＲ（Ａ＿Ｂ）を用いて形成される。この多角形重なり部分Ｐ（Ａ＿Ｂ）は、図６に示すように求められる。ノード・リンク・マップを形成するために、多角形Ｐ（Ａ）又はＰ（Ｂ）の各リンクのうち、多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の多角形重なり部分Ｐ（Ａ＿Ｂ）内に完全に位置するものが識別される（段階２４４）。（リンクの両端が最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の重なり部分ＭＢＲ（Ａ＿Ｂ）内にある場合、リンクは、最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の重なり部分ＭＢＲ（Ａ＿Ｂ）内に完全に位置する。）次いで、これらの識別された各リンクの各ノードが識別される。（この段階においては形状点を無視することができる）。次に、これらの識別されたノードの各々が、入力項目としてノード・リンク・マップに含ませられるようになる（段階２４８）。ノード・リンク・マップに入力項目として含まれた各ノードに対して、そのノードに連結する全てのリンクが識別され、地図内のノードと関連付けられる。
【００１５】
ノード・リンク・マップは、入力された多角形Ｐ（Ａ）とＰ（Ｂ）の重なり部分を形成する多角形Ｐ（Ｉ）上に位置するノード（ここでは「Ｎ（開始）」と呼ばれる）を識別するために用いられる。ノード・リンク・マップを用いて、リンクが３つ（又はそれ以上）連結されたノードが識別される（段階２５２）。連結された３つ（又はそれ以上）のリンクを有する、ノード・リンク・マップからのノードは、２つの多角形Ｐ（Ａ）とＰ（Ｂ）の重なり部分を形成する多角形Ｐ（Ｉ）上に位置している。このノードが２つの多角形Ｐ（Ａ）とＰ（Ｂ）の重なり部分を形成する多角形Ｐ（Ｉ）上に位置するので、ノードＮ（開始）に連結する３つ又はそれ以上のリンクのうちの２つ（及び２つだけ）は、重なり部分多角形Ｐ（Ｉ）のリンクである。次の段階は、３つ又はそれ以上のリンクのうちのどの２つが、重なり部分多角形Ｐ（Ｉ）の一部を形成するかを識別するためのものである。
【００１６】
ノードＮ（開始）に連結するどのリンクが重なり部分多角形Ｐ（Ｉ）の一部を形成するかを識別するために、元の多角形Ｐ（Ａ）又はＰ（Ｂ）のうちの一方のリンクのうち、他方の元の多角形Ｐ（Ｂ）又はＰ（Ａ）内に位置する１つのリンクを識別するプロセスが実行される（段階２５４）。他方の元の多角形内に位置する一方の元の多角形のリンクは、重なり部分多角形Ｐ（Ｉ）の一部である。このリンクは、「ＬＩＮＫ（開始）」と呼ばれる。このリンクを見つけるための詳細なプロセス４００が、図７Ａ、図７Ｂ及び図８に示される。
【００１７】
図７Ａ及び図７Ｂを参照すると、Ｐ（Ａ）及びＰ（Ｂ）において、全ての辺が時計回りに配向されている。ノードＮには４つの辺、即ちＰ（Ａ）からのａｅ１及びａｅ２、Ｐ（Ｂ）からのｂｅ１及びｂｅ２が連結されているので、このノードＮは開始ノードである。（図７Ａに示すように）ａｅ２がｂｅ１及びｂｅ２の右側にある場合、ａｅ２はＰ（Ｂ）内にあり、これを多角形重なり部分の開始辺として選択することができる。ａｅ１がｂｅ１及びｂｅ２の右側にある場合、ａｅ１はＰ（Ｂ）内にあり、これを多角形重なり部分の開始辺として選択することができる。（図７Ｂに示すように）ａｅ２及びａｅ１の両方がｂｅ１及びｂｅ２の右側にない場合には、Ｎにおいて重なり部分はない。ａｅ２がｂｅ１及びｂｅ２の右側にあるかどうかを判断するために、図８に示されるプロセス５００を用いることができる。図８のプロセス５００を用いて、形状点ｂｐ１がｂｅ１から選択され、形状点ｂｐ２がｂｅ２から選択され、形状点ａｐ２がａｅ２から選択される。これらの辺の上にある他の形状点を同様に選択することもできるが、ノードＮ（点ｐ）へのそれぞれの辺上で最も近い形状点であるために、これらの形状点が選択される。図８のプロセス５００は、点ａｐ２が線分ｂｐ１＿ｐ及びｐ＿ｂｐ２の右側にあるかどうかを調べるために用いられる。（図７Ａに示すように）ａｐ２が線分ｂｐ１＿ｐ及びｐ＿ｂｐ２の右側にある場合には、ａｅ２は、ｂｅ１及びｂｅ２の右側にある。そうでない場合には、（図７Ｂに示すように）ａｅ２は、ｂｅ１及びｂｅ２の右側にはない。
【００１８】
ＬＩＮＫ（開始）が識別された後、重なり部分多角形Ｐ（Ｉ）を形成する次のリンクが識別される。この次のリンクは、ＬＩＮＫ（開始）の時計回りの端部に連結する全てのリンクを調べることで識別される。図５Ｂを参照すると、ＬＩＮＫ（開始）の時計回りの端部は、ＬＩＮＫ（開始）が得られる元の多角形（Ｐ（Ａ）又はＰ（Ｂ））における時計回りの方向のリンクから求められる（段階２６４）。
リンクすなわちＬＩＮＫ（開始）の時計回りの端部に連結する他のリンクが一つしかない場合、このリンクが重なり部分多角形Ｐ（Ｉ）の次のリンクとなる。この次のリンクを示すデータは、重なり部分多角形Ｐ（Ｉ）を表すために形成されたリストに格納される（段階２７２及び２７６）。
ＬＩＮＫ（開始）の時計回りの端部に連結する他のリンクが２つ又はそれ以上ある場合には、逆時計回りの方向に最小角度を形成するリンクが、重なり部分多角形Ｐ（Ｉ）の次のリンクである。次のリンクを示すデータは、重なり部分多角形Ｐ（Ｉ）を表すために形成されたリストに格納される（段階２７２、２７８及び２７６）。
【００１９】
このリンク（即ち、ＬＩＮＫ（開始）の後のリンク）が重なり部分多角形Ｐ（Ｉ）を表すために形成されたリストに加えられた後、プロセスは、重なり部分多角形Ｐ（Ｉ）を形成する次のリンクを求めることで継続する。次のリンクは、今述べたのと同様の方法で求められる。つまり、リンクの時計回りの端部に連結する全てのリンクが識別される（再び段階２６４及び２７２）。他のリンクが一つしかない場合には、このリンクが重なり部分多角形Ｐ（Ｉ）を形成するリンクのリストに加えられる。２つ又はそれ以上の他のリンクがある場合には、次のリンクは、重なり部分多角形Ｐ（Ｉ）の一部として最後に識別されたリンクから逆時計回りの方向に最小角度を形成するものである（再び段階２７８）。
【００２０】
このプロセスは、Ｎ（開始）に来るまで継続する（段階２８０）。Ｎ（開始）に来ると、（Ｐ（Ａ）とＰ（Ｂ）の重なり部分多角形Ｐ（Ｉ）全体の一部又は全てを形成する）一つの単純多角形が識別される。この単純多角形を表すデータは、リスト２５８に含まれる。これらのデータは、Ｐ（Ａ）とＰ（Ｂ）の重なり部分多角形Ｐ（Ｉ）全体のデータ表現３１８（図５Ｃ）において、単純多角形のリストに加えられる（段階２８４）。
【００２１】
リンク−ノード地図における使用済みの全てのリンク及びノードが取り除かれる（段階２８８）。単純な多角形重なり部分が識別された後、３つ又はそれ以上の連結されたリンクを有するノードがノード・リンク・マップ内にまだある場合には（図５Ｂの段階２９２）、第１多角形と第２多角形との間に少なくとももう１つの別の単純多角形重なり部分があることになる。このプロセスは、付加的な単純多角形重なり部分の各々を求めるために繰り返される（図５Ａの段階２５２で開始する）。このプロセスは、３つ以上のリンクが連結したノードがリンク−ノード地図内になくなるまで繰り返される。
プロセス２２０は、重なり合った穴及び島をＰ（Ａ）及びＰ（Ｂ）内に見つける。地理データベース１００において表された幾つかの二次元特徴は、表された他の二次元特徴内に完全に含まれる。一例として、島は、完全に水域内に位置する。地理データベース１００において、別の二次元内に完全に含まれる二次元特徴は、多角形内の穴として表される。
【００２２】
穴を含む多角形のデータ表現は、（１）多角形全体の境界を定める（即ち、上述の図２と類似した）辺のリスト、及び（２）多角形内に位置する穴の境界を定める辺のリストを含む。地理データベース１００において用いられるきまりによると、多角形内の穴のデータ表現における辺のリストは、逆時計回りの順序で並べられる。図９は、穴を有する多角形と、そのデータ表現を示す。
穴を有する２つの多角形の重なり部分を求めるとき、重なり部分内に幾つかの穴が含まれる可能性がある。図１０は、重なり部分内に穴／島を有する２つの多角形の重なり部分を示す。
【００２３】
開示されたプロセス２２０が、２つの多角形の多角形重なり部分を求めるために用いられるとき、多角形重なり部分のデータ表現は、多角形重なり部分内に位置する元の多角形のあらゆる穴の表現を含む。まず、穴の最小境界４角形が、２つの元の多角形の最小境界４角形の重なり部分内に位置するかどうかの判断がなされる。穴の最小境界４角形が、２つの元の多角形の最小境界４角形の重なり部分内に完全に位置していない場合、穴は多角形重なり部分内に位置していない。穴の最小境界４角形が、２つの元の多角形の最小境界４角形の重なり部分内に位置している場合には、穴のあらゆる点（例えば、あらゆるノード）が、他方の多角形内に位置しているかどうかの判断がなされる。
【００２４】
図５Ｃは、重なり部分多角形Ｐ（Ｉ）内の穴／島を扱うための、プロセス２２０における段階を示す。多角形Ａの島／穴から開始し、多角形Ｂ内に直接の親の単純多角形を見つけるために、探索がなされる。Ｂ内に単純多角形があり、その配向が時計回りの場合、多角形Ａの島／穴は、単純重なり部分多角形である。Ｂ内に親の多角形がない場合、或いはＢ内の親の単純多角形の配向が逆時計回りの場合は、多角形Ａの島／穴は、単純重なり部分多角形ではない（段階３０２）。これらの段階は、多角形Ａの全ての島／穴が検討されるまで繰り返される。
【００２５】
このプロセスは、多角形Ｂの島／穴を検討し、多角形Ａ内に直接の親の単純多角形を探索することで継続する。Ａ内に単純多角形があり、その配向が時計回りの場合、多角形Ｂの島／穴は単純重なり部分多角形である。Ａ内に親の多角形がない場合、或いはＡ内の親の単純多角形の配向が逆時計回りの場合は、多角形Ｂの島／穴は単純重なり部分多角形ではない（段階３０６）。このプロセスは、多角形Ｂの全ての島／穴にあたるまで繰り返される。
【００２６】
重なり部分内のあらゆる穴又は島について明らかにした後、複雑多角形全体の重なり部分Ｐ（Ｉ）のデータ表現が、単純多角形のリスト３１８から作られる（段階３０７）。Ｐ（Ａ）とＰ（Ｂ）の重なり部分は、一つ又はそれ以上の多角形を含むことができ、その多角形の各々は、単純又は複雑のいずれとすることができる。その後、ソフトウェアプログラム２００がインストールされたシステムにおいて、Ｐ（Ａ）とＰ（Ｂ）の多角形重なり部分を示すデータを必要とする他のアプリケーションにより、多角形重なり部分のデータ表現を用いることができる（段階２８８）。
【００２７】
ＩＩＩ．多角形の和集合を求めるための方法
上述のように、地理データベースを使用するアプリケーションを用いて、２つ（又はそれ以上）の二次元特徴の和集合を求める必要があることもある。これらの二次元特徴を表すために用いられる多角形については、多角形の和集合を求める必要がある。
多角形の和集合を求める方法が、図１１から図１７に関連して説明される。図１１を参照すると、この方法は、図１及び図２に関連して説明されたような多角形のデータ表現を含む地理データベース１００を使用するソフトウェアプログラム６００によって実行される。ソフトウェアプログラム６００は、入力として２つの多角形のデータ表現を受け取る。(２つの多角形のデータ表現は、図２で述べられたものに従う）。ソフトウェアプログラム６００は、入力として提供された２つの多角形のデータ表現の多角形のデータ表現（即ち、和集合）を出力として提供する。
【００２８】
ソフトウェアプログラム６００は、コンピュータシステム６１０にインストールされる。このコンピュータシステム６１０は、図３に示すコンピュータシステム２１０と同じにすることができ、或いは異なるコンピュータシステムにすることもできる。必要に応じてソフトウェアプログラム６００をコンピュータ読み取り可能な媒体上に格納し、該媒体からシステムのメモリにロードし、実行することができる。
２つの多角形の多角形和集合を求めることについて、図１２から図１７までに関連して説明される。図１２は、Ｐ（Ａ）及びＰ（Ｂ）と表記された２つの多角形を示す。開示された実施形態を用いて、多角形Ｐ（Ａ）とＰ（Ｂ）の和集合Ｐ（Ｕ）が求められる。
【００２９】
図１３Ａから図１３Ｃまでは、多角形Ｐ（Ａ）とＰ（Ｂ）の和集合を求めるためのソフトウェアプログラム６００によって実行されるプロセス６２０における段階を示す。プロセス６２０は、２つの多角形のデータ表現が受け取られる段階から開始される（段階６２４）。プロセス６２０は、２つの多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形を形成する段階を含む（段階６２８）。図１４は、それぞれＭＢＲ（Ａ）及びＭＢＲ（Ｂ）と表記された、これらの（Ａ）及びＰ（Ｂ）に対する最小境界４角形の構成を示す。最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）は、それらが交わるかどうかを判断するために比較される（段階６３２）。Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形が重なり合わない場合、多角形Ｐ（Ａ）とＰ（Ｂ）との間に和集合はなく、否定的な結果が戻される（段階６３６）。最小境界４角形ＭＢＲ（Ａ）とＭＢＲ（Ｂ）が交わる（接触を含む）場合、多角形Ｐ（Ａ）とＰ（Ｂ）との間には和集合があることになり、プロセス２２０が継続する。
【００３０】
このプロセスは、ノード・リンク・マップを形成することで継続する。ノード・リンク・マップは、多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の多角形重なり部分ＭＢＲ（Ａ＿Ｂ）を用いて形成される。この多角形重なり部分Ｐ（Ａ＿Ｂ）は、図１４に示すように求められる。ノード・リンク・マップを形成するために、多角形Ｐ（Ａ）及びＰ（Ｂ）の最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の多角形重なり部分Ｐ（Ａ＿Ｂ）内に完全に位置する、多角形Ｐ（Ａ）又はＰ（Ｂ）のいずれかのリンクの各々が識別される（段階６４４）。（リンクの両端が最小境界４角形ＭＢＲ（Ａ）とＭＢＲ（Ｂ）の重なり部分ＭＢＲ（Ａ＿Ｂ）内にある場合、リンクは最小境界４角形ＭＢＲ（Ａ）及びＭＢＲ（Ｂ）の重なり部分ＭＢＲ（Ａ＿Ｂ）内に完全に位置する。）次いで、これらの識別された各リンクの各ノードが識別される（この段階においては形状点を無視することができる）。次に、これらの識別されたノードの各々が、入力項目としてノード・リンク・マップに含まれるようになる（段階６４８）。ノード・リンク・マップに入力項目として含まれた各ノードに対して、そのノードに連結する全てのリンクが識別され、地図内のノードと関連付けられる。
【００３１】
ノード・リンク・マップは、入力された多角形Ｐ（Ａ）とＰ（Ｂ）の和集合を形成する多角形Ｐ（Ｕ）上に位置するノード（ここでは、「Ｎ（開始）」と呼ばれる）を識別するために用いられる。ノード・リンク・マップを用いて、リンクが３つ（又はそれ以上）連結されたノードが識別される（段階６５２）。連結された３つ（又はそれ以上）のリンクを有する、ノード・リンク・マップからのノードは、２つの多角形Ｐ（Ａ）とＰ（Ｂ）の和集合を形成する多角形Ｐ（Ｕ）上に位置している。このノードは、２つの多角形Ｐ（Ａ）とＰ（Ｂ）の和集合を形成する多角形Ｐ（Ｕ）上に位置するため、ノードＮ（開始）に連結する３つ又はそれ以上のリンクのうちの２つ（及び２つだけ）は、和集合多角形Ｐ（Ｉ）のリンクである。次の段階は、３つ又はそれ以上のリンクのうちのどの２つが和集合多角形Ｐ（Ｕ）の一部を形成するかを識別するためのものである。
【００３２】
ノードＮ（開始）に連結するどのリンクが和集合多角形Ｐ（Ｕ）の一部を形成するかを識別するために、元の多角形Ｐ（Ａ）又はＰ(Ｂ)のうち、他方の元の多角形Ｐ（Ｂ）又はＰ（Ａ）の外に位置する１つのリンクを識別するプロセスが実行される（段階６５４）。他方の元の多角形の外に位置する一方の元の多角形のリンクは、和集合多角形Ｐ（Ｕ）の一部である（段階６６０）。このリンクは、「ＬＩＮＫ（開始）」と呼ばれる。このリンクを見つけるための詳細なプロセス６９７が、図１５Ａ、図１５Ｂ及び図１６に示される。
【００３３】
図１５Ａ及び１５Ｂを参照すると、Ｐ（Ａ）及びＰ（Ｂ）において、全ての辺が時計回りに配向されている。４つの辺、即ちＰ（Ａ）からのａｅ１及びａｅ２、Ｐ（Ｂ）からのｂｅ１及びｂｅ２が連結されているので、ノードＮは開始ノードである。（図１５Ａに示すように）ａｅ２がｂｅ１及びｂｅ２の左側にある場合、ａｅ２はＰ（Ｂ）の外にあり、これを多角形の和集合の開始辺として選択することができる。ａｅ１がｂｅ１及びｂｅ２の左側にある場合、ａｅ１はＰ（Ｂ）の外にあり、これを多角形和集合の開始辺として選択することができる。（図１５Ｂに示すように）ａｅ２及びａｅ１の両方がｂｅ１及びｂｅ２の左側にある場合は、ａｅ１及びａｅ２はＰ（Ｂ）の外にあり、両方を多角形和集合の開始辺として選択することができる。ａｅ１がｂｅ１及びｂｅ２の左側にあるかどうかを判断するために、図１６に示されるプロセス７００を用いることができる。図１６のプロセス７００を用いて、形状点ｂｐ１がｂｅ１から選択され、形状点ｂｐ２がｂｅ２から選択され、形状点ａｐ１がａｅ１から選択される。これらの辺の上にある他の形状点も同様に選択することもできるが、ノードＮ（点ｐ）へのそれぞれの辺上で最も近い形状点であるためにこれらの形状点が選択される。図１６のプロセス７００は、点ａｐ１が線分ｂｐ１＿ｐ及びｐ＿ｂｐ２の左側にあるかどうかを調べるために用いられる。（図１５Ａに示すように）点ａｐ１が線分ｂｐ１＿ｐ及びｐ＿ｂｐ２の左側にある場合、ａｅ１はｂｅ１及びｂｅ２の左側にあり、よって、Ｐ（Ｂ）の外にあることになる。
【００３４】
ＬＩＮＫ（開始）が識別された後、和集合多角形Ｐ（Ｕ）を形成する次のリンクが識別される。この次のリンクは、ＬＩＮＫ（開始）の非基準端部に連結する全てのリンクを調べることで識別される。図１３Ｂを参照すると、ＬＩＮＫ（開始）の非基準端部は、多角形構成のきまりによって求められる（島については時計回り、穴については逆時計回り。段階６６４）。
リンクすなわちＬＩＮＫ（開始）の非基準端部に連結する他のリンクが一つしかない場合、このリンクが和集合多角形Ｐ（Ｕ）の次のリンクとなる。この次のリンクを示すデータは、和集合多角形Ｐ（Ｕ）を表すために形成されたリストに格納される（段階６７２及び６７６）。
ＬＩＮＫ（開始）の非基準端部に連結する他のリンクが２つ又はそれ以上ある場合には、ＬＩＮＫ（開始）から逆時計回りの方向に最大角度を形成するリンクが、和集合多角形Ｐ（Ｕ）の次のリンクである。次のリンクを示すデータは、和集合多角形Ｐ（Ｕ）を表すために形成されたリストに格納される（段階６７２、６７８及び６７６）。
【００３５】
リンク（即ち、ＬＩＮＫ（開始）の後のリンク）が和集合多角形Ｐ（Ｕ）を表すために形成されたリストに加えられた後、プロセスは、和集合多角形Ｐ（Ｕ）を形成する次のリンクを求めることで継続する。次のリンクは、今述べたのと同様の方法で求められる。つまり、リンクの非基準端部に連結する全てのリンクが識別される（再び段階６６４及び６７２）。他のリンクが一つしかない場合、このリンクが和集合多角形Ｐ（Ｕ）を形成するリンクのリストに加えられる。２つ又はそれ以上の他のリンクがある場合、次のリンクは、和集合多角形Ｐ（Ｕ）の一部として最後に識別されたリンクから逆時計回りの方向に最大角度を形成するものである（再び段階６７８）。
このプロセスは、Ｎ（開始）に至るまで継続する（段階６８０）。Ｎ（開始）に至ると、（Ｐ（Ａ）とＰ（Ｂ）の多角形和集合Ｐ（Ｕ）全体の一部又は全てを形成する）一つの単純多角形が識別される。この単純多角形を表すデータは、リスト６５８内に含まれる。これらのデータは、Ｐ（Ａ）とＰ（Ｂ）の和集合多角形Ｐ（Ｕ）全体のデータ表現７１８（図１３Ｃ）において、単純多角形のリストに加えられる（段階６８４）。
【００３６】
リンク−ノード地図における使用済みの全てのリンク及びノードが取り除かれる（段階６８８）。単純多角形の和集合が識別された後、３つ又はそれ以上の連結されたリンクを有するノードがノード・リンク・マップ内にまだある場合には（図１３Ｂの段階６９２）、第１多角形と第２多角形との間に少なくとももう一つの別の単純多角形和集合がある。このプロセスは、付加的な単純多角形和集合の各々を求めるために繰り返される（図１３Ａの段階６５２で開始する）。このプロセスは、３つ以上のリンクが連結したノードがリンク−ノード地図内になくなるまで繰り返される。
プロセス６２０は、Ｐ（Ａ）及びＰ（Ｂ）において和集合に入れられた穴及び島を見つける。多角形における穴及び島は、図９に関連して上述した。
穴を有する２つの多角形の和集合を求めるとき、和集合内に幾つかの穴が含まれる可能性がある。図１７は、和集合内に穴／島を有する２つの多角形の和集合を表す。
【００３７】
開示されたプロセス６２０が２つの多角形の多角形和集合を求めるために用いられるとき、多角形和集合のデータ表現は、多角形和集合内に位置する元の多角形のいずれかのあらゆる穴の表現を含む。まず、穴の最小境界４角形が、２つの元の多角形の最小境界４角形の重なり部分の外に位置するかどうかの判断がなされる。穴の最小境界４角形が２つの元の多角形の最小境界４角形の和集合内に完全に位置していない場合、穴は多角形和集合内に位置する。穴の最小境界４角形が２つの元の多角形の最小境界４角形の重なり部分内に位置する場合には、穴のあらゆる点（例えば、あらゆるノード）が他方の多角形内に位置するかどうかの判断がなされる。
【００３８】
図１３Ｃは、和集合多角形Ｐ（Ｕ）内の穴／島を扱うためのプロセス６２０における段階を示す。多角形Ａの島／穴から開始し、多角形Ｂ内に直接の親の単純多角形を見つけるために探索がなされる。Ｂ内に親の多角形がない場合、或いはＢ内に直接の親の単純多角形があり、その配向が逆時計回りである場合は、多角形Ａの島／穴は単純和集合多角形である。Ｂ内の親の単純多角形の配向が時計回りの場合は、多角形Ａの島／穴は単純和集合多角形ではない（段階７０２）。これらの段階は、多角形Ａの全ての島／穴が検討されるまで繰り返される（段階７０２）。
【００３９】
このプロセスは、多角形Ｂの島／穴を検討し、多角形Ａにおける直接の親の単純多角形を探索することで継続される。Ａ内に親の多角形がない場合、或いはＡ内に単純多角形があり、その配向が逆時計回りである場合は、多角形Ｂの島／穴は単純和集合多角形である。Ａ内の親の単純多角形の配向が時計回りの場合は、多角形Ｂの島／穴は単純和集合多角形ではない（段階７０６）。この段階は、多角形Ｂの全ての島／穴が調べられるまで繰り返される。
このプロセスは図１７に示される。図１７において、Ｐ（Ａ）は、４つの穴ａ２、ａ３、ａ４、ａ６と、ａ４の中に位置する一つの島ａ５を有する。Ｐ（Ｂ）は、３つの穴ｂ２、ｂ３、ｂ４を有する。Ｐ（Ａ）において、ａ２、ａ３はＰ（Ｂ）内になく、よって和集合に入れられた穴とみなされる。ａ４、ａ６、ａ５はＰ（Ｂ）内にあり、よって和集合に入れられた穴とみなされない。Ｐ（Ｂ）において、ｂ２、ｂ４はＰ（Ａ）内になく、よって和集合に入れられた穴とみなされる。ｂ３はＰ（Ａ）内にあり、よって和集合に入れられた穴とみなされない。
和集合内のあらゆる穴／島について明らかにした後、複雑多角形全体の和集合Ｐ（Ｕ）のデータ表現が、単純多角形のリスト７１８から作られる（段階７０７）。Ｐ（Ａ）とＰ（Ｂ）の和集合は、単純又は複雑のいずれとすることもできる。Ｐ（Ａ）とＰ（Ｂ）の和集合についての情報を有することが必要な他のアプリケーションによって、データ表現Ｐ（Ｕ）を用いることができる。
【００４０】
ＩＶ．利点
多角形の重なり部分及び和集合を求め、多角形を構成する本方法は、従来の方法より必要とする計算が少ない。全体の線分の代わりに多角形の辺が検討されるだけであり、よって計算の量を著しく減少させるので、本方法は、この利点をある程度達成するものである。
【００４１】
Ｖ．更なる考察
一貫した順序−時計回り或いは逆時計回り
上述の実施形態において、多角形のデータ表示が多角形の境界を表すために用いられたリンクのリストを含み、リストに含まれたリンクが、リンクを介して表された多角形境界の時計回りの動きに対応して順序付けられることが説明された。リンクがリスト表示される順序が、地理データベースを通して一貫している限り、多角形を表すために用いられるリンクのリストが、リンクを時計回りの順序で識別することは必要とされない。例えば、他の実施形態によると、多角形の境界を時計回りの順序で形成するリンクをリスト表示する代わりに、多角形のデータ表現がリンクを逆時計回りの順序でリスト表示することができる。逆時計回りの順序を多角形の境界に用いる場合には、多角形内の穴を表すために時計回りの順序を用いるのが好ましいであろう。
上述の詳細な説明は、限定的なものではなく説明のためのものとみなされることを意図しており、さらに、添付の特許請求の範囲は、全ての均等物を含むものであり、本発明の範囲を定めることを意図していることを理解するべきである。
【図面の簡単な説明】
【図１】地理的地域及び該地理的地域に位置する幾つかの特徴のデータ表現を示す図である。
【図２】二次元の地理的地域を表すために用いられる多角形及び該多角形のデータ表現を示す図である。
【図３】２つの多角形の重なり部分を求めるソフトウェアプログラムを示すブロック図である。
【図４】２つの交わる多角形を示し、図３のソフトウェアプログラムによって実行されるプロセスの作動を示す。
【図５Ａ】図３のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図５Ｂ】図３のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図５Ｃ】図３のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図６】図５Ａから図５Ｃまでのプロセスにおける段階を示す。
【図７Ａ】図５Ａから図５Ｃまでのプロセスにおける別の段階を示す。
【図７Ｂ】図５Ａから図５Ｃまでのプロセスにおける別の段階を示す。
【図８】図５Ａから図５Ｃまでのプロセスにおける別の段階を示す。
【図９】穴を有する多角形と、そのデータ表現を示す。
【図１０】重なり部分内に穴を有する多角形の重なり部分を示す。
【図１１】２つの多角形の和集合を求めるソフトウェアプログラムを示すブロック図である。
【図１２Ａ】２つの多角形を示し、図１１のソフトウェアプログラムによって実行されるプロセスの作動を示す。
【図１２Ｂ】２つの多角形を示し、図１１のソフトウェアプログラムによって実行されるプロセスの作動を示す。
【図１３Ａ】図１１のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図１３Ｂ】図１１のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図１３Ｃ】図１１のソフトウェアプログラムによって実行されるプロセスの流れ図である。
【図１４】図１３Ａから図１３Ｃまでのプロセスにおける段階を示す。
【図１５Ａ】図１３Ａから図１３Ｃまでのプロセスにおける別の段階を示す。
【図１５Ｂ】図１３Ａから図１３Ｃまでのプロセスにおける別の段階を示す。
【図１６】図１３Ａから図１３Ｃまでのプロセスにおける別の段階を示す。
【図１７】和集合に入れられた穴／島を扱うための図１３Ａから図１３Ｃまでのプロセスにおける段階を示す。
【図１】
0004477818.tif 000002
【図２】
0004477818.tif 000003
【図３】
0004477818.tif 000004
【図４】
0004477818.tif 000005
【図５Ａ】
0004477818.tif 000006
【図５Ｂ】
0004477818.tif 000007
【図５Ｃ】
0004477818.tif 000008
【図６】
0004477818.tif 000009
【図７Ａ】
0004477818.tif 000010
【図７Ｂ】
0004477818.tif 000011
【図８】
0004477818.tif 000012
【図９】
0004477818.tif 000013
【図１０】
0004477818.tif 000014
【図１１】
0004477818.tif 000015
【図１２Ａ】
0004477818.tif 000016
【図１２Ｂ】
0004477818.tif 000017
【図１３Ａ】
0004477818.tif 000018
【図１３Ｂ】
0004477818.tif 000019
【図１３Ｃ】
0004477818.tif 000020
【図１４】
0004477818.tif 000021
【図１５Ａ】
0004477818.tif 000022
【図１５Ｂ】
0004477818.tif 000023
【図１６】
0004477818.tif 000024
【図１７】
0004477818.tif 000025