[알고리즘문제] 다각형의 면적

다격형의 면적

 

Q.

평면상에 볼록 다각형 P가 주어져 있다. 그리고 변이 모두 x축이나 y축에 평행인 직사각형 Q가 있다. 문제는 P와 Q를 합한 다각형의 면적을 구하는 프로그램을 작성하는 것이다.   예를 들면 아래 그림과 같이 P와 Q가 주어질 수 있다. 그림에서P는 6각형이며 Q는 점선으로 표시되어 있다. 두 볼록 다각형을 합한 다각형이 항상 볼록 다각형이 되는 것이 아님에 유의한다.

 

 

 

 

 

다각형을 나타낼 때는 임의의 한 꼭지점에서 시작하여 다각형을 반시계 방향으로 따라갈 때 만나는 꼭지점의 열(sequence)로 나타낼 수 있다. 꼭지점은 x,y-좌표값으로 나타낸다. 그리고 4각형 Q를 나타내기 위해서는 왼쪽 아래 꼭지점과 오른쪽 위 꼭지점의 좌표만 있으면 충분하다.

 

입력 형식
입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 볼록 다각형P의 꼭지점의 수 n이 주어진다. 단, n은 1000이하이다. 둘째 줄부터 n+1번째 줄까지 한 줄에 하나씩 반시계 방향으로 주어지는 꼭지점의 열이 있다. 꼭지점은 x,y-좌표로 나타낸다. 마지막 줄에는 다음과 같이 4각형 Q의 왼쪽 아래 꼭지점의 좌표와 오른쪽 위 꼭지점의 좌표가 주어진다. 입력되는 숫자 사이에는 공백이 있다.

 

출력 형식
출력파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 두 다각형을 합한 다각형의 면적을 출력한다. 두 다각형의 면적의 합이 아닐 수 있음에 주의한다. 

 

 

A.

알고리즘
도형의 전체 영역을 구하는 문제로서, 각 도형을 나누어 넓이를 구한 다음에 겹치는 부분이 있을 경우, 그 부분을 제하는 방식을 사용.

 

크게 아래 4가지 경우로 나누어 처리.

 

1. 직사각형 내에 다각형이 포함되는 경우
2. 다각형 내에 직사각형이 포함되는 경우
3. 다각형과 직사각형이 떨어져 있는 경우
4. 직사각형과 다각형이 교차하는 경우

* 2,3번은 동일한 알고리즘

 

각 도형의 넓이를 구하는 방법

직사각형의 넓이 : 주어진 좌표를 이용하여 ‘가로 X 세로’ 공식을 사용하여 계산.
다각형의 넓이 : 다각형 내에 존재하는 적당한 임의의 점을 선택,  각 모서리(밑변)와 이 임의의 점으로부터 직각으로 모서리에 이르는 선분(높이)를 구하고 이를 가지고 삼각형의 넓이 공식인 ‘밑변 X 높이 X (1/2)’를 통해 다각형을 구성하는 모든 삼각형의 넓이를 구한 후, 이를 합함. (참고로 각 삼각형의 높이는 한 직선과 직선 밖의 점의 거리 구하는 공식을 사용)
교차영역의 다각형의 넓이 : 이 것도 다각형이므로 위의 다각형의 넓이 구하는 방법과 동일.

 

상세 설명
1. 직사각형 내에 다각형이 포함되는 경우
직사각형 내에 다각형이 포함되는 경우는 오직 직사각형의 넓이만 구하면 됨.

2. 다각형 내에 직사각형이 포함되는 경우 & 3. 다각형과 직사각형이 떨어져 있는 경우
이 때에는 먼저 다각형의 임의의 점을 선택한 후, 이 점과 각 직사각형의 꼭지점을 잇는 직선의 방정식과 다각형의 각 모서리의 직선의 방정식을 연립하여 교점을 구한 후, 그 교점이 각 선분 내에 포함되는지 체크. 그리하여 교차점이 4개가 발견되고, 또, 직사각형의 모서리가 다각형의 모서리와 하나도 겹치지 않는다면 이는 다각형과 직사각형이 멀리 떨어져 있는 경우로 판단하고, 이 때에는 직사각형과 다각형의 넓이를 각각 구한 후, 더해줌.
그리고 위에서 교차점이 0개가 발견되었다면 이는 직사각형이 다각형 내에 포함된 경우이므로 다각형의 넓이만 구해주면 됨. 그리고 마지막으로 1 ~ 3개가 발견되었다면 이는 직사각형과 다각형이 겹치는 경우로, 아래 3번의 방식으로 해결.

