[📚정보] 점이 다면체에 포함되는지 구하기

[vertex(4321vertex)]

1,점이 다각형에 포함되는지 구하기

위의 그림처럼 특정한 점이 다각형에 포함되어 있다면, 이때 점에서 특정한 방향으로 나아간 선분은 다각형의 모서리와 홀수번 교차하게 되요,

즉 점에서 나아간 선분이 다각형의 모서리와 짝수번 교차하거나 교차하지 않으면 점은 다각형에 포함되어 있지 않은거에요

그리고 이때 점에서 나아간 선분이 다각형의 꼭짓점을 정확히 통과하는 경우는 예외로 해야해요

그리고 이러한 알고리즘은 위의 그림처럼 볼록다각형만이 아니라 오목다각형에도 적용되어질수 있어요

https://gall.dcinside.com/mgallery/board/view/?id=game_dev&no=166039

점이 다각형에 포함되는지 구하기

그리고 해당 알고리즘에 대한 자세한 설명은 위의 글에 있어요

2. 점이 다면체에 포함되는지 구하기

그리고 동일한 원리를 xy 좌표계에서의 다각형이 아닌 xyz좌표계에서의 다면체에도 적용할수 있어요

즉 마찬가지로 특정한 점이 특정한 다면체 안에 포함된다면, 해당 점에서 특정 방향으로 나아간 직선이 다면체의 면과 홀수번 교차해야 해요,

즉 짝수번 교차하거나 교차하지 않으면 해당 점은 해당 다면체에 포함되어있지 않은거에요,

그리고 이때 점에서 나아간 선분이 다면체의 모서리나 꼭짓점을 정확히 통과하는 경우는 예외로 해야해요

그리고 이러한 알고리즘은 역시 볼록다면체뿐만이 아닌 오목다면체에도 적용되어질수 있어요

3. 한 점에서 특정 방향으로 나아가는 직선이 특정 면과 교차하는지 구하기

위의 그림처럼 특정한 점에서 특정 방향으로 나아가는 직선이 있을때

해당 직선이 특정한 꼭짓점들로 구성된 면과 교차하는지 구하려면

우선 해당 직선이 포함된 직선의 방정식을, 해당 면이 포함된 평면의 방정식에 대입해서 교점의 좌표를 구하고

그렇게 구한 직선과 평면의 교점이 해당 꼭짓점들로 구성된 면과 교차하는지,

그리고 해당 교점이 직선위에서 특정 점에서 특정 방향으로 나아가는 쪽에 있는지, 아니면 특정 방향으로 나아가는 반대 방향에 있는지를 구해야 해요

https://gall.dcinside.com/mgallery/board/view/?id=game_dev&no=214488

평면의 방정식의 활용

그리고 이때 교점의 좌표를 구하고, 해당 교점이 특정 꼭짓점으로 구성된 면에 포함되는지는 위의 글의 5번에 나와있어요

그리고 해당 교점이 직선 위에서 특정 점을 기준으로 특정 방향으로 나아가는 쪽에 있는지 그렇지 않은지를 구하려면, 직선의 방향벡터와, 직선의 특정 점에서 교점까지의 벡터를 구한 다음 둘을 내적하면 되요,

그리고 그렇게 두 벡터를 내적해서 그 값이 0보다 크면 해당 교점은 직선 위에서 특정 점을 기준으로 특정 방향으로 나아가는 쪽에 있는거고, 0보다 작으면 특정 방향으로 나아가는 반대쪽에 있는거에요

그리고 최종적으로 특정한 점이 특정한 다면체의 내부에 포함되어 있는지를 구하려면, 위의 방식을 사용해서 특정 점에서 특정 방향으로 나아가는 직선이 해당 다면체의 각각의 면들과 교차하는지를 체크해서, 홀수번 교차하는지 아니면 교차하지 않거나 짝수번 교차하는지를 체크하면 되요

[움움몽몽(install8144)]

[익명(180.233)]

관심있어서 잘 읽었다