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

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

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

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

## アルゴリズムを理解する

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710912/181a846b-2157-f5c0-8ade-6439b38916a1.png)

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

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

```math
v = v_0 + av_1 + bv_2
``` 	

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

```math
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`」という行列式は

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

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

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

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

## アルゴリズムの実装

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

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

```elixir
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
```

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

```elixir
  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)`」の行列式がアルゴリズムの定義から取得です。

簡単ですね。

## テスト

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710912/91b92daa-ffaa-826a-21e4-8b9f89a8244d.png)

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

```elixir
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)
```

実行してみると:
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710912/09e9b640-4a4a-0360-0db6-5a10c71694d4.png)

できました!!!

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

```elixir
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`は外です。

頂点は?

```elixir

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

正常に実行されました。

全部テストは:

```elixir
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`に変更してみれば、以下のエラーが発生します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710912/459b9f3b-4c09-c652-75f0-73148449d299.png)

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

## まとめ

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

We are the Alchemists, my friends! :heart: