[알고리즘문제] 볼록 다각형의 교차 영역

Question.

 

평면상에 볼록 다각형 P가 주어져 있다.

다각형 내에 있는 임의의 두 점을 잇는 선분이 다각형 내에 완전히 속하는 다각형을 볼록 다각형이라고 한다. 그리고 변이 모두 x축이나 y축에 평행인 직사각형 Q가 있다.  문제는 P와 Q의 교차영역을 구하는 프로그램을 작성하는 것이다.

예를 들면 아래 그림과 같이P와 Q가 주어질 수 있다.

그림에서 P는 각형이며 Q는 점선으로 표시되어 있다. 두 볼록 다각형의 교차 영역은 볼록 다각형이 됨에 주의한다.

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

 

 

[입력 형식]
입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 볼록 다각형 P의 꼭지점의 수 n이 주어진다.

단, n은 3부터 1000사이이다. 둘째 줄부터 (n+1)번째 줄까지 한 줄에 하나씩 반시계 방향으로 주어지는 꼭지점의 열이 있다.

꼭지점은 x,y-좌표로 나타낸다.

마지막 줄에는 다음과 같이 4각형 Q의 왼쪽 아래 꼭지점의 좌표와 오른쪽 위 꼭지점의 좌표가 주어진다: xL, yL, xR, yR.
여기서 xL, xR은 왼쪽 아래 꼭지점, xR, yR은 오른쪽 위 꼭지점의 좌표이다. 입력되는 숫자 사이에는 공백이 있다.

[출력 형식]
출력 파일의 이름은 OUTPUT.TXT이다. 만약 교차 영역의 면적이 0이면 첫째 줄에 0을 출력한다. 그렇지 않으면 첫째 줄부터 교차 영역을 입력 다각형 P와 같은 형식으로 출력한다.

 

 

 

 

 

Answer.

 

크게 3가지의 경우로 분류하여 계산.

 

1) 직사각형이 다각형에 포함되는 경우
2) 직사각형과 다각형이 서로 만나지 않는 경우
    2-1) 다각형 내에 직사각형이 포함되는 경우
    2-2) 다각형과 직사각형이 떨어져 있는 경우
3) 두 도형이 겹치는 경우

 

1) 위의 3가지 경우중에 가장 간단한 방법.

파일로부터 입력받은 직사각형의 꼭지점을 이용해 직사각형의 범위를 알아냅니다. 그리고 다각형의 꼭지점들이 모두 그 직사각형의 범위 내에 들어가는지 체크합니다.

2) 먼저 다각형에서 인접하지 않은 임의의 두 점을 선택하여 그 두점을 이은 선분의 중점을 구합니다. (단, 삼각형일 경우는 무게 중심을 구합니다. 꼭 무게 중심이 아니더라도 항상 삼각형 내에 포함될 수 있는 좌표 이어야 합니다.)

그 두점의 중점은 항상 다각형 내에 속하는 점(이하, 이 점을 임의점이라함)입니다. 이제 이 임의점과 직사각형과의 모든 직선의 방정식을 구합니다. 그리고, 다각형의 인접한 선분들 간의 직선의 방정식도 구합니다. 이제 임의점과 직사각형의 점(4개)로 이루어진 선분과 다각형의 인접한 선분들이 교차하는지 검사합니다. 즉 직선의 방정식들의 교점을 구하여 그 교점이 각 선분내에 포함되는지 체크합니다.

 만약 단 하나의 교점도 없다면 다각형내에 직사각형이 포함된 경우입니다. 그리고 4 개(임의점과 직사각형의 꼭지점들에 의해 생긴 직선)의 모든 직선이 다각형의 임의의 모서리와 모두 겹친다면 이는 다각형과 직사각형이 서로 떨어진 경우입니다.

3) 두 도형간의 모든 교점을 구합니다. 각 도형의 모서리에 관한 직선의 방정식을 사용하고, 그것을 연립하여 풀면 교점들을 구할 수 있습니다. (단, 모서리는 직선이 아니라 선분이기 때문에 범위에 주의하여 구합니다.) 이 교점들을 결과값에 포함시킵니다.

 

