소개

점군의 처리 등 실시하는 경우에, 이 판정을 실시하고 싶을 때가 있습니다. 다음과 같이 외적을 사용하는 방법이 일반적으로 알려져 있는 것 같습니다.
htps : // bg. 오. 네. jp/Fue ld_ぃght/E/9692d20174 a8045b674d14 a260 a244 a5

이번 기사에서는 역행렬을 이용하여 판정에 필요한 시간을 삭감시키고 있습니다.

이 훌륭한 방법을 생각했을 때 아무리 google 검색해도 비슷한 방법은 히트하지 않았습니다. 이것은 세기의 발견인가라고 생각했습니다만, 이하의 Python 코드를 짜 가는 중에서 여기에서 이미 제안되고 있다고 알고 텐션 내려갔습니다. 적어도 일본어로의 해설 페이지는 없는 것 같기 때문에 써 둡니다(레이 트레이싱의 해설중에 있을지도 모릅니다).

지금은 도쿄 올림픽 개최중인 오봉. 5련의 태풍이 지나가고 있습니다.

삼각형 점의 내외 판정

이론

먼저 2차원 삼각형 ABC에 점 P가 포함되는지 여부를 판단하는 방법을 설명합니다. 이후는 점명 ABCP가 아니고 벡터명 $\vec{a},\vec{b},\vec{c},\vec{p}$로 설명합니다.

$\vec{p}$는 다음과 같이 나타낼 수 있습니다.

\vec{p} = w_a\vec{a} + w_b\vec{b}

이것을 x, y성분을 명시해 표현합니다.

\begin{equation}
\begin{split}
\begin{bmatrix}
p_x \\
p_y \\
\end{bmatrix}
& = w_a
\begin{bmatrix}
a_x \\
a_y \\
\end{bmatrix}
+
w_b
\begin{bmatrix}
b_x \\
b_y \\
\end{bmatrix}
\\
& =
\begin{bmatrix}
w_a a_x + w_b b_x \\
w_a a_y + w_b b_y \\
\end{bmatrix}
\end{split}
\end{equation}

위를 변형하면 역행렬을 사용하여 $w_a, w_b$를 구하는 식으로 할 수 있습니다.

\begin{equation}
\begin{split}
\begin{bmatrix}
p_x \\
p_y \\
\end{bmatrix}
& =
\begin{bmatrix}
a_x & b_x \\
a_y & b_y \\
\end{bmatrix}
\begin{bmatrix}
w_a \\
w_b \\
\end{bmatrix}
\\
\begin{bmatrix}
w_a \\
w_b \\
\end{bmatrix}
& =
\begin{bmatrix}
a_x & b_x \\
a_y & b_y \\
\end{bmatrix}^{-1}
\begin{bmatrix}
p_x \\
p_y \\
\end{bmatrix}

\end{split}
\end{equation}

이 $w_a, w_b$가 이하의 조건을 만족하는 경우에 삼각형중에 있다고 말할 수 있습니다.

\begin{cases}
0 \leq w_a \leq 1\\
0 \leq w_b \leq 1\\
w_a+w_b \leq 1
\end{cases}

파이썬 코드

a,b,c,p는 a = np.matrix([[2],[2]])처럼 정의하고 있습니다.

def is_in_triangle(a, b, c, p):
    v_a = b - a
    v_b = c - a
    v_p = p - a
    A = np.concatenate([v_a, v_b], axis=1)
    w = np.linalg.inv(A) * v_p
    if np.all(w>=0)and np.all(w<=1) and w.sum() <= 1.0:
        return True
    else:
        return False

결과

랜덤으로 점을 발생시켜 상기 코드로 안에 있다고 판정할 수 있었을 경우는 빨강으로 점을 치고 있습니다. 코드는 이쪽

속도 비교

10만점의 처리시간은 이하였습니다. 이번에 제시한 역행렬을 사용한 방법이 1.58배 빠릅니다.


방법 이름
시간[sec]
코드 링크


외적
48.5
링크

역행렬
30.7
링크

사면체의 점의 내외 판정

이론

삼각형과 마찬가지로 크기가 하나 늘어났습니다.

\begin{bmatrix}
w_a \\
w_b \\
w_c \\
\end{bmatrix}
 =
\begin{bmatrix}
a_x & b_x & c_x \\
a_y & b_y & c_y \\
a_z & b_z & c_z \\
\end{bmatrix}^{-1}
\begin{bmatrix}
p_x \\
p_y \\
p_z \\
\end{bmatrix}

조건도 마찬가지로 다음과 같습니다.

\begin{cases}
0 \leq w_a \leq 1\\
0 \leq w_b \leq 1\\
0 \leq w_c \leq 1\\
w_a+w_b+w_c \leq 1
\end{cases}

파이썬 코드

자신도 만들었습니다. 가 속도적으로 빠르기 때문에 여기 로부터 취해 온 이하를 채용했습니다.
위와 달리 a=np.array([1,2,3])와 같이 점을 정의합니다.

def tetraCoord_Dorian(A,B,C,D):
    v1 = B-A ; v2 = C-A ; v3 = D-A
    # mat defines an affine transform from the tetrahedron to the orthogonal system
    mat = np.array((v1,v2,v3)).T
    # The inverse matrix does the opposite (from orthogonal to tetrahedron)
    M1 = np.linalg.inv(mat)
    return(M1) 

def pointInside_Dorian(v1,v2,v3,v4,p):
    # Find the transform matrix from orthogonal to tetrahedron system
    M1=tetraCoord_Dorian(v1,v2,v3,v4)
    # apply the transform to P
    newp = M1.dot(p-v1)
    # perform test
    return (np.all(newp>=0) and np.all(newp <=1) and np.sum(newp)<=1)

결과

랜덤으로 점을 발생시켜 상기 코드로 안에 있다고 판정할 수 있었을 경우는 빨강으로 점을 치고 있습니다. 코드는 이쪽

끝에

역행렬 사용하고 있기 때문에, 정규가 아닌 경우 에러가 되므로 예외 처리 필요합니다. 애초에 면적·체적이 0인 삐샹코나형 같은 경우에 그렇게 되므로 신경 쓸 필요 없을지도 모릅니다만.

참고

h tps : // s t c ゔ ぇ rf ぉ w. 코m/아/61703017
htps //w w. 요츠베. 이 m/와 tch? v = 히 gJ 3x4가 & st = PLJRW 개 2MT2 우에시 ぇ Z 9 PFvMQW9 오쥬아 l & 가 x = 1