(57)【特許請求の範囲】
【請求項１】
ＣＰＵとメモリとを有するコンピュータを使用して、ある点Ｐが凸形の多角形の内部にあるか否かを判定する領域の内外点判定方法であって、
前記多角形の各頂点の座標と、前記点Ｐの座標と、前記多角形内にある内点例の座標とを前記メモリにより記憶する記憶ステップと、
前記頂点の座標から前記多角形のすべての辺を、前記ＣＰＵによりＸ−Ｙ座標系の一次式で表わす一次式生成ステップと、
前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記一次式に前記内点例のＸ座標Ｘｉを代入して得られるそれぞれのＹ座標Ｙｉｉｊに対する、前記内点例のＹ座標値Ｙｉの大小関係とすべて一致する場合に、前記点Ｐが前記多角形の内点であると前記ＣＰＵにより判定し、すべては一致しない場合に、前記点Ｐが前記多角形の外点であると前記ＣＰＵにより判定する判定ステップを用いて内外点を判定することを特徴とする領域の内外点判定方法。
【請求項２】
ＣＰＵとメモリとを有するコンピュータを使用して、ある点Ｐが１８０°よりも大きい内角の凹部頂点を有する多角形の内部にあるか否かを判定する領域の内外点判定方法であって、
前記多角形の各頂点の座標と、前記点Ｐの座標とを前記メモリにより記憶する記憶ステップと、
前記凹部頂点を形成する辺を延長して前記多角形の他の辺との交点、または延長した線どうしの交点を、前記ＣＰＵにより求めて前記多角形を複数の凸多角形に分割する多角形分割ステップと、
前記分割した各凸形多角形内にある内点例の座標をそれぞれ前記メモリにより記憶する記憶ステップと、
前記多角形の頂点および前記交点の座標から、前記各凸多角形のすべての辺を、前記ＣＰＵによりＸ−Ｙ座標系における一次式で表す一次式生成ステップと、
前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記各凸多角形において、前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記一次式に前記内点例のＸ座標Ｘｉを代入して得られるそれぞれのＹ座標Ｙｉｉｊに対する、前記内点例のＹ座標値Ｙｉの大小関係とすべて一致する場合に、前記点Ｐが前記多角形の内点であると前記ＣＰＵにより判定し、すべては一致しない場合に外点であると前記ＣＰＵにより判定する判定ステップを用いて内外点を判定することを特徴とする領域の内外点判定方法。
【請求項３】
前記判定ステップが、前記点Ｐの座標が前記多角形の各頂点の座標のいずれかと一致したとき、または、前記点ＰのＹ座標値Ｙ０が、そのＸ座標値Ｘ０に対応する、前記多角形の延長部を含む各辺上のＹ座標値Ｙ０ｉｊのいずれかに一致し、この一致したＹ座標値以外のＹ座標値Ｙ０ｉｊに対する前記点ＰのＹ座標値Ｙ０の大小関係が、前記内点例のＹ座標値Ｙｊの前記Ｙ座標値Ｙｉｉｊに対する大小関係とすべて一致するときに、前記点Ｐは前記凸多角形の辺上にあると前記ＣＰＵにより判定する機能を有することを特徴とする請求項１に記載の領域の内外点判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、図形を利用した計算機数値シミュレーション等の様々な分野に応用される、領域の内外点を高速に判定するための内外点判定アルゴリズムを用いた領域の内外点判定方法に関する。
【背景技術】
【０００２】
例えば、浚渫域に埋没した危険物などの対象物を船舶に搭載したセンサーで検知する場合、検知した対象物、即ち検知点が浚渫域の内部にあるかどうかを迅速に判定するためには、多数の検知点と浚渫域の海図とを計算機処理をすることが必要である。この検知点が浚渫域などの領域の内部にあるかどうかを判定する領域内外判定方法としては、例えば、内外を判定すべき点からある方向に試行錯誤的に半直線を引き、領域を形成する多角形の各辺との交差の有無を交差の方向を含めて確認し、この確認結果に基づいて前記点が領域の内部にあるかどうかを判定する内外点判定アルゴリズムが開示されている（特許文献１参照）。また、凹所を含む領域から、まず、この領域からなる多角形の隣り合う辺ベクトルの外積を求めて、前記領域を内包する、その頂点からなる凸多角形を形成し、この凸多角形中に含まれる凹所を、凹多角形がなくなるまで順次凸多角形に分割していき、検知点などの点が各凸多角形の内部にあるか外部にあるかの判定結果に基づいて、前記点が領域の内部にあるかどうかを判定する内外点判定アルゴリズムも開示されている（特許文献２参照）。
【０００３】
【特許文献１】特開２００３−８５５６９号公報（［００１７］〜［００２５］）
【特許文献２】特開２００３−８５５７７号公報（［００１４］〜［００２４］）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載された内外点判定アルゴリズムについては、各点毎に領域を形成するすべての辺との交差の有無および交差の方向を確認する必要があるため、判定アルゴリズムが複雑となり、多くの繰り返し計算を要し、判定漏れのおそれもある。また、特許文献２に記載された内外点判定アルゴリズムでは、多角形が凹部頂点を含む場合に、凸多角形に分割する計算を各頂点について繰り返して内外点を判定する必要があるため、やはり判定アルゴリズムが複雑となり、多くの繰り返し計算を要する。
【０００５】
そこで、この発明の課題は、前述の検知点などの多数の点が領域を形成する多角形の内部にあるか外部にあるかを、容易かつ高速に、漏れなく判定できる内外点判定アルゴリズムを提供することである。
【課題を解決するための手段】
【０００６】
前記の課題を解決するために、この発明では以下の構成を採用したのである。
【０００７】
即ち、請求項１に係る領域の内外判定方法は、ＣＰＵとメモリとを有するコンピュータを使用して、ある点Ｐが凸形の多角形の内部にあるか否かを判定する領域の内外点判定方法であって、前記多角形の各頂点の座標と、前記点Ｐの座標と、前記多角形内にある内点例の座標とを前記メモリにより記憶する記憶ステップと、前記頂点の座標から前記多角形のすべての辺を、前記ＣＰＵによりＸ−Ｙ座標系の一次式で表わす一次式生成ステップと、前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記一次式に前記内点例のＸ座標Ｘｉを代入して得られるそれぞれのＹ座標Ｙｉｉｊに対する、前記内点例のＹ座標値Ｙｉの大小関係とすべて一致する場合に、前記点Ｐが前記多角形の内点であると前記ＣＰＵにより判定し、すべては一致しない場合に、前記点Ｐが前記多角形の外点であると前記ＣＰＵにより判定する判定ステップを用いて内外点を判定することを特徴とする。ここで、凸多角形とは、すべての内角が１８０°よりも小さい多角形を意味する。
【０００８】
このようにすれば、予め与える内点例の数は１個で済み、一次式で表せる多角形の辺の数だけの一次計算を内点例の数（１個）と上記点Ｐについて行なえばよいため、一次計算を２回行うだけで内外点判定ができ、従来の判定アルゴリズムに比べて非常に少ない計算で済み、点Ｐが多数存在しても、判定漏れのない高速判定が可能となる。
【００１１】
請求項２に係る領域の内外判定方法は、ＣＰＵとメモリとを有するコンピュータを使用して、ある点Ｐが１８０°よりも大きい内角の凹部頂点を有する多角形の内部にあるか否かを判定する領域の内外点判定方法であって、前記多角形の各頂点の座標と、前記点Ｐの座標とを前記メモリにより記憶する記憶ステップと、前記凹部頂点を形成する辺を延長して前記多角形の他の辺との交点、または延長した線どうしの交点を、前記ＣＰＵにより求めて前記多角形を複数の凸多角形に分割する多角形分割ステップと、前記分割した各凸形多角形内にある内点例の座標をそれぞれ前記メモリにより記憶する記憶ステップと、前記多角形の頂点および前記交点の座標から、前記各凸多角形のすべての辺を、前記ＣＰＵによりＸ−Ｙ座標系における一次式で表す一次式生成ステップと、前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記各凸多角形において、前記一次式に前記点ＰのＸ座標Ｘ０を代入して得られるそれぞれのＹ座標Ｙ０ｉｊに対する、前記点ＰのＹ座標Ｙ０の大小関係が、前記一次式に前記内点例のＸ座標Ｘｉを代入して得られるそれぞれのＹ座標Ｙｉｉｊに対する、前記内点例のＹ座標値Ｙｉの大小関係とすべて一致する場合に、前記点Ｐが前記多角形の内点であると前記ＣＰＵにより判定し、すべては一致しない場合に外点であると前記ＣＰＵにより判定する判定ステップを用いて内外点を判定することを特徴とする。
【００１２】
このように、前記多角形が上記凹部頂点を有する多角形であっても、凸多角形に分割して複数の内点例を与えることにより、この凸多角形の辺の数だけの一次計算を前述の所要回数行うだけで、前記点Ｐが多数存在しても、判定漏れなく、内外点判定ができる。
【００１５】
請求項３に係る領域の内外判定方法は、請求項１に記載した判定ステップが、前記点Ｐの座標が前記多角形の各頂点の座標のいずれかと一致したとき、または、前記点ＰのＹ座標値Ｙ０が、そのＸ座標値Ｘ０に対応する、前記多角形の延長部を含む各辺上のＹ座標値Ｙ０ｉｊのいずれかに一致し、この一致したＹ座標値以外のＹ座標値Ｙ０ｉｊに対する前記点ＰのＹ座標値Ｙ０の大小関係が、前記内点例のＹ座標値Ｙｊの前記Ｙ座標値Ｙｉｉｊに対する大小関係とすべて一致するときに、前記点Ｐは前記凸多角形の辺上にあると判定する機能を有することを特徴とする。
【００１６】
このようにすれば、多角形の辺上、即ち領域の境界にある点Ｐを判別することができ、この境界上にある点以外の点Ｐについて内外点判定を行えばよく、計算が簡素化され、判定漏れのない高速判定に寄与する。
【発明の効果】
【００１７】
この発明では、ある点Ｐが多角形、即ち領域の内部にあるか否かを、この多角形内にある内点例の座標を予め与え、前記多角形のすべての辺に対して、前記点Ｐが前記内点例と同じ側にあるときに、点Ｐを内点であると判定することができるため、一次式で表せる多角形の辺の数だけの一次計算を内点例と点Ｐについて行なえばよく、従来の判定アルゴリズムに比べて非常に少ない計算で済み、点Ｐが多数存在しても判定漏れのない内外点判定を高速に行うことが可能である。
【発明を実施するための最良の形態】
【００１８】
以下に、この発明の実施形態を添付の図１から図７に基づいて説明する。この発明は、［技術分野］（段落番号［０００１］）に記載したように、図形を利用した計算機数値シミュレーション等の様々な分野に応用される、領域の内外点を高速に判定するための内外点判定アルゴリズムを用いた内外点判定方法に関するものである。前記計算機数値シミュレーションには、入力手段、ＣＰＵ等の演算手段および制御手段、メインメモリやハードディスク等のメモリ(主および補助記憶手段)など備えたコンピュータ（パソコンを含む）が一般に使用されている。したがって、本願発明による領域の内外点判定方法も、このような通常のコンピュータのハードウェア資源を通常の方法で使用することにより、すなわち、前記記憶ステップは前記メモリにより、前記一次式生成ステップ、多角形分割ステップおよび判定ステップは、前記ＣＰＵにより実現することができる。
【００１９】
図１は、領域、即ち多角形が凸多角形１の場合に、この凸多角形１がＸ−Ｙ座標系にあるとして（以下の各多角形についても同様）、内点例Ｐi（Ｘi，Ｙi）を与える内外点判定方法について示したものである。まず、凸多角形１の頂点Ａ１〜Ａ５の座標、Ａ１（Ｘ１，Ｙ１）、Ａ２（Ｘ２，Ｙ２）、Ａ３（Ｘ３，Ｙ３）を入力データとして与える。座標系はＸ−Ｙ座標系を用いることができる。次に、凸多角形１の内部に内点例Ｐi（Ｘi，Ｙi）を与える。そして、各辺Ａ１―Ａ２、Ａ２―Ａ３、Ａ３―Ａ４、Ａ４―Ａ５、Ａ５―Ａ１を一次式で表す。一例として、辺Ａ１―Ａ２（延長部を含む）について、この直線を一次式で示せば、次のようになる。
【数１】
0004000117.tif 000002
いま、内外を判定すべき点Ｐを、判定点Ｐ0（Ｘ0，Ｙ0）（判定点１）、判定点Ｐ0（Ｘ0，Ｙ0）（判定点２）とすると、点Ｐ0のＸ座標Ｘ0を式（１）に代入して得られる辺Ａ１―Ａ２（延長部を含む）上のＹ座標値Ｙ12はつぎのようになる。
【数２】
0004000117.tif 000003
また、内点例をＰi（Ｘi，Ｙi）とすると、内点例Ｐi（Ｘi，Ｙi）のＸ座標Ｘiを式（１）に代入して得られる辺Ａ１―Ａ２（延長部を含む）上のＹ座標値Ｙi12は次のようになる。
【数３】
0004000117.tif 000004
【数４】
0004000117.tif 000005
【数５】
0004000117.tif 000006
【数６】
0004000117.tif 000007
【数７】
0004000117.tif 000008
【００２０】
前記判定点Ｐ0（Ｘ0，Ｙ0）のＹ座標値Ｙ0の、Ｘ座標値Ｘ0に対応する前記各辺上（延長部を含む）のＹ座標値、Ｙ12、Ｙ23、Ｙ34、Ｙ45、Ｙ51に対する大小関係が、内点例Ｐi（Ｘi，Ｙi）のＹ座標値Ｙiの、Ｘ座標値Ｘiに対応する前記各辺上（延長部を含む）のＹ座標値、Ｙi12、Ｙi23、Ｙi34、Ｙi45、Ｙi51に対する大小関係とすべて一致する場合に、判定点Ｐ0は凸多角形１の内点、即ちこの凸多角形１からなる領域の内点と判定される。図１に示した場合では、判定点Ｐ0（Ｘ0，Ｙ0）（判定点１）は内点と判定され、判定点Ｐ0（Ｘ0，Ｙ0）（判定点２）は、前記大小関係が内点例Ｐi（Ｘi，Ｙi）とすべて一致しないため、外点と判定される。
【００２１】
なお、前記判定点Ｐ0（Ｘ0，Ｙ0）のＹ座標値Ｙ0が、Ｘ座標値Ｘ0に対応する前記各辺上（延長部を含む）のＹ座標値、Ｙ12、Ｙ23、Ｙ34、Ｙ45、Ｙ51のいずれかに一致し、この一致したＹ座標値（Ｙ12、Ｙ23、Ｙ34、Ｙ45、Ｙ51のいずれか一つ）以外のＹ座標値に対する判定点Ｐ0（Ｘ0，Ｙ0）のＹ座標値Ｙ0の大小関係が、内点例Ｐi（Ｘi，Ｙi）についての場合の前記大小関係とすべて一致するとき、判定点Ｐ0（Ｘ0，Ｙ0）は、凸多角形１の辺上にあると判定される。また、判定点Ｐ0が凸多角形の頂点Ａの座標に一致するときは、判定点Ｐ0が即座に辺上にあると予め定めておくことができる。判定点Ｐ0が辺上にあるとき、内点と判定するか外点と判定するかは、予め規約で定めておくことができる。判定点Ｐ0（Ｘ0，Ｙ0）のＹ座標Ｙ0が、前記辺上のＹ座標、または頂点のＹ座標と一致するとみなす誤差範囲、即ち、判定点Ｐ0のＹ座標値Ｙ0と辺上または頂点のＹ座標との差についても、予め定めておくことができる。
【００２２】
さらに、前記凸多角形１の辺Ａ１―Ａ２、Ａ２―Ａ３、Ａ３―Ａ４、Ａ４―Ａ５、Ａ５―Ａ１のいずれかの辺が、Ｙ軸に平行な場合には、このＹ軸に平行な辺に対して、判定点Ｐ0（Ｘ0，Ｙ0）と内点例Ｐi（Ｘi，Ｙi）とが同じ側にあり、即ち平行な辺のＸ座標に対する、判定点Ｐ0のＸ座標Ｘ0と内点例ＰiのＸ座標Ｘiの大小関係が同じであり、かつこの平行な辺以外の各辺上の、判定点Ｐ0（Ｘ0，Ｙ0）のＸ座標Ｘ0に対応する前記各辺上のＹ座標値に対するＹ座標値Ｙ0の大小関係が、内点例Ｐi（Ｘi，Ｙi）のＸ座標Ｘiに対応する各Ｙ座標値に対するＹ座標値Ｙｉの大小関係とすべて一致するとき、判定点Ｐ0（Ｘ0，Ｙ0）（判定点１）は、凸多角形１の内点と判定される。そして、判定点Ｐ0（Ｘ0，Ｙ0）（判定点２）は、凸多角形１の内点と判定されず、従って外点と判定される。
【００２３】
同様にして、前記凸多角形１の辺Ａ１―Ａ２、Ａ２―Ａ３、Ａ３―Ａ４、Ａ４―Ａ５、Ａ５―Ａ１のいずれかの辺が、Ｘ軸に平行な場合には、このＸ軸に平行な辺に対して、判定点Ｐ0（Ｘ0，Ｙ0）と内点例Ｐi（Ｘi，Ｙi）とが同じ側にあり、即ち平行な辺のＹ座標に対する、判定点Ｐ0のＹ座標Ｙ0と内点例ＰiのＹ座標Ｙiの大小関係が同じであり、かつこの平行な辺以外の各辺上の、判定点Ｐ0（Ｘ0，Ｙ0）のＸ座標Ｘ0に対応する前記各辺上のＹ座標値に対するＹ座標値Ｙ0の大小関係が、内点例Ｐi（Ｘi，Ｙi）のＸ座標Ｘiに対応する各Ｙ座標値に対するＹ座標値Ｙｉの大小関係とすべて一致するとき、判定点Ｐ0（Ｘ0，Ｙ0）は、凸多角形１の内点と判定される。
【００２４】
図２は、領域、即ち多角形が凹部頂点Ａ１を有する凹多角形２の場合に、内点例Ｐｉ（Ｘｉ，Ｙｉ）を与える内外点判定方法について示したものである。まず、前記凸多角形１の場合と同様に、頂点Ａ１〜Ａ７の座標、Ａ１（Ｘ１，Ｙ１）、Ａ２（Ｘ２，Ｙ２）、Ａ３（Ｘ３，Ｙ３）、Ａ４（Ｘ４，Ｙ４）、Ａ５（Ｘ５，Ｙ５）、Ａ６（Ｘ６，Ｙ６）、Ａ６（Ｘ７，Ｙ７）をインプットデータとして与える。多角形２は凹多角形であるため、凹部頂点Ａ１を形成する辺Ａ１―Ａ２、Ａ１―Ａ７をそれぞれ延長して辺Ａ４−Ａ５およびＡ３―Ａ４との交点Ａ８（Ｘ８，Ｙ８）およびＡ９（Ｘ９，Ｙ９）を求める。このようにして、凹多角形２を、頂点Ａ１、Ａ２、Ａ３、Ａ９を有する凸多角形３、頂点Ａ１、Ａ９、Ａ４、Ａ８を有する凸多角形４および頂点Ａ１、Ａ８、Ａ５、Ａ６、Ａ７を有する凸多角形５の３つの凸多角形３、４、５に分割し、それぞれの凸多角形に内点例を１個ずつ、即ち凸多角形３に内点例Ｐ3ｉ（Ｘ3ｉ，Ｙ3ｉ）を、凸多角形４に内点例Ｐ4ｉ（Ｘ4ｉ，Ｙ4ｉ）を、凸多角形５に内点例Ｐ5ｉ（Ｘ5ｉ，Ｙ5ｉ）をそれぞれ与える。
【００２５】
いま、内外を判定すべき点Ｐを、判定点Ｐ0（Ｘ0，Ｙ0）とすると、図１について示した手順で、凸多角形３について内外点判定を行う。前述のように、判定点Ｐ0（Ｘ0，Ｙ0）が、そのＸ座標Ｘ0に対する凸多角形３の各辺上の各Ｙ座標値に対して、内点例Ｐ3ｉ（Ｘ3ｉ，Ｙ3ｉ）についての場合と、大小関係がすべて一致せず、内点でなく外点と判定されると、次に、同様にして凸多角形４について内外点判定を行う。判定点Ｐ0（Ｘ0，Ｙ0）についての前記大小関係が、内点例Ｐ4ｉ（Ｘ4ｉ，Ｙ4ｉ）について前記大小関係とすべて一致せず、判定点Ｐ0（Ｘ0，Ｙ0）が、内点でなく外点判定されると、さらに、同様にして凸多角形５について、内点例Ｐ5ｉ（Ｘ5ｉ，Ｙ5ｉ）を用いて内外点判定を行う。図２の例では、判定点Ｐ0（Ｘ0，Ｙ0）が、そのＸ座標Ｘ0に対する凸多角形５の各辺上の各Ｙ座標値に対して、内点例Ｐ5ｉ（Ｘ3ｉ，Ｙ3ｉ）についての場合と、大小関係がすべて一致し、判定点Ｐ0（Ｘ0，Ｙ0）は凸多角形５の内点であると判定される。判定点Ｐ0（Ｘ0，Ｙ0）が、例えば、凸多角形４で内点であると判定されると、その時点で判定点Ｐ0（Ｘ0，Ｙ0）についての内外点判定は終了し、凸多角形５についての内外点判定計算は行わない。
【００２６】
このように、領域が凹部頂点を含む凹多角形であっても、凹部頂点Ａ１を形成する辺を、他の辺と交差するまで延長して、複数の凸多角形に分割し、それぞれの凸多角形に内点例を１個ずつ与えることにより、図１に示した場合と同様にして、各凸多角形において、判定点Ｐ0（Ｘ0，Ｙ0）についての内外点判定を行うことができる。
【００２７】
図３は、領域、即ち多角形が凹部頂点Ａ１およびＡ５のように、複数の凹部頂点を有する凹多角形６の場合に、内点例Ｐｉ（Ｘｉ，Ｙｉ）を与える内外点判定方法について示したものである。まず、前記凸多角形１の場合と同様に、既知の頂点Ａ１〜Ａ８の座標、Ａ１（Ｘ１，Ｙ１）、Ａ２（Ｘ２，Ｙ２）、Ａ３（Ｘ３，Ｙ３）、Ａ４（Ｘ４，Ｙ４）、Ａ５（Ｘ５，Ｙ５）、Ａ６（Ｘ６，Ｙ６）、Ａ７（Ｘ７，Ｙ７）、Ａ８（Ｘ８，Ｙ８）を入力データとして与える。前記凹多角形２の場合と同様に、凹部頂点Ａ１を形成する辺Ａ１―Ａ２、Ａ１―Ａ８を延長して辺Ａ５−Ａ４、Ａ３―Ａ４との交点Ａ１０（Ｘ１０，Ｙ１０）、Ａ９（Ｘ９，Ｙ９）を求め、同様に、凹部頂点Ａ５を形成する一方の辺Ａ５―Ａ４を延長して辺Ａ７―Ａ８との交点Ａ１１（Ｘ１１，Ｙ１１）を求める。このようにして、凹多角形６を、頂点Ａ１、Ａ２、Ａ３、Ａ９を有する凸多角形７、頂点Ａ１、Ａ９、Ａ４、Ａ１０を有する凸多角形８、頂点Ａ５、Ａ１１、Ａ８、Ａ１、Ａ１０を有する凸多角形９、および頂点Ａ５、Ａ６、Ａ７、Ａ１１を有する凸多角形１０の４つの凸多角形７、８、９、１０に分割し、それぞれの凸多角形に内点例を１個ずつ、即ち凸多角形７に内点例Ｐ７ｉ（Ｘ７ｉ，Ｙ７ｉ）を、凸多角形８に内点例Ｐ８ｉ（Ｘ８ｉ，Ｙ８ｉ）を、凸多角形９に内点例Ｐ９ｉ（Ｘ９ｉ，Ｙ９ｉ）、凸多角形１０に内点例Ｐ１０ｉ（Ｘ１０ｉ，Ｙ１０ｉ）および判定点Ｐ0（Ｘ0，Ｙ0）の座標をそれぞれインプットデータとして与える。なお、前記の凹部頂点を形成する辺を延長した直線と凹多角形６との交点Ａ９〜Ａ１１は自動計算される。
【００２８】
このように、領域が凹部頂点を複数含む凹多角形であっても、各凹部頂点を形成する辺を、他の辺と交差するまで延長して複数の凸多角形に分割し、それぞれの凸多角形に内点例を１個ずつ与えることにより、図１および図２に示した場合と同様にして、各凸多角形において、図示を省略した判定点Ｐ0（Ｘ0，Ｙ0）についての内外点判定を行うことができる。この場合も、図２に示した場合と同様に、例えば、まず凸多角形７から、判定点Ｐ0（Ｘ0，Ｙ0）が各凸多角形の各辺に対して内点例Ｐ７ｉとすべて同じ側にあるかどうかを数値計算により判断し、内点と判定されるまで、順次凸多角形８〜１０について、同様に内点例Ｐ８ｉ〜Ｐ１０ｉと同じ側にあるかどうかを判断していき、判定点Ｐ0（Ｘ0，Ｙ0）が内点と判定された時点で数値計算を終え、次の判定点について，同様の手法で内外点判定を行う。
【００２９】
前記凹部頂点を複数含む凹多角形の場合、判定点の分布状況に応じて、図４に示すように、凹部頂点を形成する辺の延長線どうしの交点を頂点に含む凸多角形、例えば、頂点Ａ１、Ａ２、Ａ３、Ａ１０、Ａ９を有する凸多角形１１、頂点Ａ１、Ａ９、Ａ１２を有する凸多角形１２、頂点Ａ１０、Ａ４、Ａ１１、Ａ１２を有する凸多角形１３、頂点Ａ１、Ａ１２、Ａ５、Ａ１３、Ａ８を有する凸多角形１４、頂点Ａ５、Ａ６、Ａ７、Ａ１３を有する凸多角形１５、頂点Ａ５、Ａ１２、Ａ１１を有する凸多角形１６に分割することもできる。従って、凹多角形の凸多角形への分割パターンは必ずしも一通りではないため、判定点の分散状況などに応じて、予め決めておくと便利である。
【００３０】
なお、多角形が凸多角形の場合、または凹部頂点を複数有する凹多角形の場合のいずれの場合も、とくに凹多角形の場合には、前述のように各凸多角形に分割した後、それぞれ外点例を与えて、判定点Ｐ0の内外点判定を行うこともできる。この場合は内点例を与える場合に比べて、より多くの外点例を必要とするため、内点でなければ外点と判定するようにして内外判定を行なうことが望ましい。しかし、例えば図５に示すように、判定点Ｐ0が凸多角形１の辺Ａ１−Ａ５の外側にあるかどうかのみを判定する場合には、外点例ＰEを与える方が判定を簡便に行なえる場合もある。このため、内点例を与えるか外点例を与えるかは、解決すべき問題において、どちらを与える方がより簡便に内外判定を行なえるかどうかによる。
【００３１】
図６、図７に、上述の、内点例を与える場合の内外点判定アルゴリズムと、このアルゴリズムを用いた領域内外点判定方法の計算の流れを示す。上述のように、実データ（判定点Ｐ0）の数と前記凸多角形１、凸多角形３〜５、または凸多角形７〜１０などの定義した領域の数だけ、上述の内外点判定アルゴリズムを繰り返すことにより、各実データについて、領域毎の内外判定の結果が得られる。
【産業上の利用可能性】
【００３２】
この発明は、海底に埋没した危険物等の除去対象物を検知し、この検知点が浚渫域内部にあるかどうかを迅速に判定し、事前に除去対象物がどの程度あるのかを容易に把握することなど、図形を利用した計算機数値シミュレーション等の様々な分野で、領域の内外点判定が必要な際に利用できる。
【図面の簡単な説明】
【００３３】
【図１】実施形態の、凹部頂点がない場合の多角形における内点判定の説明図である。
【図２】他の実施形態の、凹部頂点が１個の多角形における内点判定の説明図である。
【図３】他の実施形態の、凹部頂点が複数個の多角形における内点判定の説明図である。
【図４】図３に示した多角形で、凸多角形への分割パターンが異なる場合の内点判定の説明図である。
【図５】他の実施形態の、凹部頂点がない場合の多角形における外点判定の説明図である。
【図６】実施形態の内外点判定のアルゴリズムを示すフローチャートである。
【図７】図６のアルゴリズムを用いた内外点判定方法のフローチャートである。
【符号の説明】
【００３４】
１、３〜５、７〜１５：凸多角形        ２、６：凹多角形
Ａ１〜Ａ８：頂点      Ｐ、Ｐ0：判定点    Ｐｉ：内点例
ＰE：外点例
【図１】
0004000117.tif 000009
【図２】
0004000117.tif 000010
【図３】
0004000117.tif 000011
【図４】
0004000117.tif 000012
【図５】
0004000117.tif 000013
【図６】
0004000117.tif 000014
【図７】
0004000117.tif 000015