위키 피 디아의 라인 교차 수식은 많은 수를 처리 할 수 ​​없습니까?

Question

저는 두 줄의 교차점을 계산하는 함수가 필요한 작은 게임을 만들고 있습니다. 그래서이 공식을 Wikipedia (http://en.wikipedia.org/wiki/Line-line_intersection)에서 꺼내서 함수로 만들었습니다.

bool lineline(int L1X1, int L1Y1, int L1X2, int L1Y2, int L2X1, int L2Y1, int L2X2, int L2Y2, int* X, int* Y) { // Returns the point of intersection of two lines 
    int D = (L1X1 - L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 - L2X2); // Denominator. If zero then no intersection 

    if (D == 0) { // Parallel and possibly overlapping 
     return false; 
    } else { 
     *X = ((L1X1 * L1Y2 - L1Y1 * L1X2) * (L2X1 - L2X2) - (L1X1 - L1X2) * (L2X1 * L2Y2 - L2Y1 * L2X2))/D; // Calculate x 
     *Y = ((L1X1 * L1Y2 - L1Y1 * L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 * L2Y2 - L2Y1 * L2X2))/D; // Calculate y 

     std::cout << D << " | " << *X << " | " << *Y << "\n"; 

     if (*X >= Bmin(L1X1, L1X2) && *X <= Bmax(L1X1, L1X2) && *Y >= Bmin(L1Y1, L1Y2) && *Y <= Bmax(L1Y1, L1Y2)) { 
      // Intersection is on first line 
      if (*X >= Bmin(L2X1, L2X2) && *X <= Bmax(L2X1, L2X2) && *Y >= Bmin(L2Y1, L2Y2) && *Y <= Bmax(L2Y1, L2Y2)) { 
       // Intersection is on second line 
       return true; 
      } else { 
       // Intersection is on first, but not on second line 
       return false; 
      } 
     } else { 
      // Intersection is not on first line. 
      return false; 
     } 

     return true; 
    } 
} 

그것은 꽤 잘, 예를 들어 나는이 인수를 호출 할 때 그것은

lineline(400, 0, 400, 2000, 0, 400, 2000, 400, &x, &y); 

그러나 true를 돌려 작품 나는 1300 개 단위까지 두 번째 줄을 ... 이동할 때

lineline(400, 0, 400, 2000, 0, 1700, 2000, 1700, &x, &y) == false; 

false를 반환합니다. 두 번째 함수 호출의 두 줄은 교차해야하지만 맞습니까? 이 매개 변수로 계산 한 값은 다음과 같습니다.

D = -4000000 
*X = 400; 
*Y = -447; 

누구든지 나를 도와 줄 수 있습니까? 나는 하루 종일 붙어 있었고, 지난번처럼 단순한 무언가를 놓치고 있을지 모르지만 나는 그것을 볼 수 없다. 미리 감사드립니다!

Answer 1

수식은 입력 숫자의 차이를 3도까지 올리므로 차이가 약 3 자리 인 경우 int (9 자리 숫자를 초과하면 첫 번째 숫자가 2까지 올 수 있음)이 넘칠 수 있습니다 int을 오버플로하면 양수 값을 곱한 결과 음수가 표시되기 시작하므로 나머지 계산은 올바르지 않게됩니다.

범위를 향상 시키려면 중간 결과에 64 비트 정수 (즉, long long)를 사용하십시오.

Answer 2

100 % 확신 할 수는 없지만 값을 재조정 할 수는 없습니까? 예 : 가장 큰 것을 모두 나누고 float 결과를 사용하면 단순히 다른 비율로 동일한 크기를 갖게됩니다. 이 작업이 필요한 정확한 교차점이 필요하지 않으므로 평행선에 대해 0을 얻지 못한다는 것을 기억하십시오. 따라서 매우 작은 값의 알파를 사용하여 D 값을 정의하는 0 +/- 알파 범위를 정의해야합니다. 평행선.