アルゴリズム強化月間 - 楽しいアルゴリズムの世界を紹介しよう - 三角形の内部のチェック

この記事は

「アルゴリズム強化月間 - 楽しいアルゴリズムの世界を紹介しよう -」
テーマの応援記事です。

息子はゲームプログラミングを勉強しています。その中に「オブジェクトコリジョン」の計算をゲームエンジンに任せています。でも、その計算は実際にどう動いてますか?

ゲームのオブジェクトは三角形で作成されてます。何かが当たってるかどうかと知りたい場合、点が三角形の内部を計算します。その計算は https://mathworld.wolfram.com/TriangleInterior.htmlで説明されています。アルゴリズムでできる!!!

アルゴリズムを理解する

残念ですが、以上にリンクされたアルゴリズムを日本語で見つかりませんでした。その上、この英語が数学者以外にちっと分かりにくいです。vの変数が多くて、v0は頂点で、v1とv2はベクターです。vのみは調べてるの点です。

では、vという点が三角形の内部にあるかどうかを判断するために、v0で示される頂点を利用して、v1とv2をv0頂点から他の2つの頂点へのベクトルとします。v0頂点からvの点へのベクトルをv1とv2で表すと、次のようになります。

v = v_0 + av_1 + bv_2

以上でaとbは定数です。aとbを解くとは

a	=	{det(v, v_2) - det(v_0, v_2) \over det(v_1, v_2)} \\
b	=	-{det(v, v_1) - det(v_0, v_1) \over det(v_1, v_2)}

最後に、「det」という行列式は

 det(u, v) = u \times v = u_xv_y - u_yv_x

もしaとbは0りよ大きいと、a + bは1より小さかったら、三角形の内部にあると確認することができます。

うんんんん。コリジョンのために外部の線に当たってるとも知りたいですので、「より大きい」と「より小さい」だけできなくて、「含めて」も調べたいですね。

これで、コーディングができるでしょう。

アルゴリズムの実装

Elixirで実装してみましょう。

三角形のモジュールを作成して、is_inside関数を定義します。引数は三角の3つ頂点と調べたいの点です。

defmodule Triangle do
  
  def is_inside?({v0, v1, v2}, point) do
    vec1 = vector(v0, v1)     # v0からv1へのベクターを計算する
    vec2 = vector(v0, v2)     # v0からv2へのベクターを計算する

    # aとbの定数を解く
    a = (det(point, vec2) - det(v0, vec2)) / (det(vec1, vec2))
    b = -(det(point, vec1) - det(v0, vec1)) / (det(vec1, vec2))

    # 三角形の内部にある条件
    a >= 0 && b >= 0 && a + b <= 1
  end
end

以上はアルゴリズムを実装した通りですね。残りはベクターと行列式の計算することです。

  defp vector(origin, to) do
    %{x: to.x - origin.x, y: to.y - origin.y}
  end

  defp det(u, v) do
    (u.x * v.y) - (u.y * v.x)
  end

この場合は、ベクターが2つ頂点のxの変化とyの変化です。

「det(u, v)」の行列式がアルゴリズムの定義から取得です。

簡単ですね。

テスト

この計算は正しいかどうかを確認するためにサンプルの三角を作って、試してみましょう。iex又はLiveBookで以上のTriangleモジュールをロードして、三角の頂点とあるてんを指定してis_insideを呼んでみましょう。

import ExUnit.Assertions

# 三角のそれぞれ頂点
v0 = %{x: 1, y: 7}
v1 = %{x: 4, y: 10}
v2 = %{x: 3, y: 6}

# 三角の定義
t0 = {v0, v1, v2}

# ある点
p0 = %{x: 2, y: 7}

assert Triangle.is_inside?(t0, p0)

実行してみると:

できました!!!

もっと点を試してみると:

p1 = %{x: 3, y: 8}   # in: t0, t1, t3, t4
p2 = %{x: 4, y: 5}   # in: none

assert Triangle.is_inside?(t0, p1)
refute Triangle.is_inside?(t0, p2)

はい、p1はt1の内部ですが、p2は外です。

頂点は?

assert Triangle.is_inside?(t0, v0)
assert Triangle.is_inside?(t0, v1)
assert Triangle.is_inside?(t0, v2)

正常に実行されました。

全部テストは:

import ExUnit.Assertions