3. 직사각형과 다각형이 교차하는 경우
먼저 직사각형과 다각형의 교차점(1)을 구하고 직사각형 내에 포함되는 다각형의 꼭지점(2), 그리고 다각형 내에 포함되는 직사각형의 꼭지점(3)을 각각 구함. 위에서 구한 (1),(2),(3)의 모든 점들을 합하면 교차하는 영역의 다각형의 좌표들이 됨.

(1) 번째 경우를 구하기 위해서는 직사각형의 모서리와 다각형의 모서리를 가지고 직선의 방정식을 구한 후, 연립하여 풀면 교점을 구할 수 있음. (단, 모서리는 선분이라는 점에 유의하여 범위를 벗어나지 않도록 함.)

(2) 번째 경우를 구하는 방법은 단지 직사각형의 꼭지점들내에 다각형의 꼭지점이 포함되는지 체크하면 됨. 

(3) 번째 경우를 구하기 위해서는 먼저 다각형 내의 임의의 점을 설정하고 이 점과 직사각형의 각 꼭지점을 이용하여 직선의 방정식을 구한 후, 다각형의 모서리들과 교차점을 찾음. 교차점이 발생하지 않는다면 이는 다각형의 내부에 있는 점. (교차점이 발생했다는 것은 다각형 내의 임의의 점은 항상 다각형 내에 있으므로 직사각형의 꼭지점이 다각형의 외부에 있기 때문)

위처럼 좌표를 구했다면 위 좌표를 반시계 방향으로 정렬 (정렬을 해야만 내부의 교차 다각형의 넓이를 구할 수 있음.)

 

먼저 위에서 구한 내부 다각형(위에서 두 도형이 겹쳐져 만들어진 다각형을 내부 다각형이라 칭함)을 이루는 꼭지점 중에서 X좌표가 가장 작은 꼭지점과 가장 큰 꼭지점을 가지고, 다각형을 반으로 쪼갬. 그러면 반으로 쪼개는데 이용된 직선을 중심으로 아래쪽과 위쪽으로 좌표들이 나뉨. 나뉘어진 죄표를 임의의 리스트에 각각 저장.
그리고 각 리스트는 X좌표를 기준으로 정렬. 직선의 아래쪽에 있는 좌표 리스트는 오름차순으로, 직선의 위쪽에 있는 좌표 리스트는 내림차순으로 정렬. 그래야만 쉽게 반 시계방향으로 정렬된 좌표들을 얻을 수 있음.

첫 번째로, 새로운 리스트(Sorted List라고 칭함)에 X좌표가 가장 작은 꼭지점을 먼저 추가.
두 번째로 아래쪽의 좌표 리스트(오름 차순으로 정렬되었음)를 Sorted List에 이어서 차례로 추가.
세 번째로 X좌표가 가장 컸던 꼭지점을 Sorted List에추가.
마지막으로 위쪽의 좌표 리스트(내림 차순으로 정렬되었음)를 Sorted List에 이어서 차례로 추가.
이제 Sorted List는 내부 다각형을 구성하는 꼭지점들이 반시계방향으로 순서대로 저장됨. 이제 이 내부 다각형은 위에서 설명한 다각형의 넓이 구하는 방법대로 넓이를 구할 수 있음.
‘다각형의 넓이 + 직사각형의 넓이 – 내부다각형(교차해서 생긴)’ 이 최종 결과값.

 

소스 코드, 실행 파일, 샘플 데이터 내려 받기

 

polygon_area.zip