티바이트

글주소: http://tibyte.kr/23


 

 ※ 아래 코드는 실행해보지 않은것입니다. 동작하지 않을 수도 있습니다.




점 2개의 좌표 정보로 표현된 선분이 2개 있을 때

충돌체크를 하는방법입니다.

퍼즐게임이나 슈팅게임, 아니면 총기를 발사하는 것을 구현할 때 유용하게 쓰일 수 있습니다.
첫번째 방법은 직선의 방정식을 이용하는 것입니다.



요약



아래와 같이 선분이 주어졌을때,



선분의 양 끝 두 점의 좌표를 알기때문에
직선의 방정식도 쉽게 나옵니다.


ax + by = c
a`x + b`y = c`
이 방정식에서 a, b, c, a`, b`, c` 만 변수에 저장해두는 형식으로
가상의(화면에 나타나지 않는) 직선이 있다고 생각하는 것입니다.



액션스크립트 geom 패키지의 Matrix 클래스를 사용하여
이원 일차방정식을 간단히 풀어낼 수 있겠죠.
즉, 위 방정식의 해가 교점의 좌표가 되는 것입니다.  



여기서 중요한 것이
구하려는 게 직선교점이 아닌 선분교점이라는 것입니다.



위와 같이 직선의 교점이 선분 밖에 있으면 안되겠죠.
교점의 좌표가 두 선분의 중간값이 되는지 체크하면 됩니다.

위의 행렬연산에서
역행렬이 존재하지 않는 경우는
해가 없거나(두 직선이 평행)
해가 무수히 많거나(두 직선이 일치)
이 두가지인데요,

두 직선의 x y 계수의 비로 이를 분기할 수 있는데,
두 직선의 해가 없는경우는 물론 두 선분도 겹치치 않으니 생각할 필요 없는데,
해가 무수히 많은경우는 다릅니다.


이러한(위 그림과 같은) 경우에는 직선의 해는 (무수히)있으나
구하려는 선분의 교차여부를 본다면 교차하지 않는 경우이지요.

선분의 한 점이 다른 선분의 중간값이 되느냐 안되느냐 하는 체크를 4개의 점에 걸쳐 모두 시행하면
해결할 수 있습니다.

이 경우와 같이
두 선분이 서로 겹쳐지는 경우는 제작하는 프로그램의 상황에 따라
만나는 것으로 처리할지 아니면 만나지 않을 것으로 처리할지 달라지겠네요.
예를 들어 총쏘는 게임을 만든다면 저렇게 스쳐가는것을 무시하게 할 수도 있지만,
꼬여있는 선분을 푸는 퍼즐게임 같은경우는 교차ok로 인식을 해야겠죠.




구현

선분이 두 개 있다면 
읽어들여야 할 변수는 
 
line1_p1.x , line1_p1.y    // 선분1 의 한쪽 끝 점의 x,y 좌표
line1_p2.x , line1_p2.y    // 선분1 의 다른 한 쪽 끝 점의 x,y 좌표
line2_p1.x , line1_p1.y    // 선분2 의 한쪽 끝 점의 x,y 좌표
line2_p2.x , line1_p2.y    // 선분2 의 다른 한 쪽 끝 점의 x,y 좌표

이렇게 8개가 됩니다. line1_p1 , line1_p2  등은 선분의 양 끝 점(DisplayObject 形) 입니다.


직선의 방정식의 기본형을 살짝 변형하여
ax - by = -c
a`x - b`y = -c`
를 기본으로 삼기로 하고,
a, b, c, a` ,b` ,c` 에 해당하는 변수를 각각
line1_a, line1_b, line1_c, line2_a, line2_b, line2_c
이라고 정했습니다.

직선1의 방정식에서 x의 계수인 line1_a 의 값은
1/(line1_p2.x - line1_p1.x)
가 되는데요, 왜 그러냐면
그래프에서 x의 계수를 2배로 하면 x축 방향으로 2배 축소 되고,
1/2 배로 하면 x축 방향으로 1/2배 축소(2배 늘어남) 가 되므로
직선의 기울기를, 주어진 선분의 기울기와 맞추기 위해
선분이 x축 방향으로 늘어난 정도(line1_p2.x - line1_p1.x)의 역수를 x의 계수로 취해 준 것입니다.

line1_b 의 값은 같은이치로
1/(line1_p2.y - line1_p1.y) 가 되고,

line1_c 의 값은
지금까지 구한 계수(방정식에서 a, b에 해당)와 선분의 아무 한 점을 최초의 방정식
ax - by = -c
에 대입하면 나옵니다.
따라서 아래와 같이 프로그램할 수 있겠습니다.
line1_c = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1


직선2의 계수들도 같은방법으로 구해주면 드디어
두 직선의 방정식이 나왔네요.

이제 행렬을 이용해서 해를 구해야합니다.






Matrix 클래스는 플래시8 부터 있기때문에 그 이전 버전에서는 직접 비슷하게 구현해야 합니다.(역행렬, 행렬곱 메서드 정도만)
액션스크립트 3.0 에서는 flash.geom 패키지에 Matrix 클래스가 들어있습니다.

