网页版几何画板开发笔记(十) 计算任意带交错多边形的面积

对于一般不带交错的多边形, 有一个简单的方法可以计算出其面积, 见于网上很多文章都有, 如:
http://wenku.baidu.com/link?url=h48pnBshRsf0QzG9Cvgp22PXNqbpfX97uyfkDceUwm9zfECjmm5mS56Yj4zNa_zpZs5Fi36O2KOKDansWgCGMt5wCpErZ-ttAldF_p7zln3

如图所示的一个带交错的五边形, 不算内部那个被交错部分的面积的算法, 思路如下:

1. 已知所有的边, 计算这些边相互的交点(如图所示, 这些交点为I1,I2,I3,I4,I5). 如果边之间没有
交点, 则当做普通多边形计算即可.

2. 将所有的顶点和交点按照y坐标自上而下的排序, 过这些点做水平线, 这些水平线分割整个多边形
为多个条, 如图所示是两个条带的例子.

3. 可以证明(严格证明我不太擅长, 下面一会略略说下), 条带之间切割的边是偶数条. 将这些边从左
到右排序并从0开始编号, 则偶数编号的边&奇数编号的边 构成的梯形(或三角形)算在面积中. 反之
的, 不算在面积中.

4. 累加所有条带, 所有算在内的梯形或三角形的面积, 即可得到多边形的总面积.

在这个图中的例子, 条带1 中有三角形 AMN;
条带2 中有梯形 MNJI₅, 三角形 CI₅K 算在面积内.

这种方法最终计算出来的面积, 是不包含中间I1-I5 构成的交错部分的. 欲计算含该部分的,
我思考有另一种算法更合适一些. 但此算法, 也许适当改进一些, 也能计算吧.

  下面简单说明(3)中偶数条边的证明. 从第一个条带开始, 上面有且只有一个点设为A, 则A必有
两条边(一条入边, 一条出边)与条带的下边界相交(如图中交点M,N), 这样构成两条边, 是偶数.
  而下一个条带, 这种交点有偶数个, 每个交点有一条边; 又新的一个点也有两条边, 加起来
仍然是偶数条边.
  如果顶点就是条带与边的交点, 则此顶点的入边必算在前一个条带, 此条带中只有一条边, 这样
加起来仍然是偶数条边.
  还有别的情况, 如条带的上下边界恰好与边重合, 则出/入抵消, 仍是偶数条.

我编写了一个简单程序, 用如上的五角星测试了此算法, 基本还算对的, 但是估计浮点数计算会
有误差, 在边界条件的情况下可能要特别注意.

如果你看到此算法有问题, 可帮忙评论或邮件给 [email protected] , 谢谢~!