计算几何
程序员文章站
2022-04-01 12:46:47
...
多边形重心问题
时间限制：3000 ms | 内存限制：65535 KB
难度：5
- 描述
- 在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接， （第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；
如果是一条线段,我们定义面积为0，重心坐标为（0,0）.现在求给出的点集组成的图形的面积和重心横纵坐标的和；- 输入
- 第一行有一个整数0<n<11,表示有n组数据；
每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点； - 输出
- 输出每个多边形的面积、重心横纵坐标的和，小数点后保留三位；
- 样例输入
-
3 3 0 1 0 2 0 3 3 1 1 0 0 0 1 4 1 1 0 0 0 0.5 0 1
- 样例输出
-
0.000 0.000 0.500 1.000 0.500 1.000
导读：一开始还以为是图论里面同色三角形，后来计算多边三角形面积才懵B。也算是纪念第一次解答计算几何吧（好久没写博客了QAQ）
重要定义：
密度积分：分两个，x方向和y方向。那么x方向的积分就变成了对所有的三角形把 三角形的面积*该三角形重心的x坐标
的积加起来，
同理y方向的积分就变成了对所有三角形把三角形的面积*该三角形重心的y坐标
的积加起来。
重心：就是重量的中心。其定义就是对整个图形分别从x方向和y方向进行密度积分，然后除以总面积，就得到了重心的x坐标和y坐标。
知识储备：1 > 任何多边形都可划分成为任意多个三角形
2> 无论规则三角形还是不规则，积分通吃，即三角形面积 area= x i * y (i + 1) - y i * x （i + 1）; (i = 1 .......
n 其中n 为所有边的情况, xi, yi即为每一点的坐标，只需2点即可, 还一点默认看成 （0，0） ）
（参考文献：:// www.cnblogs.com/xiexinxinlove/p/3708147.html)
(注：这里是用叉乘的方式求三角形面积,故不能将面积设成正数)
重心坐标 gravityx = （area (i)* 每一小个三角形重心坐标）/ area
（注：这里area(i)是上述每一个小三角形的和，每次求解重心坐标即(xi + xi + 1) / 3.0）
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define INT 0.0000001
struct Node{
double x;
double y;
}mynode[1000];
//计算微分中三角形面积
double Area(Node a, Node b){
return a.x * b.y - a.y * b.x;
}
int main(void){
int i, j, N, M;
double temp, area, gravityx, gravityy;
cin>>N;
while(N--){
area = 0.0;
gravityx = 0.0;
gravityy =0.0;
//数据的初始化
cin>>M;
for(i = 0; i < M; i++)
cin>>mynode[i].x>>mynode[i].y;
for(i = 1; i <= M; i++){
temp = Area(mynode[(i - 1) % M], mynode[i % M]) / 2.0; //微分三角形面积
// temp = fabs(temp);
area += temp;
gravityx += temp * (mynode[(i - 1) % M].x + mynode[i % M].x) / 3.0;
gravityy += temp * (mynode[(i - 1) % M].y + mynode[i % M].y) / 3.0;
}
area = fabs(area);
if(area < INT)
printf("0.000 0.000\n");
else
printf("%.3lf %.3lf\n", area, fabs(gravityx + gravityy) / area);
}
return 0;
}
启示：这次不仅学到了怎么计算多边三角形面积，还搞定了重心的微分求解，另外给几点拓展知识吧：
1> fabs是针对double，float用的
2> 由于三角形面积可能会很小故加入,INT = 0.0000001
3> 外面加入fabs是因为求总的面积,不能为负数，再保证各个数据的类型正确，防止wa就很方便了,另外别忘记把gravityx,gravityy初始化0.0
4>对于三点一线即同线的三角形，即面积为0，不会加入计算
（2017年1月4日6：12pm纪念第一次入门计算几何以及宜昌下雪 QWQ）