위쪽의 수식에서
(a  b )
(a` b`)
이 행렬을  matrix1 이라고 하고
(c )
(c`)
이 행렬은 matrix2라고 하면,  


(ActionScript3.0)
import flash.geom.Matrix;
var matrix1:Matrix = new Matrix(line1_a , -1*line1_b , line2_a , -1*line2_b );
var matrix2:Matrix = new Matrix(-1*line1_c , -1*line2_c );
var matrix3:Matrix = new Matrix();

이렇게 나타낼 수 있습니다

위쪽의 수식에서와 같이
매트릭스1을 역행렬로 변환하고, 매트릭스2를 곱해주면 되는데요,
matrix1.invert();
matrix3 = matrix1.concat(matrix2);
위와 같이 내장된 메서드를 이용하면 간단히 연산할 수 있습니다.

아! 역행렬이 존재하지 않는경우(ad-bc=0 의 꼴일 때)도 있으니까 위에 추가를 해줘야 합니다.
그래서 코드를 보면,

import flash.geom.Matrix;

var line1_a:Number = 1/(line1_p2.x - line1_p1.x);
var line1_b:Number = 1/(line1_p2.y - line1_p1.y);
var line1_c:Number = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1;
var line2_a:Number = 1/(line2_p2.x - line2_p1.x);
var line2_b:Number = 1/(line2_p2.y - line2_p1.y);
var line2_c:Number = (line2_a*line1_p1.x  +  -1*line2_b*line2_p1.y)*-1;

var matrix1:Matrix = new Matrix(line1_a , line1_b*-1 , line2_a , line2_b*-1 );
var matrix2:Matrix = new Matrix(line1_c*-1 , line2_c*-1 );
var matrix3:Matrix = new Matrix();
if(matrix1.a*matrix1.d == matrix1.b*matrix1.c) {   //만약 역행렬이 존재하지 않으면
   if(matrix2.a/matrix2.c != matrix1.a/matrix2.c) {  //만약 두 직선이(일치하지 않고)평행하면
       //두  직선(선분)이 평행하므로 교차하지 않음
   }
   else {
     // 두 직선이 일치함. 상황에 따라 추가 코딩.
   }
}
else {  //(위의 if의 부정을 받아)만약 역행렬이 존재하면,
   matrix1.invert();                                 //행렬1을 역행렬화 함
   matrix3 = matrix1.concat(matrix2);        //행렬1과 행렬2의 행렬곱을 구해서 행렬3에 대입
}



일단 이렇게해서 두 직선의 교점의 좌표가 행렬3에 들어가게 됩니다.
위쪽의 행렬수식을 참고하면
matrix3.a 에는 교점의 x좌표가 들어가고
matrix3.c 에는 교점의 y좌표가 들어간다는 것을 알 수 있습니다.

그런데 구하려는 것은 직선의 교점이 아닌 선분의 교점입니다.
구한 (교)점이 선분에 포함되는지를 체크해야 합니다.

if( Math.min(line1_p1.x,line1_p2.x) <= matrix3.a  &&  Math.max(line1_p1.x,line1_p2.x) >= matrix3.a 
    Math.min(line1_p1.y,line1_p2.y) <= matrix3.b  &&  Math.max(line1_p1.y,line1_p2.y) >= matrix3.b  
    &&
    Math.min(line2_p1.x,line2_p2.x) <= matrix3.a  &&  Math.max(line2_p1.x,line2_p2.x) >= matrix3.a 
    Math.min(line2_p1.y,line2_p2.y) <= matrix3.b  &&  Math.max(line2_p1.y,line2_p2.y) >= matrix3.b ) 
   { 
      //교차.
   }
else {
   //교차하지 않음.
}


이렇게 교차여부와 교점의 좌표를 구할 수 있습니다.
(교차여부 확인하는 코드는 더 짧게 줄일 수 있지만 여기서는 쉽게 하기위해서, 교점좌표가 두 선분의 사이에 있는지 
 부등호를 사용하여 조건을 작성했습니다.)  






신고

 


  1. 아... 정말 휴면인줄 알았는데..ㅋㅋ
    가끔씩 들렀는데 메인엔 블로그 휴면 글만 있고..
    레이아웃이 바뀌는걸 모르고 있었다니. 글도 그새 많이 올라왔네.
    뭔가 위장술 같...

  2. 역시 그랬구나. ㅋㅋ
    왠지 그런 것 같았어. 뭔가 바뀐다는걸 그제야 깨달았었다니.

  3. http://devmae.tistory.com/257

    봐요 봐

    • 네.감사요
      그리고 해제했어요 그건.
      그 문자입력 달았으니까 괜찮을수도..
      근데 다시 영어스팸이 침투하기시작하면 다시 설정해야겠네요.
      그 아스키로만 된 덧글 차단하는 플러긴을..ㅠㅜ

  4. 선분의 방정식같은건 없나영??
    행렬은 아직 안배워서 쓸줄 모르겠고 범위를 지정해서 해야할것 같은데..

    .

  5. ㅋㅋㅋ지존 2013.12.11 22:43 신고

    행렬좀 어렵지 않나윰?
    뭔가 제눈에는 이상한 괴생명체러 보임

댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph