圆并面积的算法及其程序实现

动态计算圆弧并面积计算科学与技术学院0704班武汉科技大学陈绪伟问题概述提纲动态计算圆弧并面积和以前的算法对比算法主要思想介绍系统主要功能成果展示应用领域所用到的技术系统模块划分系统主要功能•形象动态的展现圆弧信息–动态画圆–动态修改圆–圆的信息的列表展现•计算圆弧的交点•合并约束圆弧•建立矢量多边形•最后计算出面积模块划分•根据分析，系统的主要模块划分如下：动态计算圆弧并面积系统文件存取子系统面积计算子系统圆弧动态展现子系统模块划分•文件存取子系统主要是对圆的信息和配置信息进行存储和读取，以便保持软件使用的连贯性。•圆弧动态展现子系统主要是对圆弧的形象直接的展现出来，让用户可以直观明了的看到要计算的圆弧并面积的形状与大小。同时，这个模块还可以在一定程度上验证这个计算算法的正确性。•面积计算子系统是对圆弧并面积以及各种前提的计算，是对算法的实现，也是本次设计的核心模块。文件存取模块设计•用XML文件对圆的信息和用户配置信息进行存取–采用XML文件来存取数据有两点原因：首先XML文本本身就是用来存储数据的，这很符合本次设计的要求。其次，它的简单性，正是因为XML的简单使其易于在任何应用程序中读写数据。•使用CMarkup库来进行操作XML文件•进入系统时自动读取相应的XML文本中圆的信息和配置信息，退出系统时自动存储圆信息和配置信息到相应的XML文本中圆弧动态展现模块设计•圆弧的动态展现模块又划分为四个子模块，如下图所示：圆弧动态展现模块视图切割画图板视图通信列表框圆弧动态展现模块设计•视图分割模块是将主视图分割成两部分：画图板子视图和列表框子视图。画图板子视图用来画出圆弧，展现出圆弧并面积的形状和大小。列表框视图用来列出圆的信息，展现圆的圆心坐标和半径大小。•视图通信模块主要是实现这两个子视图之间的通信，以实现两边的互动，比如对应选中、两个子视图对圆弧信息动态的保持一致性、一些操作的相互调用等等。圆弧动态展现模块设计•画图板模块主要是画出圆弧并面积，形象直接的展现给用户。还有，这个模块还要实现对鼠标动态拖拽画圆和用鼠标对圆的拖动，以展现圆弧的动态性。这个模块还要能根据配置信息对应的画出网格线、圆心、半径等元素。•列表框模块主要是对圆的信息列表展示。在这个的基础之上，列表框还要有右键菜单的功能，以实现对圆的信息的操作功能。面积计算模块设计•面积计算模块又划分为四个子模块，如下图所示：面积计算模块计算交点坐标建立矢量多边形合并约束圆弧面积汇总面积计算模块设计•计算交点坐标模块是利用相交圆交点坐标计算公式计算出相交圆的交点坐标，并在画图板上标出相应的点，看与上面模块中画出的圆弧的相交位置是否吻合，来验证交点坐标计算的是否正确。•合并约束圆弧模块是对每个园中能够合并的约束圆弧进行合并，同时计算出该圆的自由圆弧的度数之和，并计算出自由圆弧扇形的面积。合并完之后，画出合并之后的圆弧，看是否与上面模块中画出的圆弧中为约束圆弧那部分，来验证约束圆弧的产生与合并是否正确。•建立矢量多边形模块是建立起圆弧并面积中的矢量多边形，并画出矢量多边形，看矢量多边形是否将圆弧并面积分为不相交的两大部分区域。在这个模块中同时计算出矢量多边形的面积。•面积汇总模块是将上面两个模块中的扇形面积和多边形面积进行汇总，最终得出并面积的面积值。面积计算模块设计•将圆弧并面积分为两部分：–自由圆弧扇形–矢量多边形•然后分别计算自由圆弧扇形的面积和矢量多边形的面积，再求和核心算法的主要思想自由圆弧扇形面积计算•圆与圆的位置关系：–相交–相离(包括常规的相离和外切)–相含(包括常规的内含和内切)•相交圆的弧线分为约束圆弧和自由圆弧：–约束圆弧：这段圆弧被其他圆包含–自由圆弧：这段圆弧没有被任何其他圆包含•相离圆的圆弧全部为自由圆弧•相含圆的圆弧全部为约束圆弧自由圆弧扇形面积计算•根据圆的方程式计算出相交圆的交点坐标面积•由交点坐标得出两段弧，分别取弧中点，判断是否在相交的那个圆内，若在，这段弧为约束圆弧，若不在则为自由圆弧•将每个圆中所有的约束圆弧按三角度制排序，并在此基础上合并约束圆弧•每个圆以360°减去所有的约束圆弧的圆心角之和，剩下的就是自由圆弧度数之和，从而计算出自由圆弧扇形面积建立矢量多边形•根据上面合并之后的约束圆弧来建立矢量多边形：–由于圆弧的逆时针方向，可知圆弧有一个起点和终点–对每段合并之后的约束圆弧，可以建立两段矢量：第一段从圆弧的起点出发，终止于该圆的圆心；第二段从该圆的圆心出发，终止于圆弧的终点。–对每个圆的每段合并之后的约束圆弧进行上面处理之后，就可以形成了一个闭合的矢量多边形矢量多边形面积计算•设构成矢量多边形的矢量为，i=1,2,…,M的尾端点坐标(xi,yi)，头端点坐标(x'i,y'i)则矢量多边形面积的计算公式为：与以前的算法对比动态计算圆弧并面积区域分割方法这个方法是先用内切正方形填充，再用小的能内切于圆的正方形继续填充，达到要求的精度为止。然后减去填充过程正方形相互覆盖的那部分面积，剩下的就是圆弧并面积。是一种近似逼近算法。时间复杂度就会随着精度要求的增大而增加，不具有很有的适用性和交互性。本算法这个算法是巧妙的将并面积分为两块互不相交的区域：多边形区域和自由圆弧扇形区域。使用前面介绍的动态计算矢量多边形面积的方法可以精确计算任意多边形的面积。自由圆弧扇形面积可以通过扇形面积公式来计算。时间复杂度与园的大小、计算精度没有关系，具有很好的适用性和交互性。成果展示•根据上面的算法动态计算圆弧并面积应用领域•本次设计解决的问题不仅是计算几何,CAD/CAM和计算机图形学中的一个基础算法，而且在很多问题上具有很强的应用背景。•在军事上,将此模型应用于机场布置,如果布置合理,就可以用最少量的资源达到最大范围国土防空的目的。•此外,在商业区的布置以及城市的经济、文化生活影响范围等都涉及到圆弧并面积的计算问题,对经济、文化的评估有着一定的意义。用到的相关技术•视图分割(CSplitterWnd)–这个视图分割又涉及到了子视图间的相互通信–用到子视图间相互通信的地方有很多，比如：对应选中在画图板上画圆或对圆的拖动时，列表视图动态刷新通过在列表视图对圆进行修改和删除时，画图板上的图对应动态更新用到的相关技术•拖拽画圆–通过异或的模式画图，动态的展示拖拽画圆的效果–更直观的添加圆弧展现拖拽画圆的效果用到的相关技术•圆的拖动–通过鼠标响应，来实现画图板上对圆的拖动操作–直观形象的展示出圆与圆的位置关系的动态感展现圆的拖动的效果谢谢！计算科学与技术学院武汉科技大学