首页 > 代码库 > 判点在直线上,三角形内

判点在直线上,三角形内

判断点在直线上,需要满足两个条件,如判断Q点是否在线段p1p2上

1:(Q-P1)X(P2-P1)=0;//叉乘为0

2:Q在以P1,P2为对角顶点的矩形内//保证点Q不在线段P1P2的延长线或反向延长线上

判断点在三角形内:

如果点P在三角形内,那么Spab+Spac+Spbc=Sabc

三角形面积公式由叉积给出 S=1/2×|crossProduct(a,b,c)|;

这种方法有浮点误差

另一种是沿三角形的边顺时针方向,判断P点是否在每条边的右边,如果是,就在三角形内

此法没有浮点误差

下面只给出了有浮点误差的

#include <stdio.h>#include <math.h>#include <iostream>#include <algorithm>#define eps 1e-8using namespace std;typedef struct node{    double x,y;}point;typedef struct triangle{    point A;    point B;    point C;};double crossProduct(point p1,point p2,point p0)//(p1-p0)X(p2-p0){    double x1,x2,y1,y2;    x1=p1.x-p0.x;    y1=p1.y-p0.y;    x2=p2.x-p0.x;    y2=p2.y-p0.y;    return x1*y2-x2*y1;}bool inTriangle(triangle t,point P){    point A,B,C;    A=t.A;    B=t.B;    C=t.C;    double Sabc=fabs(crossProduct(A,B,C));printf("abc:%lf ",Sabc);    double Spab=fabs(crossProduct(P,A,B));printf("pab:%lf ",Spab);    double Spac=fabs(crossProduct(P,A,C));printf("pac:%lf ",Spac);    double Spbc=fabs(crossProduct(P,B,C));printf("pbc:%lf ",Spbc);    if(fabs(Sabc-(Spab+Spac+Spbc))<eps)        return true;    else        return false;}bool onSegment(point Pi,point Pj,point Q){    if((Q.x-Pi.x)*(Pj.y-Pi.y)==(Pj.x-Pi.x)*(Q.y-Pi.y)&&//x1*y2=x2*y1    min(Pi.x,Pj.x)<=Q.x&&Q.x<=max(Pi.x,Pj.x)&&    min(Pi.y,Pj.y)<=Q.y&&Q.y<=max(Pi.y,Pj.y))        return true;    else        return false;}int main(){    point p,q,r,s;    scanf("%lf%lf%lf%lf",&p.x,&p.y,&q.x,&q.y);//segment p--q    scanf("%lf%lf",&r.x,&r.y);//point r    scanf("%lf%lf",&s.x,&s.y);//point s    if(onSegment(p,q,r))    {        printf("YES\n");    }    else    {        printf("NO\n");    }    triangle t;    t.A=p;    t.B=q;    t.C=r;    if(inTriangle(t,s))    {        printf("YES\n");    }    else    {        printf("NO\n");    }    return 0;}
View Code