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类在其他程序中也能正常工作。
但是在这个程序中，我找不到错误所在。
请帮忙看看。

谢谢。

- palatok

---

你的方法没有考虑一个三角形完全包含在另一个三角形内的情况。 - Oliver Charlesworth

但是问题声明中说：三角形的边缘或顶点上的点不被视为内部点。 - palatok

个人而言，我会编写一个三角形类，该类接受3个顶点。然后编写一个包含顶点的函数ContainsVertex。对于另一个三角形中的每个顶点，调用ContainsVertex。如果在任何时候ContainsVertex返回true，则完成了操作。如果两个三角形相交，则每个三角形都将包含来自另一个三角形的顶点。编辑：除了一个完全在另一个三角形内的情况。但是处理这种情况非常简单。 - Aeluned

不，我不知道当时在想什么。那不是真的。你很可能需要测试两个三角形。如果三角形1不包含来自tri 2的任何点，则可能反过来也是正确的。 - Aeluned

为什么这被标记为重复？另一个问题是关于三维中的三角形，虽然答案可能是通用的（不太可能，因为在三维过程的第一步是消除共面三角形），但在二维情况下可能相对低效。据我所知，答案在Oliver的第一个评论中 - 如果其中一个三角形的顶点包含在另一个三角形中，则它们相交并且您完成了，否则请寻找边缘兴趣点。 - podperson

Answer 1

我认为这行代码存在一个 bug

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) 上的情况。

- maditya

Answer 2

如果矩形的数量超过两个，您应该考虑通过线性扫描来解决。如果只有两个矩形，则可以进行一些检查，以确定它们是否具有共同的内部点。

观察结果是三角形的线段要么相交，要么一个矩形完全包含另一个矩形。我们将其分解为一些检查，以确定线段是否相交或矩形是否包含点。

第一个条件可以通过逐对比较适当的线段来检查它们是否相交。第二个条件可以通过测试任何线段的端点是否包含在另一个矩形中来检查。这不是一个美丽的解决方案，但很容易编码。

- DennisL