(57)【要約】【課題】複数の２次元（２Ｄ）現実世界形状の間で交差を決定するための方法およびシステム。【解決手段】形状は、データによって表されてよく、かついくつかの実施形態によって入力として提供されてよく、または生成されてよい。形状（および／またはデータ）は、始点頂点と終点頂点を有する２Ｄ現実世界形状のセグメントを含み得る。複数の基準線が定義される。各基準線は、所与の軸に沿った頂点のうちの少なくとも１つと交差する。基準線は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって並列に処理される。分類することに基づいて、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかが決定される。【選択図】図１
2018185812.tif 000002
【特許請求の範囲】
【請求項１】
複数の２次元（２Ｄ）現実世界形状の間の交差を決定する方法であって、
データは、始点頂点と終点頂点とを有する前記２次元（２Ｄ）現実世界形状のセグメントを含む形状を表し、前記方法は、
複数の基準線を定義するステップであって、各基準線は、所与の軸に沿って頂点のうちの少なくとも１つと交差する、ステップと、
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点を分類することによって前記基準線を並列に処理するステップと、
分類する前記ステップに基づいて、前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定するステップと
を備える方法。
【請求項２】
前記２次元（２Ｄ）現実世界形状は、現実世界多角形を含む請求項１に記載の方法。
【請求項３】
前記現実世界形状は、前記２次元（２Ｄ）現実世界形状の前記別のものの内部にある、または前記別のものに接触している請求項１に記載の方法。
【請求項４】
前記２次元（２Ｄ）現実世界形状は、プリント回路基板およびデジタルコンピュータ画像のうちの少なくとも１つの構成要素である請求項１に記載の方法。
【請求項５】
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点を分類することは、
所与の基準線に沿った各頂点に関して、前記基準線の位置と、前記セグメントの前記始点頂点および前記終点頂点とを比較することによって、前記頂点に関連付けられた前記セグメントが前記基準線を横断しているかどうか、前記基準線に接触しているかどうか、または前記基準線に合致しているかどうかを決定するステップを含む請求項１に記載の方法。
【請求項６】
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの前記別のものと交差する現実世界形状の前記一部であるかどうかを決定するステップは、
前記セグメントのうちの複数が重なり合うかどうかを決定するステップと、
前記２次元（２Ｄ）現実世界形状のうちの異なる形状の前記セグメントのうちの複数が重なり合うかどうかをさらに決定するステップと、
前記セグメントのうちの所与のセグメントの終端頂点が前記２次元（２Ｄ）現実世界形状のうちの前記別のものの内部にあるかどうかをさらに決定するステップと、
前記セグメントのうちの所与のセグメントの終端頂点が前記２次元（２Ｄ）現実世界形状のうちの前記別のものの上にあるかどうかをさらに決定するステップと
を含む請求項１に記載の方法。
【請求項７】
前記所与の軸は、水平軸または垂直軸である請求項１に記載の方法。
【請求項８】
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの前記別のものと交差する現実世界形状の一部であるかどうかを決定するステップは、前記基準線の各基準線に接続された前記セグメントの各セグメントが各基準線を横断しているかどうか、各基準線に接触しているかどうか、または各基準線に合致しているかどうかを決定するステップを含む請求項１に記載の方法。
【請求項９】
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの前記別のものと交差する現実世界形状の一部であるかどうかを決定するステップは、優先順序に基づき、前記合致していることは、前記横断していること、および前記接触していることと比べて、より高い優先度であると見なされる請求項８に記載の方法。
【請求項１０】
複数の２次元（２Ｄ）現実世界形状の間の交差を決定するためのコンピュータシステムであって、
複数のプロセッサと、
（ｉ）メモリの上に記憶されたコンピュータコード命令と、（ｉｉ）前記２次元（２Ｄ）現実世界形状を表すデータとを含む前記メモリであって、前記データは、前記２次元（２Ｄ）現実世界形状の部分を含むセグメントを含み、前記セグメントは、前記２次元（２Ｄ）現実世界形状の前記部分の始点頂点と終点頂点とを表し、前記メモリは、前記複数のプロセッサによって実行された場合、前記コンピュータコード命令がコンピュータシステムに、
前記複数の基準線を定義することであって、各基準線は、所与の軸に沿った頂点のうちの少なくとも１つと交差すること、
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点を分類することによって前記基準線を並列に処理すること、および
前記分類することに基づいて、前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状の別のものと交差する現実世界形状の一部であるかどうかを決定することを行うように構成されたコンピューティングモジュールを実装することをさせるように前記複数のプロセッサに動作可能に結合された前記メモリと
を備えるコンピュータシステム。
【請求項１１】
各プロセッサは、前記基準線のサブセットを処理し、かつ前記セグメントは、前記メモリに読取り専用として記憶される請求項１０に記載のシステム。
【請求項１２】
前記２次元（２Ｄ）現実世界形状は、現実世界多角形を含む請求項１０に記載のシステム。
【請求項１３】
前記現実世界形状は、前記２次元（２Ｄ）現実世界形状の前記別のものの内部にある、または前記別のものに接触している請求項１０に記載のシステム。
【請求項１４】
前記２次元（２Ｄ）現実世界形状は、プリント回路基板およびデジタルコンピュータ画像のうちの少なくとも１つの構成要素である請求項１０に記載のシステム。
【請求項１５】
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点を分類することは、
所与の基準線に沿った各頂点に関して、前記基準線の位置と、前記セグメントの前記始点頂点および前記終点頂点とを比較することによって、前記頂点に関連付けられた前記セグメントが前記基準線を横断しているかどうか、前記基準線に接触しているかどうか、または前記基準線に合致しているかどうかを決定することを含む請求項１０に記載のシステム。
【請求項１６】
前記コンピューティングモジュールは、
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの前記別のものと交差する現実世界形状の前記一部であるかどうかを決定することであって、
前記セグメントのうちの複数が重なり合うかどうかを決定すること、
前記２次元（２Ｄ）現実世界形状のうちの異なる形状の前記セグメントのうちの複数が重なり合うかどうかをさらに決定すること、
前記セグメントのうちの所与のセグメントの終端頂点が前記２次元（２Ｄ）現実世界形状のうちの前記別のものの内部にあるかどうかをさらに決定すること、および
前記セグメントのうちの所与のセグメントの終端頂点が前記２次元（２Ｄ）現実世界形状のうちの前記別のものの上にあるかどうかをさらに決定すること
を含む、決定することを行うようにさらに構成される請求項１０に記載のシステム。
【請求項１７】
前記所与の軸は、水平軸または垂直軸である請求項１０に記載のシステム。
【請求項１８】
前記コンピューティングモジュールは、
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界のうちの前記別のものと交差する現実世界形状の一部であるかどうかを決定することであって、前記基準線の各基準線に接続された前記セグメントの各セグメントが各基準線を横断しているかどうか、各基準線に接触しているかどうか、または各基準線に合致しているかどうかを決定することを含む、決定することを行うようにさらに構成される請求項１０に記載のシステム。
【請求項１９】
前記コンピューティングモジュールは、前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状のうちの前記別のものと交差する現実世界形状の一部であるかどうかを決定することであって、優先順序に基づき、前記合致していることは、前記横断していること、および前記接触していることと比べて、より高い優先度であると見なされる、決定することを行うようにさらに構成される請求項１８に記載のシステム。
【請求項２０】
装置に結合されたプロセッサによってロードされ、かつ実行された場合、前記装置に、
複数の基準線を定義することであって、各基準線は、２次元（２Ｄ）現実世界形状の部分を表すセグメントの始点頂点と終点頂点のうちの少なくとも１つと交差する、定義すること、
前記基準線に沿った前記２次元（２Ｄ）現実世界形状の頂点を分類することによって前記基準線を並列に処理すること、および
前記分類することに基づいて、前記基準線に沿った前記２次元（２Ｄ）現実世界形状の前記頂点のうちのいずれかが、前記２次元（２Ｄ）現実世界形状の別のものと交差する現実世界形状の一部であるかどうかを決定すること
を行わせる命令のシーケンスを記憶している非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
物理構造のシミュレーション、物理特性、ロボット工学、グラフィックス、および画像処理などの２（または３以上）次元モデリングを含む現実世界アプリケーションにおいて、２つ以上のオブジェクトが互いに交差する（例えば、衝突する）かどうかを決定することが、しばしば、望ましい。形状のクリッピング、衝突検出、および交差の検出として知られる、そのような交差を検出するための方法が存在する。しかし、２次元多角形に関する既存の方法は、並列化に適しておらず、中央処理装置（ＣＰＵ）コアまたはグラフィックスプロセシングユニット（ＧＰＵ）スレッドなどの最新のプロセシングユニット（ＰＵ）を活用しない。
【発明の概要】
【０００２】
形状の交差を検出することによって既存のシステムの制限を克服する効率的かつ信頼できる方法、システム、および装置が提示される。本明細書において説明されるとおり、交差検出は、形状が交差しているかどうかを見出すこととして定義される。交差は、形状の一部が別の形状の内部にある、または別の形状に接触する（例えば、別の形状と重なり合う）場合に生じ得る。
【０００３】
形状は、凸面多角形もしくは凹面多角形、および／または他の形状を含むが、以上には制限されない１次元（１Ｄ）の直線、２次元（２Ｄ）の多角形（本明細書において「多角形」もしくは「２Ｄ多角形」としても知られる）を含み得るが、これらには制限されない。いくつかの実施形態において、多角形は、３つ以上の実質的に直線を含んでよい。さらに、他の実施形態によれば、多角形は、単一の実質的に直線、２つの接続された実質的に直線、および／または３つ以上の接続された直線を含んでよい。
【０００４】
いくつかの実施形態において、検出は、並列処理を使用して実行され得る。非制限的な例として、いくつかの実施形態によれば、方法（もしくはシステムもしくは装置）は、一部および／または全体の演算を並列に、かつ他のプロセシングユニット（ＰＵ）上の同一の演算とは独立に走らせることを含むが、これには制限されない並列演算を実行してよい。
【０００５】
他の実施形態において、検出は、直列様態で実行され得る。検出方法（またはシステム）の一部として、いくつかの実施形態によれば、方法（もしくはシステムもしくは装置）は、共有されるグローバルデータセットにデータをロックするのではなく、並列タスクデータを含むローカルデータセット、および／または共有される読取り専用のデータコレクションを使用することによって並列処理を可能にしてよい。データセットは、形状の間の交差に関して検査するのに使用され得る形状のコレクションを含み得るが、これには制限されない。コレクションは、均質なデータを含む動的アレイ、および／または他の類似したデータ構造を含み得るが、これには制限されない。
【０００６】
いくつかの実施形態によれば、方法（もしくはシステムもしくは装置）は、長い解析および／またはモデリング演算を走らせる前に入力データの検証技法として動作し得る前処理ツールを含んでよい。いくつかの実施形態によれば、方法（もしくはシステムもしくは装置）は、形状の間の１つまたは複数の交差を識別するデータセットをもたらし（例えば、生成し）得る。
【０００７】
いくつかの実施形態は、２Ｄ形状関連データを入力すること、入力データに基づいて基準線（本明細書において「スキャン線」とも称される）を生成すること（または受信すること）、２つ以上の基準線を並列に処理すること、２Ｄ形状に関連付けられた１つまたは複数の横断点（ｃｒｏｓｓｐｏｉｎｔ）を登録すること、および／または対応する結果を収集することを含む方法（または対応するシステム）を含み得る。
【０００８】
いくつかの実施形態によれば、交差検出の方法（および対応するシステム）は、基準線、横断点、交差点、および／またはスキャナを含み得る。いくつかの実施形態において、基準線は、垂直線（または実質的に垂直の線）であってよい。基準線は、データセットにおける形状の少なくとも１つの頂点（本明細書において「点」とも称される）を通過してよい。いくつかの実施形態において、基準線は、垂直線の代わりに水平線（または実質的に水平の線）であってよく、その事例において、本明細書においてさらに例示されるｘ（例えば、水平）座標とｙ（例えば、垂直）座標は、機能、結果、またはパフォーマンスに影響を与えることなしに交換されてよい。横断点は、基準線上の頂点（本明細書において「点」もしくは「横断点」とも称される）を含むものと定義され、基準線は、セグメントを横断する。１つまたは複数の横断点が、いくつかの実施形態の方法（またはシステム）において中間データとして使用され得る。前述したとおり、交差は、形状の一部が別の形状の内部にある、または別の形状に接触する（例えば、別の形状と重なり合う）場合に生じ得る。このため、交差点は、形状の（別の形状との）交差の点を含むものと本明細書において定義され、その結果、別の形状の接触または包含を示す。
【０００９】
実施形態は、複数の２次元（２Ｄ）現実世界形状の間の交差を決定するための方法（コンピュータ実装方法を含むが、これには制限されない）およびシステム（コンピュータ実装システムを含むが、これには制限されない）を含む。形状は、いくつかの実施形態において入力として提供され得るデータによって表され得る。他の実施形態は、データを生成し得る。
【００１０】
形状（および／またはデータ）は、２Ｄ現実世界形状のセグメントを含み得る。セグメントは、形状の単一の辺（線）を含み得るが、そのようなものであることに制限されない。セグメントは、始点頂点および／または終点頂点を有し得る。いくつかの実施形態によれば、端点は、セグメントの始点または終点を指すものと本明細書において見なされてよい。いくつかの実施形態において、方法（または対応するシステム）は、複数の基準線を定義してよい。各基準線は、所与の軸に沿って頂点のうちの少なくとも１つと交差し得る。いくつかの実施形態において、方法（または対応するシステム）は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって基準線を並列に処理してよい。いくつかの実施形態において、分類することに基づいて、方法（および対応するシステム）は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定してよい。
【００１１】
方法（および対応するシステム）のいくつかの実施形態によれば、２次元（２Ｄ）現実世界形状は、現実世界多角形を含み得る。さらに、交差する現実世界形状は、２次元（２Ｄ）現実世界形状の別のものの内部にあってよく、またはそのような別のものに接触していてよい。いくつかの実施形態において、２次元（２Ｄ）現実世界形状は、プリント回路基板およびデジタルコンピュータ画像のうちの少なくとも１つの構成要素であり得る。非制限的な例に関して、いくつかの実施形態は、２Ｄモデリング、解析、ゲーム、プリント回路基板（ＰＣＢ）のための電子設計自動化（ＥＤＡ）アプリケーション、画像認識、コンピュータビジョン、および／または拡張現実に適用され得る。
【００１２】
いくつかの実施形態において、方法（または対応するシステム）は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類し得る。いくつかの実施形態において、方法（または対応するシステム）は、所与の基準線に沿った各頂点に関して、基準線の位置と、セグメントの始点頂点および終点頂点とを比較することによって、頂点に関連付けられたセグメントが基準線を横断しているかどうか、基準線に接触しているかどうか、かつ／または基準線に合致しているかどうかを決定してよい。
【００１３】
方法（または対応するシステム）のいくつかの実施形態は、現実世界形状の一部である基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差するかどうかを決定してよい。方法（または対応するシステム）のいくつかの実施形態は、コンピュータハードウェア（および／またはソフトウェア）において任意選択で実装されるさらなるステップ（方法）および／またはシステム機能（システム）を含み得る。このため、いくつかの実施形態は、セグメントのうちの複数が重なり合うかどうかを決定してよく、かつ／または２次元（２Ｄ）現実世界形状のうちの異なる形状のセグメントのうちの複数が重なり合うかどうかをさらに決定してよく、かつ／またはセグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちの別のものの内部にあるかどうかをさらに決定してよく、かつ／またはセグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちの別のものの上にあるかどうかをさらに決定してよい。
【００１４】
方法（または対応するシステム）のいくつかの実施形態によれば、所与の軸は、水平（ｘ）軸または垂直（ｙ）軸であってよい。方法（および対応するシステム）のいくつかの実施形態によれば、その方法または対応するシステムは、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界のうちの別のものと交差する現実世界形状の一部であるかどうかを決定してよい。方法（または対応するシステム）のいくつかの実施形態は、複数の基準線のうちの各基準線に接続されたセグメントの各セグメントが各基準線を横断しているかどうか、各基準線に接触しているかどうか、かつ／または各基準線に合致しているかどうかを決定してよい。
【００１５】
システムまたは方法のいくつかの実施形態によれば、そのシステムまたはその方法は、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部である基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、優先順序に基づくかどうかを決定してよい。そのような優先順序において、（基準線を横断している、基準線に接触している、または基準線に合致しているということに関して、）「合致している」というタイプの優先度は、「横断している」および「接触している」というタイプの優先度と比べて、より高い優先度であると見なされてよい。
【００１６】
いくつかの実施形態は、複数の２次元（２Ｄ）現実世界形状の間の交差を決定するためのコンピュータシステムを含み得る。システムは、複数のプロセッサおよびメモリを含む。メモリは、（ｉ）それの上に記憶されたコンピュータコード命令、および／または（ｉｉ）２次元（２Ｄ）現実世界形状を表すデータを含み得る。データは、２次元（２Ｄ）現実世界形状の部分を含むセグメントを含み得る。セグメントは、２次元（２Ｄ）現実世界形状の部分の始点頂点と終点頂点を表し得る。メモリは、複数のプロセッサによって実行された場合、コンピュータコード命令がコンピュータシステムに、１つまたは複数の機能を実行するように構成されたコンピューティングモジュールを実装することをさせ得るように複数のプロセッサに動作可能に結合されてよい。コンピューティングモジュールは、複数の基準線を定義してよい。各基準線は、所与の軸に沿った頂点のうちの少なくとも１つと交差し得る。コンピューティングモジュールは、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって基準線を並列に処理してよい。コンピューティングモジュールは、分類することに基づいて、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状の別のものと交差する現実世界形状の一部であるかどうかを決定してよい。
【００１７】
システムの実施形態において、各プロセッサは、基準線のサブセットを処理してよい。セグメントは、読取り専用としてメモリに記憶されてよい。２次元（２Ｄ）現実世界形状は、現実世界多角形を含み得る。現実世界形状は、２次元（２Ｄ）現実世界形状の別のものの内部にあってよく、またはそのような別のものに接触していてよい。２次元（２Ｄ）現実世界形状は、プリント回路基板およびデジタルコンピュータ画像のうちの少なくとも１つの構成要素であり得る。システムの実施形態において、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することは、所与の基準線に沿った各頂点に関して、基準線の位置と、セグメントの始点頂点および終点頂点とを比較することによって、頂点に関連付けられたセグメントが基準線を横断しているかどうか、基準線に接触しているかどうか、または基準線に合致しているかどうかを決定することを含み得る。
【００１８】
システムのいくつかの実施形態において、コンピューティングモジュールは、現実世界形状の一部である基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状の別のものと交差するかどうかを決定するようにさらに構成され得る。コンピューティングモジュールは、セグメントのうちの複数が重なり合う（例えば、互いに）かどうかを決定してよい。コンピューティングモジュールは、２次元（２Ｄ）現実世界形状のうちの異なる形状のセグメントのうちの複数が重なり合うかどうかを決定してよい。コンピューティングモジュールは、セグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちの別のものの内部にあるかどうかを決定してよい。コンピューティングモジュールは、セグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちのその別のものの上にあるかどうかを決定してよい。
【００１９】
システムのいくつかの実施形態によれば、所与の軸は、水平軸または垂直軸であってよい。いくつかの実施形態によれば、コンピューティングモジュールは、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状の別のものと交差する現実世界形状の一部であるかどうかを決定するようにさらに構成され得る。コンピューティングモジュールは、基準線の各基準線に接続されたセグメントの各セグメントが各基準線を横断しているかどうか、各基準線に接触しているかどうか、または各基準線に合致しているかどうかを決定してよい。
【００２０】
システムのいくつかの実施形態によれば、コンピューティングモジュールは、優先順序に基づいて、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定するようにさらに構成され得る。そのような優先順序において、（基準線を横断している、基準線に接触している、または基準線に合致しているということに関連して、）「合致している」というタイプの優先度は、「横断している」および「接触している」というタイプの優先度と比べて、より高い優先度であると見なされてよい。
【００２１】
いくつかの実施形態は、装置に結合されたプロセッサによってロードされ、かつ実行された場合、装置に、複数の基準線を定義することであって、各基準線は、２次元（２Ｄ）現実世界形状の部分を表すセグメントの始点頂点と終点頂点のうちの少なくとも１つと交差すること、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって基準線を並列に処理すること、および分類することに基づいて、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状の別のものと交差する現実世界形状の一部であるかどうかを決定することを行うことをさせ得る。
【図面の簡単な説明】
【００２２】
以上は、同様の参照符号が異なる図のすべてにわたって同一の部分を参照する添付の図面に例示されるとおり、本発明の例示的な実施形態の以下のより詳細な説明から明白となろう。図面は、必ずしも一律の縮尺に従わずに描かれており、強調は、代わりに、本発明の実施形態を例示することに置かれている。
【図１】いくつかの実施形態による、形状の間の１つまたは複数の交差を検出することに向けられた例示的な方法（または装置もしくはシステムの一部）を示す流れ図である。
【図２】いくつかの実施形態による、形状の間の交差の検出を示す図である。
【図３】いくつかの実施形態による、横断点決定の一部として、基準線、複数の対応するセグメントを示す図である。
【図４】いくつかの実施形態による、複数の基準線、および頂点の並列の処理を示す図である。
【図５】いくつかの実施形態による、コンピュータネットワーク（もしくは装置もしくはシステム）または類似したデジタル処理環境を示す図である。
【図６】いくつかの実施形態による、図５のコンピュータシステム（および装置）におけるコンピュータ（例えば、クライアントプロセッサ／デバイスもしくはサーバコンピュータ）の例示的な内部構造を示す図である。
【発明を実施するための形態】
【００２３】
本発明の例示的な実施形態の説明が以下に行われる。
【００２４】
２次元（２Ｄ）における多角形交差（「クリッピング」および「衝突検出」とも呼ばれる）のためのアルゴリズムが存在する。電子設計自動化、またはＥＤＡにおける多角形（プリント回路基板、またはＰＣＢのような）の性質は、複雑な凸面−凹面形態であり、したがって、凸面多角形を受け入れるよく知られたアルゴリズムは、適用可能でないことがある。そのような既存のアルゴリズムは、境界形状（Ｂｏｕｎｄｉｎｇ  Ｓｈａｐｅ）（例えば、箱、円）、クイックハル（Ｑｕｉｃｋ  Ｈｕｌｌ）、空間分割（Ｓｐａｔｉａｌ  Ｐａｒｔｉｔｉｏｎｉｎｇ）（四分木（Ｑｕａｄｔｒｅｅｓ）を含むが、それには制限されない）、分離軸定理（Ｓｅｐａｒａｔｉｎｇ  Ａｘｉｓ  Ｔｈｅｏｒｅｍ）、スキャンアンドプルーン（Ｓｃａｎ  ａｎｄ  Ｐｒｕｎｅ）（ソートアンドスキャン（Ｓｏｒｔ  ａｎｄ  Ｓｃａｎ）としても知られる）を含み得るが、これらには制限されない。
【００２５】
凸面多角形と凹面多角形の両方を受け入れ得る他の既存のアルゴリズムは、他の制限を有することがある。しかし、既存のアルゴリズムとはまったく対照的に、開示される実施形態は、これらの制限を受けない（すなわち、実施形態は、そのように制限されない）。例えば、Ｂｅｎｔｌｅｙ−Ｏｔｔｍａｎｎアルゴリズムは、数値制限を有することがあり、すなわち、いずれの２つの線セグメント端点または線セグメント横断点も、同一のｘ座標を有し得ず（垂直線およびほぼ垂直の線は、特別の扱いを必要とする）、いずれの線セグメント端点も別の線セグメント上にあることはあり得ず、いずれの３つの線セグメントも単一の点において交差することはあり得ないが、まったく対照的に、本明細書において提示される実施形態は、そのように制限されない。Ｇｒｅｉｎｅｒ−Ｈｏｒｍａｎｎクリッピングアルゴリズムは、共通の辺またはちょうど頂点における交差などのデジェネラシー（ｄｅｇｅｎｅｒａｃｉｅｓ）を扱わないことがあるが、いくつかの実施形態は、そのように制限されない。
【００２６】
Ｗｅｉｌｅｒ−Ａｔｈｅｒｔｏｎアルゴリズムは、２多角形クリッピングを実行することがあり、マルチ多角形タスクにおいて非効率であることがあり、かつ多角形の各ペアに関して走らされる必要があることがあり、したがって、Ｎ*（Ｎ−１）／２の組合せが実行され得る。Ｓｕｔｈｅｒｌａｎｄ−Ｈｏｄｇｍａｎアルゴリズムは、クリッピングを含むことがあり、かつ凹面に関して堅牢でないことがある。機能的に適用可能なアルゴリズムは、マルチ多角形タスクに関してうまく機能しないことがある。非制限的な例に関して、Ｖａｔｔｉ（クリッピングアルゴリズム）は、２多角形クリッピングを定義することがあり、マルチ多角形タスクにおいて非効率であることがあり、かつ多角形の各ペアに関して走らされる必要があることがある。しかし、本明細書において提示される実施形態は、そのように制限されない。
【００２７】
さらに、多角形交差検出のためのほとんどの既存のアルゴリズムは、１９７０年代に開発されており、単一ＣＰＵマシンを対象にしていることがある。このため、多角形交差検出のための既存のアルゴリズムの大多数は、最新のマルチコアハードウェアを使用していない。対照的に、いくつかの実施形態は、最新のマルチコアハードウェアを使用することがあり、かつマルチＣＰＵマシンを対象とすることがある。
【００２８】
本明細書において提示される実施形態とは異なり、既存のアプローチは、パフォーマンス問題を被る。既存のアプローチは、グローバルデータセットを使用することがあり、並列様態で使用されるように意図されていない。このため、既存のアプローチに並列実行を適用することは、データ構造のロッキングを要求し得る。グローバルデータがそのような既存のアルゴリズムによってどれだけ活発に使用されるかを考慮すると、既存のアルゴリズムは、うまく拡大縮小しないことがある。このため、本明細書において提示される実施形態とは異なり、既存のアプローチは、順次であることがあり、したがって、最新のＣＰＵ／ＧＰＵハードウェアを使用していないことがあり、かつ高いパフォーマンスに達することができないことがある。
【００２９】
さらに、本明細書において提示される実施形態の場合とは異なり、既存のアプローチにおいて、多角形自己交差は、サポートされないことがある。さらに、本明細書において提示される実施形態の場合とは異なり、既存のアプローチは、共通の辺または頂点における交差などのデジェネラシーを扱わないことがある。このように、実施形態は、既存のアプローチの前述の欠点を克服する。
【００３０】
図１は、いくつかの実施形態による、形状の間で１つまたは複数の交差を検出することに向けられた例示的な方法（または装置もしくはシステムの一部）１０００の流れ図である。このため、図１は、いくつかの実施形態による、複数の２次元（２Ｄ）現実世界形状の間で交差を決定する方法（または対応するシステムの一部）１０００を例示する。いくつかの実施形態は、形状を表すデータを含み得る。いくつかの実施形態によれば、データは、入力として提供され得る。他の実施形態は、データを生成１０２し得る。
【００３１】
形状（および／またはデータ）は、始点頂点と終点頂点を有する２Ｄ現実世界形状のセグメントを含み得る。いくつかの実施形態において、方法（または対応するシステム）１０００は、複数の基準線を定義１０４し得る。各基準線は、所与の軸に沿った頂点のうちの少なくとも１つと交差し得る。いくつかの実施形態において、方法（または対応するシステム）１０００は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって、基準線を並列に処理１０６し得る。いくつかの実施形態において、分類することに基づいて、方法（または対応するシステム）１０００は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを並列に決定１０８してよい。
【００３２】
方法（または対応するシステム）１０００のいくつかの実施形態によれば、２次元（２Ｄ）現実世界形状は、現実世界多角形を含み得る。さらに、交差する現実世界形状は、２次元（２Ｄ）現実世界形状のうちの別のものの内部にあってよく、またはそのような別のものに接触していてよい。いくつかの実施形態において、２次元（２Ｄ）現実世界形状は、プリント回路基板およびデジタルコンピュータ画像のうちの少なくとも１つの構成要素であり得る。非制限的な例に関して、いくつかの実施形態は、２Ｄモデリング、解析、ゲーム、プリント回路基板（ＰＣＢ）のための電子設計自動化（ＥＤＡ）アプリケーション、画像認識、コンピュータビジョン、および／または拡張現実に適用され得る。
【００３３】
いくつかの実施形態において、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することは、所与の基準線に沿った各頂点に関して、基準線の位置と、セグメントの始点頂点および終点頂点とを比較することによって、頂点に関連付けられたセグメントが基準線を横断しているかどうか、基準線に接触しているかどうか、または基準線に合致しているかどうかを決定することを含み得る。
【００３４】
方法（または対応するシステム）１０００のいくつかの実施形態は、現実世界形状の一部である基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差するかどうかを決定してよい。方法（または対応するシステム）１０００のいくつかの実施形態は、コンピュータハードウェア（および／またはソフトウェア）において任意選択で実装されるさらなるステップ（方法）１０００および／またはシステム機能（システム）１０００を含み得る。このため、いくつかの実施形態において、方法（または対応するシステム）１０００は、セグメントのうちの複数が重なり合うかどうかを決定してよい。いくつかの実施形態において、方法（または対応するシステム）１０００は、２次元（２Ｄ）現実世界形状のうちの異なる形状のセグメントのうちの複数が重なり合うかどうかを決定してよい。いくつかの実施形態において、方法（および対応するシステム）１０００は、セグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちの別のものの内部にあるかどうかを決定してよい。いくつかの実施形態において、方法（または対応するシステム）１０００は、セグメントのうちの所与のセグメントの終端頂点が２次元（２Ｄ）現実世界形状のうちの別のものの上にあるかどうかを決定してよい。
【００３５】
方法（または対応するシステム）１０００のいくつかの実施形態によれば、所与の軸は、水平（ｘ）軸または垂直（ｙ）軸であってよい。いくつかの実施形態によれば、方法（または対応するシステム）１０００は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定してよい。いくつかの実施形態によれば、方法（または対応するシステム）１０００は、基準線の各基準線に接続されたセグメントの各セグメントが各基準線を横断しているかどうか、各基準線に接触しているかどうか、かつ／または各基準線に合致しているかどうかを決定してよい。
【００３６】
いくつかの実施形態によれば、方法（または対応するシステム）１０００は、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部である基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、優先順序に基づくかどうかを決定してよい。そのような優先順序において、基準線に「合致している」頂点の優先度は、基準線を「横断している」または「接触している」と比べて、より高い優先度であると見なされてよい。
【００３７】
図２は、方法（またはシステム）１０００のいくつかの実施形態による、（それぞれ、層２０２、２０４の）形状の間の１つまたは複数の交差２０６の検出を例示する。図２に例示されるとおり、通常のプリント回路基板（ＰＣＢ）の断片が、２つの層（それぞれ、２０２、２０４）を誤って含むことがある。図２において、回路２０８は、多角形によって表され得る。図２は、複雑な無効なデータの例である。
【００３８】
いくつかの実施形態は、方法（またはシステム）１０００の一部として含められ得るコンピュータ実装アルゴリズム（本明細書において「アルゴリズム」とも称される）を含み、かつ１つまたは複数のコンピューティングデバイス上のハードウェアおよび／またはソフトウェアにおいて実装されてよい。アルゴリズムは、以下の段階（機能および／またはステップとしても知られる）のうちの１つまたは複数、すなわち、（１）基準線生成、（２）基準線処理、（３）結果収集、（４）結果の後処理を含んでよい。これらの段階（１〜４）のそれぞれは、順次に実行されてよく、または並列に実行されてよい。いくつかの実施形態は、以下のとおり（並列演算および順次演算に関して）、すなわち、（１）基準線生成  順次、（２）基準線処理  並列または順次、（３）結果収集  順次、（４）結果の後処理  並列または順次である。基準線処理（段階２）は、好ましくは、並列に実行されるが、そのように制限されない。
【００３９】
いくつかの実施形態において、セグメント（辺）を含む形状のコレクションを含む入力データが方法（またはシステム）１０００に受信されて（供給されて）よく、各セグメントは、始点と、終了とを含む２つの２次元（２Ｄ）端点を含む。他の実施形態において、入力データは、方法（またはシステム）１０００によって生成され得る。
【００４０】
段階１  基準線生成（順次であってよいが、そうであることに制限されない）
【００４１】
基準線生成において、基準線のコレクションが作成され得る。基準線のコレクションは、端点のｘ座標を表す一意の数のアレイを備え得る。以下の疑似コード（例１）が、基準線生成を実行することを例示する。
例１
【００４２】
【表１】
2018185812.tif 000003
【００４３】
段階２  基準線処理（好ましくは、並列であるが、そうであることに制限されない）
【００４４】
基準線処理において、いくつかの実施形態によれば、各基準線は、本明細書において「スキャナ」または「スキャナオブジェクト」と称される別個のオブジェクトによって処理され得る。順次のスキャニングを使用する既存のアプローチとは異なり、いくつかの実施形態のスキャナは、以下に本明細書においてさらに説明されるとおり、並列アルゴリズムを適用して、２つ以上の基準線を並列に処理してよい。非制限的な例に関して、いくつかの実施形態によれば、１つのスキャナ（オブジェクト）が各基準線に別々に適用され得る。
【００４５】
いくつかの実施形態によれば、データは、ローカルであり得る。いくつかの実施形態において、ローカルデータは、セグメントの共有される読取り専用のコレクションとして適用される場合を除いて、単一の基準線に適用され得る。すなわち、いくつかの実施形態において、全体的なデータセットは、複数のローカルデータセットに細分され得る。いくつかの実施形態によれば、各ローカルデータセットは、その他のスキャナによってではなく、単一の（所与の）スキャナによって書き込まれ得る。
【００４６】
それぞれの所与のローカルデータセットは、所与の基準線に対応する（しかし、その他の基準線および／またはデータセットには対応しない）データを含み得る。各ローカルデータセットが単一の（所与の）スキャナによって書き込まれることがあり、かつ、好ましくは、その他のスキャナによって書き込まれ得ないと仮定すると、基準線は、各基準線が異なるローカルデータセットに対応し得るため、潜在的な競合条件の懸念なしに並列に処理され得る。このため、いくつかの実施形態において、方法（またはシステム）１０００は、データをロックすることも、競合条件を生じることもなしに、基準線を並列に処理してよい。さらに、いくつかの実施形態は、ＯｐｅｎＭＰ（オープンマルチ処理）および／またはＰＰＬ（並列パターンライブラリ）をサポートし、かつそれらを用いて試験される。
【００４７】
段階２（基準線処理）において、方法（またはシステム）１０００のいくつかの実施形態によれば、スキャナが、以下の段階、すなわち、（段階２．１）横断点を決定すること、および（段階２．２）形状の間の交差を決定することのうちの１つまたは複数を実行してよい。これらの機能のそれぞれのための関連付けられたアルゴリズムが、単一のスキャナを参照して以下に説明される。しかし、いくつかの実施形態において、これらのアルゴリズムは、複数のスキャナに適用されてもよい。
【００４８】
段階２．１．横断点を決定すること
【００４９】
基準線処理の一部として、横断点が、横断点をスキャンすること、および／または登録することを含め、決定され得る（本明細書において「横断点決定」としても知られる）。いくつかの実施形態によれば、横断点は、基準線上の点を含んでよく、基準線は、１つまたは複数のセグメントを横断する、またはそれらに接触する。いくつかの実施形態によれば、横断点は、中間データとして使用され得る（例えば、横断点決定の段階２．１から出力され、かつ交差を決定するために段階２．２に入力される）。
【００５０】
図３は、いくつかの実施形態による、横断点決定の一部として、基準線および複数の対応するセグメントを例示する。図３に例示されるとおり、いくつかの実施形態によれば、スキャナが、基準線３０２に沿って「スキャン」してよく、その結果、それぞれ３２０、３２２、３２４、３２６である様々な横断点を検出する。スキャナは、基準線３０２に沿って上向きに、または下向きにスキャンしてよい。
【００５１】
図３に例示されるとおり、方法（またはシステム）１０００のいくつかの実施形態は、端点頂点３３０、３３２を有する、それぞれ３０６、３０８、３１０、３１２であるセグメント（すなわち、始点頂点３３０と終点頂点３３２を有する各セグメント、「端点」頂点は、「始点」頂点と「終点」頂点を含むように定義される）が、所与の軸３０４に関連付けられた基準線３０２を横断するかどうかに基づいて、横断点３２０、３２２、３２４、３２６を決定してよい。４つのセグメント３０６、３０８、３１０、３１２が図３に例示されるものの、実施形態は、そのように制限されず、１つ乃至３つのセグメント、または５つ以上のセグメントが、本明細書において説明されるとおり適用されてよい。
【００５２】
図３に例示されるとおり、横断点決定は、基準線３０２に関して各セグメント３０６、３０８、３１０、３１２を解析すること、およびクリア（ＣＬＥＡＲ）、横断（ＣＲＯＳＳＩＮＧ）、接触（ＴＯＵＣＨＩＮＧ）、および／または合致（ＦＯＬＬＯＷＩＮＧ）の以下の決定のうちの１つまたは複数を行うことを含み得る。第１に、図３におけるセグメント３１２によって例示されるとおり、セグメント３１２が基準線３０２を横断しない場合、方法（またはシステム）１０００は、セグメント３１２、およびセグメントの関連付けられた頂点がクリア状態にある（例えば、基準線を横断することも、基準線に接触することも、基準線に合致することもない）と決定し得る。このため、いくつかの実施形態によれば、クリア状態は、横断点に対応し得ないが、横断状態、接触状態、および／または合致状態は、横断点に対応し得る。次に、図３におけるセグメント３０６によって例示されるとおり、方法（またはシステム）１０００は、セグメント３０６、およびセグメント３０６の頂点３２０が基準線３０２を横断している（例えば、「横断」の状態にある）と決定し得る。
【００５３】
次に、図３におけるセグメント３０８によって例示されるとおり、方法（またはシステム）１０００は、セグメント３０８、およびセグメント３０８の頂点３２２が基準線３０２に接触している（例えば、「接触」の状態にある）と決定し得る。いくつかの実施形態によれば、セグメント３０８は、セグメント３０８の端点３３０、３３２のうちの１つがスキャナ上にある場合、基準線に接触している。
【００５４】
さらに、図３におけるセグメント３１０によって例示されるとおり、方法（またはシステム）１０００は、セグメント３１０、およびセグメントの対応する始点頂点３２６と終点頂点３２４が基準線に合致している（例えば、「合致」の状態にある）と決定し得る。いくつかの実施形態によれば、セグメント３１０は、セグメント３１０の端点３３０、３３２の両方がスキャナ上にある場合、基準線に合致している。
【００５５】
いくつかの実施形態によれば、図３に例示されるとおり、クリア結果は、横断点をもたらし得ないが、横断、接触、および合致の結果は、１つまたは複数の横断点をもたらし得る。
【００５６】
また、いくつかの実施形態によれば、優先度スキームが、本明細書に説明されるとおり、段階２．２（交差を決定すること）の一部として使用され得る。すなわち、いくつかの実施形態において、方法（またはシステム）１０００は、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定してよく、かつこの決定は、優先順序に基づいてよい。優先順序において、「合致する」状態（本明細書において「合致」としても知られる）は、「横断すること」（本明細書において「横断」としても知られる）および「接触すること」（本明細書において「接触」としても知られる）と比べて、より高い優先度と見なされ得る。いくつかの実施形態によれば、横断は、接触と比べて、より高い優先度であり得る。このため、いくつかの実施形態によれば、合致は、以下の段階２．２のアルゴリズムにおいて最高の優先度を有し得る。
【００５７】
図３に例示されるとおり、基準線が垂直の非有界の線である限り、セグメントのｙ座標３５０は、無視されてよく、かつ結果は、基準線３０２によりセグメントの端点のｘ座標３０４がどこに位置するかに依存し得る。
【００５８】
いくつかの実施形態によれば、以下の疑似コードは、垂直線に対するセグメントの位置関係を見出すことを含み得る、横断点を検出する効率的なアルゴリズムを実証する。結果は、各基準線に関する横断点のコレクションを含み得る。
【００５９】
各横断点は、以下、すなわち、（１）形状識別子（ＩＤ）、（２）セグメント識別子（ＩＤ）、（３）横断、接触、および／または合致を含むが、これらには限定されない横断点タイプ（すなわち、開始または終了）、（４）横断、接触、および／または合致の横断点タイプ（すなわち、開始）に関するＹ座標、および（５）横断点のタイプが合致である場合、合致（すなわち、終了）に関するＹ座標のうちの１つまたは複数を含み得るデータ構造によって説明され得る。
【００６０】
以下の疑似コード（例２）は、横断点の検出（段階２．１）を例示する。
例２
【００６１】
【表２】
2018185812.tif 000004
【００６２】
前述の例２アルゴリズム（段階２．１の）を使用して、横断点が決定されてよい。次に、いくつかの実施形態によれば、段階２．１の出力（横断点）が中間データとして使用され得る（例えば、横断点決定の段階２．１からの出力が、交差を決定するための段階２．２に対する入力として使用され得る）。
【００６３】
段階２．２．交差を決定すること
【００６４】
基準線処理の一部として、形状の間の交差が、決定された横断点に基づいて決定され得る（本明細書において「交差を決定すること」とも称される）。いくつかの実施形態によれば、横断点は、基準線上の点を含んでよく、基準線は、１つまたは複数のセグメントを横断する。以下により詳細に説明される図４は、いくつかの実施形態による、複数の基準線、および頂点の並列の処理を例示する。また、図４は、交差がどのように決定されるかに関しても以下により詳細に説明される。
【００６５】
形状の間の交差を決定することの一部として、いくつかの実施形態は、１つまたは複数のスキャナ（スキャナオブジェクト）を含み得る。いくつかの実施形態によれば、各スキャナは、各横断点に関連付けられた、以降、「ｉｎＳｈａｐｅ」（または本明細書において、ｉｎＳｈａｐｅコレクションもしくはｉｎＳｈａｐｅデータ構造）および「ｏｎＳｈａｐｅ」（または本明細書において、ｏｎＳｈａｐｅコレクションもしくはｏｎＳｈａｐｅデータ構造）と呼ばれるデータ構造（または本明細書においてデータコレクションもしくはコレクション）を含み得る。いくつかの実施形態によれば、所与の横断点に関して、ｉｎＳｈａｐｅは、所与の横断点が形状（例えば、多角形）内部にあるかどうかを示し得る。いくつかの実施形態によれば、所与の横断点に関して、ｏｎＳｈａｐｅは、所与の横断点が形状（例えば、多角形）（の境界）上にあるかどうかを示し得る。例示的な例が、ｉｎＳｈａｐｅデータ構造およびｏｎＳｈａｐｅデータ構造を参照して後段で提供される。
【００６６】
図４に例示されるとおり、方法（またはシステム）１０００のいくつかの実施形態は、それぞれ４１２、４１４、４１６、４１８である各基準線（図４のｘ軸４８８に沿って示される）を、基準線４１２、４１４、４１６、４１８の一番下から４０２、４０４、４０６、４０８の方へ上向きに走査して（例えば、沿って歩いて）よい。Ｘ２基準線（図４の要素４１４）に関するそのような走査が、以下に説明される。
【００６７】
Ｘ２基準線（図４の要素４１４）に関して図４に示されるとおり、基準線４１４の一番下からの第１の横断点は、横断タイプ（例えば、横断点）の頂点Ｃ（図４の要素４２０）である。横断点４２０を走査して、スキャナは、ｉｎＳｈａｐｅコレクションに頂点Ｃを追加する、つまり、状態は、ＡＢＨＦ長方形に「入って」いる。次に、それは、ＡＢＨＦ長方形４２２の内部に到達し、ｉｎＳｈａｐｅコレクションに線セグメント４４４の頂点Ｄ（図４の横断点要素４２４）を追加し、状態がＡＢＨＦ長方形４２２に「入っている」ため、長方形４２２に交差を登録することを同時に行う。線セグメント４７０の頂点Ｄ（図４の横断点要素４２４）を再び通過して、それが三角形４４０の外部にあるため、以前に追加された頂点ＤがｉｎＳｈａｐｅコレクションから除去される。横断点Ｅ（図４の要素４２６）を通過するとき、スキャナは、ＡＢＨＦ長方形の外部に移動し（長方形４２２の境界を２度目に横断して）、方法（またはシステム）１０００は、ＡＢＨＦ長方形４２２に属する以前の横断点Ｃ（要素４２０）をｉｎＳｈａｐｅから除去し、Ｘ２基準線４１４に関してｉｎＳｈａｐｅの「入っている」状態を終了する。
【００６８】
すなわち、いくつかの実施形態によれば、ｉｎＳｈａｐｅコレクションは、入るように横断されている形状のより下の横断点を保持してよい。かつ、スキャナがより低い横断点から出るように移動した（より高い横断点を通って）場合、スキャナは、形状のより低い横断点をｉｎＳｈａｐｅコレクションから除去してよい。
【００６９】
次に、Ｘ１基準線（図４の要素４１２）に関する走査が以下に説明される。以下にも説明されるとおり、基準線４１２に沿った走査は、ｏｎＳｈａｐｅコレクションの使用も例示する。基準線４１２に関して図４に例示されるとおり、一番下からの第１の横断点は、線セグメントＡＦ（要素４３６）およびＡＢ（要素４３２）に属する頂点Ａ（図４の要素４３０）である。横断点タイプ（前述される）の優先度により、ＡＦ線セグメント（図４の要素４３６）における頂点Ａ（図４の要素４３０）は、より低い優先度を有する接触タイプを有し、したがって、それは、スキャナによって無視される。ＡＢ線セグメント（図４の要素４３２）の横断点Ａ（図４の要素４３０）を検討すると、スキャナは、ＡＢ線セグメント（図４の要素４３２）に従って進み、したがって、スキャナは、ｏｎＳｈａｐｅコレクションにＡＢ線セグメント（図４の要素４３２）の横断点Ａ（図４の要素４３０）を追加してよく、長方形ＡＢＨＦ（図４の要素４２２）のセグメント「上にある」状態を示す。次に、スキャナは、それぞれＡＢ（図４の要素４３２）およびＢＨ（図４の要素４３８）である２つの線セグメントに属する横断点Ｂ（図４の要素４３４）を通過する。このため、線セグメントＢＨ（図４の要素４３８）は、接触というそれの横断タイプが、線セグメントＡＢ（図４の要素４３２）の合致という横断タイプと比べて、より低い優先度を有するため、スキャナによって無視され、このため、スキャナは、線セグメントＡＢ（図４の要素４３２）の外部に移動する。このようにして、横断点Ａ（図４の要素４３０）は、スキャナがもはや、線セグメントＡＢ（図４の要素４３２）「上にある」のではないため、ｏｎＳｈａｐｅから除去される。すなわち、いくつかの実施形態によれば、ｏｎＳｈａｐｅコレクションは、セグメントに入るように横断することなしに合致され得るセグメントに属することがある横断点を保持し得る。
【００７０】
いくつかの実施形態によれば、ｏｎＳｈａｐｅコレクションは、線セグメントＡＦ（図４の要素４３６）の点Ａ（図４の要素４３０）および／または線セグメントＢＨ（図４の要素４３８）の点Ｂ（図４の要素４３４）などの、接触分類の横断点を一次的に保持し得る。それらは、合致というより高い優先度を有する線セグメントＡＢ（図４の要素４３２）の点Ａ（図４の要素４３０）およびＢ（図４の要素４３４）によって克服され、これらは、次に、ｏｎＳｈａｐｅから除去される、または無視される。
【００７１】
すなわち、いくつかの実施形態によれば、スキャナが基準線に沿って下から上に横断点を通って移動するにつれ、
（１）コレクションｉｎＳｈａｐｅが、形状の境界が奇数回、横断されている横断点を保持し得る。したがって、ｉｎＳｈａｐｅが空でない場合、現在の位置は、少なくとも１つの形状の内部にある。形状は、偶数回、横断されると、ｉｎＳｈａｐｅから除去されてよく、かつ／または
（２）コレクションｏｎＳｈａｐｅが、基準線上にある、形状についてのデータを保持してよく、したがって、ｏｎＳｈａｐｅが空でない場合、現在の位置は、そのような形状の合致セグメント上にあり得る。また、ｏｎＳｈａｐｅは、横断点に合致することによって除去され得る接触横断点を保持してよく、このため、短命であり得る。以下に、横断点Ｄの処理に関して接触処理の例が示される。
【００７２】
いくつかの実施形態によれば、段階２．２が、１つまたは複数の交差を決定し得る。いくつかの実施形態によれば、交差点は、方法（またはシステム）１０００の最終結果を表し得る。
【００７３】
交差点は、以下のタイプのうちの１つまたは複数を有し得る。すなわち、
（１）交差  異なる形状の２つのセグメントが交差している
（２）内部  １つの形状の端点が別の形状の内部にある
（３）頂点接触  １つの形状のセグメント端点（頂点）が別の形状のセグメント上にある、および
（４）辺接触  ２つの垂直セグメントが重なり合う
【００７４】
いくつかの実施形態によれば、交差点の優先スキームは、交差から辺接触まで上昇してよいが、方法（またはシステム）１０００は、この優先スキームにそのように制限されない。すなわち、交差は、最低の優先度を有してよく、かつ辺接触は、最高の優先度を有してよい。
【００７５】
以下の疑似コードが、交差点をもたらす。以下の疑似コード（例３）は、交差の検出（段階２．２）を例示する。
例３
【００７６】
【表３−１】
2018185812.tif 000005
【００７７】
【表３−２】
2018185812.tif 000006
【００７８】
いくつかの実施形態によれば、図４は、方法（またはシステム）１０００のスキャナがどのように横断点を処理して、形状の間の交差（本明細書において「交差点」とも称される）を決定するかを例示する。図４の非制限的な例示的な実施形態において、方法（またはシステム）１０００は、横断点Ｄ（要素４２４）、Ｇ（要素４５２）、およびＨ（要素４５４）を決定し得る。以下の説明は、どのようにこれらの横断点が決定され得るかを例示する。
【００７９】
いくつかの実施形態によれば、図４に例示されるとおり、長方形（例えば、正方形）および三角形が、４つの基準線、すなわち、Ｘ１乃至Ｘ４（それぞれ、要素４１２、４１４、４１６、および４１８）をもたらし得る。
【００８０】
基準線Ｘ１
【００８１】
図４に例示されるとおり、方法（またはシステム）１０００は、基準線Ｘ１（要素４１２）を処理し得る。段階２．１（横断点を決定すること）において、図４の処理が、基準線Ｘ１（要素４１２）に関して合計で４つの横断点をもたらす。段階２．２（交差を決定すること）において、図４の処理が、多角形交差をまったくもたらさない。
【００８２】
図４に例示されるとおり、基準線Ｘ１を処理することは、頂点Ａ（要素４３０）における２つの横断点、すなわち、線セグメントＡＦ（要素４３６）の端点、および線セグメントＡＢ（要素４３２）の端点をもたらす。スキャナは、接触タイプを有する、線セグメントＡＦ（要素４３６）の点Ａ（要素４３０）を、線セグメントＡＢ（要素４３２）の点Ａ（要素４３０）が、接触と比べて、より高い優先度である合致タイプを有するため、無視する。次に、スキャナは、線セグメントＡＢ（要素４３２）の点Ａ（要素４３０）をｏｎＳｈａｐｅコレクションに追加する。
【００８３】
基準線Ｘ１を処理することは、頂点Ｂ（要素４３４）における２つの横断点、すなわち、線セグメントＢＨ（要素４３８）の端点（要素４３４）、および線セグメントＡＢ（要素４３２）の端点（要素４３４）ももたらす。スキャナは、接触タイプを有する、線セグメントＢＨ（要素４３８）の点Ｂ（要素４３４）を、線セグメントＡＢ（要素４３２）の点Ｂ（要素４３４）が、接触と比べて、より高い優先度である合致タイプを有するため、無視する。それが、合致セグメント（線セグメントＡＢ、要素４３２）の終了に到達すると、スキャナは、線セグメントＢＨ（要素４３８）の開始を見出し、ｏｎＳｈａｐｅコレクションから点Ａ（要素４３０）を除去する。
【００８４】
基準線Ｘ２
【００８５】
図４に例示されるとおり、方法（またはシステム）１０００は、基準線Ｘ２（要素４１４）を処理し得る。段階２．１（横断点を決定すること）において、処理は、基準線Ｘ２（要素４１４）に関して合計で４つの横断点、すなわち、頂点Ｃ（要素４２０）における横断点、頂点Ｄ（要素４２４）における２つの横断点、および頂点Ｅ（要素４２６）における横断点をもたらす。段階２．２（交差を決定すること）において、処理は、頂点Ｄ（要素４２４）における多角形交差をもたらす。
【００８６】
基準線Ｘ２（要素４１４）を処理することが、頂点Ｃ（要素４２０）における横断点、すなわち、線セグメントＡＦ（要素４３６）における横断点をもたらす。頂点Ｃ（要素４２０）における横断点は、横断タイプを有し、この時点でｉｎＳｈａｐｅにおいて同一の長方形４２２の他の横断点は存在せず、このことは、基準線Ｘ２（要素４１４）が形状（長方形４２２）に入るように横断することを意味する。スキャナは、点Ｃ（要素４２０）をｉｎＳｈａｐｅに追加し、したがって、基準線Ｘ２（要素４１４）上の点Ｃ（要素４２０）に合致する点が、この形状である長方形４２２の第２の横断点（横断点Ｅ、要素４２６）が到達されるまで、交差となる。
【００８７】
基準線Ｘ２（要素４１４）を処理することは、頂点Ｄ（要素４２４）における２つの横断点、すなわち、それぞれが接触横断タイプを有する、線セグメントＤＩおよびＤＪ（それぞれ、要素４４２、４４４）の端点をもたらす。次に、スキャナは、ｉｎＳｈａｐｅコレクションが空でないことを認識し、したがって、頂点Ｄ（要素４２４）が内部交差点になる。次に、スキャナは、線セグメントＤＪ（要素４４４）の点Ｄ（要素４２４）をｏｎＳｈａｐｅコレクションに追加する。次に、スキャナは、線セグメントＤＩ（要素４４２）の点Ｄ（要素４２４）に至り、線セグメントＤＪ（要素４４４）の点Ｄ（要素４２４）がｏｎＳｈａｐｅに既に入っていることを発見し、したがって、線セグメントＤＩとＤＪ（それぞれ、要素４４２、４４４）の両方が同一の形状（三角形ＩＤＪ、要素４４０）に属するため、スキャナは、ｏｎＳｈａｐｅから線セグメントＤＪ（要素４４４）の点Ｄ（要素４２４）を除去する。
【００８８】
基準線Ｘ２（要素４１４）を処理することは、頂点Ｅ（要素４２６）における横断点、すなわち、線セグメントＢＨ（要素４３８）の横断点をもたらす。スキャナは、ｉｎＳｈａｐｅ（点Ｃ、要素４２０）において形状（長方形ＡＢＨＦ、要素４２２）を見出し、このことは、ｉｎＳｈａｐｅ状態が長方形ＡＢＨＦ（要素４２２）「内部」にあり、次に、長方形ＡＢＨＦ（要素４２２）の「外部」に変化することを意味し、したがって、スキャナは、ｉｎＳｈａｐｅから点Ｃ（要素４２０）を除去する。次に、ｏｎＳｈａｐｅコレクションは、空であり、したがって、点Ｃ（要素４２０）は、交差点とならない。
【００８９】
基準線Ｘ３
【００９０】
図４に例示されるとおり、方法（またはシステム）１０００は、基準線Ｘ３（要素４１６）を処理し得る。段階２．１（横断点を決定すること）において、図４の処理は、基準線Ｘ３（要素４１６）に関して合計で７つの横断点、頂点Ｆ（要素４５０）における２つの横断点、頂点Ｇ（要素４５２）における横断点、頂点Ｈ（要素４５４）における２つの横断点、および頂点Ｉ（要素４５８）における２つの横断点をもたらす。段階２．２（交差を決定すること）において、図４の処理は、２つの多角形交差、すなわち、それぞれ、頂点Ｇ（要素４５２）および頂点Ｈ（要素４５４）をもたらす。
【００９１】
基準線Ｘ３（要素４１６）を処理することは、頂点Ｆ（要素４５０）における２つの横断点、すなわち、線セグメントＡＦおよびＦＨ（それぞれ、要素４３６および４５６）の端点をもたらす。スキャナは、接触タイプを有する線セグメントＡＦ（要素４３６）の点Ｆ（要素４５０）を、線セグメントＦＨ（要素４５６）の点Ｆ（要素４５０）が、接触横断タイプと比べて、より高い優先度である合致横断タイプを有するため、無視する。スキャナは、線セグメントＦＨ（要素４５６）の点Ｆ（要素４５０）をｏｎＳｈａｐｅコレクションに追加する。すなわち、点Ｈ（要素４５４）が到達されるまで基準線Ｘ３（要素４１６）上でＦ（要素４５０）に合致する点（要素４５２および４５４）が、交差（本明細書において「交差点」としても知られる）である。
【００９２】
基準線Ｘ３（要素４１６）を処理することは、線セグメントＤＪ（要素４４４）の頂点Ｇ（要素４５２）における横断点をもたらす。スキャナは、ｏｎＳｈａｐｅコレクションが空ではないため、頂点Ｇ（要素４５２）を交差点として認識する。次に、スキャナは、スキャナが、ＩＤＪ三角形（要素４４０）に入るように基準線Ｘ３（要素４１６）に沿ってスキャンするため、ｉｎＳｈａｐｅコレクション（三角形ＩＤＪに関して、要素４４０）に頂点Ｇ（要素４５２）を追加する。次に、頂点Ｉ（要素４５８）に関する横断点が到達されるまで、ＩＤＪ三角形（要素４４０）に属さない他の横断点が交差（すなわち、要素４５２および４５４）となる。
【００９３】
基準線Ｘ３（要素４１６）を処理することは、頂点Ｈ（要素４５４）の２つの横断点、すなわち、ＢＨ線セグメント（要素４３８）の端点、およびＦＨ線セグメント（要素４５６）の端点をもたらす。スキャナは、接触横断タイプを有する線セグメントＢＨ（要素４３８）の点Ｈ（要素４５４）を、合致横断タイプのＦＨ線セグメント（要素４５６）に属するより高い優先度の点Ｈ（要素４５４）が存在するため、無視する。点Ｈ（要素４５４）は、ｉｎＳｈａｐｅコレクションが、形状ＩＤＪ（要素４４０）に属する点Ｇ（要素４５２）を含むため、交差点である。スキャナは、点Ｈ（要素４５４）が合致横断タイプのＦＨ線セグメント（要素４５６）の終了にあるため、ｏｎＳｈａｐｅコレクションから点Ｈ（要素４５４）を除去する。
【００９４】
基準線Ｘ３（要素４１６）を処理することは、頂点Ｉ（要素４５８）の２つの横断点、すなわち、ＤＩ線セグメント（要素４４２）の端点、およびＩＪ線セグメント（要素４６０）の端点をもたらす。スキャナは、ｉｎＳｈａｐｅコレクション（点Ｇ、要素４５２に関連付けられた）における三角形形状ＩＤＪ（要素４４０）を見出し、ｉｎＳｈａｐｅコレクションからＧ（要素４５２）を除去する。ｏｎＳｈａｐｅコレクションは、空であり、したがって、点Ｉ（要素４５８）は、交差点ではない。
【００９５】
基準線Ｘ４
【００９６】
図４に例示されるとおり、方法（またはシステム）１０００は、基準線Ｘ４（要素４１８）を処理し得る。段階２．１（横断点を処理すること）において、図４の処理は、基準線Ｘ４（要素４１８）に関する合計で２つの横断点、すなわち、線セグメントＤＪおよびＩＪ（それぞれ、要素４４４および４６０）の端点をもたらす。段階２．２（交差を決定すること）において、図４の処理は、多角形交差をまったくもたらさない。
【００９７】
スキャナは、線セグメントＤＪ（要素４４４）の点Ｊ（要素４６２）をｉｎＳｈａｐｅコレクションに追加し、次の点（線セグメントＩＪ、要素４６０の点Ｊ、要素４６２）が、両方の線セグメントＤＪ（要素４４４）とＩＪ（要素４６０）に関する同一の形状（三角形ＩＤＪ、要素４４０）に属するため、ｉｎＳｈａｐｅコレクションから点Ｊ（要素４６２）を除去する。ｏｎＳｈａｐｅコレクションは、空であり、したがって、点Ｊ（要素４６２）は、交差点ではない。
【００９８】
段階３  基準線収集（好ましくは、順次であるが、そのように制限されない）
【００９９】
いくつかの実施形態において、方法（またはシステム）１０００は、１つまたは複数の交差点を含み得る結果を収集し得る。
【０１００】
結果収集のための疑似コードが、以下のとおり例４に例示される。
例４
【０１０１】
【表４】
2018185812.tif 000007
【０１０２】
図４に例示されるとおり、いくつかの実施形態によれば、例４の疑似コードを適用することによって、方法（またはシステム）１０００は、以下の３つの交差点（１）長方形ＡＢＨＦ（図４の要素４２２）の内部の三角形ＩＤＪ（図４の要素４４０）の頂点Ｄ（図４の要素４２４）、（２）三角形ＩＤＪ（図４の要素４４０）および長方形ＡＢＨＦ（図４の要素４２２）の辺と交差する頂点Ｇ（図４の要素４５２）、ならびに（３）三角形ＩＤＪ（図４の要素４４０）の内部の長方形ＡＢＨＦ（図４の要素４２２）の頂点Ｈ（図４の要素４５４）のうちの１つまたは複数をもたらし（例えば、生成し）得る。
【０１０３】
いくつかの実施形態によれば、点Ｋ（図４の要素４７０）は、点Ｋ（図４の要素４７０）が基準線に属さないため、好ましくは、結果収集に含められず、好ましくは、アルゴリズムによって発見されることもない。しかし、方法（またはシステム）１０００は、そのように制限されない。いくつかの実施形態によれば、点Ｋ（図４の要素４７０）のような点が関心の対象である場合、結果は、交差するセグメントに関して照会されてよく、かつそのような点（点Ｋ、要素４７０のような）が計算されてよい。
【０１０４】
段階４  結果の後処理（並列または順次）
【０１０５】
いくつかの実施形態によれば、方法（またはシステム）１０００は、当業者に知られている任意のアプローチを使用して、収集された結果を後処理してよい。
【０１０６】
図５は、いくつかの実施形態による、複数の２次元（２Ｄ）現実世界形状の間の交差を決定するためのコンピュータネットワーク（もしくはシステム）１０００または類似したデジタル処理環境を例示する。クライアントコンピュータデバイス５０およびサーバコンピュータ６０が、アプリケーションプログラムおよび類するものを実行する処理デバイス、ストレージデバイス、および入出力デバイスを提供する。クライアントコンピュータデバイス５０は、通信ネットワーク７０を介して、他のクライアントデバイス／プロセス５０およびサーバコンピュータ６０を含む他のコンピューティングデバイスに結び付けられることもできる。通信ネットワーク７０は、それぞれのプロトコル（ＴＣＰ／ＩＰ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、その他）を現在、使用して互いに通信する遠隔アクセスネットワーク、グローバルネットワーク（例えば、インターネット）、コンピュータの全世界のコレクション、ローカルエリアネットワークもしくはワイドエリアネットワーク、およびゲートウェイの一部であることができる。他の電子デバイス／コンピュータネットワークアーキテクチャが適切である。
【０１０７】
クライアントコンピュータ／デバイス５０は、コンピューティングモジュール（要素５０、６０、および／または７０のうちの１つまたは複数に配置された）を用いて構成され得る。いくつかの実施形態において、ユーザは、モバイルデバイス、パーソナルコンピュータ、または制限なしに当業者に知られている任意のコンピューティングデバイスなどのユーザデバイスからサーバコンピュータ６０上で実行されるコンピューティングモジュールにアクセスしてよい。いくつかの実施形態によれば、クライアントデバイス５０およびサーバコンピュータ６０は、コンピューティングモジュールにわたって分散され得る。
【０１０８】
サーバコンピュータ６０は、２次元（２Ｄ）現実世界形状を表すデータを含むデータベースに対するアクセスを提供する（かつ／またはアクセスする）ためにクライアントデバイス５０と通信するコンピューティングモジュールとして構成され得る。サーバコンピュータ６０は、別個のサーバコンピュータでなくてよく、クラウドネットワーク７０の一部であってよい。いくつかの実施形態において、サーバコンピュータ（例えば、コンピューティングモジュール）は、クライアント５０、サーバ６０、またはネットワーク７０（例えば、グローバルコンピュータネットワーク）の上に配置されたデータに対するアクセスを許すことによって複数の２次元（２Ｄ）現実世界形状の間の交差をユーザが決定することを可能にし得る。クライアント（構成モジュール）５０は、２次元（２Ｄ）現実世界形状を表すデータをサーバ（コンピューティングモジュール）６０に戻すように、かつ／またはサーバ（コンピューティングモジュール）６０から通信し得る。いくつかの実施形態において、クライアント５０は、複数の２次元（２Ｄ）現実世界形状の間の交差を決定するためにクライアント５０上で実行しているクライアントアプリケーションまたはクライアント構成要素を含んでよく、かつクライアント５０は、対応するデータをサーバ（例えば、コンピューティングモジュール）６０に通信してよい。
【０１０９】
システム１０００のいくつかの実施形態は、複数の２次元（２Ｄ）現実世界形状の間の交差を決定するためのコンピュータシステムを含み得る。システム１０００は、複数のプロセッサ８４を含み得る。また、システム１０００は、メモリ９０を含んでもよい。メモリ９０は、（ｉ）それの上に記憶されたコンピュータコード、および／または（ｉｉ）２次元（２Ｄ）現実世界形状を表すデータを含み得る。データは、２次元（２Ｄ）現実世界形状の部分を含むセグメントを含んでよい。セグメントは、２次元（２Ｄ）現実世界形状の部分の始点頂点と終点頂点を表し得る。メモリ９０は、複数のプロセッサ８４によって実行された場合、コンピュータコード命令がコンピュータシステム１０００に、１つまたは複数の機能を実行するように構成されたコンピューティングモジュール（コンピューティングモジュールは、図５の要素５０、６０、７０、または図６の要素８２、８４、８６、９０、９２、９４、９５のいずれかに配置される、またはいずれかによって実装される）を実装することをさせ得るように複数のプロセッサ８４に動作可能に結合されてよい。コンピューティングモジュールは、複数の基準線を定義してよい。各基準線は、所与の軸に沿った頂点のうちの少なくとも１つと交差し得る。コンピューティングモジュールは、基準線に沿った２次元（２Ｄ）現実世界形状の頂点を分類することによって基準線を並列に処理してよい。コンピューティングモジュールは、分類することに基づいて、基準線に沿った２次元（２Ｄ）現実世界形状の頂点のうちのいずれかが、２次元（２Ｄ）現実世界形状のうちの別のものと交差する現実世界形状の一部であるかどうかを決定してよい。
【０１１０】
いくつかの実施形態によれば、図６は、図５のコンピュータシステム１０００におけるコンピュータ（例えば、クライアントプロセッサ／デバイス５０もしくはサーバコンピュータ６０）の例示的な内部構造の図である。各コンピュータ５０、６０は、システムバス７９を包含し、バスは、コンピュータまたは処理システムの構成要素の間のデータ転送のために使用されるハードウェア線のセットである。システムバス７９は、基本的に、要素の間で情報の転送を可能にするコンピュータシステムの異なる要素（例えば、プロセッサ、ディスクストレージ、メモリ、入出力ポート、ネットワークポート、その他）を接続する共有されるコンジットである。システムバス７９に取り付けられているのが、様々な入力デバイスおよび出力デバイス（例えば、キーボード、マウス、ディスプレイ、プリンタ、スピーカ、その他）をコンピュータ５０、６０に接続するためのＩ／Ｏデバイスインターフェース８２である。ネットワークインターフェース８６は、コンピュータが、ネットワーク（例えば、図５のネットワーク７０）に取り付けられた様々な他のデバイスに接続することを許す。メモリ９０は、いくつかの実施形態（例えば、本明細書において説明されるマルチユーザサイト、構成モジュール、および／または管理モジュールエンジン要素）を実装するのに使用されるコンピュータソフトウェア命令９２およびデータ９４のための揮発性ストレージを提供する。ディスクストレージ９５は、本開示の実施形態を実装するのに使用されるコンピュータソフトウェア命令９２およびデータ９４のための不揮発性ストレージを提供する。また、中央プロセッサユニット８４もシステムバス７９に取り付けられ、かつコンピュータ命令の実行を可能にする。
【０１１１】
一実施形態において、プロセッサルーチン９２およびデータ９４は、本発明のシステムのためのソフトウェア命令の少なくとも一部分を提供するコンピュータ可読媒体（例えば、１つまたは複数のＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭ、ディスケット、テープ、その他などのリムーバブル記憶媒体）を含むコンピュータプログラム製品（全般的に９２と称される）である。コンピュータプログラム製品９２は、当技術分野においてよく知られているとおり、任意の適切なソフトウェア設定手順によってインストールされることができる。別の実施形態において、ソフトウェア命令の少なくとも一部分が、ケーブル接続、通信接続、および／または無線接続を経由してダウンロードされてもよい。他の実施形態において、本発明のプログラムは、伝搬媒体（例えば、電磁波、赤外線波、レーザ波、音波、またはインターネットもしくは他のネットワークなどのグローバルネットワークを経由して伝搬される電波）上の伝搬される信号上に実現されたコンピュータプログラム伝搬信号製品１０７（図５の）である。そのようなキャリア媒体または信号が、本発明のルーチン／プログラム９２に関するソフトウェア命令の少なくとも一部分を提供する。
【０１１２】
代替の実施形態において、伝搬される信号は、アナログキャリア波、または伝搬される媒体上で搬送されるデジタル信号である。例えば、伝搬される信号は、グローバルネットワーク（例えば、インターネット）、遠隔通信ネットワーク、または他のネットワークを経由して伝搬されるデジタル化された信号であってよい。一実施形態において、伝搬される信号は、数ミリ秒、数秒、数分、またはより長い周期にわたってネットワークを経由してパケット内で送信されるソフトウェアアプリケーションのための命令などの、時間周期にわたって伝搬媒体を経由して伝送される信号である。別の実施形態において、コンピュータプログラム製品９２のコンピュータ可読媒体は、コンピュータプログラム伝搬信号製品に関して前述されるとおり、伝搬媒体を受信すること、および伝搬媒体において実現された伝搬される信号を識別することなどによってコンピュータシステム５０が受信し、読み取ってよい伝搬媒体である。
【０１１３】
一般的に言えば、「キャリア媒体」または一時的キャリアという用語は、前述の一時的信号、伝搬される信号、伝搬される媒体、記憶媒体、および類するものを包含する。
【０１１４】
実施形態、またはそれの態様は、ハードウェア（ハードウェア回路を含むが、これには制限されない）、ファームウェア、またはソフトウェアの形態で実装されてよい。ソフトウェアにおいて実装される場合、ソフトウェアは、プロセッサがソフトウェア、またはそれの命令のサブセットをロードすることを可能にするように構成された任意の非一時的コンピュータ可読媒体上に記憶され得る。次に、プロセッサが、命令を実行し、本明細書において説明される様態で動作する、または装置にそのような様態で動作させるようにするように構成される。
【０１１５】
さらに、ハードウェア、ファームウェア、ソフトウェア、ルーチン、または命令が、データプロセッサの或るアクションおよび／または機能を実行するものとして本明細書において説明され得る。しかし、本明細書に包含されるそのような説明は、便宜のために過ぎないこと、およびそのようなアクションは、実際、コンピューティングデバイス、プロセッサ、コントローラ、または他のデバイスがファームウェア、ソフトウェア、ルーチン、命令、その他を実行することからもたらされることを認識されたい。
【０１１６】
流れ図、ブロック図、およびネットワーク図は、より多くの、もしくはより少ない要素を含んでよく、異なるように配置されてよく、または異なるように表されてよいことを理解されたい。しかし、或る実装形態は、実施形態の実行を例示するブロック図およびネットワーク図、ならびにブロック図およびネットワーク図の数が特定の様態で実現されるべきことを規定してよいことをさらに理解されたい。
【０１１７】
したがって、さらなる実施形態が、様々なコンピュータアーキテクチャ、物理コンピュータ、仮想コンピュータ、クラウドコンピュータ、および／またはそれらの何らかの組合せにおいて実装されてもよく、このようにして、本明細書において説明されるデータプロセッサは、例示の目的でのみ意図され、実施形態の制限としては意図されない。
【０１１８】
本開示は、それの例示的な実施形態を参照して特に示され、説明されてきたものの、それらにおいて形態および詳細の様々な変更が、添付の特許請求の範囲によって包含される本開示の範囲を逸脱することなく行われ得ることが、当業者によって理解されよう。
【０１１９】
いくつかの実施形態は、挙動および／またはデータを変換すること、機能的向上を提供すること、および／または技術的問題を解決することがある１つまたは複数の技術的利点を提供し得る。いくつかの実施形態において、技術的利点（および／または機能的向上）は、既存の方法と比べて効率、精度、速度、または他の効果の向上を含み得るが、これらには制限されない。いくつかの実施形態は、それらが既存の方法の機能的欠点を克服するという点で技術的利点（および／または機能的向上）を提供する。いくつかの実施形態は、パフォーマンス向上および／またはスケーラビリティ（例えば、ＰＵの効率的使用）を含むが、これらには制限されない技術的利点を含む。いくつかの実施形態の他の技術的利点（および／または機能的向上）は、以下の照会、すなわち、交差が存在するかどうか、或るタイプの交差が存在するかどうか、１つの形状が別の形状と交差するかどうか、および／またはどのような形状が所与の形状と交差するかを含むが、これらには制限されない照会の実行に適した結果データセットの作成を含む。
【０１２０】
いくつかの実施形態によれば、他の技術的利点（および／または機能的向上）は、クエリを扱い、かつ／または少なくとも以下、すなわち、形状が別の形状と交差するかどうか、およびどのような形状が所与の形状と交差するかを決定する能力を含む。
【０１２１】
いくつかの実施形態は、データに関連付けられた複数の２次元（２Ｄ）現実世界形状の間の交差を決定することによって、２次元（２Ｄ）現実世界形状を表すデータを変換し得る。データは、２次元（２Ｄ）現実世界形状の部分を含むセグメントを含み得る。セグメントは、２次元（２Ｄ）現実世界形状の部分の始点頂点と終点頂点を表し得る。
【０１２２】
いくつかの実施形態は、複数の２次元（２Ｄ）現実世界形状の間の交差を決定することによって技術的問題を解決する（その結果、技術的効果を提供する）。既存のアプローチは、２Ｄ入力データから作成されたモデルを使用する、ブール結合（Ｂｏｏｌｅａｎ  ｕｎｉｔｅ）のような数千乃至数十万の３Ｄモデリング演算を含むことがある。既存のアプローチは、数分乃至数時間かかり、かつ無効な入力データを含んで、無効な結果をもたらすことが可能である。ワークフローは、入力を評価できない可能性がある。既存のアプローチとはまったく対照的に、本明細書において提示される実施形態は、技術的問題を解決する（その結果、技術的効果を提供する）だけでなく、いくつかの実施形態を使用してデータを検査することが、非常に大きいデータセットに対して数ミリ秒または数秒かかることがあり、かつデータが有効であるかどうか決定し得るという点で技術的利点（および／または機能的向上）も提供する。入力データを検証するという技術的利点を提供することに加えて、いくつかの実施形態は、形状の交差に関する情報を含むデータセットをもたらすだけではないという技術的利点（および／または機能的向上）を提供してもよい。
【図１】
2018185812.tif 000008
【図２】
2018185812.tif 000009
【図３】
2018185812.tif 000010
【図４】
2018185812.tif 000011
【図５】
2018185812.tif 000012
【図６】
2018185812.tif 000013