三角形の中と外の判定処理

ある座標が三角形の中と外にあるかを判定します。
計算式はGodot Engineのものを引用しています。
# Vector2とsegment_intersects_segmentの引用元コード
# https://github.com/godotengine/godot/blob/master/core/math/vector2.h
# https://github.com/godotengine/godot/blob/master/core/math/vector2.cpp
# https://github.com/godotengine/godot/blob/master/core/math/geometry_2d.h
# https://github.com/godotengine/godot/blob/master/core/math/geometry_2d.cpp

import pyxel

SCREEN_W = 256
SCREEN_H = 256


class Vector2(object):
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector2(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        if isinstance(other, (int, float)):
            return Vector2(self.x * other, self.y * other)

    def __truediv__(self, other):
        if isinstance(other, (int, float)):
            return Vector2(self.x / other, self.y / other)

    def dot(self, other):
        return self.x * other.x + self.y * other.y


def segment_intersects_segment(p_from_a, p_to_a, p_from_b, p_to_b):
    """
    線分A(p_from_a, p_to_a)と線分B(p_from_b, p_to_b)が交わるかを調べます。
    交差する場合
        Trueと交差した座標を戻します。
    交差しない場合
        FalseとNoneを戻します。
    """

    B = p_to_a - p_from_a
    C = p_from_b - p_from_a
    D = p_to_b - p_from_a

    ABlen = B.dot(B)

    if ABlen <= 0:
        return False, None

    Bn = B / ABlen
    C = Vector2(C.x * Bn.x + C.y * Bn.y, C.y * Bn.x - C.x * Bn.y)
    D = Vector2(D.x * Bn.x + D.y * Bn.y, D.y * Bn.x - D.x * Bn.y)

    if (C.y < 0 and D.y < 0) or (C.y >= 0 and D.y >= 0):
        return False, None

    ABpos = D.x + (C.x - D.x) * D.y / (D.y - C.y)

    if ABpos < 0 or ABpos > 1.0:
        return False, None

    return True, p_from_a + B * ABpos


def main():

    pyxel.init(SCREEN_W, SCREEN_H, scale=1)
    pyxel.mouse(True)

    # 三角形を構成する頂点
    vtx = [Vector2(50, 30), Vector2(180, 80), Vector2(80, 120)]
    # 三角形を構成する辺
    tri = ((0, 1), (1, 2), (2, 0))

    while True:

        pyxel.cls(0)

        # マウスの位置から、上向きと下向きの線を描きます。
        vct_mouse = Vector2(pyxel.mouse_x, pyxel.mouse_y)

        # 上向きの線（紫）
        vct_mouse_u = Vector2(pyxel.mouse_x, -1000)
        pyxel.line(vct_mouse.x, vct_mouse.y, vct_mouse_u.x, vct_mouse_u.y, 2)

        # 下向きの線（青）
        vct_mouse_d = Vector2(pyxel.mouse_x, 1000)
        pyxel.line(vct_mouse.x, vct_mouse.y, vct_mouse_d.x, vct_mouse_d.y, 5)

        # 上向きの線と三角形を構成する辺それぞれが交差しているかを調べて
        # 交差した辺の数を記録
        intersect_count_u = 0
        for fr, to in tri:
            r, intersect_pos = segment_intersects_segment(
                vtx[fr], vtx[to], vct_mouse, vct_mouse_u
            )
            if r:
                pyxel.circ(intersect_pos.x, intersect_pos.y, 3, 2)
                intersect_count_u += 1

        # 下向きの線と三角形を構成する辺それぞれが交差しているかを調べて
        # 交差した辺の数を記録
        intersect_count_d = 0
        for fr, to in tri:
            r, intersect_pos = segment_intersects_segment(
                vtx[fr], vtx[to], vct_mouse, vct_mouse_d
            )
            if r:
                pyxel.circ(intersect_pos.x, intersect_pos.y, 3, 5)
                intersect_count_d += 1

        # 三角形の描画処理
        for fr, to in tri:
            # 上向き線と三角形の辺との交差回数が一回以上 + 下向き線と三角形の辺との交差回数が一回以上
            # という条件を満たす場合、マウス座標は三角形の中にあります。
            # （三角形内の領域はどの場所でも二つの辺に挟まれた状態になります）

            if intersect_count_u > 0 and intersect_count_d > 0:
                pyxel.line(vtx[fr].x, vtx[fr].y, vtx[to].x, vtx[to].y, 7)
            else:
                pyxel.line(vtx[fr].x, vtx[fr].y, vtx[to].x, vtx[to].y, 3)

        pyxel.flip()


if __name__ == "__main__":
    main()
三角形の中と外の判定処理

関連
