티스토리 뷰
계산 기하 알고리즘(Computational Geometry Algorithm)은 각종 기하학적 도형을 다루는 알고리즘입니다.
계산 기하의 기본 도구로는 방향과 크기의 의미를 모두 포함하는 벡터(Vector)를 자주 사용합니다.
이유는 벡터를 사용하였을 때 더 많은 계산을 빠르고 간편하게 할 수 있으며
벡터끼리의 연산인 내적과 외적을 활용하여 더 효율적으로 문제에 접근할 수 있기 때문입니다.
내적을 이용하여 두 벡터의 사이각, 두 벡터의 직각 여부, 벡터의 사영을 쉽게 구현할 수 있으며
외적을 이용하여 삼각형 또는 사각형의 면적, 두 벡터의 방향을 판별할 수 있습니다.
이 때 벡터의 방향을 판별하는 기법을 CCW(Counter-Clockwise) 알고리즘이라 하며
두 벡터의 방향이 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0을 반환하는 외적을 이용하여
점 3개의 방향성이나 두 선분의 교차 여부 확인을 쉽게 확인 할 수 있는 알고리즘입니다.
이러한 벡터들이 차례로 이루어져 있는 다각형(Polygon)에는 볼록 다각형, 오목 다각형, 단순 다각형이 있으며
볼록 다각형은 모든 내각이 180도 미만인 다각형이며 오목 다각형은 180도 넘는 내각을 갖는 다각형,
단순 다각형은 경계가 스스로를 교차하지 않는 다각형을 뜻합니다.
이러한 단순 다각형의 면적을 외적을 이용하여 구하거나 주어진 점이 단순 다각형의 내부에 있는 지,
두 볼록 다각형이 교차되어있는 지 확인 해 볼 수 있으며 다양한 알고리즘 또한 존재합니다.
추후 다각형 클리핑, 볼록껍질, 회전하는 캘리퍼스 알고리즘에 대하여 설명합니다.
기본 문제
