두 선분간의 거리 구하기

알고리즘 카테고리를 새로 만들었는데요. ㅎㅎ

 

특별한 것은 아니고, 예전에 학교 다니면서 구현했던 간단한 알고리즘 소스에 대해 공유하려고 합니다.

물론 학교 다닐 때 말고, 새로 습득한 알고리즘 이론이라던지, 기술 등도 종종 올릴 예정입니다.

 

-----------------------------------------------------------------------------------------------------------------------

이번에는 두 선분간의 거리를 계산하여 출력해 주는 알고리즘입니다.

 

소스 파일로는 줄 맞춤이 잘 되어 있는데, 코드를 붙여넣기 하니, 줄이 잘 안맞는 것 같네요.ㅎㅎ

소스 파일도 별도로 첨부하였으니, 바로 아래에서 내려 받으셔도 됩니다.

 

- 소스 파일 받기 -

 

segment.cpp

 

 

구현 언어 : C언어

 

 

}
#include <conio.h> // getch()
#include <math.h> // sqrt(), fabs(), pow()
#include <stdlib.h> // exit()

 

#define CHECK_FOUR true
#define CHECK_TWO false

 

float data[4][2] = {0.0, }; // 선분 2개를 표현하기 위해 사용된 좌표값 4개
double gra[2]; // 두 선분의 각각의 기울기

 

void InputData(); // 데이터 입력
void OutputData(double result); // 데이터 출력 (프로그램 종료 함수 포함)
bool CheckContainPoint(double a, double b); // 두 직선의 교점이 두 선분내에 포함되는지를 체크하여 두 선분이 겹치는지 알아본다.
bool CheckCalculatePoint(int a, int b, double gra); // 두 직선의 교점을 구한다. (세번째 경우에만 사용)
bool CheckPointOnTheLine(double a, double b); // 최단 거리를 구성하는 점이 선분내에 포함되는지 체크

 

