Polygon(다각형)

다각형

종류

1. 볼록 다각형(Convex Polygon): 모든 내각이 180도 미만인 다각형
2. 오목 다각형(Concave Polygon): 180도가 넘는 내각을 갖는 다각형
3. 단순 다각형(Simple Polygon): 다각형의 경계가 스스로를 교차하지 않는 다각형

볼록 다각형의 특별한 성질

1. 볼록 다각형 내부의 임의의 두 점을 연결하는 선분은 볼록 다각형의 테두리를 절대 교차하지 않는다.
2. 두 볼록 다각형의 교집합은 항상 볼록 다각형
   • 이 성질을 이용하여 많은 다각형 문제를 증명, 해결 가능

다각형 구현

• 컴퓨터 프로그래밍을 위함
• 다각형의 꼭지점을 나타내는 점들의 리스트로 표현 (po, p1, …, pn-1)

다각형 면적 구하기

• 다각형 P가 n개의 정점들을 반시계 방향으로 나열해서 p0, p1, … pn-1로 주어짐
  1. 볼록 다각형
  • 다각형 내부의 한 점 q를 잡아 q와 인접한 두 정점들로 이루어진 삼각형들로 분리
  • 삼각형의 면적은 벡터의 외적으로 구한 후, 다 합해준다.
    
    

1. 오목 다각형
   • 평면 상의 임의의 점 q(다각형 내부/외부 무관)를 잡아 q와 다각형의 인접한 두 정점 pi와 p(i+1)%n를 꼭지점으로 갖는 삼각형의 넓이 생각
   • 넓이 = (pi-q) x (p(i+1)%n-q) / 2
   • 위 넓이는 q, pi, p(i+1)%n이 좌회전할 때는 양수, 우회전할 때는 음수
   • 따라서 모든 삼각형들의 합을 하면 다각형의 내부 면적 구할 수 있다.
   • 아래 그림에서, 정점 p0, p1, …, p4에서의 삼각형 넓이는 양수, 정점 p4, p5, …, p0에서는 음수
     
     

    double area(Polygon p, int n) {
    int ret = 0, j;
    for (int i = 0; i < n; i++) {
        j = (i + 1) % n;
        ret = ret + (p[i].x * p[j].y - p[i].y * p[j].x);
    }
    return abs(ret) / 2.0;
   }
   

다각형 포함 문제

• 다각형 P와 점 q가 주어졌을 때, q가 P의 내부에 위치하는지 검사

  Crossing Count

• q를 지나는 반직선 R과 P의 경계선과의 교차점의 수가
  • 홀수: q는 P 내부
  • 짝수: q는 P 외부

    예외 상황

1. 반직선이 정점을 지나는 경우
2. 반직선이 에지를 지나는 경우

3. 점 q가 P의 경계선에 있는 경우

   
   

해결 방안

• 1, 2번의 경우, 반직선 R과 교차하는 에지에 대해서, 에지의 한 쪽 끝점이 R에 위치하면 다른 쪽 끝점이 R의 아래쪽에 있는 경우만 교차점으로 인정
  • 교차점 인정
    
  • 교차점 불인정
    
• 3번의 경우 q가 P의 각 에지에 위치하는 지 검사

bool  insidePolygon(Point q, Polygon P, int n) {
	int crossings = 0, j;
	Point origin = { 0,0 }; // 원점

	//q가 원점에 오도록 다각형 이동, 반직선은 양의 x축
	for (int i = 0; i < n; i++) {
		P[i].x = P[i].x - q.x;
		P[i].y = P[i].y - q.y;
	}
	for (int i = 0; i < n; i++) {
		j = (i + 1) % n;
		if (between(P[i], P[j], origin)) return false; //q가 P의 에지 위에 존재
	}

	if (P[i].y < 0 && P[j].y >= 0 && leftTurn(P[i], P[j].origin) ||
		P[j].y < 0 && P[i].y >= 0 && leftTurn(P[j], P[i].origin))
		crossings++;

	if (crossings % 2) return true;
	return false;

}