(기하알고리즘) 반직선의 교점 찾기 1

지난번에 두 선분의 교점 찾기에 대해 설명을 해 드린적이 있는데요.

https://wondangcom.com/466

기하알고리즘] 두 선분의 교차점 찾기

오늘은 반직선의 교점 찾기에 대해 설명을 해 볼까 합니다.

 

반직선은 한쪽은 막혀 있고 다른쪽 방향으로 진행을 하는 화살표를 가진 직선을 반직선이라고 합니다.

 

반직선의 교점을 찾기 위해서는 먼저 직선의 교점을 찾는 방법에 대해 확인을 해 봐야 하는데요.

 

지난번의 두선분의 교점은 시작점과 끝점이 주어졌기에 그 위치에서만 교점이 있는지 없는지를 판가름하면 되었지만...

직선에서는 방향을 가지고 계속 진행하는 것이기에 방정식을 이용한 풀이를 해 주어야 합니다.

 

한 직선을 방정식으로 나타내면 ax + by + c = 0 과 같이 나타낼 수 있습니다.

반 직선에서 시작점과 진행 방향의 두번째 점이 들어 오면 위의 방정식 형태와 같이 a,b,c 를 구해 주면 되는데요.

a,b,c를 구하는 방식은 다음과 같습니다.

 

만약 (x1,y1) 에서 시작해서 (x2,y2) 로 진행하는 반직선이 있다고 하면 

 

직선은 y = mx + c 형태로 나타낼 수 있는데요 여기서 m은 기울기가 되고 이 기울기는 (y2-y1)/(x2-x1) 이므로

a=(y2-y1), b= -(x2-x1) = (x1 - x2) 형태로 나타낼 수 있습니다.

또한 c =  -ax - by 이므로 c = -ax1 - by1 혹은 c = -ax2 - by2 로 표현이 가능합니다.

 

이러한 직선 클래스를 구현해 보면 다음과 같이 구현이 가능합니다.

 

class Line{

  int a,b,c;

  int x1,y1,x2,y2;

  int dx,dy;  //x축 간의 거리, y축 간의 거리

  void setting(int nX1,int nY1,int nX2,int nY2)

  {

    a=(nY2-nY1);

    b=(nX1-nX2);

    c=(a*nX1 + b*nY1) * -1;

    x1 = nX1;

    x2 = nX2;

    y1 = nY1;

    y2 = nY2;

    dx =  x2 - x1; //나중에 진행 방향을 알기 위해 먼저 구해 놓자. -> 이 방향이라면 +

    dy = y2 - y1;  

  }

}

 

이러한 클래스를 만들어 두면 두 직선이 들어 왔을때 기울기가 같은지 다른지 체크는 다음과 같이 할 수 있습니다.

y=a1/b1 * x + c1/b1

y=a2/b2 * x + c2/b2

에서 a1/b1 = a2/b2 가 같은지를 체크해주면 됩니다.

하지만 특성상 a1/b1 == a2/b2 와 같이 계산하면 b1 또는 b2 가 0 이 되는 경우 에러가 날 수도 있기 때문에 다음과 같이 체크해주면 됩니다.

a1 * b2 == a2 * b1

 

이렇게 기울기를 체크하는 함수를 하나 만들어 보자.

 

bool isSameSlope(Line l, Line r)

{

      return l.a * r.b == l.b * r.a;   //기울기가 같으면 true 가 리턴 된다.

}

 

이렇게 기울기가 같다면 두개의 직선이 평행선상에서 같이 가고 있는 직선인지 아니면 같은곳을 지나고 있는 직선인지 판단해야 합니다.

 

이때는 두 직선의 방정식에서 기울기가 같고 c 값이 같다면 두 직선은 같은 선상에 있는 것입니다.

 

따라서 두 직선이 같은 선상에서 진행하는 직선이라면 b1/c1 = b2/c2 이고 a1/c1 = a2/c2 인 경우입니다.

 

체크하는 함수는 다음과 같이 만들면 됩니다.

bool isSameLine(Line l,Line r)

{

   if(!isSameSlope(l,r) return false; //기울기가 다르다면 이미 같은 직선이 아니다.

   return l.a * r.c == r.a * l.c && l.b*r.c == r.b * l.c; //b1/c1 = b2/c2 이고 a1/c1 = a2/c2  인 경우

}

 

직선이 수직선인 경우 y축만 가지고 계산을 하면 되기 때문에 이 수직선 인 경우를 체크 해 줄 필요가 있는데  수직선인지 아닌지 판단은 b 값이 0 이라고 하면 그 직선은 수직선이다. x2 == x1 이라면 이 직선은 수직선이라는 의미 이다.

 

 

이렇게 한개의 직선이 수직선인지 확인하는 함수도 다음과 같이 만들어 볼 수 있습니다.

bool isVertical(Line l)

{

     return l.b ==0; //b값이 0 이면 수직선이다.

}

 

이렇게 하면 반직선의 교점을 구하는 기본적인 함수는 모두 만들어 보았습니다.

 

반직선의 교점을 구할때 교점의 위치를 리턴해야 하는데 교점이 있는지 없는지,

또는 교점이 있다면 교점의 위치를 가지고 있는 자료구조를 다음과 같이 만들어 봅니다.

 

class Point{

         bool p; //교점이 없는 경우 false;

         double x,y;

         Point(){p=false;}

         Point(double nx, double ny){p=true,x=nx,y=ny;}

}

 

교점이 없는 경우는 Point() 를 리턴하면 되고 교점이 있는 경우는 Point(x,y) 를 리턴하게 되면

위의 생성자에 의해서 p 를 이용해서 교점이 있는지 여부를 판단 할 수 있습니다.

 

다음에는 반직선의 교점을 리턴하는 함수를 만들어 보도록 하겠습니다.

 

 

 

기하알고리즘이란? https://wondangcom.com/453?category=717978

두선분의 교점 찾기 https://wondangcom.com/466

반직선의 교점찾기1 https://wondangcom.com/903

반직선의 교점찾기2  https://wondangcom.com/930