注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

风的驿站

一徐清风,半指烛光,觥筹已净,只余茶香。残卷一章,妙趣非常,忽闻帘响,愿闻其详?

 
 
 

日志

 
 
关于我

喜欢写生 编程 音乐 设计 喜欢把自己的想法变成实实在在的东西 喜欢安静的做一些事情 CSDN博客:http://blog.csdn.net/qwertyupoiuytr

网易考拉推荐

【原创】根据凸多边形顶点坐标来计算面积算法与实现  

2014-08-22 15:55:54|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

本文我们来介绍一下如何利用凸多边形的所有顶点的坐标来计算其面积,并使用该算法制作一个小的示例程序。

注:对于凹多边形的面积,可以将其分解为若干个凸多边形分别计算求和,关于凹多边形的分解算法请参考Box2d中使用b2Separate开源代码创建凹多边形及其算法分析

求解的思路其实非常简单,对于任何凸多边形,我们以它的任意一个顶点为一个端点,连接该顶点与其他所有的顶点得到若干条线段,就可以将这个多边形切割成若干个三角形,如下图:

【原创】根据凸多边形顶点坐标来计算面积算法与实现 - 远行的风 - 风的驿站

对于得到的任何一个三角形,它的三个顶点都是多边形的顶点,因此其坐标是已知的(我们假定多边形的顶点坐标为已知量)。那么我们就可以利用三个顶点的坐标求解每一个三角形的面积(关于如何利用坐标求解三角形面积,请参考游戏中两个常用的数学运算推导即算法推论)。于是我们得到下面的算法步骤:

对于给定的顶点数组vertexes,数组大小为n(即n边形),我们选取第一个顶点vertexes[0]作为起点,从i=1开始,一直循环到i=n-2,每次计算顶点vertexes[0]vertexes[i]vertexes[i+1]组成的三角形面积,将从1n-2次循环得到的所有三角形的面积累加起来,就得到了vertexes围成的多边形的面积。

如果给定的顶点数组不是按照顺时针或者逆时针的顺序排列,而是乱序的,可以对顶点进行重新排序,具体算法请参考Box2D中切割刚体效果的实现一览(完)reorderVertexes的方法实现。

下面我们来制作一个小例子,先来看一下最终的运行效果(使用的是Box2d 2.3.1的模板创建的工程):

【原创】根据凸多边形顶点坐标来计算面积算法与实现 - 远行的风 - 风的驿站

在屏幕上任意绘制一个凸多边形,然后最上方显示出所绘制的多边形的面积。

关于如何绘制多边形,记录所绘制的顶点以及将绘制的路径显示在场景中,请参考Box2d中使用开源的PRKit库来制作任意形状的多边形刚体的纹理。我们将绘制的颜色改为红色(因为要添加的参考网格的颜色想要使用白色,当然也可以按照自己的喜好来设置)。

接着添加绘制参考网格的方法:

-(void) drawGrids {

    CGSize size = [[CCDirector sharedDirector] winSize];

    float winHeight = size.height;

    float winWidth = size.width;

    int verCount = winWidth / PTM_RATIO;

    int horCount = size.width / PTM_RATIO;

    for (int i = 1; i < verCount-5; i++) {

        ccDrawLine(ccp(0, i*PTM_RATIO), ccp(winWidth, i*PTM_RATIO));

    }

    for (int i = 1; i < horCount; i++) {

        ccDrawLine(ccp(i*PTM_RATIO, 0), ccp(i*PTM_RATIO, winHeight));

    }

}

方法比较简单,我们知道Box2d中单位“米”与像素的转换比例就是PTM_RATIO,因此我们使用这个转换比例来作为相邻网格线的间距,这样单个网格的面积就是1平方米。同样,我们将绘制路径的取样距离也设置为PTM_RATIO,这样方便我们验证结果。

下面两个算法一个是计算三角形面积的算法,另一个是计算多边形面积的算法:

-(float) calculatePolygonArea:(NSMutableArray*) vertexes {

//    vertexes = [self reorderVertexes:vertexes];

    float result = 0;

    int vertexCount = [vertexes count];

    CGPoint startPoint = [vertexes[0] CGPointValue];

    for (int i = 1; i < vertexCount - 1; i++) {

        result += [self calculateTriangleArea:startPoint pointB:[vertexes[i] CGPointValue] pointC:[vertexes[i+1] CGPointValue]];

    }

   

    return result;

}

 

-(float) calculateTriangleArea:(CGPoint) pointA

                        pointB:(CGPoint) pointB

                        pointC:(CGPoint) pointC {

    float result =  (pointA.x * pointB.y + pointB.x * pointC.y + pointC.x * pointA.y

                     - pointA.y * pointB.x - pointB.y * pointC.x - pointC.y * pointA.x) * 0.5f;

    return result > 0 ? result : -result;

}

实现之后,在ccTouchEnded方法中调用calculatePolygonArea即可。

 

这里我能想到的两个关于实际物理模拟的过程中的应用情景:

一个是计算物体的质量,根据物体的密度和顶点坐标,可以计算出物体的质量。

另一个应用场景是可以通过面积来计算在液体中物体受到的浮力,因为我们知道浮力F等于液体密度乘以重力常量再乘以物体排开液体的体积(对于2D来说,体积就变成了面积),而物体在水中是一个动态的过程,因此可以通过求解物体水面以下的面积来实时地计算浮力。

 

好了,教程就写到这儿,如果有问题欢迎留言。

  评论这张
 
阅读(255)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017