void main()
{

 InputData(); // 데이터 입력 받기

 

 double a, b; // 교점
 double d = 99999999.0; // 거리 (결과값)
 double distance[4]; // 최단거리의 4가지 경우 수 저장

 gra[0] = (data[1][1] - data[0][1]) / (data[1][0] - data[0][0]); // 첫번째 선분 기울기 구하기
 gra[1] = (data[3][1] - data[2][1]) / (data[3][0] - data[2][0]); // 두번째 선분 기울기 구하기

 

 /* 첫번째 경우 (두 선분이 평행) */
 if(gra[0] == gra[1]) // 두 선분이 평행인 경우
 {
  // 평행한 두직선의 거리 체크 (직선 밖의 점에서 직선에 이르는 거리)
  // 두 직선이 평행하다면 한 직선에 포함된 임의의 점과 다른 직선에 이르는 거리는 항상 같다.
  // 단, 두 직선이 같은 선상에 있을 때는 이를 따로 체크하여 거리를 구한다.
  if(data[0][1] == data[2][1]) // 두 직선이 같은 y좌표 선상에 있을때
  {
   a = fabs(data[0][0] - data[3][0]); // x좌표간의 거리 첫번째
   b = fabs(data[1][0] - data[2][0]); // x좌표간의 거리 두번째

   if(a > b) d = b; // 두개의 거리중에 짧은 것을 선택한다.
   else      d = a;

   OutputData(d);
  }
  else if(data[0][0] == data[2][0]) // 두 직선이 같은 x좌표 선상에 있을때
  {
   a = fabs(data[0][1] - data[3][1]); // y좌표간의 거리 첫번째
   b = fabs(data[1][1] - data[2][1]); // y좌표간의 거리 두번째

   if(a > b) d = b; // 두개의 거리중에 짧은 것을 선택한다.
   else      d = a;

   OutputData(d);
  }
  else
  {
   d = (gra[0]*data[2][0] + (-1)*data[2][1] - gra[0]*data[0][0] + data[0][1]) / sqrt(gra[0]*gra[0] + (-1)*(-1));
   OutputData(d); // 결과값(거리) 출력
  }
 }

 /* 두번째 경우 (두 선분이 교차) */
 if(gra[0] != 0 && gra[0] != 0) // 두 선분(또는 직선도 가능)의 기울기가 0이라면 x=@, y=@ 인 선분
 {
  a = (gra[0]*data[0][0] - gra[1]*data[2][0] - data[0][1] + data[2][1]) / (gra[0] - gra[1]); // 두 직선의 교점의 x좌표
  b = gra[0]*a - gra[0]*data[0][0] + data[0][1]; // 두 직선의 교점의 y좌표

  if(CheckContainPoint(a, b) != true) // 두 직선이 겹치는가? (겹친다면 직선을 선분으로 제한했을 때에도 겹치는지 체크)
   OutputData(0.0); // 선분 내에서도 겹친다면 0.0을 출력
 }
 else // 두 직선이 수직으로 교차한다면 (단 각 선분의 기울기는 0), 기울기가 0이 아니고, 수직인 경우는 위의 if문에서 체크됨.
 {
  // 아래의 a와 b는 두 선분이 반드시 수직이므로 겹쳐져 저장되는 경우는 없다.
  // 아래 두개의 if, else if문을 거치면, 자동으로 (a, b)는 두 직선은 교차한다.
  if(data[0][0] == data[1][0]) // 첫번째 선분이 x 축에 평행하다면
   a = data[0][0];
  else if(data[0][1] == data[1][1]) // 첫번째 선분이 y축에 평행하다면
   b = data[0][1];

  if(data[2][0] == data[3][0]) // 두번째 선분이 x 축에 평행하다면
   a = data[2][0];
  else if(data[2][1] == data[3][1]) // 두번째 선분이 y축에 평행하다면
   b = data[2][1];

  if(CheckContainPoint(a, b) != true) // 두 직선이 겹치는가? (겹친다면 직선을 선분으로 제한했을 때에도 겹치는지 체크)
   OutputData(0.0); // 선분 내에서도 겹친다면 0.0을 출력
 }

 /* 세번째 경우 (그 이외의 경우) */
 // 직선 밖의 점에서 직선에 이르는 거리를 구하는 공식을 사용
 // 각 선분의 양 끝점과 다른 선분(직선으로 인식)과의 거리를 구한다. 총 4가지 경우가 가능
 // fabs() : 실수의 절대값을 취하는 함수
 distance[0] = fabs((gra[0]*data[2][0] + (-1)*data[2][1] - gra[0]*data[0][0] + data[0][1])) / sqrt(gra[0]*gra[0] + (-1)*(-1));
 distance[1] = fabs((gra[0]*data[3][0] + (-1)*data[3][1] - gra[0]*data[0][0] + data[0][1])) / sqrt(gra[0]*gra[0] + (-1)*(-1));
 distance[2] = fabs((gra[1]*data[0][0] + (-1)*data[0][1] - gra[1]*data[2][0] + data[2][1])) / sqrt(gra[1]*gra[1] + (-1)*(-1));
 distance[3] = fabs((gra[1]*data[1][0] + (-1)*data[1][1] - gra[1]*data[2][0] + data[2][1])) / sqrt(gra[1]*gra[1] + (-1)*(-1));

 if(gra[0] == -gra[1]) // 두 선분이 수직이라면 (서로 만나지는 않는다. 만나는 경우는 위의 두번째에서 이미 모두 체크되었음)]
 {
  // 두 선분이 만나지 않으면서 수직인 경우 중에는 한 선분과 겹쳐져 구해지는 거리가 발생하는 경우가 항상 2개씩 존재. 이를 제외해야 한다.
  if((distance[2] + distance[3]) == sqrt(pow((data[0][0] - data[1][0]), 2) + pow((data[0][1] - data[1][1]), 2)))
   distance[2] = distance[3] = 0;

  if((distance[0] + distance[1]) == sqrt(pow((data[2][0] - data[3][0]), 2) + pow((data[2][1] - data[3][1]), 2)))
   distance[0] = distance[1] = 0;

  for(int x = 0; x < 4; x++)
  {
   if(d > distance[x] && distance[x] != 0)
    d = distance[x];
  }

  OutputData(d);
 }

 // 위에서 구한 4가지 경우의 수 중에서 가장 작은 값을 취한다.
 // 단 직선과 점의 거리를 구하는 공식을 사용하였으므로 선분과 점의 거리를 구해야 하는 문제에서는
 // 정확하지 않은 결과값이 나올 가능성이 있다. 즉, 선분이 아닌, 직선의 방정식을 사용하여 계산하였으므로
 // 정확한 결과값보다 더 작은, 하지만 올바르지 않은 결과값이 선택될 수 있다.
 // 이를 제외시켜야 한다.
    // 가장 짧은 거리 선택, 그리고 그 짧은 거리를 나타내는 양끝점은 모두 선분 내에 포함되어야 한다. 
 if(d > distance[0] && CheckCalculatePoint(2, 0, gra[0])) 
  d = distance[0];
 if(d > distance[1] && CheckCalculatePoint(3, 0, gra[0])) 
  d = distance[1];
 if(d > distance[2] && CheckCalculatePoint(0, 2, gra[1])) 
  d = distance[2];
 if(d > distance[3] && CheckCalculatePoint(1, 2, gra[1])) 
  d = distance[3];

 // 두 직선의 최단 거리를 구한 경우, 그 최단 거리를 표시하기 위한 두 양 끝점중에 하나가 (나머지 하나는 확실하게 포함된다.)
 // 선분내에 포함되지 않는다면.. 위에서 구한 4가지 경우중에 어떠한 경우도 이러한 결과를 나타낸다면
 // 최단 거리는 각 선분의 양 끝점을 가지고 피타고라스 정리를 이용하여 거리를 계산한다.
 if(d == 99999999.0) // 위의 조건들을 만족하는 적절한 거리를 계산하지 못했다면
 {                   // 피타고라스의 정리를 이용 각 선분의 양 끝점간의 최단 거리를 구한다. 모두 4가지 경우
  distance[0] = sqrt(pow(data[0][0] - data[2][0], 2) + pow(data[0][1] - data[2][1], 2)); // pow는 제곱
  distance[1] = sqrt(pow(data[1][0] - data[2][0], 2) + pow(data[1][1] - data[2][1], 2));
  distance[2] = sqrt(pow(data[0][0] - data[3][0], 2) + pow(data[0][1] - data[3][1], 2));
  distance[3] = sqrt(pow(data[1][0] - data[3][0], 2) + pow(data[1][1] - data[3][1], 2));

  for(int x=0; x<4; x++)
  {
   if(d > distance[x])
    d = distance[x];
  }
 }
 OutputData(d); // 결과값 출력
}

 

