个人中心
gpt4 book ai didi

C++ : check if two triangles intersect or not

转载 作者：太空狗 更新时间：2023-10-29 23:06:27 25 4
gpt4 key购买 nike

<分区>

问题:

给定两个三角形的顶点，检查它们是否有公共(public)内点。边或顶点上的任何点都不会被视为三角形的内部。
我认为这是一个判断两个三角形是否相交的问题。

我的想法是:

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 类是否有其他程序，它工作正常。
但是在这，我找不到错误。
请帮忙。

谢谢。

25 4 0
文章推荐： c++ - 这是哪个标准容器行为？
文章推荐： c# - 使用 Roslyn 生成格式良好的语法
文章推荐： c# - 合并单元格上的 OpenXML SDK 边框仅应用于第一个单元格
文章推荐： c++ - 红黑高斯赛德尔和 OpenMP
太空狗
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com