이제 위의 1)번과 2)번에서 사용한 방법을 여기서도 사용합니다. 1)번의 방법을 사용하여 직사각형 내에 포함된 다각형의 모든 꼭지점을 구합니다. 이 점들도 결과값에 포함시킵니다. 2)번의 방법을 사용하여 다각형내에 포함된 모든 직사각형의 꼭지점을 구합니다. 이 점들도 결과값에 포함시킵니다.

 이제 결과 값에는 새로 생성된 좌표 영역을 구성하는 모든 좌표가 포함되어 있습니다.

 

// 소스가 줄맞춤이 제대로 안되어 있습니다. 아래 소스 코드를 파일로도 첨부하였으니, 게시물 맨 아래 링크에서 받으시면 됩니다. 

// 코드는 C언어로 작성되었습니다.

 

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <math.h>

#define CONTAINPOLYGON 0
#define INTERSECTION   1
#define NOTCONTAIN     2

#define INPOLYGON      3
#define OUTPOLYGON     4

void SearchIntersection(); // 교점 구하기
bool CheckIntersection(double point[], double gra[], int i, int &j, double &iX, double &iY, int &crossCount); // 두 직선이 교차하는지 체크
bool CheckPolygonInRectangle(); // 직사각형내에 포함된 다각형 구하기
bool CheckRectangleInPolygon(int &containCheck); // 다각형내에 포함된 직사각형 구하기
bool CheckContainPoint(double iX, double iY, double rectX[], double rectY[], double polyX[], double polyY[]); // 직선의 방정식을 이용하여 구한 교점이 각 도형의 모서리에 포함되는지 체크 
void InputData(); // 파일 입력
void OutputData(int flag); // 파일 출력

int vertexNo; // 다각형 꼭지점의 개수
int intersectionNo; // 교점의 개수
int outPointCount = 0; // 결과값으로 가지고 있는 꼭지점의 수
int interFuncFlag = 0; // 임시 플래그 변수
double polyPoint[1000][2] = {0.0, }; // 다각형 꼭지점 저장
double rectPoint[4][2] = {0.0, }; // 직사각형 꼭지점 저장
double outputPoint[100][2] = {0.0, }; // 결과 도형 꼭지점 저장

void main()
{
 int containCheck; // 임시 플래그 변수

 InputData(); // 파일로 부터 데이터 입력

 if(CheckPolygonInRectangle() == true) // 직사각형내에 다각형이 포함
 {
  OutputData(CONTAINPOLYGON); // 결과 출력
  return;
 }

 if(CheckRectangleInPolygon(containCheck) == true) // 직사각형과 다각형이 서로 만나지 않는 경우
 {
  if(containCheck == INPOLYGON) // 다각형내에 직사각형이 포함
  {
   printf("직사각형이 다각형내에 포함됩니다.\n");
   OutputData(NOTCONTAIN); // 결과 출력
   return;
  }
  else // 다각형과 직사각형이 서로 떨어져 있음
  {
      printf("직사각형과 다각형이 서로 떨어져 있습니다. (포함관계 아님)\n");
   OutputData(NOTCONTAIN); // 결과 출력
   return;
  }
 }

 SearchIntersection(); // 두 도형이 겹치는 경우 체크

 for(int i = 0; i < outPointCount; i++) // 결과 좌표 화면에 출력
 {
  printf("(%f, %f)\n", outputPoint[i][0], outputPoint[i][1]);
 }
}