bool CheckContainPoint(double a, double b) // 두 선분이 겹치는지 체크
{
 int cross = 0;

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

 if((data[2][0] >= data[3][0]) && (a >= data[3][0] && a <= data[2][0]))
  cross++;
 else if((data[2][0] < data[3][0]) && (a >= data[2][0] && a <= data[3][0]))
  cross++;

 if((data[2][1] >= data[3][1]) && (b >= data[3][1] && b <= data[2][1]))
  cross++;
 else if((data[2][1] < data[3][1]) && (b >= data[2][1] && b <= data[3][1]))
  cross++;

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

 return true;
}

 

bool CheckCalculatePoint(int index, int index2, double gra) // 두 직선의 교점을 구한다.
{
 double a, b;

 // 한 직선과 그에 수직인 어느 떨어져있는 한 점을 지나는 직선과의 교점이 두 선분내에 존재하는 점인지 체크
 // a, b 는 식에 의해 구해진 점이며, CheckContainPoint()를 통해 그 교점이 선분내에 존재하는지 체크하며,
 // 선분내에 존재한다면 위에서 구해진 거리값(distance[])은 유효한 값
 if(gra != 0)
 {
  a = (gra*data[index2][0] - (-gra)*data[index][0] - data[index2][1] + data[index][1]) / (gra - (-gra));
  b = gra*a - gra*data[index2][0] + data[index2][1];
 }
 else if(gra == 0 && (data[index2][0] == data[index2+1][0])) // 한 선분이 y축과 평행할 때,
 {
  a = data[index2][0];
  b = data[index][1];
 }
 else if(gra == 0 && (data[index2][1] == data[index2+1][1])) // 한 선분이 x축과 평행할 때,
 {
  a = data[index][0];
  b = data[index2][1];
 } 

 if(CheckPointOnTheLine(a, b) == true) // 선분내에 존재하는 교점이라면 유효한 거리이므로
  return true; // true 리턴

 return false; // 선분내에 포함되지 않는 점과 거리가 계산된 경우라면 false 리턴 (유효하지 않은 값)
}

 

