【非原创】一个有趣的数学题，可以给出编程解法

闲人

这是几个月前我遇到的一个编程问题，网上有解法，但是最好自己动手试试，数学嘛，自己解才有意思。
設 A1 (x1 , y1) , A2 (x2 , y2) , … , An (xn,yn) 為 n 邊形之頂點坐標且為逆時針定向，則此 n 邊形的面積為？

Young Villia

7楼提到外点位置该如何选取呢？如果只取给定原点可能会增大数值误差，不妨先做一次坐标变换。
应保证让所有的径矢长度的差距不要太大，同时径矢长度与对应边的长度差距也不要太大。
选取具有最短距离和的点的话或许可以满足上述条件，这个点在构造凸多边形的时候能计算出来。

非凸多边形已知边顺序的情况下可以作凸包分割，遍历边的同时判断边的方向不累计面积，在每个拐点处累计凸包的面积。

此外，既然6楼说了扫描线法，有人考虑一下蒙特卡洛方法吗？

0xAA55

这个嘛，很简单，既然是逆时针方向，那么统计每个三角形的面积最后求和就行了。

闲人

0xAA55 发表于 2014-8-7 04:32
这个嘛，很简单，既然是逆时针方向，那么统计每个三角形的面积最后求和就行了。 ...

有没有更简单的，编程实现，考虑多一点，还有，当时没有说明是逆时针的，有没有想过这些点如果是乱序的话，如何解？

0xAA55

闲人 发表于 2014-8-15 09:05
有没有更简单的，编程实现，考虑多一点，还有，当时没有说明是逆时针的，有没有想过这些点如果是乱序的话 ...

当然想过乱序的，我做过2D物理引擎的时候就接触到。
乱序的话，如果是凸多边形就好办多了。否则就可能有各种组合而导致有不同的解。
我记得Havok和PhysX的物理引擎都有从多个点计算凸多边形物体的功能

向日葵

我想到一个解法，就描述下吧：

既然逆时针图形，那么可以近似的看做为圆形。


首先判定边界，在所有X与Y点中找出X轴和Y轴的极大值和极小值，定义为Xmax、Xmin、Ymax、Ymin，令Sfull=|Xmax-Xmin|*|Ymax-Ymin|，先求出能囊括这个圆形的正方形面积。

再求出正方形不包含该圆形部分的阴影面积，相减就是所求面积。

图形描述

阴影面积由两部分组成，令每个点在Y轴方向上划直线，分割阴影面积，那么可得到四个三角形阴影以及多个梯形阴影。


同时还有：如果一个轴的方向上出现2个点乃至多个点都在极大值、极小值的位置的情况，那么就记下当它们在X轴方向有极大值的A点集合，记为数组AXmax，再在AXmax中找出Y轴上拥有最大值与最小值的两个点AXmaxYmax、AXmaxYmin，同样可得X轴方向有极小值的点AXmixYmax、AXminYmin。
同理不排除Y轴也有类似情况，若有，则也要获得该类点的集合，记为数组Bmax，并筛选出BXmaxYmax、BXminYmax、BXmaxYmin、BXminYmin。



最少4个顶点，最多8个顶点。

接下来的事情就简单了，为方便，这里选定水平方向的X轴为基准，从Y轴方向的顶点出发，先求出上半部分阴影的2个三角形阴影，再向左、向右逐步求出多个梯形阴影面积，公式大家都知道的，我不啰嗦，问题得解。

向日葵

第二个方法，搜索到一个公式，如下图：



用程序实现也能解，实际上这个公式的思路还是分解多边形为多个三角形，求三角形和实现求面积的解。

单个三角形的面积，S△=1/2 * |(x2-x1)(y3-y1)-(x3-x1)(y2-y1)|，本来我也看不出，感觉和上图公式相似，高数早还给老师了！

向日葵

玫瑰花葬礼

很好的一个问题

watermelon

Young Villia 发表于 2020-2-1 11:58
7楼提到外点位置该如何选取呢？如果只取给定原点可能会增大数值误差，不妨先做一次坐标变换。
应保证让所有 ...

哈哈哈哈哈，蒙卡方法是最简单粗暴的，但是随机数量大的时候，效率低，并且只能得到近似解，蒙卡方法效率和精准度是两个矛盾来着。