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

闲人

这是几个月前我遇到的一个编程问题，网上有解法，但是最好自己动手试试，数学嘛，自己解才有意思。
設 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)|，本来我也看不出，感觉和上图公式相似，高数早还给老师了！

向日葵

找到了相关的算法资料，任意多边形面积计算：
http://www.cnblogs.com/vbspine/archive/2013/03/28/2987818.html
原来我第一个方法是所谓的扫描线算法，我感觉也是有些复杂，第二个方法才是主流啊。
直接拷贝了。
任意多边形的面积可由任意一点与多边形上依次两点连线构成的三角形矢量面积求和得出。

       矢量面积=三角形两边矢量的叉乘。

       如下图：


按定理，多边形面积由P点与A-G的各顶点连接所构成的三角形矢量面积构成，假定多边形顶点坐标顺序为A-G，逆时针为正方向，则有如下结论：

PAB,PBC,PCD均为顺时针，面积为负；

PDE，PEF，PFG，PGA均未逆时针，面积为正；

但无论正负，均可通过P点与顶点连线的矢量叉乘完成，叉乘结果中已包含面积的正负。

什么是矢量叉乘我早就还给老师，得去补课了。。。{:soso_e110:}

上文后面还有实现程序，有兴趣的自己去看吧。

玫瑰花葬礼

很好的一个问题

watermelon

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

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