上海王2推迟上映:判断点是否在三角形内的算法-收集备用

设三角形三个点A(a1,a2),B(b1,b2),C(c1,c2)三条边方程BC:fa(x,y)=0AC:fb(x,y)=0AB:fc(x,y)=0以BC为例，在三角形内的点必须与点A在BC的同侧所以对于点D(x,y)在三角形内首先要满足fa(x,y)*fa(a1,a2)>0其他边也同理所以只要比较fa(x,y)*fa(a1,a2)fb(x,y)*fb(b1,b2)fc(x,y)*fc(c1,c2)这三个数的正负性1三个数都是正数：D在三角形内2至少有一个负数：D在三角形外3有且只有一个0，另两个为正数：在三角形边上4有且只有一个0，一个正数一个负数：在三角形边的延长线上，也算在三角形外，因为满足25有二个0：在三角形的顶点上6不可能出现3个0，或3个负数，或一个0两个负数的情况 

＝＝＝＝＝＝＝＝＝

4. 

一、调用API。
view sourceprint?                        BOOL PtInRegion(                                      HRGN hrgn,  // handle to region                                      int X,      // x-coordinate of point                                      int Y       // y-coordinate of point                                    );                                                                         HRGN CreatePolygonRgn(                                      CONST POINT *lppt,  // array of points                                      int cPoints,        // number of points in array                                      int fnPolyFillMode  // polygon-filling mode                                    );            
二、
设三角形为ABC  所判断点为P  area表示面积函数 

判断 area(PAB)+area(PAC)+area(PBC)-area(ABC)与0关系 

大于0  则在三角形外部 

等于0  则在三角形内部 
 
三、http://www.cnblogs.com/aoyihuashao/archive/2009/12/28/1633810.html
设三角形三个点 
A(a1,a2),B(b1,b2),C(c1,c2) 
三条边方程 
BC:fa(x,y)=0 
AC:fb(x,y)=0 
AB:fc(x,y)=0 
以BC为例，在三角形内的点必须与点A在BC的同侧 
所以对于点D(x,y) 
在三角形内首先要满足fa(x,y)*fa(a1,a2)>0 
其他边也同理 
所以只要比较 
fa(x,y)*fa(a1,a2) 
fb(x,y)*fb(b1,b2) 
fc(x,y)*fc(c1,c2) 
这三个数的正负性 
1三个数都是正数：D在三角形内 
2至少有一个负数：D在三角形外 
3有且只有一个0，另两个为正数：在三角形边上 
4有且只有一个0，一个正数一个负数：在三角形边的延长线上，也算在三角形外，因为满足2 
5有二个0：在三角形的顶点上 
6不可能出现3个0，或3个负数，或一个0两个负数的情况
＝＝＝＝＝＝＝
5. 判断点是否在三角形内（来自csdn)
http://lhs8600.ycool.com/post.2853038.html
设   ap×ab   代表矢量ap与ab的矢性积，其坐标表达式为   
        ap×ab   =   (xp-xa)*(yb-ya)-(yp-ya)*(xb-xa)   
  于是判别过程如下：   
    
  若   ap×ab>0   and   bp×bc>0   and   cp×ca>0   或   ap×ab<0   and   bp×bc<0   and   cp×ca<0   
  则可判定p在△abc内。   
    
  若   ap×ab=0   and   (bp×bc>0   and   cp×ca>0   或   bp×bc<0   and   cp×ca<0)   
  或   bp×bc=0   and   (ap×ab>0   and   cp×ca>0   或   ap×ab<0   and   cp×ca<0)   
  或   cp×ca=0   and   (ap×ab>0   and   bp×bc>0   或   ap×ab<0   and   bp×bc<0)   
  则可判定p在△abc轮廓上。   
    
  否则，p在△abc在外。 

int   inside4(const   struct   TPoint   tr[],   struct   TPoint   p)   
  ...{   
  struct   TPoint   arr[3];   
  memcpy(arr,tr,sizeof(arr));   
  for(int   i=0;i<3;i++)   //   求三个向量   
  ...{   
  arr[i].x   =   tr[i].x   -   p.x;   
  arr[i].y   =   tr[i].y   -   p.y;   
  }   
  for(i=0;i<3;i++)     //   判断是否在边界上   
  ...{   
  int   j=(i+1)%3;   
  if(   arr[i].x*arr[j].y-arr[i].y*arr[j].x==0   )     //点在边界上，向量对称   
  ...{   
  if(   arr[i].x*arr[j].x>0   ||   arr[i].y*arr[j].y>0   )   return   0;//   同方向   
  return   1;                                                                   //   方向相反   
  }   
  }   
  for(i=0;i<2;i++)   //   判断在内还是外，在此只需判断两个向量，下有说明【注1】   
  ...{   
  int   front   =   (i+2)%3,   next   =   3-i-front;   
  int   cnt   =   0;   
  int   t1   =   arr[i].y*arr[front].x   -   arr[front].y*arr[i].x;   
  int   t2   =   arr[i].y*arr[next].x     -   arr[next].y   *arr[i].x;   
  if(   (t1>0)+(t2>0)!=1   )   return   0;   //向量分布在同一侧，则在外；否则不能确定   
  }   
  return   1;   //   三个向量都在不同两侧，则在内   
  //   【注1】：如果三个向量分布在同一侧，则必定有两个向量使得另外的两个向量在该向量的同一侧   
  //                         a   b   c   
  //                     如   |/   三条线，b,c在a的一边，   a,b在c的一边，所以a,b,c中有两条线都可以判断   
  //                     a,b,c三个向量对应的三个顶点在三个向量原点的一个方向，所以该点不在此三角形中   
  }   

