도형이 오목 다각형인지 알아보기 - Concave 판단

서론

 

 도형을 크게 2가지로 분류한다면 하나는 일반적으로 볼 수 있는 볼록 다각형과 오목하게 들어가있는 오목 다각형이 있습니다. 오목 다각형의 경우 내각들 중 하나라도 180도를 넘어가는 각이 있다면 오목 다각형이 됩니다. 이를 영어로 Concave Polygon이라고 하는데 그래픽스에서 혹시나 이런 도형들이 있다면 다루기가 복잡하기 때문에 일반적인 Convex(볼록) Polygon으로 만들어줘야 합니다.

 

 그래서 이번 글에서는 혹시나 Concave Polygon이 있다고 하면 이를 어떻게 판단하는지, 어떻게 처리할 것인지 정하는 방법들을 공부한 뒤 정리해 보았습니다.

 

Concave Polygon판단하기

 위와 같은 식으로 오목 다각형이 있다고 하면 벡터들의 외적을 통해서 구분이 가능하게 됩니다. 반시계 방향으로 벡터의 방향을 지정해주면(시계방향으로도 가능) A ⇀ B, B ⇀ C, C ⇀D, D ⇀A로 총 4개의 벡터가 나오게 됩니다. 각각 번호를 E1,2,3,4 라고 지정을 해 주면 (E1 X E2), (E2 X E3), (E3 X E4), (E4 X E1)을 했을 때 부호가 다른 결과가 나오게 됩니다.

 

 이 벡터들의 외적의 부호들이 전부 같으면 이 도형은 Convex, 다르다면 Concave임을 판단할 수 있게 됩니다. 이는 벡터의 외적의 결과가 벡터들의 크기의 곱과 sinθ 의 곱으로 이루어져 있기 때문입니다.

 

 

Concave 도형 잘라서 Convex로 만들어주기

 

1. 위 결과에서 벡터를 사용하기

400

 일단 위 도형에서 벡터의 외적을 해본다면 B ⇀ C, C ⇀D의 곱 즉, E2 X E3에서 음수의 결과값이 나오게 됩니다. 이때 음수의 결과값이 나온 경우에서 좌항의 벡터를 연장해 도형을 잘라 도형을 2개로 쪼개게 됩니다.

 

 다만 이 방법 후에 다시 Concave한 부분이 있을 수 있으니 결과물들에 대해서 한번 더 Convex 인지 판단을 해 줘야 합니다.

 

 

2. Rotational 메소드

 점 하나를 원점에 두고 다음 vertex를 X 축 위에 둬서 이 축을 벗어나는 부분을 자르는 알고리즘입니다.

 

 

Convex(볼록 다각형)은 처리 과정이 너무 귀찮다

 

 위 과정만 보더라도 볼록 다각형의 경우 처리 과정이 복잡해집니다. 또한 4개 이상의 점을 가지게 되면 이게 한 평면에 있는지 알 수 없어서(non-planar인 도형) 이것까지 전부 처리하면 한 화면 내에서 오브젝트가 많아질수록 속도 저하가 심해질 것입니다.

 

 그래서 보통의 경우 도형을 전부 삼각형으로 나누어서 처리를 한다고 합니다.