위-아래(above-below) 기본 요소로 두 직선의 교차 여부를 판별하는 C++ 프로그램

다음은 위-아래(above-below) 원시 연산(primitive)을 활용하여 두 직선이 서로 교차하는지 판별하는 C++ 프로그램입니다. 이 기법은 한 직선이 특정 선분과 교차하는지 검사하는 데에도 활용할 수 있습니다. 판별 원리는 간단합니다. 선분의 한 끝점이 직선의 왼쪽에 있고 다른 끝점이 오른쪽에 있는 경우, 그리고 그 경우에만 두 직선은 교차합니다.

동작 원리

직선의 방정식 ax + by + c = 0에 어떤 점의 좌표를 대입하면, 결과값의 부호에 따라 그 점이 직선의 어느 쪽에 위치하는지 알 수 있습니다. 결과가 양수면 한쪽 면, 음수면 반대쪽 면에 있는 것이며, 0이면 점이 직선 위에 있습니다. 따라서 선분의 두 끝점을 대입한 결과값(Y1, Y2)의 부호가 서로 다르거나 하나가 0이라면, 선분이 직선과 교차하거나 접한다고 판단할 수 있습니다.

알고리즘

시작
    첫 번째 직선의 방정식을 생성하기 위해, 실행 시마다 rand() 함수로 x와 y의 계수에 해당하는 난수를 생성한다.
    두 번째 직선의 방정식을 생성하기 위해, 실행 시마다 rand() 함수로 x와 y의 계수에 해당하는 난수를 생성한다.
    첫 번째 직선 식에 선분의 첫 번째 끝점을 대입한 값을 Y1으로 구한다.
    if (Y1 < 0)
        선분의 두 번째 끝점을 대입한 값 Y2를 구한다.
        if (Y2 >= 0)
            "두 직선은 교차한다"고 출력한다.
        else if (Y2 < 0)
            "두 직선은 교차하지 않는다"고 출력한다.
    else if (Y1 > 0)
        선분의 두 번째 끝점을 대입한 값 Y2를 구한다.
        if (Y2 <= 0)
            "두 직선은 교차한다"고 출력한다.
        else if (Y2 > 0)
            "두 직선은 교차하지 않는다"고 출력한다.
종료

예제 코드

#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>

using namespace std;
const int L = 2;
const int H= 20;
int main(int argc, char **argv) {
   time_t s;
   time(&s);
   srand((unsigned int) s);

   int x1, x2, y1, y2;
   x1 = rand() % (H - L+ 1) + L;
   x2 = rand() % (H - L+ 1) + L;
   y1 = rand() % (H- L+ 1) + L;
   y2 = rand() % (H - L + 1) + L;

   cout << "The Equation of the 1st line is : (" << (y2 - y1) << ")x+(" << (x1 - x2) << ")y+(" << (x2 * y1 - x1 * y2) << ") = 0\n";

   int p1, p2, q1, q2;
   p1 = rand() % (H- L+ 1) + L;
   p2 = rand() % (H- L + 1) + L;
   q1 = rand() % (H - L + 1) + L;
   q2 = rand() % (H - L + 1) + L;

   cout << "The Equation of the 2nd line is : (" << (q2 - q1) << ")x+(" << (p1 - p2) << ")y+(" << (p2 * q1 - p1 * q2) << ") = 0\n";

   int Y1 = (y2 - y1) * p1 + (x1 - x2) * q1 + (x2 * y1 - x1 * y2); //Y1 segment
   if (Y1 < 0) {
      int Y2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2); //Y2 segment
   if (Y2 >= 0)
      cout << "Lines are intersecting";
   else if (Y2 < 0)
      cout << "Lines are not intersecting";
   } else if (Y1 >0) {
      int Y2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2);
      if (Y2 <= 0)
         cout << "Lines are intersecting";
      else if (Y2 >0)
         cout << "Lines are not intersecting";
   } else
      cout << "The point lies on the line";
   return 0;
}

실행 결과

The Equation of the 1st line is : (-3)x+(2)y+(1) = 0
The Equation of the 2nd line is : (-5)x+(-5)y+(130) = 0
Lines are intersecting


The Equation of the 1st line is : (-1)x+(7)y+(-15) = 0
The Equation of the 2nd line is : (-4)x+(4)y+(-8) = 0
Lines are not intersecting

첫 번째 실행에서는 두 직선의 방정식에 선분 끝점을 대입한 값의 부호가 서로 반대이므로 "Lines are intersecting(교차함)"이 출력됩니다. 반면 두 번째 실행에서는 두 끝점이 같은 쪽 면에 위치하여 "Lines are not intersecting(교차하지 않음)"이 출력됩니다. 난수를 사용하기 때문에 프로그램을 실행할 때마다 직선의 방정식과 판별 결과가 달라질 수 있습니다.