＝＝＝＝＝＝＝＝＝＝＝＝＝
6.判断点是否在三角形内(C++测试代码)
http://www.csplace.cn/html/Program/Software/CPP/185.html










/*--------------------------------------------------------------------- 
//file name:InTriangleOrNot.cpp 
//Coder: rainday163 
//E-mail: rainday1631@163.com 
//Create date: 2009.11.19 
//Last modify date: 2009.11.20 
//Test platform: WinXP sp2 & Dev-C++ 4.9.9.2 
---------------------------------------------------------------------*/ 
//判断点是否在三角形内部 

#include  
#include  
class Point//点类  
{ 
public: 
   Point():x(0),y(0) 
   {} 
   Point(double Vx,double Vy):x(Vx),y(Vy) 
   {} 
   Point(Point &p) 
   { 
    this->x=p.x; 
    this->y=p.y; 
   } 
   Point &operator=(const Point &p) 
   { 
    if(this==&p) 
    { 
     return *this; 
    } 
    this->x=p.x; 
    this->y=p.y; 
    return *this; 
   } 
   double x,y; 
}; 

class Segment//线段类  
{ 
public: 
   Segment() 
   { 
    begin.x=0,begin.y=0; 
    end.x=0,end.y=0; 
   } 
   Segment(Point A,Point B) 
   { 
    begin=A; 
    end=B;    
   } 
   Point begin,end; 
}; 

enum Direct{left,right}; 
class Half_Line//射线类  
{ 
public: 
   public: 
    Half_Line():x(0),y(0) 
    { 
     source.x=x,source.y=y; 
    } 
    Half_Line(Point &p,Direct d) 
    { 
     x=p.x,y=p.y; 
     source=p; 
     direction=d; 
    } 
    double x,y; 
    Point source; 
    enum Direct direction; 
}; 

class Triangle//三角形类  
{ 
public: 
   Triangle() 
   {} 
   Triangle(Point AP,Point BP,Point CP) 
   { 
    A=AP,B=BP,C=CP; 
    AB.begin=A,AB.end=B; 
    BC.begin=B,BC.end=C; 
    AC.begin=A,AC.end=C; 
   } 
   Point A,B,C; 
   Segment AB,BC,AC; 
}; 

// 计算向量AB与向量AC的叉积 
double multi(Point const &A,Point const& B,Point const& C) 
{ 
Point AB(B.x-A.x,B.y-A.y); 
Point AC(C.x-A.x,C.y-A.y); 
return (AB.x*AC.y - AB.y * AC.x); 
} 

bool PointOfSegment(Point P,Segment L)//判断点是否在线段上  
{ 
Point AP,AB; 
AP.x=P.x-L.begin.x , AP.y=P.y-L.begin.y ; 
AB.x=L.end.x-L.begin.x , AB.y=L.end.y - L.begin.y ; 
double TempResult = AP.x * AB.y - AP.y * AB.x ; 
if(fabs(TempResult)<(double)1e-6 \ 
&& P.x >= L.begin.x && P.x <= L.end.x) 
{ 
   return true; 
} 
return false; 
} 
//若线段AB和CD能同时通过快速排斥试验和跨立试验则返回true 
// 否则返回false 
bool SegmentCross(Segment AB,Segment CD) 
//A、B为AB的端点，C、D为CD的端点  
{ 
Point A,B,C,D; 
A=AB.begin,B=AB.end; 
C=CD.begin,D=CD.end; 
if( ( std::max(A.x,B.x) >= std::min(C.x,D.x) ) 
    &&( std::max(C.x,D.x) >= std::min(A.x,B.x) ) 
    &&( std::max(A.y,B.y) >= std::min(C.y,D.y) ) 
    &&( std::max(C.y,D.y) >= std::min(A.y,B.y) ) 
    &&( multi(C,A,D) * multi(C,B,D) <=0 ) 
    &&( multi(A,C,B) * multi(A,D,B) <=0 ) 
   ) 
   return true; 
return false; 
} 

bool CrossOrNot(Half_Line &P,Segment &L) 
//判断水平方向上射线是否与线段相交  
{ 
Point temp; 
if(P.direction == left) 
{ 
   temp.x=L.begin.x,temp.y=P.y; 
} 
if(P.direction == right) 
{ 
   temp.x=L.end.x,temp.y=P.y; 
} 
Point Ptemp=P.source; 
Segment OP(temp,Ptemp); 
if(!SegmentCross(OP,L)) 
{ 
   return false; 
} 
return true;   
} 
//测试代码 
int main() 
{ 
Point A,B,C,P; 
std::cout<<"Please input A,B,C:"<std::cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y; 
std::cout<<"Please input P:"<std::cin>>P.x>>P.y; 
Triangle ABC(A,B,C); 
Half_Line PB(P,left),PC(P,right); 
if(PointOfSegment(P,ABC.AB) || PointOfSegment(P,ABC.AC) || PointOfSegment(P,ABC.BC)) 
{ 
   std::cout<<"点在三角形上"<} 
else if(CrossOrNot(PB,ABC.AB) && CrossOrNot(PC,ABC.AC)) 
{ 
   std::cout<<"在内部"<} 
else 
{ 
   std::cout<<"在外部"<} 
std::cin.get(); 
std::cin.get(); 
return 0; 
}