判断一点是否在三角形的外接圆内

时间：2021-04-08 10:24:58

在平面上，如果已知 △P0P1P2 的三个顶点坐标 P0(x0,y0), P1(x1,y1), P2(x2,y2) 和另一点 P 的坐标 (x,y) ，要判断点P是否在 △P0P1P2 内。
判断一点是否在三角形的外接圆内
这里给出两种判断方法，第一种方法是先求出 △P0P1P2 的外接圆圆心坐标，然后得到三角形的半径，比较半径和圆心到点 P 的距离，就能判断点 P 和外接圆的位置关系。第二种方法是选择 △P0P1P2 的一条边作为界线，如边 P0P2 ，然后根据点 P1 和点 P 是否在 P0P2 同侧，比较 ∠P0P1P2 和 ∠P0PP2 的大小，判断点 P 和外接圆的位置关系。

第一种方法

三角形的外心坐标公式为：
x=∣∣∣∣∣x20+y20x21+y21x22+y22y0y1y2111∣∣∣∣∣2∣∣∣∣∣x0x1x2y0y1y2111∣∣∣∣∣,y=∣∣∣∣∣x0x1x2x20+y20x21+y21x22+y22111∣∣∣∣∣2∣∣∣∣∣x0x1x2y0y1y2111∣∣∣∣∣
根据这个外心的坐标公式计算出外接圆的圆心坐标，就能得到圆的半径，从而判断出点 P 与外接圆的位置关系。
定义平面点的数据结构：

struct PointTri
{
double x;    // x 坐标
double y;    // y 坐标
};

求解行列式用到能够计算 N 阶行列式的子函数：

// 求 aij 的代数余子式
vector< vector<double> > Cofactor(vector< vector<double> > vecDet_ij, int i, int j)
{
int k;
vector< vector<double> > vecReturn;
vector< vector<double> >::iterator veck;
// vector<double>::iterator vecl;

// 初始化二维容器 vecReturn
    k = 0;
for (veck=vecDet_ij.begin(); veck<vecDet_ij.end(); veck++)
    {
if ((veck - vecDet_ij.begin()) != i)
        {
            vecReturn.push_back(*veck); // 加入除第 i 行外的所有行

            vecReturn[k].erase(vecReturn[k].begin() + j);
            k++;
        }
    }
return vecReturn;
}
// 计算行列式的值, 采用递归
double det_Array(vector< vector<double> > vecDet)
{
int i;
double Sum = 0.0;
vector< vector<double> >::iterator vec_Row = vecDet.begin();
vector<double>::iterator vec_Column = (*vec_Row).begin();
if (vecDet.size() == 1)
    {
return *vec_Column;
    }
else
    {
        i = 0;
for (; vec_Column < (*vec_Row).end(); vec_Column++)
        {
            Sum = Sum + pow(-1.0, i) * (*vec_Column) * det_Array( Cofactor(vecDet, 0, i++) );
        }
return Sum;
    }
}

主要的判断函数为：

