随笔-8  评论-5  文章-0  trackbacks-0
解该题分为两步:
  1. 确定多边行的有效性
  2. 计算面积

确定多边形的有效性算法如下:

  • 如果该多边形的边数小于3,则视为无效
  • 如果该多边形的变数等于3,视为有效
  • 如果变数大于3,则对于没一条边,确保与它相邻的边不与它重合,与它不相邻的边,不与它相交。

为检查线段(i, k)和(k, j)重合,只需:

  • (i, k)和(k, j)平行,即(i, k)×(k, j)=0
  • j在以i, k为对角的矩形内,或i在以j, k为对角的矩形内。

为检查线段(i, j)与线段(m, n)是否相交,只需:

  • (i, m)×(m, n)与(j, m)×(m, n)异号,则线段(i, j)与直线(m, n)相交
  • (m, i)×(i, j)与(n, i)×(i, j)异号,则线段(m, n)与直线(i, j)相交
  • 如果以上两点同时成立,则可得出线段(m, n)与线段(i, j)相交
  • 如果以上叉乘有任何一个为0,如(i, m)×(m, n)==0,则如果i在线段(m, n)上,则相交

最后一步要计算面积,可以用测量师公式(A Surveryor's formula):

一个n边形A1,A2,A3,...,An,其顶点按逆时针方向配置,且坐标分别为

Ak = (xk, yk),k=1, 2, 3,...,n

则面积为:

        n
       ----   | Xk   X(k+1) |
       \        |                 |
1/2* /       |                 |
       ----   | Yk   Y(k+1) |
       k=1
其中,X(k+1) = X1, Y(k+1)=Y1

posted on 2005-08-02 23:47 pumpkin 阅读(746) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。