결정이있는 경우 선분

Question

나는이 질문에 대한 답변으로 게시 한이 코드를 사용하고 허용 오차 교차 : 그것은 나의 이해는이 기능은 교차점을 반환 How do you detect where two line segments intersect?

입니다 두 선분 경우 정확히 교차합니다. 공차를 포함하도록이 함수를 수정하여 선분 이 거의 인 경우 (즉 0.01 범위 내에서) 교차점을 반환해야합니다. 나는이 기능을 뒷받침하는 수학을 이해하지 못해 누군가가 도울 수 있기를 바랬다.

감사

// 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 
} 

편집 : 이미지 아래 시나리오의 종류를 묘사 명확한 설명함으로써 것 거의 교차하는 두 개의 선분.

Nearly intersecting lines - image

Answer 1

그것은 아직 정확하게는 "근처 교차로"로 계산 원하는 것을 명확하지 않다. 예제 이미지에서 각 선을 양방향으로 선택한 공차 값만큼 연장하고 연장 된 선 사이의 (정확한) 교차점을 확인하여 교차점을 찾을 수 있습니다.

더 예각으로 선의 교차점을 감지하려면 각 선을 공차로 결정된 너비의 직사각형 영역으로 확장 한 다음 직사각형 영역 사이의 겹침을 검사 할 수 있습니다.

두 경우 모두 허용치가 약간 다를 수 있습니다. 당신은 당신의 질문에 그것을 정의하지 않았습니다. 허용차 값은 정확히 무엇을 의미합니까? 그것은 라인 중 하나가 다른 것과의 교차점을 형성하기 위해 확장 될 필요가있는 양입니까? 교차로로 간주 될 수있는 각 선의 모든 점 사이의 최대 거리입니까? 등

Answer 2

나는 그래픽 전문가가 아니지만, 이것은 내가 무엇을 할 것이라고입니다 :

각 엔드 포인트의 경우 : threshold의 반경 엔드 포인트를 중심으로 원이 다른 선분을 교차하는지 확인합니다. 그러면 선들이 거의 교차합니다.