[고급개념] 컴퓨터그래픽스(기하연산, 다각형 면적과 포함, Convex Hull, Plane Sweeping)

컴퓨터 그래픽스에 관련한 고급 알고리즘들을 알아보겠다.

구현한 코드가 궁금하다면 컴퓨터그래픽스 구현 게시물을 참고!!

다음과 같은 순서로 진행된다.

• 기본 기하 연산
• 다각형 면적과 포함 계산
• 볼록 외피(Convex Hull)
• 평면 소거법(Plane Sweeping) => 직사각형 합집합의 면적
• 예시 문제
  • CCW
  • 선분 교차 2
  • 다각형의 면적
  • 지민이의 테러(다각형의 포함)
  • 볼록 껍질(외피)
  • 직사각형의 합집합(평면 소거법)

기본 기하 연산

• ccw 함수(cw : counter clockwise = 시계방향)

  • ccw(p,q) 의 경우 q벡터가 p벡터의 반시계 방향이면 양수, 시계 방향이면 음수 일직선은 0 반환

  • 또한, 벡터의 외적을 이용한 방법이다.

    

• leftTurn, rightTurn, collinear 함수 : 좌,우,일직선 검사

  • 앞에서 구현한 ccw(p,q) 함수를 통해서 왼쪽, 오른쪽, 일찍선인지 정확한 방향을 구할 수 있다.

    

• direction 함수 : 세점의 회전방향 검사에 따라서 1,-1,0 반환
  • 앞에서 본 leftTurn, rightTurn, collinear 함수 와 동일한데, 결과를 1,-1,0 으로 반환하는 차이점이 있다. (앞의 함수는 bool 타입, 현재 함수는 int 타입인 것)
    • 좌 : 1, 우 : -1, 일 : 0

1. between 함수

중간검사 즉, 점 c가 선분 (a, b) 상에 위치하는지를 검사하는 함수이다.

• 일직선 상에 없으면 false를 주고,
• 일직선 상에 있으면 수직선인지 아닌지를 판별한다.
  • 수직선이 아니면 x를 기준으로 범위 제한을 주면 되고,
  • 수직선이면 y를 기준으로 범위 제한을 주면 된다.

범위 제한을 왜주냐면 기하학에서는 좌표없이 방향으로 위치를 해결하려고 하는것이기 때문이다.

따라서 방향만 알기 때문에 직선의 범위는 무제한으로 보고, 범위 제한이 꼭 필요하다.

2. intersect(intersectProp) 함수

선분 교차 검사를 하는 함수를 구현한다.

• intersectProp 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하지 않는 경우
• intersect 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하는 경우
• 구현 로직
  • 같은 회전이 아닌 서로 반대로 회전을 했는지 확인 필요
  • 또한, 반대 선분으로도 마찬가지로 확인 필요
  • 둘다 true라면 교차한다고 판별
  • 마지막으로 intersect 함수의 경우 같은 직선상에 존재하는 두 직선의 교차도 예외적으로 처리필요
    • between 함수를 사용해서 교차 여부를 판별

다각형 면적과 포함 계산

1. 다각형 면적

말그대로 다각형의 면적을 구하는 알고리즘이다.

삼각형의 면적은 벡터의 외적으로 구하면 되는데, 여기서 q와 모든 정점들 사이의 외적값을 전부 합하게 되면 다각형 면적을 구할 수 있다.

2. 다각형 포함

점 q가 다각형 내부에 포함되어 있는지 유무를 판별하는 알고리즘이다.

기본 아이디어는 경계선과의 “교차점 수”가 홀수 or 짝수냐에 따라 내부 or 외부로 나눈다.

• 그런데, 반직선이 정점 or 에지를 지나는 경우의 예외상황이 존재한다.

• 해결 방안은 반직선이 교차하는 에지가 한 쪽 끝점이 아래쪽에 있는경우만 “교차점”으로 인정한다.

• 교차점 홀수 개면 내부점 인정

볼록 외피(Convex Hull)

볼록 외피(Convex Hull)란 주어진 점들을 모두 둘러싸는 가장 작은 볼록 다각형이다.
극단점(extreme point)이란 볼록 외피의 정점이 되는 점이다.

• Jarvis’s march 알고리즘 (복잡도 : N^2)

  • 볼록 외피의 한 극단점 𝑝를 찾는다

    • 초기 극단점을 찾을땐 제일 크거나 작은 x or y 값을 찾아서 극단점으로 사용한다.

  • 시계방향 또는 반시계 방향으로 p에 인접한 볼록 외피의 한 에지를 찾아서 볼록 외피의 다음 정점을 찾고, 다음 정점에서 이 과정을 반복하면서 블록 외피의 모든 극단점을 찾는다

    • 즉, 시계방향을 가정한다면 한바퀴 돌 동안 LeftTurn으로 제일 많이 갔을때의 값이 다음 극단점이 되는것이다.

    

• 위 함수 개선한 알고리즘 (복잡도 NlogN)

  • 그라함 스캔(Graham’s Scan) 알고리즘

    • 참고 : https://www.crocus.co.kr/1288

  • Quick Hull 알고리즘

    • 가장 왼쪽 위, 가장 오른쪽 아래 두 점을 잡고 그 선분을 이었을 때 선분과 가장 먼 거리의 점을 잡아 총 3개의 점이 생기면 그 삼각형 내부에 있는 점은 볼록 껍질 후보가 될 수 없다는 사실로 시작한다.

    

평면 소거법(Plane Sweeping)

평면소거법은 평면을 수평선 또는 수직선(sweep-line 이라 부름)으로 아래에서 위 또는 왼쪽에서 오른쪽으로 쓸어가면서 주어진 문제를 해결하는 기법이다

기본적인 아이디어는 해결하기 복잡한 2차원의 문제를 단순한 1차원의 문제로 나누어 해결하고자 하는 것이다. Sweep-line이 1차원을 표현한다.
이를 위하여 다음 두 가지의 자료 구조를 이용한다

• Event point의 순서를 결정하는 자료 구조
• Sweep-line 의 상태를 나타내는 자료 구조