コンテンツにスキップ

多角形内外判定

内外判定

Shaderの場合、対象のuv座標の範囲内外判定から領域内の塗りつぶしが可能

Crossing Number Algorithm

交差した回数が奇数であれば内側

Winding Number Algorithm

各頂点間に対する角度の合計をとり、1周以上であれば内側

範囲を定義する多角形の各頂点のインデックスを0,1,2,3と定義した場合について(四角形)、各辺の番号を01,12,23,30とおく

この各辺をこの頂点順序でfrom,toとし、判定対象の座標からそれぞれへのベクトル\(\vec{a}\),\(\vec{b}\)を定義

各辺に対して\(\vec{a}\)から\(\vec{b}\)の向きで符号付き角度を求め、総和を求める(deg or rad)

1周\(360^\circ\)(\(2\pi\))とし、合計角が1周以上である場合、判定対象座標は範囲の内側である

Info 
def is_inrange(self, range_p, p):
    """Winding Number Algorithm

    Args:
        range_p (np.ndarray)  : [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]
        p       (np.ndarray)  : [x, y]
    """

    angle: float = 0.0
    normal: np.ndarray = None
    for i in range(4):
        vfrom   = range_p[i] - p
        vto     = range_p[(i+1)%4] - p
        nfrom   = np.linalg.norm(vfrom)
        nto     = np.linalg.norm(vto)
        if nfrom==0 or nto==0:
            continue
        vfrom   = vfrom/nfrom
        vto     = vto/nfrom
        # Calculate angle
        vcos = np.clip(np.inner(vfrom, vto), -1, 1)
        theta = np.rad2deg(np.arccos(vcos))
        if normal==None:
            normal = np.cross(vfrom, vto)
        elif np.dot(np.cross(vfrom, vto), normal)<0:
            theta *= -1
        angle += theta

    return abs(angle/(360.0)) > 1

Reference

最終更新日: August 14, 2023
作成日: August 14, 2023