三角形の内側判定2017年10月06日 14:07

アプリの開発中に、Polygonで描く四辺形が凹型にならないよう、移動する点が残りの3点からなる三角形の内側に入るかどうか判定しようと考えた。結局、この方法は採用しなかったが、備忘として記す。

※この目的のためには、移動する点が対角線を越えないようにすればよいのだった。

三角形の内側判定は、ゲームなどで多用されるらしく、ググってみると、ベクトルの外積を用いる方法と、3つの座標のxとyの四則演算で左回りか右回りかを判定する方法が見つかる。実装を考えると後者が簡便だが、ぱっと証明がでてこない。外積を用いる方法はエレガントだが、初等的な方法が他にないか考えてみたくなった。

P.S.
前者は重心座標を用いた方法でしょうか。

三角形の内側判定

三角形の3つの頂点をx座標の小さい順にA,B,Cと名付ける。y座標の並び順の組み合わせを考えると、6つある。

調べる点が、各辺である1次直線の上にあるか、下にあるかを調べる。3辺について、上が2つ下が1つ、か、上が1つ下が2つ、の場合に、三角形の内側にありそう。bool値の積が偽で判定できる。ところが、もう少し調べてみると、この判定法では、図中の星マークの箇所で誤判定になる。

少し手直しして、x座標の2番目の頂点Bの両側の辺については同じ方向、残りの一辺についてそれとは反対の方向、にあるとする。こうすれば、正しく判定できそう。

コード的には、頂点の並び替え、一次式の導出、上下判定、と少し込み入るが、外積を求める方が軽いのかしら。

コメント

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

※なお、送られたコメントはブログの管理者が確認するまで公開されません。

名前:
メールアドレス:
URL:
コメント:

トラックバック

このエントリのトラックバックURL: http://c5d5e5.asablo.jp/blog/2017/10/06/8695506/tb

※なお、送られたトラックバックはブログの管理者が確認するまで公開されません。