# The verticies
v0 = %{x: 1, y: 7}
v1 = %{x: 4, y: 10}
v2 = %{x: 3, y: 6}
v3 = %{x: 7, y: 10}
v4 = %{x: 6, y: 4}
v5 = %{x: 10, y: 10}
v6 = %{x: 10, y: 2}
v7 = %{x: 10, y: 8}
v8 = %{x: 16, y: 2}

# The triangles
t0 = {v0, v1, v2}
t1 = {v0, v3, v2}
t2 = {v0, v5, v2}
t3 = {v0, v1, v4}
t4 = {v0, v3, v4}
t5 = {v0, v5, v4}
t6 = {v6, v7, v8}

#The points
p0 = %{x: 2, y: 7}   # in: t0 - t5
p1 = %{x: 3, y: 8}   # in: t0, t1, t3, t4
p2 = %{x: 4, y: 5}   # in: none
p3 = %{x: 6, y: 7}   # in: t4, t5
p4 = %{x: 7, y: 8}   # in: t5
p5 = %{x: 8, y: 6}   # in: none
p6 = %{x: 5, y: 9}   # in: t1, t4
p7 = %{x: 8, y: 10}  # in: none
p8 = %{x: 7, y: 6}   # in: t2, t5
p9 = %{x: 8, y: 7}   # in: none
p10 = %{x: 12, y: 4} # in: t6
p11 = %{x: 13, y: 5} # in: t6
p12 = %{x: 14, y: 6} # in: none
p13 = %{x: 12, y: 5} # in: t6
p14 = %{x: 11, y: 8} # in: none
p15 = %{x: 11, y: 6} # in: t6

# p0 = %{x: 2, y: 7}   # in: t0 - t5
assert Triangle.is_inside?(t0, p0)
assert Triangle.is_inside?(t1, p0)
assert Triangle.is_inside?(t2, p0)
assert Triangle.is_inside?(t3, p0)
assert Triangle.is_inside?(t4, p0)
assert Triangle.is_inside?(t5, p0)
refute Triangle.is_inside?(t6, p0)

# p1 = %{x: 3, y: 8}   # in: t0, t1, t3, t4
assert Triangle.is_inside?(t0, p1)
assert Triangle.is_inside?(t1, p1)
refute Triangle.is_inside?(t2, p1)
assert Triangle.is_inside?(t3, p1)
assert Triangle.is_inside?(t4, p1)
refute Triangle.is_inside?(t5, p1)
refute Triangle.is_inside?(t6, p1)

# p2 = %{x: 4, y: 5}   # in: none
refute Triangle.is_inside?(t0, p2)
refute Triangle.is_inside?(t1, p2)
refute Triangle.is_inside?(t2, p2)
refute Triangle.is_inside?(t3, p2)
refute Triangle.is_inside?(t4, p2)
refute Triangle.is_inside?(t5, p2)
refute Triangle.is_inside?(t6, p2)

# p3 = %{x: 6, y: 7}   # in: t4, t5
refute Triangle.is_inside?(t0, p3)
refute Triangle.is_inside?(t1, p3)
refute Triangle.is_inside?(t2, p3)
refute Triangle.is_inside?(t3, p3)
assert Triangle.is_inside?(t4, p3)
assert Triangle.is_inside?(t5, p3)
refute Triangle.is_inside?(t6, p3)

# p4 = %{x: 7, y: 8}   # in: t5
refute Triangle.is_inside?(t0, p4)
refute Triangle.is_inside?(t1, p4)
refute Triangle.is_inside?(t2, p4)
refute Triangle.is_inside?(t3, p4)
refute Triangle.is_inside?(t4, p4)
assert Triangle.is_inside?(t5, p4)
refute Triangle.is_inside?(t6, p4)

# p5 = %{x: 8, y: 6}   # in: none
refute Triangle.is_inside?(t0, p5)
refute Triangle.is_inside?(t1, p5)
refute Triangle.is_inside?(t2, p5)
refute Triangle.is_inside?(t3, p5)
refute Triangle.is_inside?(t4, p5)
refute Triangle.is_inside?(t5, p5)
refute Triangle.is_inside?(t6, p5)

# p6 = %{x: 5, y: 9}   # in: t1, t4
refute Triangle.is_inside?(t0, p6)
assert Triangle.is_inside?(t1, p6)
refute Triangle.is_inside?(t2, p6)
refute Triangle.is_inside?(t3, p6)
assert Triangle.is_inside?(t4, p6)
refute Triangle.is_inside?(t5, p6)
refute Triangle.is_inside?(t6, p6)