bool CheckRectangleInPolygon(int &containCheck)
{
 int crossCount = 0, i, j=0;
 double inPoly[2] = {0, 0};
 double iX = 0, iY = 0;
 double gra[2] = {0.0, };

 for(i = 0; i < 4; i++)
 {
  gra[0] = (rectPoint[i][1] - rectPoint[(i+1)%4][1]) / (rectPoint[i][0] - rectPoint[(i+1)%4][0]);

  if(CheckIntersection(rectPoint[(i+1)%4], gra, i, j, iX, iY, crossCount) == true) // 하지만, 교점이 하나라도 있다면
   return false; // 다음 단계로 넘어가야 한다.
 }

 if(vertexNo == 3) // 삼각형이라면
 {
  // 무게중심을 임의의 점으로 선택 (삼각형의 무게중심은 항상 삼각형 내에 포함된다.)
  inPoly[0] = (polyPoint[0][0] + polyPoint[1][0] + polyPoint[2][0]) / 3; 
  inPoly[1] = (polyPoint[0][1] + polyPoint[1][1] + polyPoint[2][1]) / 3;
 }
 else
 {
  // 다각형 내의 인접하지 않는 두점을 선택 (볼록 다각형에서 이 점은 항상 다각형 내에 포함된다.)
  inPoly[0] = (polyPoint[0][0] + polyPoint[2][0]) / 2;
  inPoly[1] = (polyPoint[0][1] + polyPoint[2][1]) / 2;
 }

 crossCount = 0;

 for(i = 0; i < 4; i++)
 {
  gra[0] = (rectPoint[i][1] - inPoly[1]) / (rectPoint[i][0] - inPoly[0]);

  if(CheckIntersection(inPoly, gra, i, j, iX, iY, crossCount) == true) // 직사각형의 점이 모두 다각형의 밖에 있다면
  {
//   crossCount++; // 제외
  }
  else
  {
   outputPoint[outPointCount][0] = rectPoint[i][0];
   outputPoint[outPointCount][1] = rectPoint[i][1];
   outPointCount++;
  }

 }

 if(crossCount == 0) // 다각형내에 직사각형이 포함된다.
 {
  containCheck = INPOLYGON;
  return true;
 }
 else if(crossCount >= 4) // 다각형밖에 직사각형이 있다.
 {
  containCheck = OUTPOLYGON;
  return true;
 }

 return false;
}

bool CheckPolygonInRectangle() // 사각형내에 포함된 다각형 찾기
{
 int count = 0;

 for(int i = 0; i < vertexNo; i++)
 {
  if(polyPoint[i][0] > rectPoint[0][0] && polyPoint[i][0] < rectPoint[2][0] &&
     polyPoint[i][1] > rectPoint[0][1] && polyPoint[i][1] < rectPoint[2][1])
     count++;
 }

 if(count == vertexNo) // 직사각형안에 다각형이 포함된다.
  return true;

 return false;
}

void SearchIntersection() // 교점 찾아내기
{
 int crossCount = 0, i, j=0;
 double iX, iY;
 double inPoly[2] = {0, 0};
 double gra[2] = {0.0, };

 for(i = 0; i < outPointCount; i++)
 {
  outputPoint[outPointCount][0] = 0.0;
  outputPoint[outPointCount][1] = 0.0;
 }
 outPointCount = 0;

 if(vertexNo == 3) // 삼각형이라면
 {
  // 무게중심을 임의의 점으로 선택 (삼각형의 무게중심은 항상 삼각형 내에 포함된다.)
  inPoly[0] = (polyPoint[0][0] + polyPoint[1][0] + polyPoint[2][0]) / 3; 
  inPoly[1] = (polyPoint[0][1] + polyPoint[1][1] + polyPoint[2][1]) / 3;
 }
 else
 {
  // 다각형 내의 인접하지 않는 두점을 선택 (볼록 다각형에서 이 점은 항상 다각형 내에 포함된다.)
  inPoly[0] = (polyPoint[0][0] + polyPoint[2][0]) / 2;
  inPoly[1] = (polyPoint[0][1] + polyPoint[2][1]) / 2;
 }

 for(i = 0; i < 4; i++) // 직사각형과 다각형의 교점 구하기
 {
  gra[0] = (rectPoint[i][1] - rectPoint[(i+1)%4][1]) / (rectPoint[i][0] - rectPoint[(i+1)%4][0]); // 직사각형을 이루는 어떤 선분의 기울기

  interFuncFlag = 1;

  if(CheckIntersection(rectPoint[(i+1)%4], gra, i, j, iX, iY, crossCount) == true) // 교차점이 있다면
  {
//   outputPoint[outPointCount][0] = iX; // CheckIntersection 내에서 이미 저장했음
//   outputPoint[outPointCount][1] = iY; // 한 선분에 중복되어 겹치는 선분이 있을 수 있으므로
//   outPointCount++;                    // 여기서 체크하지 않는다. 제외
  }
 }

 for(i = 0; i < 4; i++) // 다각형 내에 있는 직사각형의 점들 구하기
 {
  gra[0] = (rectPoint[i][1] - inPoly[1]) / (rectPoint[i][0] - inPoly[0]);

  interFuncFlag = 2;
  if(CheckIntersection(inPoly, gra, i, j, iX, iY, crossCount) == true)
  {
//   crossCount++; // 제외
  }
  else
  {
   if(crossCount == 2)
   {
    outputPoint[outPointCount][0] = rectPoint[i][0];
    outputPoint[outPointCount][1] = rectPoint[i][1];
    outPointCount++;
   }
  }
  crossCount = 0;
 }

 for(i = 0; i < vertexNo; i++) // 직사각형 내에 있는 다각형의 점들 구하기
 {
  if(polyPoint[i][0] > rectPoint[0][0] && polyPoint[i][0] < rectPoint[2][0] &&
     polyPoint[i][1] > rectPoint[0][1] && polyPoint[i][1] < rectPoint[2][1])
  {
     outputPoint[outPointCount][0] = polyPoint[i][0];
     outputPoint[outPointCount][1] = polyPoint[i][1];
     outPointCount++;
  }
 }

 OutputData(INTERSECTION);
}

