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

https://wondangcom.com/903

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

지난번에 반직선의 교점 찾기 위해서 기본적인 클래스를 구현해 보았는데요.

오늘은 지난번에 만들어 놓은 클래스와 함수들을 이용해서 다음의 문제를 풀어 보도록 하겠습니다.

문제 원본 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2555&sca=30d0

JUNGOL | 반직선이 만나는 경우의 수 > 문제은행

이미지 출처 : jungol.co.kr

위의 그림과 같이 반직선의 만나는 위치의 갯수가 15개인것을 찾는 문제인데요.

입력 데이터는 다음과 같이 들어 옵니다.

 

먼저 교점을 찾는 함수를 구현해 보도록 하겠습니다.

위의 함수에서 만약에 기울기가 같은 경우를 처리 했는데요.

기울기가 같은데 같은 직선이 아니라면 평행 한 것이므로 교점이 존재하지 않게 됩니다.

같은 직선에 대해서만 처리했는데요...  수직선인 경우에는 y축만 가지고 판단을 하면 되는데요...

방향이 같은 방향이라면 앞에 있는 시작점에서 만나게 되기 때문에 앞에 있는 시작점을 리턴해 주면 되고요.

방향이 반대 방향이라면 서로가 마주 보고 있는지 -> <- 아니면 <- -> 서로 다른 방향으로 진행하는지에 따라서 교점이 존재 하거나 존재하지 않게 됩니다.

마주보는 방향을 (l.y1 - r.y1 ) * l.dy < 0 으로 판단을 했는데요.

l 선분이 (0,2) -> (0,1) 로 진행을 하고 있고 r 선분은 (0.0) -> (0,1) 로 진행을 하는 선분이라고 가정을 해 보면

l.dy 는 음수값이 나오는데 l.y1 이 r.y1 보다 큰 경우이기 때문에 마주보고 있다는 것을 알 수 있겠죠.^^

수직선이 아닌 경우는 x축을 가지고 동일하게 처리해 주면 됩니다.

위의 예제는 평행이 아니므로 직선에서는 반드시 교점이 존재하게 되는데요.

이렇게 교점이 나온 경우 반직선이므로 해당 영역 내에서 만나는 부분이 있는지를 판단 해 주어야 합니다.

예를 들면 (1,1) -> (2,2) 방향으로 진행하는 직선과 (0,0) -> (1,0) 의 방향으로 진행하는 직선은 교점이(0,0) 이 나오지만 실제로는 만나지 않는데 이러한 부분을 걸러 내 주면 되는데요.

l 선분이 수직선일때 r선분이 수직선일때 아닐때 판단하는 루틴이예요.

위의 예처럼 (1,1)->(2,2) 와 (0,0) ->(1,0) 과 같은 경우

(2,2)->(3,3) 와 (2,0) -> (1,1) 과 같은 선분을 걸러 내는 경우를 생각해 보시면 위의 

    if(isVertical(l) && ( (y-l.y1) * l.dy <0)) return Point(); 

    if(isVertical(r) && ( (y-r.y1) * r.dy < 0) )return Point();

    if(!isVertical(l) && ((x-l.x1)*l.dx < 0)) return Point();

    if(!isVertical(r) && ((x-r.x1)*r.dx < 0)) return Point();

이 부분의 의미를 아실 거예요.

 

이렇게 함수를 만들었다면

마지막으로 메인에서 교점의 갯수를 세 주시면 되는데...

메인 부분은 다음과 같이 간단하게 처리 할 수가 있습니다.

cin >> N >> L;      for(int i=0;i<N;i++)     {         int x1,y1,x2,y2;         cin >> x1 >> y1 >> x2 >> y2;         line[i].init(x1,y1,x2,y2);     }       for(int i=0;i<N;i++)     {         for(int j=i+1;j<N;j++)         {             Point pt;             pt = LineIntersection(line[i],line[j]);             if(pt.p) cnt++;         }     }     cout << cnt;

 

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

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

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

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