首页 > 代码库 > 判点在直线上,三角形内
判点在直线上,三角形内
判断点在直线上,需要满足两个条件,如判断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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。