bool CheckContainPoint(double iX, double iY, double rectP1[], double rectP2[], double polyP1[], double polyP2[])
{
 int cross = 0;

 // 두 직선의 교점 a, b가 두 선분의 내부에 포함되는지 체크한다.
 if((rectP1[0] >= rectP2[0]) && (iX >= rectP2[0] && iX <= rectP1[0]))
  cross++;
 else if((rectP1[0] < rectP2[0]) && (iX >= rectP1[0] && iX <= rectP2[0]))
  cross++;
 
 if((rectP1[1] >= rectP2[1]) && (iY >= rectP2[1] && iY <= rectP1[1]))
  cross++;
 else if((rectP1[1] < rectP2[1]) && (iY >= rectP1[1] && iY <= rectP2[1]))
  cross++;

 if((polyP1[0] >= polyP2[0]) && (iX >= polyP2[0] && iX <= polyP1[0]))
  cross++;
 else if((polyP1[0] < polyP2[0]) && (iX >= polyP1[0] && iX <= polyP2[0]))
  cross++;

 if((polyP1[1] >= polyP2[1]) && (iY >= polyP2[1] && iY <= polyP1[1]))
  cross++;
 else if((polyP1[1] < polyP2[1]) && (iY >= polyP1[1] && iY <= polyP2[1]))
  cross++;

 if(cross >= 4) // 두 선분이 겹친다면
  return true;

 return false;
}

bool CheckIntersection(double point[], double gra[], int i, int &j, double &iX, double &iY, int &crossCount)
{
 bool flag = false;

 for(j = 0; j < vertexNo; j++)
 {
  gra[1] = (polyPoint[j][1] - polyPoint[(j+1)%vertexNo][1]) / (polyPoint[j][0] - polyPoint[(j+1)%vertexNo][0]); // 다각형을 이루는 어떤 선분의 기울기

  if(gra[0] == gra[1]) // 평행이면
   continue;

  if((polyPoint[j][0] - polyPoint[(j+1)%vertexNo][0]) == 0)
   gra[1] = 0;

  if((rectPoint[i][0] - point[0]) == 0) // 직사각형의 수직부분이라면 (기울기가 무한대라 계산이 따로 필요)
  {
   iX = rectPoint[i][0];
   iY = gra[1]*iX - gra[1]*polyPoint[j][0] + polyPoint[j][1];
  }
  else if(gra[0] == 0 && gra[1] == 0) // 수직이라면
  {
   if(rectPoint[i][0] == point[0])
    iX = rectPoint[i][0];
   else if(rectPoint[i][1] == point[1])
    iY = rectPoint[i][1];

   if(polyPoint[j][0] == polyPoint[(j+1)%vertexNo][0])
    iX = polyPoint[j][0];
   else if(polyPoint[j][1] == polyPoint[(j+1)%vertexNo][1])
    iY = polyPoint[j][1];
  }
  else
  {
   iX = (gra[0]*rectPoint[i][0] - gra[1]*polyPoint[j][0] - rectPoint[i][1] + polyPoint[j][1]) / (gra[0] - gra[1]); // 두 직선의 교점의 x좌표
   iY = gra[0]*iX - gra[0]*rectPoint[i][0] + rectPoint[i][1]; // 두 직선의 교점의 y좌표
  }

  if(CheckContainPoint(iX, iY, rectPoint[i], point, polyPoint[j], polyPoint[(j+1)%vertexNo]) == true)
  { 
   if(interFuncFlag == 1)
   {
    outputPoint[outPointCount][0] = iX;
    outputPoint[outPointCount][1] = iY;
    outPointCount++;
   }

   crossCount++;
   flag = true;
  }
 }

 if(flag == true)
  return true;

 return false;
}

