(57)【要約】 【課題】  任意の図形に対して任意の判別点がその内側にあるか外側にあるか、正確かつ容易に判別できるようにする。【解決手段】  複数の頂点を結んで閉じるように形成された図形に対し、判別点Ｐから最短距離にある前記図形の頂点間の距離を求める。判別点Ｐと当該頂点との距離がベクトル外積法を適用して誤判別が発生しない範囲以内においては、ベクトル外積法を用い、判別点Ｐが図形の内側に位置するか外側に位置するか判別する。その範囲外においては、コーシーの積分定理を用い、判別点Ｐが図形の内側に位置するか外側に位置するか判別する。【選択図】  図１
2008287337.tif 000002
【特許請求の範囲】
【請求項１】
複数の頂点を結んで閉じるように形成された図形に対し、判別点から最短距離にある前記図形の頂点との距離を求め、前記判別点と当該頂点との距離がベクトル外積法を適用しても誤判別が発生しない範囲以内においては、前記ベクトル外積法を用いて前記判別点が前記図形の内側に位置するか外側に位置するか判別し、前記範囲外においては、コーシーの積分定理を適用して前記判別点が前記図形の内側に位置するか外側に位置するか判別することを特徴とする図形に対する内点判別方法。
【請求項２】
前記ベクトル外積法は、前記判別点を始点とし前記最短距離にある頂点の右回りに隣接する頂点を終点とするベクトルと、当該頂点の右回りに隣接する頂点を始点とし当該頂点を終点とするベクトルの外積、および前記判別点を始点とし当該頂点を終点とするベクトルと、当該頂点を始点とし当該頂点の左回りに隣接する頂点を終点とするベクトルの外積の二つベクトル外積の結果により、前記判別点が前記図形の内側に位置するか外側に位置するか判別する請求項１記載の図形に対する内点判別方法。
【請求項３】
前記ベクトル外積法は、前記判別点が前記図形の内側に位置するか外側に位置するか判別する際に、誤判別が発生しない当該頂点と前記判別点の距離を算出し、その範囲内で前記ベクトル外積による前記判別点が前記図形の内側に位置するか外側に位置するか判別する請求項２記載の図形に対する内点判別方法。
【請求項４】
前記範囲は、前記図形を形成するある辺とその辺の端点を除く全ての図形の頂点との距離を求める計算を全ての辺について行い、それら求めた辺と頂点との距離の最小値以下とする請求項１〜３いずれか１記載の図形に対する内点判別法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は図形に対する内点判別方法に係り、例えば任意の点が任意の図形に対してその内側にあるか外側にあるかをコンピュータによって数値シミュレーション可能な図形の内点判定方法の改良に関する。
【背景技術】
【０００２】
現在、例えば、加熱ヒータによって加熱制御する種々の被加熱物について、被加熱物の外形形状が任意の形状であっても、その測定点が被加熱物の内部か外部か判別できれば、測定点の正確な測定温度をコンピュータによって数値シミュレーション可能で、被加熱物に対する正確な加熱制御に寄与する。
【０００３】
そのため、ある判別点が図形や物体の内側に位置するか外側に位置するかの正確な判別が重要である。
【０００４】
そこで、例えば特開平１１−１１０５６９号公報（特許文献１）等の方法が提案されている。
【０００５】
この特許文献１は、図１２に示すように、ステップＳ１にて図形を形成する頂点のデータを読み込み、ステップＳ２でその図形の形状を算出認識し、ステップＳ３にて図形が凸多角形か否か判別し、図形が凸多角形であってステップＳ３がＹｅｓであれば、ステップＳ４にてベクトル外積法を用いて全ての判別点が図形の内部にあるか否かを判別して終了し、図形が凸多角形ではなくステップＳ３がＮｏであれば、ステップＳ５にてコーシーの積分定理を用いて全ての判別点が図形の内部にあるか否かを判別して終了する処理手順を有し、図形が凸多角形であれば、全ての判別点に対してベクトル外積法を適用して処理負担を軽減しようとするものである。
【特許文献１】特開平１１−１１０５６９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した特許文献１では、凹部のない単純な凸多角形の場合は処理可能であるが、凹部があるといった複雑な多角形（非凸多角形）では、ベクトル外積を使用すると判定の誤りが生じ易く、全ての判別点をコーシーの積分定理で処理することになり、ベクトル外積法を用いるよりも計算処理負荷が重くなり易い欠点がある。
【０００７】
さらに、コーシーの積分定理は、判別点と図形を形成する頂点が一致又は近接すると、演算結果にいわゆる零割が発生して判別困難となる場合があり、処理能力の極めて高いコンピュータを用いないと判別精度が向上しない難点がある。
【０００８】
本発明はそのような課題を解決するためになされたもので、任意の判別点が任意の図形の内側にあるか外側にあるか正確かつ容易に判別可能な図形に対する内点判別方法の提供を目的とする。
【課題を解決するための手段】
【０００９】
そのような課題を解決するために本発明に係る図形に対する内点判別方法は、複数の頂点を結んで閉じるように形成された図形に対し、その判別点から最短距離にある頂点間の距離を求め、その判別点と当該頂点との距離がベクトル外積法を適用しても誤判別が発生しない範囲以内においては、ベクトル外積法を用いてその判別点がその図形の内側に位置するか外側に位置するか判別し、その範囲外においては、コーシーの積分定理を適用してその判別点がその図形の内側に位置するか外側に位置するか判別するものである。
【００１０】
本発明の内点判別方法における上記ベクトル外積法は、その判別点を始点とし上記最短距離にある頂点の右回りに隣接する頂点を終点とするベクトルと、当該頂点の右回りに隣接する頂点を始点とし当該頂点を終点とするベクトルの外積、およびその判別点を始点とし当該頂点を終点とするベクトルと、当該頂点を始点とし当該頂点の左回りに隣接する頂点を終点とするベクトルの外積の二つベクトル外積の結果により、その判別点が上記図形の内側に位置するか外側に位置するか判別する構成が好ましい。
【００１１】
本発明の内点判別方法における上記ベクトル外積法は、その判別点が当該図形の内側に位置するか外側に位置するか判別する際に、誤判別が発生しない当該頂点と判別点の距離を算出し、その範囲内でそのベクトル外積による判別点が当該図形の内側に位置するか外側に位置するか判別する構成も可能である。
【００１２】
本発明の内点判別方法では、上記範囲として、上記図形を形成するある辺とその辺の端点を除く全ての図形の頂点との距離を求める計算を全ての辺について行い、それら求めた辺と頂点との距離の最小値以下とする構成も可能である。
【発明の効果】
【００１３】
このような本発明に係る内点判別方法では、任意の図形を形成する頂点のうち判別点から最短距離にある頂点との距離を求め、その距離がベクトル外積法を適用しても誤判別が発生しない範囲以内においてはベクトル外積法を用い、その範囲外においてはコーシーの積分定理を適用してその判別点の位置を判別するから、任意の判別点と任意の図形との関係で、その判別点が図形の内側にあるか外側にあるか、正確かつ容易に判別可能となる。
【００１４】
また、本発明における上記ベクトル外積法が、その判別点を始点とし上記最短距離にある頂点の右回りに隣接する頂点を終点とするベクトルと、当該頂点の右回りに隣接する頂点を始点とし当該頂点を終点とするベクトルの外積、およびその判別点を始点とし当該頂点を終点とするベクトルと、当該頂点を始点とし当該頂点の左回りに隣接する頂点を終点とするベクトルの外積の二つベクトル外積の結果により、その判別点が上記図形の内側に位置するか外側に位置するか判別する構成では、具体的に判別可能となる。
【００１５】
さらに、本発明における上記ベクトル外積法が、その判別点が当該図形の内側に位置するか外側に位置するか判別する際に、誤判別が発生しない当該頂点と判別点の距離を算出し、その範囲内でそのベクトル外積による判別点が当該図形の内側に位置するか外側に位置するか判別する構成では、より具体的に判別可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を図面を参照して説明する。
【００１７】
図１、図２、図３および図４は本発明に係る内点判別方法の実施の形態を説明するフローチャートである。
【００１８】
ここで、本発明に係る内点判別方法の実施の形態を説明する前に、便宜上、本発明の内点判別方法の前提となる考え方、特にベクトル外積法について考察しておく。
【００１９】
従来のベクトル外積法では、図５Ａ、Ｂに示すように、複数の頂点（Ｚ[0]〜Ｚ[n-1]）を結んで閉じるように形成された図形に対し、それら図形の各頂点（Ｚ[0]〜Ｚ[n-1]）と判別点Ｐとを結ぶベクトルと、それら個々の頂点（Ｚ[0]〜Ｚ[n-1]）と左回りに隣接する頂点（Ｚ[1]〜Ｚ[n]、但しＺ[0]＝Ｚ[n]）とのベクトルとで外積計算している。
【００２０】
図形を形成する全ての頂点（Ｚ[0]〜Ｚ[n-1]）で同様のベクトル外積計算を行ったとき、全ての計算結果が「０」以上、すなわち判別点Ｐと図形の頂点（Ｚ[0]〜Ｚ[n-1]）を結ぶベクトル方向に対し、図形の各頂点（Ｚ[0]〜Ｚ[n-1]から左回りに隣接する各頂点（Ｚ[1]〜Ｚ[n]）を結ぶベクトル方向が全て左側に折れている場合、判別点Ｐが図形の内側に位置すると判断し（図５Ａ）、１個でも右側に折れていたら判別点Ｐが図形の外側に位置すると判断していた（同図Ｂ）。
【００２１】
ところが、例えば図６に示すように、一部の頂点（Ｚ[k]）が凹状に窪んだ位置に位置する図形では、判別点Ｐが内側にあっても全てのベクトル外積の演算結果が「０」以上にならないため、従来のベクトル外積法をそのまま適用できない。
【００２２】
そこで、本願のべクトル外積法においては、図７および図８に示すように、判別点Ｐから最短距離にある図形の頂点Ｚ[k]との間の距離と、その頂点Ｚ[k]の前後の頂点Ｚ[k-1]、Ｚ[k+1]で各々形成されるベクトルの向きに着目した。
【００２３】
すなわち、図７および図８において、判別点Ｐと最短距離にある図形の頂点Ｚ[k]を求め、その前後の頂点Ｚ[k-1]、Ｚ[k+1]とで形成する頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルの外積がプラス、つまり頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルが左回り（紙面上）に三角形を形成し（図７）、判別点Ｐが図７Ａ、Ｂの斜線部の領域にあるとき、Ｚ[k-1]とＺ[k]間のベクトルと判別点ＰとＺ[k-1]間のベクトルの外積が「０」以上（図７Ａ）、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積が「０」以上（図７-Ｂ）となる。
【００２４】
なお、それら図７、図８は、判別点Ｐがその最短距離にある図形の頂点Ｚ[k]からの距離を制限した場合（すなわち円弧内）、判別点Ｐが図形の内側であるか外側であるかを、ベクトル外積法を用いて判別可能であることを示すための図であり、図中の斜線領域は同じ判別結果となる領域を示したものである。
【００２５】
さらに、図７Ｃ、Ｄのように、判別点Ｐが斜線部の領域にあるとき、Ｚ[k-1]とＺ[k]間のベクトルと判別点ＰとＺ[k-1]間のベクトルの外積が「０」以上、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積が「０」以上とならない。
【００２６】
つまり、判別点Ｐと最短距離にある図形の頂点Ｚ[k]とその前後の頂点Ｚ[k-1]、Ｚ[k+1]とで形成する頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルの外積がプラスでそれらベクトルが左回りに三角形を形成しているとき、頂点Ｚ[k-1]とＺ[k]間のベクトルと判別点Ｐと頂点Ｚ[k-1]間のベクトルの外積が「０」以上、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積が「０」以上であれば、判別点Ｐは図形の内側であると判断できる。
【００２７】
他方、頂点Ｚ[k-1]とＺ[k]間のベクトルと判別点Ｐと頂点Ｚ[k-1]間のベクトルの外積が「０」以上、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積が「０」以上でなければ、図形の外側であると判断できる。
【００２８】
そして、判別点Ｐと最短距離にある図形の頂点Ｚ[k]を求め、その前後の頂点Ｚ[k-1]、Ｚ[k+1]とで形成する頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルの外積がマイナス、つまり頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルが右回りに三角形を形成し（図８）、判別点Ｐが図８Ａ、Ｂの斜線部の領域にあるとき、Ｚ[k-1]とＺ[k]間のベクトルと判別点ＰとＺ[k-1]間のベクトルの外積がマイナス（図８Ａ）、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]のベクトルの外積がマイナス（図８Ｂ）となる。
【００２９】
さらに、図８Ｃ、Ｄに示すように、判別点Ｐが斜線部の領域にあるとき、Ｚ[k-1]とＺ[k]間のベクトルと判別点ＰとＺ[k-1]間のベクトルの外積がマイナス、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積がマイナスとならない。
【００３０】
つまり、判別点Ｐと最短距離にある図形の頂点Ｚ[k]とその前後の頂点Ｚ[k-1]、Ｚ[k+1]とで形成する頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルの外積がマイナスでそれらベクトルが左回りに三角形を形成しているとき、頂点Ｚ[k-1]とＺ[k]間のベクトルと判別点Ｐと頂点Ｚ[k-1]間のベクトルの外積がマイナス、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積がマイナスであれば、判別点Ｐは図形の外部であると判断できる。
【００３１】
他方、頂点Ｚ[k-1]とＺ[k]間のベクトルと判別点Ｐと頂点Ｚ[k-1]間のベクトルの外積がマイナス、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積がマイナスでなければ、図形の外側であると判断できる。
【００３２】
もっとも、図９Ａ、Ｂのように、判別点Ｐが位置にあるとき、判別点Ｐと最短距離にある図形の頂点Ｚ[k]とその前後の頂点Ｚ[k-1]、Ｚ[k+1]とで形成する頂点Ｚ[k-1]とＺ[k]間のベクトルと頂点Ｚ[k]とＺ[k+1]間のベクトルの外積がプラスでそれらベクトルが左回りに三角形を形成し、頂点Ｚ[k-1]とＺ[k]間のベクトルと判別点Ｐと頂点Ｚ[k-1]間のベクトルの外積が「０」以上、かつＺ[k]とＺ[k+1]間のベクトルと判別点ＰとＺ[k]間のベクトルの外積が「０」以上であるにもかかわらず、判別点Ｐは図形の外部にある。
【００３３】
なお、図９は、ベクトル外積法を用いて判別する方法において、判別点Ｐとその最短距離にある図形の頂点Ｚ[k]の距離を制限しないと、判別誤りを生じる例を示すものである。
【００３４】
このような現象を除外するために、ベクトル外積法の適用に当たり、判別点Ｐの最短距離にある図形の頂点Ｚ[k]と判別点Ｐとの距離を短く制限し、例えば、図９Ｃ、Ｄの点線で囲まれた領域内に判別点Ｐが存在する場合にのみ本願のベクトル外積法を適用し、領域外ではコーシーの積分定理を適用することにする。
【００３５】
本願のベクトル外積法を用いて誤判別（判別エラー）の発生しない範囲の堺を、本願では便宜上「臨界値」と称する。
【００３６】
そして、本願のベクトル外積法を適用する全ての判別点Ｐに対して図９Ａのような誤判別を生じさせないためには、臨界値を予め求めておく必要がある。
【００３７】
例えば図９において判別点Ｐが点線で描かれた円の中にあれば、誤判別は発生しない。つまり、判別点Ｐとその最短距離にある図形の頂点Ｚ[k]との距離が、図形のＺ[n-1]−Ｚ[0]間の辺と図形の頂点Ｚ[k]との距離以下であれば誤判別とならない。
【００３８】
そこで、図形を形成する全ての辺と全ての頂点に拡張して考えると、図形を形成するある辺とその辺の端点を除く全ての図形の頂点との距離を求める計算を全ての辺について行い、これらの求めた辺と頂点との距離の最小値を以下臨界値とし、判別点Ｐとその最短距離にある図形の頂点との距離がこの臨界値以下であれば、本願のベクトル外積法を適用しても誤判別が発生しないことが判った。
【００３９】
図１０ではＺ[k]−Ｚ[k+1]間で作る辺に対して、その辺の端点でない図形の頂点Ｚ[j]を順番に移動させて頂点Ｚ[j]と辺Ｚ[k]−Ｚ[k+1]で形成される三角形を表したものである。
【００４０】
図形を形成する全ての辺とその辺の端点でない図形の頂点との距離は、図形の頂点と前記図形の辺を底辺として形成する三角形において、その三角形が鋭角三角形又は直角三角形のときはその三角形の高さとし（図１１Ａ、Ｂ、Ｃ）、その三角形が鈍角三角形でのときに鈍角をなす頂点が前期頂点であれば、その三角形の高さとし（図１１Ｄ）、その三角形が鈍角三角形でのときに鈍角をなす頂点が前期頂点以外であれば、鈍角をなす頂点と前期頂点を結ぶ辺の長さとする（図１１Ｅ）。
【００４１】
次に、本発明に係る内点判別方法の実施の形態を図１〜図４を参照して説明する。
【００４２】
図１は本発明に係る内点判別方法の実施の形態を示すフローチャートである。
【００４３】
図１において、ステップＳ１０１にて図形を形成する全頂点（Ｚ[0]〜Ｚ[n-1]）のデータを読み込み、ステップＳ１０２にてベクトル外積法の適用可能な図形の頂点Ｚ[k]からの距離、すなわち臨界値Ａを計算する。臨界値Ａを求める詳細な説明は後述する。
【００４４】
次いで、ステップＳ１０３にて全判別点（Ｐ[i]：Ｐ[0]〜Ｐ[m-1]）のデータを読み込み、ステップＳ１０４にて判別点Ｐ[i]の配列子を初期化し、ステップＳ１０５にて判別点Ｐ[i]に最も近い図形の頂点Ｚ[k]との距離Ｌを求める。
【００４５】
さらに、ステップＳ１０６にて判別点Ｐ[i]に最も近い頂点Ｚ[k]までの距離Ｌと、ベクトル外積法を適用可能な臨界値Ａとを比較する。
【００４６】
距離Ｌと臨界値Ａとの関係がＬ≦Ａであって、ステップＳ１０６がＹｅｓであればステップＳ１０７に移り、ステップＳ１０７にてベクトル外積法を用いて判断点Ｐ[i]が図形の内側か否かの判断を行う。本発明におけるベクトル外積法の具体的処理については後述する。
【００４７】
他方、距離Ｌと臨界値Ａとの関係がＬ＞Ａであって、ステップＳ１０６がＮｏであればステップＳ１０８に移り、ステップＳ１０８にてコーシーの積分定理を用いて判断点Ｐ[i]が図形の内側か否かの判断を行う。本発明におけるコーシーの積分定理については後述する。
【００４８】
そして、ステップＳ１０９にて判別点Ｐ[i]の配列子をインクリメント（＋１）し、ステップＳ１１０にて全て（ｍ）の判別点Ｐの判別を終了したか否か判別し、判別が終了していないためステップＳ１１０がＮｏであればステップＳ１０５に戻り、ステップＳ１１０がＹｅｓになるまでステップＳ１０５〜Ｓ１１０を繰り返し、ステップＳ１１０がＹｅｓになれば終了する。
【００４９】
次に、上述した臨界値Ａを求める手順を図２のフローチャートを参照して説明する。
【００５０】
図２において、ステップＳ２０１にて図形の頂点Ｚ[k:0、1、・・・n-1]の配列子[k]の初期値を「０」にセットし、ステップＳ２０２にてＺ[k]−Ｚ[k+1]間の辺と三角形を形成する図形の頂点Ｚ[j]との初期値をセットするとともに、次が初回のループ処理であることを示すフラグをセット（ＯＮ）する。
【００５１】
続くステップＳ２０３では三角形の頂点Ｚ[j]とＺ[k]-Ｚ[k+1]間の辺とが重複するか否か判別し、重複するときは三角形が形成されないので処理を除外するため、ステップＳ２０３がＹｅｓとなってステップＳ２１２に移る。
【００５２】
重複せずにステップＳ２０３がＮｏのときには、ステップＳ２０４にて上述した三角形が鋭角三角形又は直角三角形か否か判別され、三角形が鋭角三角形又は直角三角形であってステップＳ２０４がＹｅｓであれば（図１１Ａ、Ｂ、Ｃ）、ステップＳ２０７に移る。
【００５３】
三角形が鋭角三角形又は直角三角形ではなくてステップＳ２０４がＮｏであればステップＳ２０５に移り、三角形の鈍角が頂点Ｚ[j]であるか否か判別され、三角形の鈍角が頂点Ｚ[j]であれば（図１１Ｄ）、ステップＳ２０５がＹｅｓとなってステップＳ２０７に移る。
【００５４】
三角形の鈍角が頂点Ｚ[j]ではなくて（図１１Ｅ）、ステップＳ２０５がＮｏであればステップＳ２０６に移り、ステップＳ２０６では、鈍角頂点とＺ[j]を結ぶ辺の長さをＲとしてステップＳ２０８に移る。
【００５５】
すなわち、判別点Ｐと最短距離にある図形の頂点を結んだ直線が、その図形の頂点を端点としない辺と交差しなければ、本願のベクトル外積法を適用できるから、図１１Ｅに示すように、図形の頂点から対辺に対して垂線を引けない条件では、図形の頂点と対辺の近い方の端点との距離を臨界値候補Ｒとした。
【００５６】
このような条件のとき、頂点と対辺で形成する三角形の頂点と近い方の辺の端点が形成する内角が鈍角となるので、上記の条件のとき、図形の頂点と鈍角頂点を結ぶ辺の長さを臨界点候補Ｒとした。
【００５７】
ステップＳ２０７では、Ｚ[k]とＺ[k+1]を底辺とする三角形の高さＲとする処理を実行してステップＳ２０８に移る。
【００５８】
ステップＳ２０８では上述した処理が初回か否か判別され、初回であってステップＳ２０８がＹｅｓあればステップＳ２０９にて初回フラグをｏｆｆとし、続くステップＳ２１１で臨界値ＡにＲをセットする。
【００５９】
初回ではなくてステップＳ２０８がＮｏであればステップＳ２１０にて臨界値Ａと高さＲを比較して大小が判別され、Ｒの方が小さくてステップＳ２１０がＹｅｓであれば、ステップＳ２１１でＲを臨界値ＡとしてセットしてステップＳ２１２に移る。これにより高さＲの最小値が臨界値Ａとして求められる。
【００６０】
高さＲの方が大きくてステップＳ２１０がＮｏであれば、ステップＳ２１２にて符号（ｊ）をインクリメント（＋１）して三角形の頂点Ｚ[j]位置を移動し、ステップＳ２１３に移って辺Ｚ[k]、Ｚ[k+1]で形成する全ての三角形の処理が終了している否か（ｎ-１がｊを超えたか）判別する。
【００６１】
符号（ｊ）がｎ-１を超えておらず（終了していない。）、ステップＳ２１３がＮｏであればステップＳ２０３に戻り、以降、ステップＳ２１３がＹｅｓになるまでステップＳ２０３〜Ｓ２１３を繰り返す。
【００６２】
ステップＳ２１３がＹｅｓになければ、ステップＳ２１４に移って符号（ｋ）をインクリメント（＋１）して辺Ｚ[k]-Ｚ[k+1]の位置を移動し、続くステップＳ２１５にて全ての図形の辺に対して処理を終了しているか否か判別される。
【００６３】
符号（ｋ）がｎ−１を超えておらず（終了していない。）、ステップＳ２１５がＮｏであればステップＳ２０２に戻り、以降、ステップＳ２１５がＹｅｓになるまでステップＳ２０２〜Ｓ２１５を繰り返し、ステップＳ２１５がＹｅｓになればループ処理を終了する。
【００６４】
この臨界を求めることにより、図９Ａに示すような条件では、後述する本願のベクトル外積法を適用しないようにして、判別処理の誤り（判定エラー）を回避するようにしている。
【００６５】
上述した方法では三角形の高さを臨界値の候補としたが、臨界値はこの高さ以下の値であれば誤判別は発生しない。従って、計算処理の負荷や容易さを考慮して、図１１Ａ、Ｂ、Ｃ、Ｄのような条件では、形成された三角形の内接円の直径を臨界値の候補とするなど別な方法をとっても良い。
【００６６】
次に、上述したベクトル外積法を用いて判別点Ｐ[i]が図形の内部にあるか否かを判別する処理を、図３を参照して説明する。
【００６７】
ステップＳ３０１にて判別点Ｐ[i]とその最短距離にある図形の頂点Ｚ[k]とその前後の図形の頂点Ｚ[k-1]、Ｚ[k+1]からＺ[k-1]とＺ[k]の作るベクトルを Ｖk-1、Ｚ[k]とＺ[k+1]の作るベクトルをＶk 、Ｐ[i]とＺ[k-1]の作るベクトルを ＶＰk-1、Ｐ[i]とＺ[k]の作るベクトルをＶＰkとする。
【００６８】
ステップ３０２にてＶk-1とＶkが「０」であるか否かを判別し、ステップ３０２がＹｅｓであれば頂点Ｚ[k-1]、Ｚ[k]、Ｚ[k+1]は直線状に並んでいることになり、ステップＳ３０４に移る。
【００６９】
ステップ３０２がＮｏであれば、ステップＳ３０３にてＶk-1とＶk-1の外積が「０」より大きいか否かを判別し、Ｓ３０３がＹｅｓであれば頂点Ｚ[k-1]、Ｚ[k]、Ｚ[k+1]は左回りに三角形を形成していることになり、ステップＳ３０５に移る。ステップＳ３０３がＮｏであれば頂点Ｚ[k-1]、Ｚ[k]、Ｚ[k+1]は右回りに三角形を形成していることになり、ステップＳ３０７に移る。
【００７０】
ステップＳ３０４にてＶＰkとＶk-1の外積が「０」以上か否か判別し、ステップＳ３０４がＹｅｓであればステップＳ３０９に移り、ステップＳ３０４がＮｏであればステップＳ３１０に移る。
【００７１】
ステップＳ３０５では、ＶＰk-1とＶk-1の外積が「０」以上か否か判別し、ステップＳ３０５がＮｏであればステップＳ３１０に移り、ステップＳ３０５がＹｅｓであればステップＳ３０６にてＶＰkとＶkの外積が「０」以上か否か判別される。
【００７２】
ステップＳ３０６がＮｏであればステップＳ３１０に移り、ステップＳ３０６がＹｅｓであればステップＳ３０９に移る。
【００７３】
ステップＳ３０７では、ＶＰk-1とＶk-1の外積が「０」未満か否か判別し、ステップＳ３０７がＮｏであればステップＳ３０９に移り、ステップＳ３０７がＹｅｓであればステップＳ３０８にてＶＰkとＶkの外積が「０」未満か否か判別され、ステップＳ３０８がＮｏであればステップＳ３０９に移り、ステップＳ３０８がＹｅｓであればステップＳ３１０に移る。
【００７４】
ステップＳ３０９では判別点Ｐ「i」が図形の内側にあると判別して終了し、ステップＳ３１０では判別点Ｐ「i」が図形の外側であると判別処理して終了する。
【００７５】
さらに続いて、本発明におけるコーシーの積分定理を図４を参照して簡単に説明する。
【００７６】
ステップＳ４０１にてコーシーの積分定理を用いて判別点Ｐ[i]と図形の全頂点Ｚ[K:0、1、・・・n-1]について後述する「数１」による計算を行い、ステップＳ４０２にて計算結果が「０」か否か判別する。
【００７７】
計算結果が「０」でなくてステップＳ４０２がＮｏであれば、ステップＳ４０３にて判別点Ｐ[i]は図形の内点であると判別処理し、計算結果が「０」であってステップＳ４０２がＹｅｓであれば、ステップＳ４０４にて点Ｐ[i]は図形の外点であると判別処理し、終了する。
【００７８】
ここで、コーシーの積分定理を用いた計算とは、複素関数平面に、図形（閉曲線C）を描き、判別点Ｐを与えると、
【００７９】
【数１】
2008287337.tif 000003
の計算結果が「０」のとき判別点Ｐは図形の外部にあり、計算結果が２πiのとき判別点Ｐが図形の内部にあると判別できる。
【００８０】
このように本発明の内点判別方法は、複数の頂点を結んで閉じるように形成された図形に対し、判別点Ｐから最短距離にある図形の頂点間の距離を求め、それら判別点Ｐと当該頂点との距離が本願のベクトル外積法を適用しても誤判別（判別エラー）が発生しない臨界値以内においてはベクトル外積法を用い、判別点Ｐが図形の内側に位置するか外側に位置するか判別し、その臨界値外においてはコーシーの積分定理を用い、判別点Ｐが図形の内側に位置するか外側に位置するか判別する。
【００８１】
特に、その臨界値として、ある辺とその辺の端点を除く全ての図形の頂点との距離を求める計算を全ての辺について行い、これらの求めた辺と頂点との距離の最小値以下とする構成した。
【００８２】
そのため、全ての判別点をベクトル外積法で判別するのではなく、判別点Ｐと当該頂点との距離が本願のベクトル外積法を適用しても誤判別が発生しない範囲以内においてベクトル外積法を用い、それ以外ではコーシーの積分定理を用いるから、任意の判別点Ｐが任意の図形の内側にあるか外側にあるか正確かつ容易に判別可能となる。
【００８３】
しかも、判別点Ｐと図形を形成する頂点とがある程度離れているときには、コーシーの定理を用いるから、演算結果にいわゆる零割が発生し難く、コンピュータの処理能力に依存せずに精度を高く維持可能である。
【００８４】
さらに、本発明では、凹部があるといった複雑な多角形（非凸多角形）においても、軽い処理負荷によって判別点Ｐの判別演算が可能である。
【図面の簡単な説明】
【００８５】
【図１】本発明の内点判別方法の実施の形態を説明するフローチャートである。
【図２】本発明の内点判別方法における臨界値を求める手順を説明するフローチャートである。
【図３】本発明の内点判別方法におけるベクトル外積法を説明するフローチャートである。
【図４】本発明の内点判別方法におけるコーシー積分定理を説明するフローチャートである。
【図５】従来のベクトル外積法による内点判別方法の動作を説明する図である。
【図６】従来のベクトル外積法による内点判別方法の動作を説明する図である。
【図７】本発明の内点判別方法の動作を説明する図である。
【図８】本発明の内点判別方法の動作を説明する図である。
【図９】本発明の内点判別方法の動作を説明する図である。
【図１０】本発明の内点判別方法の動作を説明する図である。
【図１１】本発明の内点判別方法の動作を説明する図である。
【図１２】従来の内点判別方法を説明するフローチャートである。
【符号の説明】
【００８６】
Ｐ[i]、Ｐ[0]〜Ｐ[n-1]）  判別点
Ｚ[0]〜Ｚ[n-1]  図形の頂点
【図１】
2008287337.tif 000004
【図２】
2008287337.tif 000005
【図３】
2008287337.tif 000006
【図４】
2008287337.tif 000007
【図５】
2008287337.tif 000008
【図６】
2008287337.tif 000009
【図７】
2008287337.tif 000010
【図８】
2008287337.tif 000011
【図９】
2008287337.tif 000012
【図１０】
2008287337.tif 000013
【図１１】
2008287337.tif 000014
【図１２】
2008287337.tif 000015