帮我编一个判断点在三角形内的C语言程序

在控制机器人的程序中用,用向量的方法判断一个点是不是在某个三角形内... 在控制机器人的程序中用,用向量的方法判断一个点是不是在某个三角形内 展开
 我来答
cobrawlm
2014-03-23 · TA获得超过136个赞
知道答主
回答量:81
采纳率:0%
帮助的人:22.6万
展开全部

如果不用向量的方法,可以用凸多边形理论求解。

 

设三角形的三顶点为A、B、C,现有点P(点P不是点A、B、C),过A、P两点作直线交BC所在直线于点D,若点D位于线段BC上,则点P一定位于该三角形内。代码如下:

 

#include<stdio.h>

#include "math.h"

#define DBL_MIN 2.2250738585072014e-308

struct Point { /* (x,y) */

    double x;

    double y;

};

struct Line { /* a*x+b*y=c */

    double a;

    double b;

    double c;

};

struct Triangle {

    struct Point A;

    struct Point B;

    struct Point C;

};

struct Line createLine(struct Point p1, struct Point p2) {

    struct Line line;

    line.a = p1.y - p2.y;

    line.b = p2.x - p1.x;

    line.c = p1.x * (p1.y - p2.y) + p1.y * (p2.x - p1.x);

    return line;

}

int isInTriangle(struct Triangle* tri, struct Point* P) {

    /*P落在三角形顶点上*/

    if (((fabs(P->x - tri->A.x) < DBL_MIN && fabs(P->y - tri->A.y) < DBL_MIN))

            || ((fabs(P->x - tri->B.x) < DBL_MIN && fabs(P->y - tri->B.y) < DBL_MIN))

            || ((fabs(P->x - tri->C.x) < DBL_MIN && fabs(P->y - tri->C.y) < DBL_MIN)))

        return 1;

    struct Line line1 = createLine(tri->A, *P);

    struct Line line2 = createLine(tri->B, tri->C);

    struct Point D;

    if (fabs(line1.a * line2.b - line2.a * line1.b) >= DBL_MIN) {/* 不平行或不重合 */

        D.x = (line2.b * line1.c - line1.b * line2.c) / (line1.a * line2.b - line2.a * line1.b);

        D.y = (line1.a * line2.c - line2.a * line1.c) / (line1.a * line2.b - line2.a * line1.b);

        if (((tri->B.x <= D.x && D.x <= tri->C.x) || (tri->C.x <= D.x && D.x <= tri->B.x))

                &&((tri->B.y <= D.y && D.y <= tri->C.y) || (tri->C.y <= D.y && D.y <= tri->B.y)))

            return 1;

    }

    return 0;

}

int isTriangle(struct Triangle tri) {

    double AB, BC, AC;

    AB = sqrt((tri.A.x - tri.B.x)*(tri.A.x - tri.B.x)+(tri.A.y - tri.B.y)*(tri.A.y - tri.B.y));

    BC = sqrt((tri.C.x - tri.B.x)*(tri.C.x - tri.B.x)+(tri.C.y - tri.B.y)*(tri.C.y - tri.B.y));

    AC = sqrt((tri.A.x - tri.C.x)*(tri.A.x - tri.C.x)+(tri.A.y - tri.C.y)*(tri.A.y - tri.C.y));

    if (AB + BC > AC && BC + AC > AB && AC + AB > BC)

        return 1;

    else

        return 0;

}

int main(int argc, char** argv) {

    struct Triangle triangle = {{-2, 0},{2, 3}, {2, 0} };//三角形

    struct Point points[] = {{-1.999,0.0001},{0, 0},{1,1},{2,3},{-1, 2} }; //测试点数组

    if (isTriangle(triangle)) {

        int i;

        for (i = 0; i < 5; i++) {

            if (isInTriangle(&triangle, &points[i]))

                printf("点(%f,%f)在三角形内。\n", points[i].x, points[i].y);

            else

                printf("点(%f,%f)不在三角形内。\n", points[i].x, points[i].y);

        }

    } else

        printf("不构成三角形!\n");

    return 0;

}

运行结果:

cnnbwhq1972
2014-03-22 · TA获得超过3843个赞
知道小有建树答主
回答量:488
采纳率:83%
帮助的人:240万
展开全部
//
// Do not forget my qq:573827574, thanks
//

#include "stdafx.h"
#include "math.h"
#include<stdio.h>
#include<stdlib.h>

typedef struct Point{
float x;
float y;
};
//输入参数:设定 A为原点 ;B为射线上的一点, BA组成一条射线
//输出参数:输出射线BA与X轴的夹角
double slope(Point A,Point B)
{
float tansita;
float sita;
float subEBx;

subEBx = abs(B.x - A.x );
if (B.x == A.x) subEBx = 0.0001;

tansita =(abs(B.y - A.y ))/subEBx;
sita = atan(tansita);

if ((B.x >=A.x )&&(B.y >=A.y )) return sita;
if ((B.x <=A.x )&&(B.y >=A.y )) return 3.1416 - sita;

if ((B.x <=A.x )&&(B.y <=A.y )) return  3.1416 +sita;
if ((B.x >=A.x )&&(B.y <=A.y )) return  2*3.1416 -sita;
}

