判断线段与圆是否相交(计算几何)

线段与圆有三种位置关系,通过线段两个端点来看:

1:两个端点都在圆内, 一定不相交, 可以把两个点带入圆的方程判断是否小于0

2:两个端点,一个在圆内,一个在圆外, 一定相交, 同样点带入方程判断

3:两个端点都在外面, 此时略微麻烦, 可以通过点到直线的距离来判断,但是当直线和圆心一条直线时,此时需要特别处理

光有距离判断是不行的. 要通过角度来判断.-->余弦方程转换成向量表示

[代码实现]

可能比较难看懂, 因为坐标用的pair<double,double>写的 frist是x,second是y

double x,y,r;
vector<pair<double,double> > V;
typedef pair<double,double> PAIR;
PAIR yuan;
bool judge(PAIR P)// 判断是否在圆内
{
    if( (P.first-x)*(P.first-x) + (P.second-y)*(P.second-y) -r*r <=0)
        return 1;
    return 0;
}
bool Judis(PAIR P1,PAIR P2,double R) //线段与圆的关系
{

    if(judge(P1)&&judge(P2))//都在圆内 不相交
        return false;
    if(!judge(P1)&&judge(P2)||judge(P1)&&!judge(P2))//一个圆内一个圆外 相交
        return true;
    double A,B,C,dist1,dist2,angle1,angle2;//Ax+By+C=0;//(y1-y2)x +(x2-x1)y +x1y2-y1x2=0
    if(P1.first==P2.first)
        A=1,B=0,C= -P1.first;
    else if(P1.second==P2.second)
        A=0,B=1,C= -P1.second;
    else
    {
        A = P1.second-P2.second;
        B = P2.first-P1.first;
        C = P1.first*P2.second - P1.second*P2.first;
    }
    dist1 = A * yuan.first + B * yuan.second + C;
    dist1 *= dist1;
    dist2 = (A * A + B * B) * R * R;
    if (dist1 > dist2) return false;//点到直线距离大于半径r  不相交
    angle1 = (yuan.first - P1.first) * (P2.first - P1.first) + (yuan.second - P1.second) * (P2.second - P1.second);
    angle2 = (yuan.first - P2.first) * (P1.first - P2.first) + (yuan.second - P2.second) * (P1.second - P2.second);
    if (angle1 > 0 && angle2 > 0) return true;//余弦都为正，则是锐角 相交
    return false;//不相交
}

应用:

51Nod1298 圆与三角形

给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"Yes"，否则输出"No"。（三角形的面积大于0）。

Input

第1行：一个数T，表示输入的测试数量(1 <= T <= 10000)，之后每4行用来描述一组测试数据。
4-1：三个数，前两个数为圆心的坐标xc, yc，第3个数为圆的半径R。(-3000 <= xc, yc <= 3000, 1 <= R <= 3000）
4-2：2个数，三角形第1个点的坐标。
4-3：2个数，三角形第2个点的坐标。
4-4：2个数，三角形第3个点的坐标。(-3000 <= xi, yi <= 3000）

Output

共T行，对于每组输入数据，相交输出"Yes"，否则输出"No"。

Input示例

Output示例

Yes
No

[代码实现]

处理掉不相交已经都在圆内的是no其余是yes

#include <iostream>
#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
const double INFINV=1e10;
const double ESP=1e-6;

double x,y,r;
vector<pair<double,double> > V;
typedef pair<double,double> PAIR;
PAIR yuan;
bool judge(PAIR P)// 判断是否在圆内
{
    if( (P.first-x)*(P.first-x) + (P.second-y)*(P.second-y) -r*r <=0)
        return 1;
    return 0;
}
bool Judis(PAIR P1,PAIR P2,double R) //线段与圆的关系
{

    if(judge(P1)&&judge(P2))//都在圆内 不相交
        return false;
    if(!judge(P1)&&judge(P2)||judge(P1)&&!judge(P2))//一个圆内一个圆外 相交
        return true;
    double A,B,C,dist1,dist2,angle1,angle2;//Ax+By+C=0;//(y1-y2)x +(x2-x1)y +x1y2-y1x2=0
    if(P1.first==P2.first)
        A=1,B=0,C= -P1.first;
    else if(P1.second==P2.second)
        A=0,B=1,C= -P1.second;
    else
    {
        A = P1.second-P2.second;
        B = P2.first-P1.first;
        C = P1.first*P2.second - P1.second*P2.first;
    }
    dist1 = A * yuan.first + B * yuan.second + C;
    dist1 *= dist1;
    dist2 = (A * A + B * B) * R * R;
    if (dist1 > dist2) return false;//点到直线距离大于半径r  不相交
    angle1 = (yuan.first - P1.first) * (P2.first - P1.first) + (yuan.second - P1.second) * (P2.second - P1.second);
    angle2 = (yuan.first - P2.first) * (P1.first - P2.first) + (yuan.second - P2.second) * (P1.second - P2.second);
    if (angle1 > 0 && angle2 > 0) return true;//余弦都为正，则是锐角 相交
    return false;//不相交
}



int main()
{
  //  freopen("out.txt","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        V.clear();
        cin>>x>>y>>r;
        yuan={x,y};//圆心坐标
        for(int i=1;i<=3;i++)
        {
            double a,b;
            cin>>a>>b;
            V.push_back(make_pair(a,b));
        }
        int flag=0;
        for(int i=0;i<V.size();i++)
        {
            if( judge(V[i]))
            {
                flag++;
            }
        }

        if( !Judis(V[0],V[1],r)&&!Judis(V[0],V[2],r)&& !Judis(V[1],V[2],r)|| flag==3 )
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;

    }
    return 0;
}
/*
5
2 -2 1
-3 -3
2 -2
2 2
*/

附上test2数据:

15
-3 -3 2
1 2
1 -2
2 2
0 1 2
0 -1
2 1
1 -1
0 1 1
-2 0
-3 0
0 -2
2 -1 2
0 -2
2 1
-3 1
0 0 1
1 0
-1 -3
-1 0
0 2 1
0 1
1 2
-1 -2
-3 1 2
2 1
1 1
-1 0
0 0 1
-3 -1
1 1
-3 1
0 2 2
1 -1
2 -3
2 0
-2 0 1
2 -3
2 1
-1 -3
2 -2 1
-3 -3
2 -2
2 2
-3 -2 1
-3 2
2 -3
2 2
1 1 2
-2 2
-3 -3
-1 2
1 -2 2
-1 -2
1 -2
1 2
-3 -3 2
0 -1
0 2
2 -2

No
Yes
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
Yes
No

判断线段与圆是否相交(计算几何)

推荐阅读