void InputData()
{
 FILE *fp; // 파일 포인터 개체
 int i;

 fp = fopen("Input.txt", "r"); // 읽기 모드로 파일 Input.txt을 연다.

 fscanf(fp, "%d", &vertexNo);

 for(i = 0; i < vertexNo; i++) // 다각형의 좌표 얻기
 {
  fscanf(fp, "%lf", &polyPoint[i][0]); 
  fscanf(fp, "%lf", &polyPoint[i][1]); 
 }

 for(i = 0; i < 2; i++)
 { 
  fscanf(fp, "%lf", &rectPoint[i*2][0]); // 직사각형의 두개의 꼭지점 얻기
  fscanf(fp, "%lf", &rectPoint[i*2][1]);
 }

 // 직사각형의 나머지 꼭지점 얻기
 // 대각선으로 마주보는 두개의 꼭지점을 파일로부터 얻었으므로 나머지 두개의 꼭지점은 쉽게 구할 수 있다.
 rectPoint[1][0] = rectPoint[2][0];
 rectPoint[1][1] = rectPoint[0][1]; 

 rectPoint[3][0] = rectPoint[0][0];
 rectPoint[3][1] = rectPoint[2][1];

 fclose(fp); // 파일 닫기
}

void OutputData(int flag)
{
 FILE *fp; // 파일 포인터 개체
 int i;
 fp = fopen("Output.txt", "w"); // Output.txt 파일을 쓰기 형식으로 열기

 if(flag == CONTAINPOLYGON)
 {
  fprintf(fp, "%d\n", vertexNo);
  printf("직사각형이 다각형을 포함합니다.\n");

  for(i = 0; i < vertexNo; i++)
  {
   fprintf(fp, "%lf ", polyPoint[i][0]);
   fprintf(fp, "%lf\n", polyPoint[i][1]);
  }
 }
 else if(flag == NOTCONTAIN)
 {
  fprintf(fp, "%d\n", 4);
  fprintf(fp, "%lf ", rectPoint[0][0]);
  fprintf(fp, "%lf\n", rectPoint[0][1]);
  fprintf(fp, "%lf ", rectPoint[1][0]);
  fprintf(fp, "%lf\n", rectPoint[1][1]);
  fprintf(fp, "%lf ", rectPoint[2][0]);
  fprintf(fp, "%lf\n", rectPoint[2][1]);
  fprintf(fp, "%lf ", rectPoint[3][0]);
  fprintf(fp, "%lf\n", rectPoint[3][1]);
 }
 else // INTERSECTION
 {
  fprintf(fp, "%d\n", outPointCount);
  printf("직사각형과 다각형이 겹칩니다.\n");

  for(i = 0; i < outPointCount; i++)
  {
   fprintf(fp, "%lf ", outputPoint[i][0]);
   fprintf(fp, "%lf\n", outputPoint[i][1]);
  }
 }

 printf("결과는 Output.txt에 출력되었습니다.\n");

 fclose(fp); // 파일 닫기
}

 

 

 

 

 

 

이 알고리즘은 다각형 내에 직사각형이 포함된 경우, 또는 서로 떨어져 있는 경우, 모두 쉽게 판별할 수 있으며, 실수 값을 입력 받고, 실수 값을 결과로 출력합니다.

시간 복잡도는 이중 루프가 있지가 종종 있지만, 외부 루프는 모두 n번(4번, 내부는 다각형의 꼭지점 개수 : n만큼 실행)만 실행되기 때문에 n의 속도에 가깝습니다. 단 복잡한 계산식이 많고, 함수 호출이 많아서 속도가 조금 느릴 수도 있는데, 실행시간은 5초를 초과하지 않습니다.

그리고 입력받은 n값에 따라 처리 성능(속도)이 O(n)의 비율로 증가합니다.

 

 

소스코드, 실행파일, 샘플Input/Output 파일 받기

 

IntersectionOfTheConvex.zip