강의실/정보영재

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

https://wondangcom.com/466

 

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

위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다. 이러한 두 선분의 교차점을 검사하는 방법으로는 다음과 같이 찾아 볼수가 있습니다. 1] 각 선분에 대해서 그 선분을 포함하는 양방향으로..

wondangcom.com

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

 

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

 

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

 

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

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

 

한 직선을 방정식으로 나타내면 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

 

 

 

  • 라미드니오니 2019.06.26 19:46 신고    

    이거 너무 전문적인데요ㅠ스윽읽다 중간에 포깁니다ㅠ

  • 행복사냥이 2019.06.26 21:00 신고    

    헉...읽다가 포기했습니다.^^ 다른 분에게는 정말 소중한 정보라고 생각합니다.ㅎ

  • 연예인 2019.06.26 21:14 신고    

    찜통더위가 심각하네요 ㅠㅠ 더위 조심하시고 글 잘 읽고 갑니다~ 공감 꾸욱

  • Deborah 2019.06.26 21:39 신고    

    이거..하하하 읽어 봐도 잘 모르겠어요 ㅠㅠ

  • 잉여토기 2019.06.26 23:34 신고    

    반직선의 교점을 찾는 알고리즘 내용이군요.
    전문 영역으로 비전공자가 보기에 내용이 쉽지만은 않네요.
    이 분야를 공부하는 여러분 파이팅입니다.

  • 청결원 2019.06.27 06:28 신고    

    비오는 날이지만 좋은 하루 보내세요~
    포스팅 잘 보고 갑니다~

  • 핑구야날자 2019.06.27 06:49    

    열심히 해결 방법을 찾다 보면 도움이 많이 되는 거 같아요 오늘도 잘 보고 갑니다

  • 공수래공수거 2019.06.27 07:57 신고    

    도움이 될분들이 보시면 참 좋겠습니다.^^

  • 휴식같은 친구 2019.06.27 08:39 신고    

    수학시간에 배운 반직선의 교점을 알고리즘으로 구현ㅇ사는것이군요.
    잘 보고 갑니다.

  • 유하v 2019.06.27 12:16 신고    

    하하하하. 어려워요ㅜㅜㅋㅋㅋㅋ

  • 버블프라이스 2019.06.28 04:14 신고    

    반직선의 교점 찾기 방법, 알고리즘 관련 내용이군요? 어렵지만 참고만 하고 갑니다^^