关于多边形的算法

2009-02-05 14:58

求简单（包括凹）多边形的面积（叉积）：
#include<iostream>
using namespace std;
#define N 20
struct point{
       double x,y;
};
struct polygon{
       point p[N];
       int n;
};
double abs(double x){
       return x>0?x:-x;
}
double S_poly(polygon poly);
int main(void){
    polygon poly;
   
    cout<<"Input the quantity of edges:";
    cin>>poly.n;
    for(int i=0;i<poly.n;i++){
        cout<<"Input p"<<i+1<<":";
        cin>>poly.p[i].x>>poly.p[i].y;
    }
   
    cout<<S_poly(poly);
   
    system("pause");
    return 0;
}
double S_poly(polygon poly){
       double S = 0.0;
      
       for(int i=0;i<poly.n;i++){
           S += poly.p[i].x * poly.p[(i+1)% poly.n].y;
           S -= poly.p[(i+1)% poly.n].x * poly.p[i].y;
       }
      
       return 0.5*abs(S);
}
判断点是否在简单多边形内：
#include<iostream>
using namespace std;
#define N 20
struct point{
       double x,y;
};
struct polygon{
       point p[N];
       int edges;
};
point operator-(point p1,point p2){
      point r;
     
      r.x = p1.x - p2.x;
      r.y = p1.y - p2.y;
     
      return r;
}
double min(double x,double y){
       return x<y?x:y;
}
double max(double x,double y){
       return x>y?x:y;
}
bool inside_polygon(point p,polygon poly);
bool R_ray_intersect(point p,point p1,point p2);
double vp(point p1,point p2);
bool on_segment(point p,point p1,point p2);
int main(void){
    polygon poly;
    point p;
   
    cout<<"Input the quantity of edges:";
    cin>>poly.edges;
    for(int i=0;i<poly.edges;i++){
        cout<<"Input p"<<i+1<<":";
        cin>>poly.p[i].x>>poly.p[i].y;
    }
   
    cout<<"Input p:";
    cin>>p.x>>p.y;
   
    if(inside_polygon(p,poly) ) cout<<"Inside!"<<endl;
    else cout<<"Outside!"<<endl;
   
    system("pause");
    return 0;
}
bool inside_polygon(point p,polygon poly){
     int n;
    
     n = 0;
     for(int i=0;i<poly.edges;i++){//注意顺序！

        if(vp(poly.p[(i+1)%poly.edges ] - poly.p[i], poly.p[(i+1)%poly.edges ] - p)==0.0&&
           on_segment(p,poly.p[(i+1)%poly.edges ],poly.p[i]) )
           return true;
        if(p.y==min(poly.p[i].y,poly.p[(i+1)%poly.edges ].y) ) continue;
        if(poly.p[i].y == poly.p[(i+1)%poly.edges ].y) continue;
        if(R_ray_intersect(p,poly.p[i],poly.p[(i+1)%poly.edges ]) ) n++;
     }
    
     if(n%2==0) return false;
     return true;
}
bool R_ray_intersect(point p,point p1,point p2){
     return p.x<=max(p1.x,p2.x) &&
            p.y>=min(p1.y,p2.y) &&
            p.y<=max(p1.y,p2.y);
}
double vp(point p1,point p2){
       return p1.x*p2.y - p2.x*p1.y;
}
bool on_segment(point p,point p1,point p2){
     return p.x>=min(p1.x,p2.x) && p.x<=max(p1.x,p2.x) &&
            p.y>=min(p1.y,p2.y) && p.y<=max(p1.y,p2.y);
}