欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算几何之用叉乘求多边形面积

程序员文章站 2022-04-01 17:55:42
...

一、理论基础

二维向量叉乘得到的是对应平行四边形的有向面积,所以,只要保证按照逆时针对点排序,以下的算法都是可行的:

①凸多边形,选取一个A0,从A1开始依次挑选相邻的两个点,求三角形面积,求和即可

②非凸多边形,同上法,由于算的是有向面积,正负抵消就可以得到面积

③任意多边形,选取其边外一点A0,同上法,答案亦相同

可见有向面积的定义比起纯粹的面积定义更本质

二、例题

codevs1249题目弱了一点,但是还是一道入门好题

point p[110];
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i].x>>p[i].y;
	}
	double sum=0;
	point A0=p[0];
	for(int i=1;i<n-1;i++){
		point Ai=p[i],Aj=p[i+1];
		sum+=cross(Ai-A0,Aj-A0)/2;
	}
	cout<<sum;
}