FWIW에서 다음 함수 (C)는 선 교차를 감지하고 교차점을 결정합니다. Andre LeMothe의 ” Tricks of the Windows Game Programming Gurus ” 알고리즘을 기반으로합니다 . 다른 답변 (예 : Gareth)의 일부 알고리즘과 다르지 않습니다. 그런 다음 LeMothe는 Cramer ‘s Rule (나에게 묻지 않음)을 사용하여 방정식 자체를 해결합니다.

나는 그것이 연약한 소행성 클론에서 작동한다는 것을 증명할 수 있으며 Elemental, Dan 및 Wodzu의 다른 답변에 설명 된 가장자리 사례를 올바르게 처리하는 것으로 보입니다. KingNestor가 게시 한 코드보다 아마 빠를 수도 있습니다. 왜냐하면 그것은 모두 곱셈과 나눗셈이기 때문입니다.

내 경우에는 문제가되지 않았지만 0으로 나눌 가능성이 있다고 생각합니다. 어쨌든 충돌을 피하기 위해 쉽게 수정할 수 있습니다.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

BTW, 나는 LeMothe의 책에서 분명히 알고리즘을 올바르게 얻지 만, 구체적인 숫자는 플러그를 잘못된 숫자로 표시하고 계산을 잘못한다고 말합니다. 예를 들면 다음과 같습니다.

(4 * (4-1) + 12 * (7-1)) / (17 * 4 + 12 * 10)

= 844 / 0.88

= 0.44

그것은 몇 시간 동안 나를 혼란스럽게했다 . 🙁

답변

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

A + E*g = C + F*h

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // Both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;
    }
}