3

問題 ：

2 つの三角形の頂点が与えられた場合、それらの両方に共通の内点があるかどうかを確認します。エッジまたは頂点上のポイントは、三角形の内部と見なされません。
これは2つの三角形が交わるか交わらないかを求める問題だと思います。

私の考えは： 

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

私のプログラムが動かないケースも多いです。
他のプログラムのセグメント クラスを確認したところ、問題なく動作しました。
しかし、これでは、私は間違いを見つけることができません。
助けてください。

ありがとうございました。

4

2 に答える 2

1

行にバグがあると思います

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

私の理解が正しければ、方向関数は、点が線分を表すベクトルの左または右にあるかどうかを示します。上記のステートメントは、他のセグメントの両方のポイントが左または右にあると想定していますが、たとえばセグメント B の 1 つのポイントがたとえばセグメント A にあるが、もう一方のポイントがそうでない場合は考慮していません。

したがって、たとえば、厳密により大きい ( >) ではなく、より大きいか等しい ( >=) をチェックするように変更します。

これはあなたの例の問題を説明するかもしれません。あなたの例では、点 (4,0) がセグメント (0,0),(5,0) にあり、点 (2,4) がセグメント (-4,16),( 4,0)。

于 2013-03-29T21:16:54.593 に答える
0

四角形の数が 2 つを超える場合は、ライン スイープでこれを解決することを検討する必要があります。2 つの長方形だけの場合は、内点が共通しているかどうかを調べるいくつかのチェックを行うことができます。

観察は、三角形のセグメントが交差するか、1 つの長方形が他の長方形に完全に含まれているかのいずれかです。線が交差するか、長方形に点が含まれているかどうかをいくつかのチェックに分割します。

最初の条件は、適切なセグメントが交差する場合、それらのペアワイズ比較によってチェックできます。2 番目の条件は、いずれかのセグメントの端点が他の長方形に含まれているかどうかをテストすることで確認できます。美しいソリューションではありませんが、簡単にコーディングできます。

于 2013-03-29T20:49:19.410 に答える