3

问题 ：

给定两个三角形的顶点，检查它们是否有任何共同的内点。边或顶点上的任何点都不会被认为是三角形的内部。
我认为这是找出两个三角形是否相交的问题。

我的想法是： 

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 类是否有其他程序，它运行良好。
但在这方面，我找不到错误。
请帮忙。

谢谢你。

4

2 回答 2

1

我认为该行存在错误

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

如果我理解正确，Direction 函数会告诉你一个点是在代表你的线段的向量的左边还是右边。上面的陈述假设您的其他线段的两个点都在左侧或右侧，但没有考虑例如线段 B 的一个点位于例如线段 A 上但另一个点不在的情况。

所以我会改变它，例如，不是严格大于（>），而是检查大于或等于（>=）。

这可以解释您的示例的问题。在您的示例中，恰好点 (4,0) 位于段 (0,0),(5,0) 上，而点 (2,4) 位于段 (-4,16),( 4,0)。

于 2013-03-29T21:16:54.593 回答
0

如果矩形的数量多于两个，则应考虑通过线扫解决此问题。如果它只是两个矩形，你可以做一些检查，如果它们有共同的内部点，你可以得到答案。

观察结果是三角形的线段相交，或者一个矩形完全包含在另一个矩形中。如果线条相交或矩形是否包含点，我们将其分解为几个检查。

如果它们相交，则可以通过适当的线段的成对比较来检查第一个条件。第二个条件可以通过测试任何段的端点是否包含在另一个矩形中来检查。不是一个漂亮的解决方案，但易于编码。

于 2013-03-29T20:49:19.410 回答