【第2回】点の多角形に対する内外判定｜【技業LOG】技術者が紹介するNTTPCのテクノロジー｜【公式】NTTPC
前回(と言っても一年近く経過していますね・・・。遅くなりました。)に引き続き、地図上に存在するエリアと現在地との関係性を計算機上で把握する手法の第2回目です。今回は、第3工程にあたる、「内外判定」について解説します。 現在地があるエリアの内側にいるか外側にいるかを考える場合、２次元平面上に存在する任意の点Pと多角形Tについて、点Pが多角形Tの内側にいるか外側にいるかを判定するにはどうしたらよいかを考えます。 この時、主に次の2つのアルゴリズムが利用されていることがわかりました。 Crossing Number Algorithm Winding Number Algorithm そこで、今回はこれらのアルゴリズムと実装方法(コード)について説明します。 まずはそれぞれのアルゴリズムの概要を簡単に説明します。 1.1.Crossing Number Algorithm（交差数判定）の概要 こ
点の多角形に対する内外判定
点が多角形ループの内側にあるか外側にあるかを判定するには？ 要素は２次元空間内に存在するものとします。 解説 内外判定の基本的な考え方として、「内外を判定したい点から発するレイ（ray：一条の光）を仮定し、レイが多角形の辺を何回横切るかを数え、偶数回横切るとき、点は多角形の外側、奇数回横切るとき、点は多角形の内側と判定することができる」という考え方があります。 ただ、この考え方に従って実装を行うと、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合に判定を誤ってしまう実装になることがあります。 下に示す実装では、レイをＸプラス方向に発して、多角形の辺がレイを、「上から下に横切るときには横切り回数を１引き、下から上に横切るときには横切り回数を１足すこととする」ことや、「レイの線上にある点はレイより上にあることとする」ことにより、レイに対して点接触になる点の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
