文章目录

多边形相关点与多边形的位置关系（内部和外部）求多边形的重心 凸包持续更新。。。。。。

多边形相关

前面讲过求多边形的面积，今天再多分析两例问题：

点与多边形的位置关系多边形的重心

点与多边形的位置关系（内部和外部）

假设有一点P，我们需判断和多边形的位置关系 思路： 以P点引一条水平线，按一个方向统计P与多边形每条边相交的情况 定义三个参数： c=Cross( P - j , i - j ) u= i.y - P.y v= j.y - P.y 叉积c用来检查P点在线段ij的左侧还是右侧，u，v用来检查经过P的水平线是否穿过线段ij。 用num计数，当num>0时，P在多边形内部

if (c>0&&u<0&&v>=0) num++; if (c<0&&u>=0&&v<0) num--;

以下是全部代码：

int Point_in_polygon(Point pt,Point *p,int n){ 点pt,多边形Point *p for (int i=0;i<n;i++){ if (p[i]==pt) return 3; //3：点在多边形顶点上 } for (int i=0;i<n;i++){ Line v = Line(p[i],p[(i+1)%n]); if (Point_on_seg(pt,v)) return 2; //2:点在多边形的边上 } int num=0; for (int i=0;i<n;i++){ int j=(i+1)%n; int c=sgn(Cross(pt-p[j],p[i]-p[j])); int u=sgn(p[i].y-pt.y); int v=sgn(p[j].y-pt.y); if (c>0&&u<0&&v>=0) num++; } return num!=0; //1:在内部 2：在外部 }

求多边形的重心

将多边形三剖分，然后对每个三角形的有向面积求加权平均

double Polygon_area(Point *p,int n){ double area=0; for (int i=0;i<n;i++){ area+=Cross(p[i],P[(i+1)%n]); } return area/2; } Point Polygon_center(Point *p,int n){ Point ans(0,0); double area=Polygon_area(p,n); if (area==0) return ans; for (int i=0;i<n;i++){ ans=ans+(p[i]+p[(i+1)%n])*Cross((p[i],p[(i+1)%n); } return ans/area/6; }

凸包

时间复杂度nlogn 1.对点进行排序，x坐标小的优先，x坐标相同的，y坐标小的优先。 假设排序后得到序列{p1,p2,p3,…,pn} 2.从左到右扫描求出“下凸包”，如下图所示p0,p1,p2,p3还能构成“下凸包”，p4加入时，发现p4p3对p3p2是右拐的的，所以p3不符合题意，我们退回到p2,发现p4p2对p2p1也是右拐的，退回到p1;

int Convex_hull(Point *p,Point *ch,int n){ sort(p,p+n); n=unique(p,p+n)-p; int v=0; for (int i=0;i<n;i++){ while (v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--; ch[v++]=p[i]; } int j=v; for (int i=n-2;i>=0;i--){ while (v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--; ch[v++]=p[i]; } if (n>1) v--; return v; }

持续更新。。。。。。