// 判断点 Ｐ 是否在圆内
bool InnerOROut(PointTri Vrtx0, PointTri Vrtx1, PointTri Vrtx2, PointTri Vrtx)
{
double Radius_2;  // 半径的平方
/* double Radius_2T1, Radius_2T2;*/
double Cntrx, Cntry; //圆心坐标

// 求圆心和半径
vector< vector<double> > vecDet1, vecDet2;
vector<double> A, B, C;

// 计算圆心的 x 坐标
    A.push_back(pow(Vrtx0.x, 2.0) + pow(Vrtx0.y, 2.0)); A.push_back(Vrtx0.y); A.push_back(1.0);
    B.push_back(pow(Vrtx1.x, 2.0) + pow(Vrtx1.y, 2.0)); B.push_back(Vrtx1.y); B.push_back(1.0);
    C.push_back(pow(Vrtx2.x, 2.0) + pow(Vrtx2.y, 2.0)); C.push_back(Vrtx2.y); C.push_back(1.0);
    vecDet1.push_back(A); vecDet1.push_back(B); vecDet1.push_back(C);

    A.clear(); B.clear(); C.clear();
    A.push_back(Vrtx0.x); A.push_back(Vrtx0.y); A.push_back(1.0);
    B.push_back(Vrtx1.x); B.push_back(Vrtx1.y); B.push_back(1.0);
    C.push_back(Vrtx2.x); C.push_back(Vrtx2.y); C.push_back(1.0);
    vecDet2.push_back(A); vecDet2.push_back(B); vecDet2.push_back(C);
    Cntrx = det_Array(vecDet1) / (2 * det_Array(vecDet2));

// 计算圆心的 y 坐标
    vecDet1.clear(); vecDet2.clear();
    A.clear(); B.clear(); C.clear();
    A.push_back(Vrtx0.x); A.push_back(pow(Vrtx0.x, 2.0) + pow(Vrtx0.y, 2.0)); A.push_back(1.0);
    B.push_back(Vrtx1.x); B.push_back(pow(Vrtx1.x, 2.0) + pow(Vrtx1.y, 2.0)); B.push_back(1.0);
    C.push_back(Vrtx2.x); C.push_back(pow(Vrtx2.x, 2.0) + pow(Vrtx2.y, 2.0)); C.push_back(1.0);
    vecDet1.push_back(A); vecDet1.push_back(B); vecDet1.push_back(C);

    A.clear(); B.clear(); C.clear();
    A.push_back(Vrtx0.x); A.push_back(Vrtx0.y); A.push_back(1.0);
    B.push_back(Vrtx1.x); B.push_back(Vrtx1.y); B.push_back(1.0);
    C.push_back(Vrtx2.x); C.push_back(Vrtx2.y); C.push_back(1.0);
    vecDet2.push_back(A); vecDet2.push_back(B); vecDet2.push_back(C);
    Cntry = det_Array(vecDet1) / (2 * det_Array(vecDet2));

// 外接圆的半径的平方
    Radius_2 = pow(Vrtx0.x - Cntrx , 2.0) + pow(Vrtx0.y - Cntry, 2.0);

// 判断 Vrtx0 是否在外接圆内或其上，若是，返回 true,否则，返回 false
double Rad_V0Cntr;
    Rad_V0Cntr = pow(Vrtx.x - Cntrx , 2.0) + pow(Vrtx.y - Cntry, 2.0);
if (Rad_V0Cntr <= Radius_2)
    {
return true;
    } 
else
    {
return false;
    }
}

这种采用通用的计算行列式值的方法代码会比较多，针对三阶行列式的求解可以采用固定的公式，展开求解，针对这个特定的求解问题会显得简化一些：

// 判断点 Ｐ 是否在圆内
bool InnerOROut1(PointTri Vrtx0, PointTri Vrtx1, PointTri Vrtx2, PointTri Vrtx)
{
double Radius_2;  // 半径的平方
double Cntrx, Cntry; //圆心坐标

// 求圆心和半径
double a1 = (Vrtx1.x - Vrtx0.x), b1 = (Vrtx1.y - Vrtx0.y);
double c1 = (a1*a1 + b1*b1) / 2.0;
double a2 = (Vrtx2.x - Vrtx0.x), b2 = (Vrtx2.y - Vrtx0.y);
double c2 = (a2*a2 + b2*b2) / 2.0;
double d = (a1*b2 - a2*b1);
    Cntrx = Vrtx0.x + (c1 * b2 - c2 * b1) / d;
    Cntry = Vrtx0.y + (a1 * c2 - a2 * c1) / d;
    Radius_2 = pow(Vrtx0.x - Cntrx , 2.0) + pow(Vrtx0.y - Cntry, 2.0);

// 判断 Vrtx0 是否在外接圆内或其上，若是，返回 true,否则，返回 false
double Rad_V0Cntr;
    Rad_V0Cntr = pow(Vrtx.x - Cntrx , 2.0) + pow(Vrtx.y - Cntry, 2.0);
if (Rad_V0Cntr <= Radius_2)
    {
return true;
    } 
else
    {
return false;
    }
}

主函数的调用示例：

void main()
{
    system("color F1");

// -------------------------------------
    PointTri P0, P1, P2, P;
    P0.x = 0.0; P0.y = 0.0;
    P1.x = 0.0; P1.y = 1.0;
    P2.x = 1.0; P2.y = 0.0;
    P.x = 0.5; P.y = 0.5;

// if (InnerOROut1(P0, P1, P2, P))
if (InnerOROut(P0, P1, P2, P))
    {
cout << "P in the circle" << endl;
    }
else
    {
cout << "P not in the circle" << endl;
    }
// -------------------------------------

    system("pause");
}