//函数功能:判断射线DB是否在角ABC范围内,通过判断射线的与X轴的夹角是否在射线AB、CB范围之内
//输入参数:输入三个点,ABC,我们约定以B点为原点,射线AB,CB组成角ABC;
//输入参数:第四点为所要判断的点D ,如果射线DB在角ABC的范围内,
//输出参数:true = 该点在角ABC内,false = 该点不在角ABC内
bool InAngleArea(Point A,Point B,Point C,Point D)
{
float StartAngle,EndAngle;
float DAAngle;
StartAngle = slope(B,A);
EndAngle = slope(B,C);
if (EndAngle == 0.0 ) EndAngle = 2*3.1416;
DAAngle = slope(B,D);

//printf("\nn%f %f - %f\n",StartAngle,EndAngle,DAAngle);

if ((DAAngle>StartAngle )&&(DAAngle< EndAngle )) 
return true;
else return false;

}

/////////////////////////////////////////////////
//***重要提示:请确保点参数A B C按逆时针输入***//
/////////////////////////////////////////////////
bool PointInTriangle(Point A,Point B,Point C,Point D)
{
bool aa,bb,cc;
aa = InAngleArea(C,B,A,D);
bb = InAngleArea(B,A,C,D);
cc = InAngleArea( A,C,B,D);
if (aa &&bb &&cc)
//if ( InAngleArea(A,B,C,D)  && InAngleArea(B,C,A,D)&& InAngleArea( C,A,B,D))
return true ;
else
return false;

}

void main()

Point A,B,C,D;
   
printf("请输入三个点(按逆时针输入)的坐标(X,Y)\n");
scanf("%f%f",&A.x ,&A.y );
scanf("%f%f",&B.x ,&B.y );
scanf("%f%f",&C.x ,&C.y );
printf("请输入第四个点的坐标(X,Y)\n");

scanf("%f%f",&D.x ,&D.y );

printf("\n%f, %f",A.x , A.y );
printf("\n%f, %f",B.x , B.y );
printf("\n%f, %f",C.x , C.y );
printf("\n%f, %f\n",D.x , D.y );

if (PointInTriangle(A,B,C,D) == true)
printf("第四个点在三角形ABC中。\n");
else
printf("第四个点不在三角形ABC中。\n");
getchar();
system("pause");
}
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
章氏SaiKouDa
2014-03-23 · TA获得超过212个赞
知道小有建树答主
回答量:340
采纳率:0%
帮助的人:209万
展开全部
可以利用三角形定理证明。
点如果在三角形内,其与3顶点会形成3条线段。这3条新线段两两组合与三角形的三边形成3个新3角型。点在三角形里的条件就是原角型的3边都是新三角形里的最长边。ABC 顶i点d
(Ad<AB&&Bd<AB)&&....
你看是否简单易懂。别人说的射线太难了。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
supersarah
推荐于2017-11-26 · TA获得超过7151个赞
知道大有可为答主
回答量:2623
采纳率:80%
帮助的人:1207万
展开全部
数学知识啊....

假设三角形三个顶点 A (x1, y1), B (x2, y2), C (x3, y3), 需要判定的点 P (x0, y0)

现在, 以A 为原点, 判断向量 AP, 与 AB, AC 的关系, 最简单的办法就是看它们的向量积
AP x AB = [ (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1) ] i = Kb i
其中 i 是垂直于平面方向的单位向量
AP x AC = [ (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1) ] i = Kc i

如果 AP 在 AB, AC 之间, 那么 Kb, Kc 符号相反, 看起来比较聪明的方式是把他们相乘, 不过这显然增加了运算量, 其实还是用逻辑判断比较好,
double Kb, Kc;
Kb = (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1);
Kc = (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1);
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) PinBC = 1;
else PinBC = 0;
.....
然后, 以 B, C 为原点, 分别判断 PinAC, PinAB.......

PinBC, PinAC, PinAB 只要有一个不满足, 就可以判断 P 不在三角形内了....

可以写成函数比较简洁

int PinAB ( double x0, double y0, double x1, double y1, double x2, double y2)
{
double Kb, Kc;
Kb = x0*y1 - x1*y0;
Kc = x0*y2 - x2*y1;
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) return 1;
return 0;
}

int PinABC ( double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3)
{
if ( PinAB ( x0 - x1, y0 -y1, x2 - x1, y2 - y1, x3 - x1, y3 - y1) &&
PinAB ( x0 - x2, y0 -y2, x3 - x2, y3 - y2, x1 - x2, y1 - y2) &&
PinAB ( x0 - x3, y0 -y3, x2 - x3, y2 - y3, x1 - x3, y1 - y3) ) return 1;
return 0;
}

当然这个算法没能利用 cpu 的向量计算能力, 如果 cpu 支持向量计算, 直接算向量的差/积要快不少....
本回答被提问者和网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 更多回答(2)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式