(57)【要約】【課題】８０角形以上の多角形がいくつもあり、しかも何度も内外判定する必要がある時、内外判定の速度効率を良くし、しかも判定結果を安定したい。【解決手段】三角形分割されている多角形の各三角形を４分木の各ノードに登録し、４分木上で内外判定対象点が入っている最小ノードに向かう方向の各ノードに登録されている三角形のみとの間で内外判定することで速度効率を良くし多角形の内外判定をする。【選択図】図１
2004078867.tif 000002
【特許請求の範囲】
【請求項１】
三角形分割されている多角形の各三角形を４分木の各ノードに登録し、４分木上で内外判定対象点が入っている最小ノードに向かう方向の各ノードに登録されている三角形のみとの間で内外判定することを特徴とする多角形の内外判定方法。
【請求項２】
凸多角形を三角形分割し、凹多角形を、再帰言語をサポートする言語の分割統治手段を用いて三角形分割することを特徴とする請求項１に記載の多角形の内外判定方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
内外判定の対象となる多角形は、平面上におかれた２次元図形か、３次元図形で、ｚ上空からながめて、ｚ値を無視した多角形で、それは、等高線等の地図情報から３次元三角パッチができていて、上空から見て、多角形のように見える三角形パッチが１つに結びついた閉領域が対象となる。本発明は、凸多角形、凹多角形を三角形分割し、特に凹多角形の分割統治法に基づく凸多角形さらに三角形への分割方法を示し、それらを、領域の４分木構造体に分割統治の手法を生かす合理的な方法で登録し、平面の１点を与えた時、迅速に内外判定をする方法に関する。
【従来の技術】
【０００２】
多角形の内外判定としては、次の２種類の方法が知られていて、通常のグラフィク説明書に記載され、多角形の内外判定、およびコンピュータチップに挿入された内外判定は、このどちらかのアルゴリズムでなされている。
（１）半直線との交点を数える方法（図４参照）
（２）外角の和が３６０度（２πラジアン）になるかで判定する方法（図５参照）
【０００３】
アルゴリズム（１）は、平面上の１点から半直線を引いて、多角形との交点を数え、奇数なら、内点、偶数なら外点と判断するのであるが、この半直線に多角形の頂点が接している場合、２点がどの誤差範囲で同じと判断するか、点が線分上にあることを、どの誤差範囲で、判定するかの関連で、どのように交点数を数えるかに不安定要因があるが、（２）の方法よりも、同じコンピュータの性能のもとで、このアルゴリズムをサポートした時、判定が速いという利便性がある。
【０００４】
図４は、このアルゴリズムを説明したもので、点４０１から出発する半直線と多角形との交点数は３で奇数であるので、点４０１は、多角形の内点と判定され、点４０２から出発する半直線と多角形との交点数は２で偶数であるので、点４０２は多角形の外点と判定される。点４０３から出発する半直線は、多角形の頂点で接していると判定される例で、項点数を数えるときのアルゴリズムを複雑にする不安定要因になる。さらに半直線と多角形の辺の一部が重複する場合も考えられ、重複されると考える誤差範囲との関連で、問題を複雑化する。
【０００５】
特許公開平０９−２３７３４７、特許公開平１１−１４４０４１、特許公開２０００−３２２５８３、特許公開２０００−３２２５８４、特許公開２０００−３２２５８５等は、（１）の方法に沿う内外判定方法である。
【０００６】
アルゴリズム（２）は多角形（ｎ，ｘ［＊］，ｙ［＊］）を反時計まわりに判定ルーチンに入れて、判定点から多角形の頂点への半直線の外角の総和が、計算誤差を考慮して２πラジアンなら、内点と判断し、それ以外なら、外点と判断する。頂点の前の辺から、判定半直線への角度が反時計まわりならプラスの符号で、時計回りならマイナスの符号を与えて総和をとるもので、（１）の方法より判定速度は遅いが、安定しているという利便性もある。
【０００７】
図５は、アルゴリズム（２）を説明したもので、計算誤差があるので、点５０１から各頂点に下した半直線への外角の総和α０＋α１＋．．．＋αｎ−１が計算誤差を考慮して２πラジアンと判定されれば、多角形の内点、そうでなければ、外点と判定される。
【０００８】
公開特許には、完全にこの方向のアルゴリズムは無いが、特許公開平１０−１７１５２０、特許公開２０００−０７６４６５の内外判定方法が、（２）の方法に近い内外判定方法である。
【発明が解決しようとする課題】
【０００９】
本発明で導入する方法（３）は、（１），（２）の方法よりも、コンピュータメモリの容量を必要とし、判定速度が遅いが、何回も内外判定する必要がある場合に効率が良い内外判定の方法として、提案する。
【００１０】
同じ性能をもつコンピュータで、標準的な多角形を作成し、１００点の頂点をランダムに作成し、内外判定の判定速度を調査すれば、頂点数が、少ない多角形では、（１），（２）の方法での内外判定の方が圧倒的に速いが、頂点数が８０点を越すあたりから、判定速度が（１），（２）の方法より効率が良くなることが実験により確かめられている。もちろん、８０角形以上の多角形の形状と三角形分割の仕方により、判定速度が追い越すようになる頂点数にバラつきがあるが、だいたい８０頂点が目安になる。
【００１１】
もちろんグラフィックシステムによれば、多角形の頂点数が最大８０までしか認めてないシステムもあり、それが、この判定方法が今まで認知されてなかった要因の１つであるとも思える。
【課題を解決するための手段】
【００１２】
内外判定の対象となる多角形は、平面上におかれた２次元図形か、３次元図形で、ｚ上空からながめて、ｚ値を無視した多角形で、それは、等高線等の地図情報から３次元三角パッチができていて、上空から見て、多角形のように見える三角形パッチが１つに結びついた閉領域が対象となる。凸多角形、凹多角形が三角形分割されており、特に凹多角形の分割統治法に基づく凸多角形さらに三角形への分割方法が示され、それらは、領域の４分木構造体に分割統治の手法を生かす合理的な方法で登録され、平面の１点を与えた時、迅速に内外判定ができる。
【発明の実施の形態】
【００１３】
コンピュータのソフトウエアを作成した経験者なら、降順か昇順にソートしてあるデータから１データを検索するのに、初めから順良く検索するより二分探索法で探索した方が速く探索できることを知っている。この二分探索法の考え方が分割統治（ｄｉｖｉｄｅ　ａｎｄ　ｃｏｎｑｕｅｒ）という考え方で、これはコンピュータ・ソフトウエア独自の考え方で、速くソフトで計算するには、この考え方を豊富に取り入れたアルゴリズムを採用することである。
【００１４】
本発明は、平面または３次元空間上の１点の多角形による内外判定に、この分割統治の考え方を導入し、多角形の三角パッチ分割によって内外判定をするというものである。
【００１５】
点の内外判定をするｎ多角形は、平面図形（ｎ，ｘ［＊］，ｙ［＊］）か３次元上の図形（ｎ，ｘ［＊］，ｙ［＊］，ｚ［＊］）かであるが、３次元の図形の場合はｚ上空から見て、２次元の時は普通に、重複点、自己交叉がなく反時計回りになっている場合を想定しているが、説明を判りやすくする為、平面図形
（ｎ，ｘ［＊］，ｙ［＊］）＝｛（ｘ［０］，ｙ［０］），（ｘ［１］，ｙ［１］），．．．，（ｘ［ｎ−１］，ｙ［ｎ−１］）｝
の場合で説明する。
【００１６】
この多角形を含む領域は、［１］内外判定を必要とする全ての多角形を含む領域を１つの対象とするか、［２］この多角形のバウンディング・ボックスだけの領域を対象としても良いが、説明を簡単にする為、［２］の場合にアルゴリズムを詳説する。
【００１７】
この多角形を三角形分割して、その構成要素の三角形をｔｒｉｆｉｎｄという４分木に登録するのだが、これからその登録の仕方を説明する。
【００１８】
入力多角形（ｎ，ｘ［＊］，ｙ［＊］）を含むバウンディング・ボックス領域を
（ｘｍｉｎ，ｙｍｉｎ，ｘｍａｘ，ｙｍａｘ）とし、
ｘｍｉｄ＝０．５＊（ｘｍｉｎ＋ｘｍａｘ），ｙｍｉｄ＝０．５＊（ｙｍｉｎ＋ｙｍａｘ）の各辺の中間点で、
最初の４分木領域分割▲１▼（ｘｍｉｎ，ｙｍｉｎ，ｘｍｉｄ，ｙｍｉｄ），▲２▼（ｘｍｉｄ，ｙｍｉｎ，ｘｍａｘ，ｙｍｉｄ），▲３▼（ｘｍｉｄ，ｙｍｉｄ，ｘｍａｘ，ｙｍａｘ），▲４▼（ｘｍｉｎ，ｙｍｉｄ，ｘｍｉｄ，ｙｍａｘ）をする。
今登録しようとしている三角形のバウンディング・ボックスが、▲１▼〜▲４▼のどの領域にも含まれないなら、この４分木のトップノードにこの三角形を登録する。
【００１９】
今例えば▲１▼の領域に含まれているなら、この▲１▼の領域を各辺の中点で、４分割して、どれかの領域に含まれないかチェックする。どれにも含まれないなら、▲１▼の分割のノードに、この三角形を登録し、ある分割に含まれるなら、その分割の４分木構造に入り、また中点で、４分割し、どの分割に入るかをチェックし、どれにも入らなければ、そこの分割のノードに三角形を登録する。入力三角形は、縮退していないと仮定され、４分木を下っていった時、どこかで、どの４分割にも含まれないことが、成り立ち、そこのノードに登録される。４分割の各ノードは、入力三角形が、ある分割に入ると判った段階でメモリ領域が作成され、それ以外は、ＮＵＬＬのノードにしておく。
【００２０】
次に、平面上の１点Ｐ（ｘ，ｙ）が与えられた時、どのように内外判定されるかを説明する。これは、点Ｐがトップ・ノードの領域にあれば、この点が入っている最小のノードに向かう方向の各ノードに登録されている三角形のみとの間での内外判定することを特徴とする多角形の内外判定方法である。
【００２１】
点Ｐがｔｒｉｆｉｎｄのトップ・ノードの領域（ｘｍｉｎ，ｙｍｉｎ，ｘｍａｘ，ｙｍａｘ）に入らなければ外（ｏｕｔ）と判定され、入ればここのノードに登録されている三角形に対し内外判定がなされる。そこで内（ｉｎ）と判定されれば、それで判定は終了し内である。トップノードに登録されている三角形の全てに外と判定されたのなら、これが４分割されている４分木領域分割▲１▼、▲２▼、▲３▼、▲４▼に降りていき、点Ｐ（ｘ，ｙ）が含まれる領域が対象となる。
【００２２】
今▲１▼（ｘｍｉｎ，ｙｍｉｎ，ｘｍｉｄ，ｙｍｉｄ）の領域に点Ｐが含まれ、すなわち　ｘ≧ｘｍｉｎ，ｘ≦ｘｍｉｄ，ｙ≧ｙｍｉｎ，ｙ≦ｙｍｉｄで、そのノードがＮＵＬＬでないと判定されたら、▲１▼のノードに登録されている三角形に関し内外判定され、どれか１つの三角形で、内と判定されたら、判定は終了し内である。そうでないなら、再び、この４分割で、Ｐ（ｘ，ｙ）をふくみノードがＮＵＬＬでない領域の登録三角形に対し同様な操作が繰り替えされる。これで、ある領域の４分割ノードが全てＮＵＬＬなら、これ以上深くノードを探索せずに、外と判定される。
【００２３】
内外判定の検査点が前の検査点と近くの点が次に検査されると判っている状況下では、前に内と判定されたノードかその三角形へのポインターを登録しておいて、そこから、先に内外判定することにして、さらに速度の高速化を測ることもできる。また検査点領域が、４分木のトップノードの領域の一部でしか検査されないことがわかっている場合、その検査点領域と交叉する４分木の分割領域の頂上ノードを取り出せる関数を用意して、そのノード以下の４分木に対し、同様な内外判定をすれば良いので、さらに高速化を測ることができる。
【００２４】
次に点Ｐ（ｘ，ｙ）の三角形Ｐ（１）（ｘ（１），ｙ（１）），Ｐ（２）（ｘ（２），ｙ（２）），Ｐ（３）（ｘ（３），ｙ（３））での内外判定の仕方を述べる。この３角形は縮退していないので、頂点は一次独立であり、点Ｐ（ｘ、ｙ）は、
2004078867.tif 000003
と一意に表現されることが知られ（λ（１），λ（２），λ（３））は、この三角形の三角形座標と呼ばれている。具体的には、
2004078867.tif 000004
を解いて係数（λ（１），λ（２），λ（３））を決定するのだが、これは３つの未知数をもつ３元連立線型方程式で、頂点が一次独立なことから、必ず解け、しかも現在のコンピュータで高速に解が得られる。
【００２５】
ここで全てのλ（ｉ），ｉ＝１，２，３が
λ（ｉ）≧　０　かつ　λ（ｉ）≦　１
（式２）
なら内点と判定され、それ以外なら外点と判定される。λ（ｉ）≧　０　が全てのｉ，ｉ＝１，２，３に対して成立するなら、数学的に　λ（ｉ）≦　１　となり後の条件は不必要なのだが、安全策のために入れておいた。もちろん係数が０以上という条件は、それぞれのシステムの誤差条件を考慮して決定して良い。またｉ＝１，２に対し、式２が成立するならｉ＝３に対しても式２が成立することも導けるのだが、これをｉ＝１，２，３と計算することによる速度の減少の影響は、現在の高速の計算コンピュータでは、すごく小さい。
【実施例】
【００２６】
実施例を図１、図２、図３により説明する。図１は、三角形分割されている多角形の一例で、この例では、多角形が三角形ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇの７つの三角形に分割されている。
【００２７】
図２では、図１の三角形分割されている多角形のバウンディング・ボックス領域（ｘｍｉｎ，ｙｍｉｎ，ｘｍａｘ，ｙｍａｘ）が４分割され、４分木構造体ｔｒｉｆｉｎｄの各ノードの領域と分割三角形の位置関係を示している。三角形ｂ，ｃ，ｄ，ｆは４分割されたノード▲１▼、▲２▼、▲３▼、▲４▼の単独の領域には含まれないので、図３で、トップ・ノードに登録される。三角形ａは、ノード▲２▼の領域に含まれ、ノード▲２▼の長方形領域を各辺の中点で４分割した領域に単独には、含まれないので、図３のノード▲２▼に登録される。同様に三角形ｅは図３のノード▲４▼に登録され、三角形ｇは図３のノード▲１▼に登録される。ノード▲１▼の長方形領域を各辺の中点で４分割しても、その分割した領域に単独で入る分割三角形は、無いので、図３のノード▲１▼の４分割ノードはどれもＮＵＬＬになっている。　同様に、ノード▲３▼の長方形領域に単独で入る分割三角形は、無いので図３のノード▲３▼はＮＵＬＬになっている。
【００２８】
今、図２のノード▲２▼の領域にある点２０１の多角形に対する内外判定が、どのように実施されるかを示す。まず図３のトップ・ノードに登録されてある三角形ｂ，ｃ，ｄ，ｆとの内外判定が成され、どれも外と判定される。次に点２０１の属する最小ノード▲２▼に登録されてある三角形ａとの内外判定が成され、やはり外と判定される。ノード▲２▼以下の４つの分割ノードは分割三角形が登録されておらず、ＮＵＬＬなので、これ以上内外判定の探索は、おこなわれず、点２０１は多角形の外と判定される。この判定において、三角形ｇ，ｅとの内外判定は、行われず、このことが内外判定速度を速くする要因となる。
【００２９】
次に多角形の三角形分割について記述する。多角形がすでに三角形分割されているなら、その三角形を上述の４分木構造体ｔｒｉｆｉｎｄに登録する。これは多角形の中に、いくつかの標高点があり、その標高点を頂点として三角形分割されるシステムとか、細長い多角形があり、他の方法で三角形分割した方が、針のように細長い三角形ができるのを避けたり都合の良い場合が生ずるからである。これは、多角形の三角形分割を他の用度に使用した方が、点の多角形の内外判定だけに使用するよりもシステム全体としては、効率が良いと使用者が判断して決定することである。
【００３０】
また多角形の中に三角パッチの頂点が通る点が指定されてある場合は、各点との距離が他のどの点よりも近いものを表す領域の境界図（ボロノイ図という）を作成し、ボロノイ図の境界辺がある点同士を線分で結んでできたドローネ三角形分割を使用したら、できるだけ正三角形に近い指定点を通る三角形分割ができるが、それを使用することによって生ずる、このアルゴリズムの速度の鈍化は、この内外判定方法の考慮範囲外である。
【００３１】
ここでは、速度の速い三角形分割として、再帰ルーチンをサポートしている言語における以下のような分割統治の考え方による凸分割・三角形分割のアルゴリズムを提唱する。
【００３２】
今多角形Ｐ（０）（ｘ［０］，ｙ［０］），Ｐ（１）（ｘ［１］，ｙ［１］），．．．，Ｐ（ｎ−１）（ｘ［ｎ−１］，ｙ［ｎ−１］）が重複点、自己交叉がない反時計回りの凸多角形なら、これを三角形分割する時、新たに頂点を付加して良いなら、その点を
Ｏ（ｘｘ，ｙｙ）とし、
三角形（Ｏ，Ｐ（０），Ｐ（１）），（Ｏ，Ｐ（１），Ｐ（２）），（Ｏ，Ｐ（２），Ｐ（３）），．．．，（Ｏ，Ｐ（ｎ−１），Ｏ（０））を４分木構造体ｔｒｉｆｉｎｄに登録する。Ｏの点としては、ｍ＝ｎ／２なる正の整数とした時の平均値
Ｏ＝（Ｐ（０）＋Ｐ（ｍ））／２
（式３・Ａ）
すなわち、成分表示では
ｘｘ＝（ｘ［０］＋ｘ［ｍ］）／２，　ｙｙ＝（ｙ［０］＋ｙ［ｍ］）／２
（式３・Ｂ）
として決定しても良いし、多角形上の対心点のいくつかのペアーの平均値としても良い。
【００３３】
また、新たに頂点を付加しない分割なら、三角形（Ｐ（０），Ｐ（１），Ｐ（２）），（Ｐ（０），Ｐ（２），Ｐ（３）），．．．，（Ｐ（０），Ｐ（ｎ−２），Ｐ（ｎ−１）），を４分木構造体ｔｒｉｆｉｎｄに登録する。
【００３４】
ここで、多角形Ｐ（０）（ｘ［０］，ｙ［０］），Ｐ（１）（ｘ［１］，ｙ［１］），．．．Ｐ（ｎ−１）（ｘ［ｎ−１］，ｙ［ｎ−１］）が重複点、自己交叉がない反時計回りの一般的な凹多角形のメインの再帰処理を備えた言語での分割統治の手法に基づく処理ルーチンを紹介する。これは、凹多角形を分割統治の考え方で凸多角形に分割し、凸部分は、上記のルーチンで三角形部分に分け、４分木構造体ｔｒｉｆｉｎｄに登録するものである。
【００３５】
まず辺Ｐ（０）Ｐ（１）を凸分割の１辺として採用する。次に辺Ｐ（０）Ｐ（１）と辺Ｐ（１）Ｐ（２）の角度を反時計回りに測ってこれが、１直線の角度πラジアンより大きいなら、このメインの凸分割の他の１辺として採用する。そうでないなら、辺Ｐ（１）Ｐ（３），辺Ｐ（１）Ｐ（４），．．．，辺Ｐ（１）Ｐ（ｍ）、（ｍ＜ｎ）と辺Ｐ（０）Ｐ（１）からの反時計まわりの角度を計算していく。今最初に辺Ｐ（０）Ｐ（１）と辺Ｐ（１）Ｐ（ｍ）の反時計回りの角度が１直線の角度πラジアンより大きくなったとしたら、頂点列｛Ｐ（１），Ｐ（２），．．．．．Ｐ（ｍ）｝をメインの再帰ルーチンに送り込み、再び凸分割の処理を続行させる。
【００３６】
さて今、メインの凸分割ルーチンで、辺Ｐ（０）Ｐ（１），辺Ｐ（１）Ｐ（ｍ）（ｍ＜ｎ）が反時計まわりに測って最初の１直線の角度πラジアンより大きくなった角度とする。ここでｍ＝ｎ−１なら、頂点列｛Ｐ（０），Ｐ（１），Ｐ（ｍ）｝は三角形で凸多角形であるので、これは４分木構造体ｔｒｉｆｉｎｄに登録する。ｍがｎ−１より小さいなら、Ｐ（ｍ）とＰ（０）を結ぶ線分と折れ線｛Ｐ（ｍ），Ｐ（ｍ＋１），．．．，Ｐ（ｎ−１），Ｐ（０）｝の交点を計算し、交点がこの折れ線の始点Ｐ（ｍ）と終点Ｐ（０）以外に交点が無ければ、Ｐ（１）Ｐ（ｍ）はメインの凸多角形の辺と解釈し、そうでなければ、
頂点列｛Ｐ（ｍ），Ｐ（ｍ＋１），Ｐ（ｍ＋２），．．．，Ｐ（ｎ−１），Ｐ（０），Ｐ（１）｝をメインの再帰ルーチンに送り込む。どんな凹多角形でも、連続する３点でできる三角形が凹多角形の内部に含まれる部分を持つので、これが無限再帰ルーチンになることは無い。
【００３７】
さて今辺Ｐ（０）Ｐ（１），辺Ｐ（１）Ｐ（ｍ）（ｍ＜ｎ−１）がメインの凸多角形の辺と解釈されたら、次にＰ（ｍ＋１）とＰ（０）を結ぶ線分と折れ線｛Ｐ（ｍ＋１），Ｐ（ｍ＋２），．．．，Ｐ（ｎ−１），Ｐ（０）｝の交点を計算し、交点がこの折れ線の始点Ｐ（ｍ＋１）と終点Ｐ（０）以外に交点が無く、辺Ｐ（ｍ＋１）Ｐ（０）と辺Ｐ（０）Ｐ（１）の角度がこの順序で反時計回りに測って直線の角πラジアンより大きければ、辺Ｐ（ｍ）Ｐ（ｍ＋１）はメインの凸多角形の辺と解釈され、そうでなければ、三角形Ｐ（０）Ｐ（１）Ｐ（ｍ）を４分木構造体ｔｒｉｆｉｎｄに登録し、頂点列｛Ｐ（０），Ｐ（１），Ｐ（ｍ），Ｐ（ｍ＋１），．．．，Ｐ（ｎ−１）｝をメインの再帰ルーチンに送り込む。
【００３８】
さて一般的に辺Ｐ（０），Ｐ（１），辺Ｐ（１）Ｐ（ｍ），辺Ｐ（ｍ）Ｐ（ｍ＋１），．．．，辺Ｐ（ｍ＋ｋ−１）Ｐ（ｍ＋ｋ）（ｍ＜ｎ−２，ｍ＋ｋ＜ｎ）がメインの凸多角形の辺と解釈されたら、もしｍ＋ｋ＝ｎ−１ならこれを上記の凸多角形の三角形分割のルーチンに送り処理は終了する。
ｍ＋ｋ＜ｎ−１なら、頂点Ｐ（ｍ＋ｋ＋１）とＰ（０）を結ぶ線分と折れ線
｛Ｐ（ｍ＋ｋ＋１），Ｐ（ｍ＋ｋ＋２），．．．，Ｐ（ｎ−１），Ｐ（０）｝の交点を計算し、この折れ線の始点Ｐ（ｍ＋ｋ＋１）と終点Ｐ（０）以外に交点が無く、辺Ｐ（ｍ＋ｋ＋１）Ｐ（０）と辺Ｐ（０）Ｐ（１）との角度をこの順序で反時計回りに測って直線の角πラジアンより大きければ、辺Ｐ（ｍ＋ｋ）Ｐ（ｍ＋ｋ＋１）はメインの凸多角形の辺と解釈し処理は続行され、そうでなければ、頂点列｛Ｐ（０），Ｐ（１），Ｐ（ｍ），Ｐ（ｍ＋１），．．．，Ｐ（ｍ＋ｋ−１），Ｐ（ｍ＋ｋ）｝は、上記の凸多角形の三角形分割のルーチンに送り、
頂点列｛Ｐ（０），Ｐ（ｍ＋ｋ），Ｐ（ｍ＋ｋ＋１），．．．，Ｐ（ｎ−１）｝は、メインの再帰ルーチンに送り込まれ処理は終了となる。
この処理により、凹多角形が、頂点数が少ない凸多角形に分割され、さらに三角形分割され、４分木構造体ｔｒｉｆｉｎｄに送りこまれ、分割統治の手法で高速に処理される。
【００３９】
最後に、本発明は、３次元空間での多面体の４面体分割での８分木登録による空間上の点の多面体内外判定に容易に拡張できるが、半直線と交面の個数による内外判定との効率比較は、されておらず、さらに、多面体の４面体分割のアルゴリズムは、平面の場合の凹多角形の三角形分割より複雑になることが想定されるので、本発明の請求項の範囲外としている。
【００４０】
【発明の効果】
本発明は、８０角形以上の多角形の点の内外判定に対し有効であるが、アルゴリズム自体は、どんな多角形の点の内外判定にも適応でき、他の判定方法に対しｔｒｉｆｉｎｄという構造体のメモリを保有しなければならないという不利があるが、何度でも内外判定をする必要がある時、非常に効率が良い方法であることが確認されている。
【図面の簡単な説明】
【図１】本発明による三角形分割されている多角形の実施例を示す図である。
【図２】図１の実施例の４分木分割領域と分割三角形の関係を示す図である。
【図３】図１の実施例の４分木構造を示す図である。
【図４】従来の半直線と多角形の交点の個数による内外判定方法を示した図である。
【図５】従来の外角の和による内外判定方法を示した図である。
【図１】
2004078867.tif 000005
【図２】
2004078867.tif 000006
【図３】
2004078867.tif 000007
【図４】
2004078867.tif 000008
【図５】
2004078867.tif 000009