C++는 : 두 개의 삼각형이 교차하는지 확인 여부를

Question

문제 :

두 개의 삼각형의 정점을 감안할 때, 둘은 어떤 공통의 내부 지점이 있는지 확인합니다. 모서리 나 정점의 점은 삼각형의 내부로 간주되지 않습니다.
두 개의 삼각형이 교차하는지 아닌지를 찾는 것이 문제라고 생각합니다.

내 아이디어이다

1. Make three line segments for each of the two triangles 
2. For each pair of line segment (A,B) (where A is in triangle #1 and B is in Triangle #2) check whether they intersect or not. 
3. If any pair of segments intersect, then the two triangles have a interior point. Otherwise not . 

내 코드이 입력 그러나

#include <algorithm> 
#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cmath> 

#define READ freopen("in.txt","r",stdin) 
#define ui64 unsigned long long int 
#define i64 long long int 

using namespace std; 

class Point{ 
public: 
    i64 x, y; 
    Point() : x(0), y(0) {} 
    Point(int a, i64 b) : x(a), y(b) {} 
}; 

class Segment{ 
public: 
    Point a, b; 
    Segment() : a(0,0), b(0,0) {} 
    Segment(Point e, Point r) : a(e), b(r) {} 
    Segment(const Segment &s){ 
     a = s.a; 
     b = s.b; 
    } 
    i64 Direction(const Point &p){ 
     return (p.x - a.x) * (b.y - a.y) - (b.x - a.x) * (p.y - a.y); 
    } 
    inline bool inside(int a,int b,int c){ 
     return a<=c && c<=b; 
    } 
    bool onSegment(const Point &p){ 
     return inside(min(a.x,b.x), max(a.x,b.x), p.x) && inside(min(a.y,b.y), max(a.y,b.y), p.y); 
    } 
    bool Intersect(Segment &s){ 
     int d1 = this->Direction(s.a); 
     int d2 = this->Direction(s.b); 

     int d3 = s.Direction(a); 
     int d4 = s.Direction(b); 

     if(((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) return true; 

     //check if the two segments just touch each other but don't cross 
     //i ignored this because as the problem said ... 
     //No points on the edges or vertices are considered interior to a triangle. 
     /*if(!d1 && this->onSegment(s.a)) return true; 
     if(!d2 && this->onSegment(s.b)) return true; 
     if(!d3 && s.onSegment(a)) return true; 
     if(!d4 && s.onSegment(b)) return true;*/ 
     return false; 
    } 
}; 

Point p1[3], p2[3]; 
Segment s1[3], s2[3]; 

bool check() 
{ 
    for(int i=0;i<3;i++) 
     for(int j=0;j<3;j++) 
      if(s1[i].Intersect(s2[j])) 
       return true; 
    return false; 
} 

int main() 
{ 
    //READ; 

    int t, ts=0; 

    scanf("%d",&t);//number of test cases 
    while(t--){ 
     //points for first triangle 
     for(int i=0;i<3;i++){ 
      scanf("%lld %lld",&p1[i].x, &p1[i].y); 
     } 
     //points for second triangle 
     for(int i=0;i<3;i++){ 
      scanf("%lld %lld",&p2[i].x, &p2[i].y); 
     } 
     for(int i=0;i<3;i++){ 
      s1[i] = Segment(p1[i], p1[(i+1)%3]); 
      s2[i] = Segment(p2[i], p2[(i+1)%3]); 
     } 
     printf("pair %d: %s\n",++ts, check() ? "yes" : "no"); 
    } 

    return 0; 
} 

..

1 

0 0 5 0 2 4 
4 0 5 0 -4 16 

내 프로그램 제공 출력

no 

하지만 정답은

yes 

이며 내 프로그램이 작동하지 않는 많은 경우가 있습니다.
다른 프로그램에 대한 Segment 클래스를 검사했는데 정상적으로 작동했습니다.
그러나이 경우 실수를 찾을 수 없습니다.
도와주세요.

감사합니다.

Answer 1

사각형 수가 3보다 많으면이 값을 줄 스윕으로 해결해야합니다. 그것이 단지 두 개의 직사각형 인 경우, 공통된 내부 점이있는 경우 대답을 제공하는 두 가지 검사를 수행 할 수 있습니다.

삼각형의 세그먼트가 교차하거나 하나의 사각형이 다른 세그먼트에 완전히 포함되어 있다는 관찰이 있습니다. 선이 교차하거나 직사각형에 점이 있으면 몇 가지 검사로 구분합니다.

첫 번째 조건은 교차하는 경우 적절한 세그먼트를 쌍으로 비교하여 확인할 수 있습니다. 두 번째 조건은 세그먼트의 끝 점이 다른 사각형에 포함되어 있는지 테스트하여 검사 할 수 있습니다. 아름다운 솔루션은 아니지만 쉽게 코드화 할 수 있습니다.

Answer 2

나는 버그가 내가 제대로 이해한다면, 방향 기능이 점은 왼쪽이나 선분을 나타내는 벡터의 오른쪽에 있는지 여부를 알려줍니다

if(((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) return true;

라인에 있다고 생각합니다. 위의 설명은 귀하의 다른 세그먼트의 포인트가 모두 왼쪽 또는 오른쪽이지만, 한 포인트가 예를 들어, 세그먼트 B는 예를 들어. 세그먼트 A하지만 다른 세그먼트는 그렇지 않습니다.

그래서 예를 들어, 정확히 (>)보다 크지 않고 (>=)보다 크거나 같음을 확인합니다.

예를 들어 문제가 설명 될 수 있습니다. 예를 들어, 점 (4,0)은 세그먼트 (0,0), (5,0)에 있고 점 (2,4)은 세그먼트 (-4,16)에 놓여 있습니다. 4,0).