bool CheckPointOnTheLine(double a, double b) // 교점이 선분내에 존재하는지 체크
{
 int cross = 0;

 if((gra[0]*a - gra[0]*data[0][0] + data[0][1] - b) == 0.0) // 교점이 선분내에 존재하는 점이라면 (교점의 점을 직선의 방정식에 대입하여 만족하는지 체크)
 {
  if((data[0][0] >= data[1][0]) && (a >= data[1][0] && a <= data[0][0]))
   cross++;
  else if((data[0][0] < data[1][0]) && (a >= data[0][0] && a <= data[1][0]))
   cross++;
 
  if((data[0][1] >= data[1][1]) && (b >= data[1][1] && b <= data[0][1]))
   cross++;
  else if((data[0][1] < data[1][1]) && (b >= data[0][1] && b <= data[1][1]))
   cross++;

  if(cross == 2)
   return true;
  else
   return false;
 }
 else if((gra[1]*a - gra[1]*data[2][0] + data[2][1] - b) == 0.0) // 교점이 선분내에 존재하는 점이라면
 {
  if((data[2][0] >= data[3][0]) && (a >= data[2][0] && a <= data[3][0]))
   cross++;
  else if((data[2][0] < data[3][0]) && (a >= data[2][0] && a <= data[3][0]))
   cross++;
 
  if((data[2][1] >= data[3][1]) && (b >= data[3][1] && b <= data[2][1]))
   cross++;
  else if((data[2][1] < data[3][1]) && (b >= data[2][1] && b <= data[3][1]))
   cross++;

  if(cross == 2)
   return true;
  else
   return false;
 }

 return false;
}

 

void InputData() // 파일로 부터 입력받기
{
 FILE *fp; // 파일 포인터 개체
 int i,j;

 fp = fopen("input.txt", "r"); // 파일 열기

 for(i = 0; i < 4; i++) // 데이터 얻어오기
  for(j = 0; j < 2; j++)
   fscanf(fp, "%f", &data[i][j]);

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

 

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

 printf("Result : %f (결과는 Output.txt에도 출력되었습니다.)\n", result);
 fprintf(fp, "%f\n", result); // 파일에 결과 출력

 fclose(fp); // 파일 닫기

 exit(0);
} 

 

 

선분의 거리를 체크하는 방법에 있어서 크게 3가지의 경우로 분류하였으며, 또한 특정 케이스에 따라서 정상적으로 처리될 수 있도록 다음과 같이 분기 처리하였습니다.

 

1) 두 선분이 평행한 경우
    1-1) 다른 선상에서 평행한 경우
    1-2) 같은 선상에서 평행한 경우

 

2) 두 선분이 만나는 경우
    2-1) 최소한 하나 이상의 선분의 기울기가 0이 아닌 상태에서 만나는 경우
     즉, 2-2)를 제외한 만나는 경우의 모든 경우 
    2-2) 두 선분의 기울기가 모두 0, 즉 수직으로 두 선분이 만나는 경우

3) 위의 경우가 아닌 경우, 즉, 두 선분이 평행하지도 않고, 만나지도 않는 경우
    3-1) 두 선분이 서로 수직이지만, 만나지 않는 경우
    3-2) 두 선분이 떨어져 있는 경우, 단 x축 또는 y축으로 하나의 선분을 이동했을 경우, 다른 선분과 만나는 경우
    3-3) 두 선분이 떨어져 있는 경우, 단 x축 또는 y축으로 하나의 선분을 이동하더라도 다른 선분과 만나지 않는 경우
    3-4) 기타 세부적인 예외의 경우 체크

 

 

Input 파일의 정보를 읽어들여 연산 후, 결과를 화면과 파일로 출력합니다.

 

 

Microsoft Visual Studio 6.0으로 개발되었습니다.

기본 C언어로 개발되었기 때문에 C언어 컴파일 가능한 툴이라면 다른 환경에서도 컴파일 가능할 것이라 생각됩니다.