第二种方法

判断一点是否在三角形的外接圆内

基本思路：
step1 计算 ∠P0P1P2 和 ∠P0PP2 的大小，两个角的大小在[0, π ]范围内。
   step1.1 如果 ∠P0PP2=0 ，则点 P 不在圆内，结束；如果 ∠P0PP2=π ，则点 P 在圆内，结束。
setp2 判断点 P 和 P1 是否在 P0P2 同侧。
   step2.1 这里通过判断向量积 P1P0−→−−×P1P2−→−− 与 PP0−→−×PP2−→− 是否同号，如果同号则在同一侧，否则在两侧。
step3 如果点 P 和 P1 是在 P0P2 同一侧，若 ∠P0P1P2≤∠P0PP2 ，则点 P 在圆内，否则在圆外，结束；如果点 P 和 P1 是在 P0P2 不在侧，若 ∠P0P1P2+∠P0PP2≥π ，则点 P 在圆内，否则在圆外，结束。

// 若果点 Vrtx 在外接圆内或在圆上返回 true, 否则返回 false
bool InnerOROut2(PointTri Vrtx0, PointTri Vrtx1, PointTri Vrtx2, PointTri Vrtx)
{
    double PI = 3.14159265358979323846;

    // 选择 P0P1 作为边, 相关的向量定义
    PointTri P2P0, P2P1, PP0, PP1;

    P2P0.x = Vrtx0.x - Vrtx2.x;
    P2P0.y = Vrtx0.y - Vrtx2.y;
    P2P1.x = Vrtx1.x - Vrtx2.x;
    P2P1.y = Vrtx1.y - Vrtx2.y;

    PP0.x = Vrtx0.x - Vrtx.x;
    PP0.y = Vrtx0.y - Vrtx.y;
    PP1.x = Vrtx1.x - Vrtx.x;
    PP1.y = Vrtx1.y - Vrtx.y;

    // 计算角 P0P2P1,
    double angle_P0P2P1;
    if (P2P0.x * P2P0.x + P2P0.y * P2P0.y < 0.000001 || P2P1.x * P2P1.x + P2P1.y * P2P1.y < 0.000001)
    {
        return false;
    } 
    else
    {
        angle_P0P2P1 = acos((P2P0.x * P2P1.x + P2P0.y * P2P1.y) / 
            (sqrt(P2P0.x * P2P0.x + P2P0.y * P2P0.y) * sqrt(P2P1.x * P2P1.x + P2P1.y * P2P1.y)));
    }

    // 计算角 P0PP1,
    double angle_P0PP1;
    if (PP0.x*PP0.x + PP0.y*PP0.y < 0.000001 || PP1.x*PP1.x + PP1.y*PP1.y < 0.000001)
    {
        // 点 P 与点 P0,P1中的一点重合
        return true;
    } 
    else
    {
        angle_P0PP1 = acos((PP0.x*PP1.x + PP0.y*PP1.y) / 
            (sqrt(PP0.x*PP0.x + PP0.y*PP0.y) * sqrt(PP1.x*PP1.x + PP1.y*PP1.y)));
    }

    if (angle_P0PP1 < 0.000001)
    {
        // 点 P 在线段 P0P1 外，但三点共线
        return false;
    }
    if ((PI/2.0 - angle_P0PP1) < 0.000001)
    {
        // 点 P 在线段 P0P1 内，三点共线
        return true;
    }

    // 判断点 P2 和 P 在否在直线 P0P1 的同一侧
    // 通过向量积来判断，PP0 X PP1, P2P0 X P2P1
    double product_P2 = P2P0.x * P2P1.y - P2P1.x * P2P0.y;
    double product_P = PP0.x * PP1.y - PP1.x * PP0.y;
    if (product_P2 * product_P > 0) // 点 P,P2同侧
    {
        if (angle_P0P2P1 <= angle_P0PP1)
        {
            // 在同侧时，角P0P2P1 <= 角P0PP1，点 P 在圆内或圆上
            return true;
        } 
        else
        {
            return false;
        }

    }
    else
    {
        // 不在同侧时
        if (angle_P0PP1+angle_P0P2P1 - PI/2.0 >= 0.0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
标签：

相关文章