wan.cpp

对各种图形判别程序

#include "stdio.h" 
#include <math.h> 
#include "conio.h" 
#include "Graphics.h" 
const double INFINITY  = 1e10; 
const double ESP = 1e-5; 
const int MAX_N= 1000; 

struct Point { 
  int x, y; 
}; 

struct LineSegment { 
 struct Point pt1, pt2; 
}; 


int n, m,count; 
struct Point polygon[1000]; 
struct Point P; 

void initgr(void) /* 图形初始化 */ 
{  int gd=DETECT,gm=0; 
  registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */ 
  initgraph(&gd,&gm,""); 
} 

int max(int x, int y) 
{ 
  return (x > y ? x : y); 
} 

int min(int x, int y) 
{ 
  return (x < y ? x : y); 
} 

/*计算叉乘 |P1P0| × |P2P0|*/ 
int Multiply(struct Point p1, struct Point p2,struct Point p0) 
{ 
return ( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) ); 
} 

/* 判断线段是否包含点point */ 
int IsOnline(struct Point point, struct  LineSegment line) 

{ 
return( ( fabs(Multiply(line.pt1, line.pt2, point)) < ESP ) && 
( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) <= 0 ) && 
( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) <= 0 ) ); 
} 

/* 判断线段相交 */ 
int Intersect(struct LineSegment L1, struct LineSegment L2) 
{ 
return( (max(L1.pt1.x, L1.pt2.x) >= min(L2.pt1.x, L2.pt2.x)) && 
           (max(L2.pt1.x, L2.pt2.x) >= min(L1.pt1.x, L1.pt2.x)) && 
           (max(L1.pt1.y, L1.pt2.y) >= min(L2.pt1.y, L2.pt2.y)) && 
           (max(L2.pt1.y, L2.pt2.y) >= min(L1.pt1.y, L1.pt2.y)) && 
           (Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) >= 0) && 
           (Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply(L2.pt2, L1.pt2, L2.pt1) >= 0) 
         ); 
} 


/* 判断点在多边形内*/ 
int InPolygon(struct Point polygon[], int n, struct Point point) 
{ 
if (n == 1) { 
      return ( (fabs(polygon[0].x - point.x) < ESP) && (fabs(polygon[0].y - point.y) < ESP) ); 
                  } 
else if (n == 2) { 
          struct LineSegment side; 
          side.pt1 = polygon[0]; 
          side.pt2 = polygon[1]; 
          return IsOnline(point, side); 
                   } 
else{ 
  int count=0,i=0; 
  struct LineSegment line; 
  line.pt1 = point; 
  line.pt2.y = point.y; 
  line.pt2.x = -INFINITY; 

  for( i=0;i< n;i++) 
    { 
/* 得到多边形的一条边 */ 
      struct LineSegment side; 
      side.pt1=polygon; 
      side.pt2=polygon[(i + 1) % n]; 

     if( IsOnline(point, side) ) { 
     return 1; 
     } 

/* 如果side平行x轴则不作考虑 */ 
if( fabs(side.pt1.y - side.pt2.y) == 0 ) { 
continue; 
} 

if( IsOnline(side.pt1, line) ) { 
                  if( side.pt1.y > side.pt2.y ) count++; 
                                 } 
else if( IsOnline(side.pt2, line) ) { 
           if( side.pt2.y > side.pt1.y ) count++; 
                                    } 
else if( Intersect(line, side) ) 
          { 
           count++; 
           } 
}   /* end of for */ 

   return ( count % 2 == 1 ); } 
} 



main() 

{ 
   int a,Result; 
  int PXY[1000]; 
  char c; 

  printf("**********************判断点是否在多边形内(李维靖)**********************\n"); 
  printf("Please Enter '1' to Start！\n"); 
  c=getch(); 
  loop:if (c=='1'){printf("Please Enter the polygon's side num:\n"); 
  scanf("%d",&n); 
  printf("You want draw a %d polygon\n",n); 
  for(a=0;a<n;a++) 
   { 
     printf("Please enter %d x：\n",a+1); 
     scanf("%d",&polygon[a].x); 
     printf("Please enter %d y：\n",a+1); 
     scanf("%d",&polygon[a].y); 

     PXY[(2*a+1)]=polygon[a].y; 
     PXY[2*a]=polygon[a].x; 
     if(a==0){ 
          PXY[2*n]=polygon[a].x; 
           PXY[2*n+1]=polygon[a].y; 
             } ; 
     printf("%d %d OK!\n",polygon[a].x,polygon[a].y); 

   } 
      ; 
  initgr(); 
  drawpoly(n+1,PXY); 
  printf("please enter X:\n"); 
  scanf("%d",&P.x); 
  printf("please enter Y:\n"); 
  scanf("%d",&P.y); 

  putpixel(P.x,P.y,4); 
  printf("Start check:\n"); 

  Result=InPolygon(polygon,n,P); 
  if (Result==1)  printf("InPolygon\n"); 
  else   printf("OutPolygon\n"); }; 
  printf("If you want continue please enter '1',else if you want quit please enter any other key:\n"); 
  if(getch()=='1'){c='1';goto loop;} 

}