初学计算几何（三）——多边形的简单操作

前言

去学习了一下一些多边形相关的简单操作。

多边形

下面是一个多边形的基本定义：

struct Polygon//一个结构体用来存储一个多边形
{
    int n;Point p[10005];//n存储点数，P数组存储点
    Polygon() {n=0;}//构造函数
};

精度控制

在多边形问题中，我们需要好好控制精度：

#define eps 1e-10//设置eps减小精度误差
inline int dcmp(double x) {return fabs(x)<eps?0:(x>0?1:-1);}//判断正负

判断一个点是否在多边形内部

我们可以以该点向外引一条射线，如果与多边形边界相交奇数次，就说明该点在多边形内，否则就在多边形外。

特殊地，如果该点在多边形边上，我们可以返回(-1)。

代码如下：

inline int IsInPolygon(Point A,Polygon P)//判断一个点是否在多边形内部
{
	register int i,flag=0,k,d1,d2;
	for(i=1;i<=P.n;++i)//枚举边
	{
    	if(!dcmp(PToS(A,Segment(P.p[i],P.p[i%P.n+1])))) return -1;//如果点在边上，返回-1
    	k=dcmp(Cro(P.p[i%P.n+1]-P.p[i],A-P.p[i])),d1=dcmp(P.p[i].y-A.y),d2=dcmp(P.p[i%P.n+1].y-A.y),
    	k>0&&d1<=0&&d2>0&&++flag,k<0&&d1>0&&d2<=0&&--flag;//更新flag
	}
	return flag?1:0;//flag>0表示在多边形内部，否则说明在多边形外部
}

求多边形面积

求多边形面积，我们可以选一个点作为端点，然后枚举与它不相临的边，计算出该点与这些边所构成的三角形的面积和即可。

代码如下：

inline double PolygonArea(Polygon P)//求多边形面积
{
	register int i;register double res=0;//res统计和
	for(i=2;i<P.n;++i) res+=Cro(P.p[i]-P.p[1],P.p[i+1]-P.p[1])/2;//计算由1号节点，i号节点，i+1号节点构成的三角形面积
	return res;//返回答案
}

后记

关于多边形的内容貌似就这些？

如果还有的话我会继续进行补充的。