#p7 = %{x: 8, y: 10}  # in: none
refute Triangle.is_inside?(t0, p7)
refute Triangle.is_inside?(t1, p7)
refute Triangle.is_inside?(t2, p7)
refute Triangle.is_inside?(t3, p7)
refute Triangle.is_inside?(t4, p7)
refute Triangle.is_inside?(t5, p7)
refute Triangle.is_inside?(t6, p7)

# p8 = %{x: 7, y: 6}   # in: t5
refute Triangle.is_inside?(t0, p8)
refute Triangle.is_inside?(t1, p8)
refute Triangle.is_inside?(t2, p8)
refute Triangle.is_inside?(t3, p8)
refute Triangle.is_inside?(t4, p8)
assert Triangle.is_inside?(t5, p8)
refute Triangle.is_inside?(t6, p8)

# p9 = %{x: 8, y: 7}   # in: t5
refute Triangle.is_inside?(t0, p9)
refute Triangle.is_inside?(t1, p9)
refute Triangle.is_inside?(t2, p9)
refute Triangle.is_inside?(t3, p9)
refute Triangle.is_inside?(t4, p9)
assert Triangle.is_inside?(t5, p9)
refute Triangle.is_inside?(t6, p9)

# p10 = %{x: 12, y: 4} # in: t6
refute Triangle.is_inside?(t0, p10)
refute Triangle.is_inside?(t1, p10)
refute Triangle.is_inside?(t2, p10)
refute Triangle.is_inside?(t3, p10)
refute Triangle.is_inside?(t4, p10)
refute Triangle.is_inside?(t5, p10)
assert Triangle.is_inside?(t6, p10)

# p11 = %{x: 13, y: 5} # in: t6
refute Triangle.is_inside?(t0, p11)
refute Triangle.is_inside?(t1, p11)
refute Triangle.is_inside?(t2, p11)
refute Triangle.is_inside?(t3, p11)
refute Triangle.is_inside?(t4, p11)
refute Triangle.is_inside?(t5, p11)
assert Triangle.is_inside?(t6, p11)

# p12 = %{x: 14, y: 6} # in: none
refute Triangle.is_inside?(t0, p12)
refute Triangle.is_inside?(t1, p12)
refute Triangle.is_inside?(t2, p12)
refute Triangle.is_inside?(t3, p12)
refute Triangle.is_inside?(t4, p12)
refute Triangle.is_inside?(t5, p12)
refute Triangle.is_inside?(t6, p12)

# p13 = %{x: 12, y: 5} # in: t6
refute Triangle.is_inside?(t0, p13)
refute Triangle.is_inside?(t1, p13)
refute Triangle.is_inside?(t2, p13)
refute Triangle.is_inside?(t3, p13)
refute Triangle.is_inside?(t4, p13)
refute Triangle.is_inside?(t5, p13)
assert Triangle.is_inside?(t6, p13)

# p14 = %{x: 11, y: 7} # in: none
refute Triangle.is_inside?(t0, p14)
refute Triangle.is_inside?(t1, p14)
refute Triangle.is_inside?(t2, p14)
refute Triangle.is_inside?(t3, p14)
refute Triangle.is_inside?(t4, p14)
refute Triangle.is_inside?(t5, p14)
refute Triangle.is_inside?(t6, p14)

# p15 = %{x: 11, y: 6} # in: t6
refute Triangle.is_inside?(t0, p15)
refute Triangle.is_inside?(t1, p15)
refute Triangle.is_inside?(t2, p15)
refute Triangle.is_inside?(t3, p15)
refute Triangle.is_inside?(t4, p15)
refute Triangle.is_inside?(t5, p15)
assert Triangle.is_inside?(t6, p15)

# Check vertices
assert Triangle.is_inside?(t2, v5)
assert Triangle.is_inside?(t6, v6)
assert Triangle.is_inside?(t6, v7)
assert Triangle.is_inside?(t6, v8)

p1, p6, p9, p11, p15は全部先の上にあります。aとbの条件を>0と<1に変更してみれば、以下のエラーが発生します。

p1の点がv0からv1の線の上にあるので、内部ではないです。当たりの条件が線を含むか含まないでコントロールすることができます。

まとめ

ゲームプログラマーの息子にはこんなアルゴリズムがゲームエンジンに隠れされてます。以上はすごく簡単の実装ですが、最低なレベルでこんなように動いてるでしょう。

We are the Alchemists, my friends!