1. 您所在位置：首页 > 路桥工程 > 选线设计 > 基于图论的道路平面设计研究与软件开发论文

基于图论的道路平面设计研究与软件开发论文 69页

  • 894.10 KB
  • 2022-05-11 18:29:09 发布

基于图论的道路平面设计研究与软件开发论文

  • 69页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
华中科技大学硕士学位论文基于图论的道路平面设计研究与软件开发姓名：张军华申请学位级别：硕士专业：道路与铁道工程指导教师：吴小平20080601 摘要在国内市政工程建设中，道路平面设计是不可缺少的一部分。目前国内土木工程辅助设计软件其平面设计中还则存在着许多问题。这些软件重几何计算，轻数据结构；重单线，无系统，忽视了道路网的设计，没有将“带状问题”转换成“网状问题”来进行解决；重主线，无辅助线；软件中的图形对象只是简单对象，没有实体化，对象间没有任何关联，也没有横向、竖向的约束；并且计算慢，出错率高。故需要建立一个新的模型来解决上述问题。本文系统论述了图论以及约束模型在道路平面设计中的研究以及应用。本文的创新点在于：1、线元研究：可以任意在后台控制缓和曲线的坐标通式的余项，来控制缓和曲线的精度；突破了传统的缓和曲线的最大偏角为180度的极限，将最大偏角控制在900度；道路平面设计中的各种缓和曲线组合的算法进一步完善；2、模型建立：建立基于图论的约束模型，打破了传统的静态几何模型，适应动态设计和再设计的需求；3、编程思想：运用最新计算机编程理念（面向过程→面向对象→泛型）与STL，BGL和计算几何库四者结合，突破了传统的面向对象理念，提高计算速度，并且建立一个可以面向多个CAD的平台；本课题的研究成果，具有很强的现实意义。线元的深入研究满足了市政工程设计中的需求，提高了设计精确度。而基于图论的约束模型的建立将大大突破现行道路设计软件的表达瓶颈，实现动态设计与再设计的需求，同时将推动道路设计理论的进一步研究。关键词：道路平面设计;缓和曲线;图论;泛型编程;约束图模型I AbstractTheRoadPlaneDesignisanindispensablepartinthemunicipalengineering.Atpresent,therearemanyproblemsintheroadplanedesignofthecivilengineeringaideddesignsoftwareinourcountry.Thesesoftwarepayanimportantattentiontogeometriccalculation,ignorethedatastructure;emphasizesingleline,nosystem,ignorethedesignoftheroadnetwork,theysolvethe“zonal”problemsinsteadofconvertingtheminto“network”problems;emphasizemainline,noassistedline;Inthesesoftware,theobjectsofgrapharesimple、nohypostatization,andthereisnocorrelationamongthem,alsonotransverseorverticalconstrain,moreover,calculateslowly,therateoferrorishigh.Therefore,anewmodelshouldbesetuptosolveproblemsabove.Thispaperdescribedtheresearchandapplicationofgraphicandconstraintmodelintheroadplanedesignsystematically.Theinnovationsofthisarticleareasfollows:1、Theresearchoflinesegment:tocontroltheaccuracyofspiral,theremainderofgeneralformulaofitcanbecontrolledarbitrarilyinthebackstage;breakthroughtheotraditionallimitofmaximumdeflectionangleofspiral,whichis180C,andsetitattheodegreeof900C;thealgorithmofallkindsofspiralwasimprovedfurtherintheroadplanedesign;2、Theestablishmentofmodel:constraintsmodelwassetupbasedongraphictheory,breakthroughthetraditionalstaticgeometricmodel,meettheneedsofdynamicdesignandre-design;3、Thethinkingofprogramming:usingthecombinationoflatestconceptsofcomputerprogramming(Process-orientedprogramming→Object-Orientedprogram--ming→genericprogramming)、STL、BGLandcomputationalgeometrylibrary,breakthroughthetraditionalconceptsofObject-Oriented,improvecalculationspeed,andestablishamultiple-orientedCADplatform;Theresultsofresearchonthissubjecthaveastrongpracticalsignificance:thein-depthstudyoflinesegmentmeetstheneedofthedesignofmunicipalengineering,andasaresultdesignprecisionwasimproved;constraintmodelbasedongraphtheorywillII greatlybreakthroughthebottleneckofexpressionofdomesticmunicipalsoftware,meettheneedsofdynamicdesignandre-design.Andatthesametimeitwillpromotethefurtherstudyofthetheoryofroaddesign.Keyword：RoadPlaneDesign;spiral;graphtheory;genericprogramming;ConstraintgraphmodelIII 独创性声明本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。近我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在______年解密后适用本授权数。本论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日 1绪论1.1研究的背景1.1.1计算机辅助工程(CAE)和计算机辅助设计(CAD)技术介绍计算机辅助工程（ComputerAidedEngineering）简称CAE，它是把计算机应用于工程规划、设计、管理等的统称。它以其巨大的社会和经济效益在工程实践中占[1]据越来越重要的地位。在设计过程中，利用计算机作为工具，帮助工程师进行设计的一切实用技术的总和称为计算机辅助设计（ComputerAidedDesign）简称CAD。计算机辅助设计CAD[1]是属于计算机辅助工程CAE中重要的一项。计算机辅助工程，包括计算机辅助设计是近40年发展起来的一门新兴技术。随着计算机硬件和软件技术的巨大进步，CAE技术已成为工程实施及科学研究不可缺少的组成部分。CAE技术充分利用了计算机的高速运算、数据处理和绘图模拟等能力，不仅可以缩短工程规划、设计和施工的周期，减少工程技术人员的繁杂劳动，而且能够提高工程质量、降低成本；同时，CAE技术也为科学研究的发展和教育的[1]现代化提供了方便的工具。计算机辅助设计CAD包括的内容很多，如：概念设计、优化设计、有限元分析、计算机仿真、计算机辅助绘图、计算机辅助设计过程管理等。在工程设计中，一般包括两种内容：带有创造性的设计（方案的构思、工作原理的拟定等）和非创造性的工作，如绘图、设计计算等。创造性的设计需要发挥人的创造性思维能力，创造出以前不存在的设计方案，这项工作一般应由人来完成。非创造性的工作是一些繁琐重复性的计算分析和信息检索，完全可以借助计算机来完成。一个好的计算机辅助设计系统既能充分发挥人的创造性作用，又能充分利用计算机的高速分析计算能[2,3]力，即要找到人和计算机的最佳结合点。计算机辅助设计CAD在工程领域中的应用有以下几个方面。建筑：方案设计、三维造型、建筑渲染图即概念设计、平面布景、建筑构造设计、小区规划、日照分析、室内装潢等；结构：有限元分析、结构平面设计、框架和排架结构计算和分析、高层结构分析、地基的基础设计、钢结构设计与加工；设备：水、电、暖等各种设1 备及管道设计；市政管线：自来水、污水排放、煤气、电力、暖气、通信等；市政建筑：城市规划、城市交通、道路高架、轻轨、地铁；交通工程：公路、桥梁、铁[2,3]路、航空、机场、港口、码头；水利工程：大坝、水渠、河海工程。1.1.2国内土木工程CAD的发展阶段介绍通过对国内土木工程CAD软件开发过程的研究，将国内土木工程CAD软件开发历程分为下面两个阶段：1、第一代土木工程CAD此阶段时间是在20世纪80年代后期到20世纪90年代前期，第一代土木工程CAD软件只能适用于设计方案已经基本确定，通过软件进行一些大量计算后直接驱动绘图仪绘图。这一代土木工程CAD软件只是作为绘图工具，后期设计方案修改十分不方便，只能通过修改数据后重新绘制图形。数据计算处理模块为这一代软件产品的设计重点。其特点：面向数据设计，只能由数据到图形。所采用的设计模型为用数组表达的线性链表。2、第二代土木工程CAD此阶段时间是在20世纪90年代后期到至今，在此段时间里，电脑硬件和软件技术飞速发展，这些高新技术的发展推动了CAD技术的现代化，出现了MiroStation、AutoCAD等优秀的CAD图形平台。第二代土木工程CAD就是基于CAD图形平台进行土木工程设计。这样便在第一代产品的基础上，利用CAD图形平台的图形数据库，完成了由图形到数据的逆操作，实现了数据和图形的双向交换。通过修改图形就可以完成设计数据的更新，即常说的所见即所得。图形修改处理模块为这一代软件产品的设计重点。第二代土木工程CAD的特点：面向数据和图形，数据和图形双向交换，重点是图形，实现所见即所得。设计模型仍为线性链表。链表一般只能表达线性对象，使得表达上存在局限性。1.1.3土木工程设计CAD软件软构件技术介绍[1]软构件技术是一种新的现代化的软件开发方法，也是土木工程学术界在CAD软件开发的历程中通过摸索和研究，认为是值得推荐的实用方法。软构件（Componentware）又称软组件、软件构件，是具有一定实际功能的、相2 对独立的、存在于某一系统而又不依赖于这一系统的、可以被相同的构件所替换的软件包。软构件是相对于由其所组成的软件系统而言的，相对于其它软件，软构件又可称为“构件软件（componentsoftware）”。通过软构件的组装集成开发完成的软件系统称为“构件化软件”，而通过软构件的组装集成来开发软件系统的技术则称为“软件构件化”。不同的软构件按照一定的规则可以组装成具有一定功能作用的“构件化软件”，组装后的“构件化软件”也可以成为其它系统的“软构件”，一个构件[1]软件也可以由更小的软构件所构成。[1]基于构件的开发方法（ComponentBasedDevelopment，简称CBD方法）又称构件化软件的开发方法，它是指软件的开发建立在已有的可重用构件的基础上，通过对已有构件的组装或集成，达到开发完成应用系统目的的一种软件开发方法。CBD方法是当今软件行业最新的一种软件开发方法，它大大提高了软件开发的效率和质量，必将引起一场软件行业的革命。1.1.4道路平面设计方法介绍随着计算机的功能越来越强，道路平面设计在道路设计中的应用也越来越广；同时随着我国的经济发展水平及速度的不断提高，对公路交通的发展也提出了更高的要求；高速公路、一级公路、汽车专用道等高等级公路的大规模建设，对传统简单平曲线技术方法提出了挑战；由此，众多道路专业工程师及相关教育科研人员对道路平面线形设计方法进行了大量的研究，也已经取得了很多有用的成果。目前道[1]路平面线形设计方法以达到了“丰富多彩”的境界：1、从定线的主导方法看：有直线型和曲线型两类方法；2、从曲线构造方法看：分为组合线形（直线、圆曲线、回旋线）构造法和样条曲线拟合法；[1,4~7]3、从具体应用方法看：有常规交点平曲线设计法、卵形曲线设计法、复合导线法、五单元导线法、模式法、积木法、动态交互式模式法、动态交互式积木法、线元法、固定/浮动/自由线元法、控制法、参数法、位移法、试算优化方法、三次样条曲线拟合法等；4、从曲线形式看：出现了从最早的单圆曲线到对称曲线、非对称曲线、拱形曲线；从复曲线到单卵形、双卵形及至多卵形曲线；还有S形曲线、C形曲线等；3 5、从适用对象看：有些以主线为主；有些以互通立交为主；有些立足于人机立交；有些侧重于计算；有些适合于构造初始线形；有些适合于交互修改；等等⋯1.2国内外的研究状况1.2.1国外研究情况取目前国外通用的土木工程设计CAD软件中下列三种作为调研对象：英国MXRoad软件；德国IB&T(IngenierbueroBasedow&TornowGmbH)有限公司开发的CARD/1系统；[8~9]美国Autodesk公司开发的CIVIL3D系列。英国Infrasoft公司于1998年推出新一代的大型土木工程MX软件，它为公路、铁路、水利工程、机场、场地工地已经露天矿山工程等土木工程提供勘测设计一体[10]化的解决方案。在平面设计里它的理论基础是采用了独特的“串”的概念。“串”是“点”的集合。该系统建立了多种形式的“串”线，每个串以标签、维和数码来表示。例如：等高线为一个二维串，形成每一根等高线的“点”的坐标是以标签的形式用数据记录在串的最前面。公路和铁路中的测站点、中心线、导线都用六维串来表达，串中每一个点的前面三个维是点的坐标，后面几个是沿串的桩号（或距离），然后是该串的方向角和曲率半径。在应用上，该软件可以实现动态的进行平面选线和纵断面设计，对于平面交叉口设计，采用的参数化图片界面导向设计模式进行转弯曲线和交通岛的设置。它也具备多种类型和方法进行缓和曲线自动设计。CARD/1软件自设图形平台，并建立独立完整的数据与图形编辑体系，由11个[11]模块组成。对于平面设计该软件有两个模块：平面图模块，平面线形设计模块。平面图模块是完全独立的，可用于土地，交通等规划和图形绘制。而平面线形设计模块可在平面图中对道路、铁道、渠道及相应路边线进行交互式图形设计。它的新特点是能在图形环境下构造轴线，进行各种轴线元素的图形设计。该软件的平面设计方法采用的是曲线法定线设计。对于平面交叉设计采用的模板化和参数化的方法提供交通岛模板，方便平面设计。AutodeskCivil3D能够在对象之间创建智能关系，使设计更改能够动态更新。4 其三维交互功能提供了更大的设计灵活性，可以使用土木工程模型中对象间的动态、实时交互功能，探讨概念方案并以更快的速度完成最终设计。这一特点源于智能的中央三维工程模型。该模型包含对象（如点、曲面、地块、道路和放坡）的核心几何图形和设计智能。另外，表格、对象标签和各种分析显示也用来表示模型。如果更改了模型中的任何一部分，所有与其相关的部分都会立即动态更新。它采用导线法和线元法进行道路平面路线布设，使用参数化的布局工具生成平面路线。1.2.2国内研究情况自1979年起，先后有同济大学、重庆交通学院与重庆公路研究所、交通部武汉第二公路勘察设计院、西安公路学院、上海铁道学院、西南交通大学、北方交通大学、铁道部铁路专业设计院等单位先后为公路和铁路的纵断面优化技术、公路及铁路的平面和空间线形优化技术等进行了研究，编制了各自的优化程序。这些程序经过试算，证明其优化效果是令人满意的，但至今还没有广泛地应用到实际的工程设[1]计中，有待于进一步的完善和应用开发。目前，国内生产中使用的国产软件有东南大学开发的道路与互通式立交ICAD及DICAD、EICAD系统；武汉城市建设学院开发的市政工程设计软件MECAD；交通部第二公路勘察设计院开发的微机公路路线设计；海德公司开发的HEAD软件系统以及各设计单位自行开发或基于AutoCAD支撑软件作二次开发的各种软件等。这些国内已有软件与国外优秀软件相比较，仍属于低水平、不完整和不稳定状态。在平面设计及软件开发上，很多地方不完善，甚至有的部分基本是空白，例如回旋线的开发。平面设计方法因为受到国外“曲线形设计法”的启发，我国发展了“模式法”，[1]“积木法”，“新的导线法”，“扩展的模式法”。在基于DEM的道路设计CAD系[12]统中，它将交点法、积木法等多种设计方法融为一体，使平纵横联动设计功能使设计效率更加提高，但与AutodeskCivil3D的智能动态更新还有很大的差距。且国内采用的是面向对象编程，其采用的存储模型是线性链表。1.2.3结论通过调研比较国内外专业软件，目前国内土木工程辅助设计软件还则存在着下5 面这些问题：1、重几何计算，轻数据结构：过多看重计算，很少考虑整体的数据结构，系统不稳定，出错几率大；2、重单线，无系统：目前软件过多的考虑一条道路线的设计情况，而忽视了道路网的设计。没有将“带状问题”转换成“网状问题”来进行解决；3、重主线，无辅助线：只考虑主线的设计，与主线相关联的对象却没有考虑。比如一条道路上的相交道路，相交管线，立交匝道等等；4、无约束，非实体化：软件中的图形对象只是简单对象，没有实体化，对象间没有任何关联，也没有横向、竖向的约束；5、重中心线，轻边线、纵断面线、横断面线等；6、计算慢，出错率高；7、操作不统一，界面复杂，思路不清晰：每使用一个软件都需要重新学习软件使用方法。各种软件之间数据不统一，程序无法通用，软件开发中没有使用软构件技术。以上的这些问题，就是国内第二代土木工程CAD软件的主要弊端。因此目前迫切需要打破第二代土木工程CAD软件开发瓶颈，完善构件化土木工程CAD软件开发方法的理论，建立基于土木工程统一数据结构模型，并尝试使用软构件技术进行专业软件开发，实现快速高效系统完整的软件系统，以满足动态设计要求和再设计的需求。1.3论文研究的目的和内容1.3.1研究目的在对道路设计中平面，纵断面，横断面，交叉口，市政管线的平面和纵断面的设计模型的分析和总结的基础上，运用最新计算机编程理念（面向过程→面向对象→泛型），把它们统一抽象为约束图模型。与此同时完善平面的线元研究，减少程序的时间复杂度和空间复杂度，以满足平面设计的需要。6 1.3.2研究内容1、道路平面设计软件的几个库的开发：分析标准模板库，计算几何库，BGL库，这三个库在AutoCAD里的应用以及开发。2、平面设计里线元的完善：在平面设计里最基本的线形控制单元有三种：直线，圆曲线，缓和曲线。分别对这三种线元进行研究，特别是对缓和曲线的组合，精度以及偏转角的研究。3、建立基于图论的约束模型并求解：先分析线元模型的抽象图模型，导线法模型的抽象图模型，建立基于图论的统一约束模型。然后提出求解约束模型的算法，求解约束模型。1.4开发平台及主要的技术路线1.4.1采用的软件平台及开发工具软件平台：CAD软件AutoCAD2004、AutoCAD2006、AutoCAD2008，GIS软件AutoCADMAP2006、AutoCADMAP2005，专业软件CIVIL3D2006、CIVIL3D2005；开发工具：MicrosoftVisualStudio.NET2003，MicrosoftVisualStudio.NET20052002，AutoCAD二次开发包ObjectARX2002、2006、2008，SetupFactory7.0，ObjectDCL，Lisplink，VisualLisp；数据库平台：MicrosoftAccess2003。1.4.2论文采用的软件技术和开发工具介绍1、AutoCAD及AutoCADMap软件简介AutoCAD是美国Autodesk公司多年以来发展起来的旗舰产品，是目前世界上应用最广泛的CAD软件之一，绝大多数设计单位都在应用其进行设计，其图形数据格式也成了工程界图形数据存储与交换的标准。同时，该软件在图形处理上的强大功能及开放的二次开发平台使许多软件开发企业在其基础上进行了大量的二次开发工7 作。为了顺应信息技术，特别是地理信息系统（GIS）的发展，Autodesk公司也利用自身的CAD平台开发了面向地理信息系统的应用AutoCADMap，提供了地理信息系统的功能，但由于受AutoCAD图形特性的一些限制，其地理信息系统的功能较之其他专业的地理信息系统，如美国ESRI的ArcGIS、MapInfo等有一定的差距，但Autodesk公司正在不断完善中，其近年最新的产品Civil3D和LandDesktop以Map平台为基础，表现出了在土木工程领域强大的生命力。[13]2、AutoCAD-ObjectARX技术简介ObjectARX技术是AutoCAD的二次开发技术之一。ObjectARX应用程序是一个动态链接库（DLL），它共享AutoCAD的地址空间并直接调用AutoCAD的函数。ObjectARX程序设计环境，为开发者使用、定制和扩充AutoCAD，提供了一个面向对象的应用程序设计接口。ObjectARX库包含一系列多功能的工具，开发者利用AutoCAD的开放式体系结构，直接访问AutoCAD的数据库结构和图形系统，定义本地命令。ObjectARX从AutoCAD2000到目前最新发布的AutoCAD2006的每个CAD版本都有不同的版本相对应，并随AutoCAD同时发布，提供给开发者。从最初的只支持VisualC++到2005和2006版的支持VS.NET的所有组件：VB.NET、VC.NET、C#，为开发者提供了更广阔的选择空间，同时也向微软新一代的开发战略靠拢，顺应现代软件技术发展的潮流。3、AutoCADVBA技术简介AutoCADVBA也是AutoCAD的二次开发技术之一，AutoCAD在R14版之后都提供了VBA支持，是面向对象体系结构的一种编程语言。目前VBA代码在AutoCAD中以解释的方式执行，但它与AutoCAD完全共享内存空间，所以执行速度比用C语言开发的ADS程序还要快，同时它又是VB的子集，其语法结构十分简洁，便于掌握。与ObjectARX相比，语法结构简洁、便于掌握是其最大的优点，但由于它是VB的子集，其面向对象的程序设计方面还有很大的不足，如不支持派生和重载等。4、AutoCADActiveX技术概述8 ActiveX：一组允许软件组件与网络环境中的另一个组件交互，而不管创建组件所用语言的技术。AutoCADActiveX使用户能够从AutoCAD的内部或外部以编程方式来操作AutoCAD。它是通过将AutoCAD对象显示到“外部世界”来做到这一点的。这些对象被显示后，许多不同的编程语言和环境以及其他应用程序（例如Microsoft®WordVBA或ExcelVBA）就可以访问它们。图1-1ActiveX模型图在AutoCAD中实现ActiveX接口有两大优点：更多的编程环境可以编程访问AutoCAD图形。在ActiveXAutomation出现以前，开发人员只能使用AutoLISP或C++接口。与其他Windows应用程序（如MicrosoftExcel和Word）共享数据变得更加容易。对象是所有ActiveX应用程序的主要构造块。每一个显示的对象均精确代表一个AutoCAD组件。AutoCADActiveX接口中有许多不同类型的对象。例如：直线、圆弧、文字和标注等图形对象都是对象；线型与标注样式等样式设置都是对象；图层、编组和块等组织结构都是对象；视图与视口等图形显示都是对象；甚至图形、AutoCAD应用程序本身也是对象。5、Microsoft.NET技术简介.NET是微软为简化在第三代Internet的高分布式环境下的应用程序开发，基于开放互联网标准和协议之上，实现不同语言和不同平台高度交互性而建的新一代计算和通信平台。.NET支持多种语言的互操作，在一种语言下开发的组件可以在另一组件下通过9 面向对象的继承而得以重用，.NET通过将各语言先编译成中间语言（IntermediateLanguage，IL），然后在执行时用即时编译器编译成本地平台代码执行，从而实现跨平台使用。.NET的核心是.NET框架，它位于操作系统之上，为其他部件提供服务。它的主要组成部分有公共语言运行库和.NET框架类库及基础类库。ObjectARX提供了托管类使用户可以利用VB.NET和C#编写基于Microsoft.NET框架的应用程序。托管类实现了数据库功能使你可以读写DWG文件，同时也提供操作AutoCAD的用户界面元素的方法，这些元素包括命令行，对话框，AutoCAD编辑器，以及出版和绘图组件等。[13]ObjectARX托管类含两大程序集：●acdbmgd.dll动态链接库包含ObjectDBXAPIs；它随AutoCAD一起发售。●acmgd.dll动态链接库包含了大部分的AutoCADAPIs；它随AutoCAD一起发售。其内容详见ObjectARX文档。1.4.3主要的技术路线本文首先是通过对平面线元的研究，主要是圆弧和缓和曲线的研究，再建立统一的约束图模型和分析约束求解算法。然后对标准模板库、计算几何库、BGL库进行相应的研究与开发。结合这四个库，采用如上软件平台和开发工具，用泛型编程来实现平面设计软件的开发。10 2道路平面设计软件开发库的简介与开发2.1STL的基本组成2.1.1STL简介STL（StandardTemplateLibrary，标准模板库）是惠普实验室开发的一系列软件的统称。它是由AlexanderStepanov、MengLee和DavidRMusser在惠普实验室工作[14]时所开发出来的。STL标准模板库，又称泛型库，是一个使用模板技术实现的通用程序库，所提供的数据结构和算法具有泛化形式，不依赖于某个具体的C++数据类型，既体现了软件代码的可重用性，又保证代码具有相当的执行高效性，是一个具有工业强度的、高效的C++程序库。该库包含了诸多在计算机科学领域里所常用的数据结构和算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可重用性。ANSI/ISO（美国国家标准/全球一致标准）的C++STL规范文本正式通过以后，各个C++编译器厂商就依照标准所描述的原型去实现C++STL泛型库，于是出现了多种符合标准接口，但具体实现代码不同的泛型库。目前流行的版本有：HPSTL、SGISTL、STLport、P.J.STL、RougeWaveSTL几种。[15]STL标准中的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：、、、、、、、、、、、和。2.1.2模板与泛型1、模板概念通过使用模板可以使程序具有更好的代码重用性。模板是对源代码进行重用，而不是通过继承和组合重用对象代码，当用户使用模板时，参数由编译器来替换。模板由类模板和函数模板二部分组成，以所处理的数据类型的说明作为参数的类就叫类模板，而以所处理的数据类型的说明作为参数的函数叫做函数模板。模板参数11 可以由类型参数或非类型参数组成，类型参数可用class和typename关键字来指明，二者的意义相同，都表示后面的参数名代表一个潜在的内置或用户定义的类型，非[16]类型参数由一个普通参数声明构成。2、泛型编程概念泛型编程和面向对象编程不同，它并不要求你通过额外的间接层来调用函数，它让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型编程的代表作品STL是一种高效、泛型、可交互操作的软件组件。所谓泛型（Genericity），是指具有在多种数据类型上皆可操作的含意，与模板有些相似。STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。STL以迭代器（Iterators）和容器（Containers）为基础，是一种泛型算法（GenericAlgorithms）库，容器的存在使这些算法有东西可以操作。STL包含各种泛型算法（algorithms）、泛型指针（iterators）、泛型容器（containers）以及函数对象（function[15]objects）。STL并非只是一些有用组件的集合，它是描述软件组件抽象需求条件的一个正规而有条理的架构。2.1.3STL算法函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。算法部分主要由头文件，和组成。12 是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。中则定义了一些模板类，用以声明函数对象。2.1.4STL容器在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。容器部分主要由头文件，，，，，和组成。对于常用的一些容器和容器适配器，可以通过下表总结一下它们和相[16]应头文件的对应关系。表2-1容器列表数据结构描述实现头文件向量（vector）连续存储的元素列表(list)由节点组成的双向链表，每个结点包含一个元素双队列(deque)连续存储的指向不同元素的指针所组成的数组由节点组成的红黑树，每个节点都包含着一个元素，节集合(set)点之间以某种作用于元素对的谓词排列，没有两个不通的元素能够拥有相同的次序多重集合(multiset)允许存在两个次序相等的元素的集合13 续表2-1数据结构描述实现头文件栈(stack)后进先出的值的排列队列(queue)先进先出的执的排列优先队列元素的次序是由作用于所存储的值对上的某种谓词决(priority_queue)定的的一种队列由{键，值}对组成的集合，以某种作用于键对上的谓词映射(map)排列多重映射(multimap)允许键对有相等的次序的映射2.1.5STL迭代器迭代器从作用上来说是最基本的部分，可是理解起来比前两者都要费力一些。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。[15]迭代器部分主要由头文件，和组成。是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，中提供了迭代器使用的许多方法，而对于的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制，中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。2.2计算几何库的研究与开发2.2.1几何算法20世纪70年代末，计算几何从算法设计和分析中孕育而生。至今，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因而已经成长为一个被广泛认同的学科。该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，另一方面，是由14 于在众多的领域（诸如计算机图形学、地理信息系统和机器人学等）中，计算几何都发挥了重要的作用。所谓“计算复杂性”，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数（这叫时间复杂度），二是计算所需的存储单元数量（这叫空间复杂度）。我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类，即ComplexityClass。在采用图灵于30年代提出的理想化的计算模型即图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题：1、静态问题（Staticproblems）：这类问题，输入给定，输出需要构建。典型的静态问题的如下：(1)、凸包（Convexhull）：给定点集，找出包含所有点集的最小凸多面体、多边形。(2)、线段求交（Linesegmentintersection）：计算给定线段集的所有交点。(3)、三角剖分（Delaunaytriangulation）：利用三角形对平面进行剖分。(4)、图（Voronoidiagram）：给定点集，利用最近点原理对空间进行剖分。(5)、最近点对（Closestpairofpoints）：给定点集，找出距离最小的点对。(6)、欧几里德最短路径（Euclideanshortestpath）：在欧几里德空间（有多面体障碍）两点时间的最短路径。(7)、多边形三角形剖分（Polygontriangulation）：给定一个多边形，把多边形剖分成所有的三角形。2、几何查询问题几何查询问题，也即几何搜索问题，输入包括两部分：搜索空间部分和查询部分。搜索空间一般需要预处理，这样可以高效查询多个问题。典型的几何查询问题如下：(1)、范围搜寻（Rangesearching）：预处理点集，计算查询区域内的点数。(2)、点定位（Pointlocation）：把空间剖分成单元，快速处理点的定位。(3)、最近邻居（Nearestneighbor）：预处理点集，快速找到离查询点最近的点。15 (4)、光线追踪（Raytracing）：给定空间的对象集，快速发现第一个与光线相交的对象。3、动态问题（Dynamicproblems）：这类问题主要特征是不断回答问题时，输入的数据不断修改（增加或删除几何对象）。解决这类问题涉及到动态数据结构。任何计算几何问题都可以转化为动态问题。例如，范围搜索问题，当反复增加或删除点时，它则可以转化为动态范围搜索问题。动态凸包问题是反复跟踪凸包，比如，动态修改点集，又如，不断插入或删除点。求解这类问题的计算复杂度由以下组成：(1)、构建数据结构所需要的时间和空间。(2)、修改数据结构所需要的时间和空间。(3)、回答问题所有的的时间（常常需要额外的空间）。(4)、变异问题（Variations）：有些问题的处理不仅取决它的种类，还取决问题的环境。(5)、点在多边形里（Pointinpolygon）：判断一个点是位于多边形内还是在多边形外。许多应用把这个问题当作单杆问题来处理，即第一类问题。比如，在计算机图形学中鼠标点击的区域问题。然而，一些应用中多边形是不变的，点代表查询。比如，多边形代表一个国家的边界，点则代表一架飞机，问题是判断飞机是否侵犯边界。最后，在上述的图形学的例子，在CAD应用中，不断变化的输入数据存储在动态的数据结构中，这样可以加速点在多边形中查询计算。2.2.2wykobi库简介wykobi是一种高效，耐用且简单易用的多平台的2D/3DC++泛型计算几何库。wykobi提供了一个简明性，可预见性和确定性边界的基本几何和复杂几何使用程序，并符合国际标准化组织/国际电工技术委员会14882:2003C++语言规范。它的设计和结构，很方便和无缝与任何规模的项目集成，它将提供强有力的，高效的2D/3D[17]计算几何后台。wykobi库，可用于高效和无缝地解决复杂的几何问题，如碰撞和接近检测，高效的空间查询和几何构造等领域的使用，包括游戏，电脑辅助设计与制造，电子设16 计和地理信息系统。wykobi提供一系列的基本几何结造的算法，如相交计算，距离，包含以及裁裁操作。[18]1、GeneralFeatures一般特征(1)、Pairwiseintersectionsin2D/3Dbetween（求交）-Rays,Segments,Lines,Planes,Triangles,Quadii,Circles,Spheres,Rectangles,Boxes,Polygons,CubicandQuadraticbeziers（三次和二次贝塞尔曲线）(2)、Pointinclusiontest（点的包含检测）-Triangle,Rectangle,Circle,Quadix,SphereandConvexConcavePolygonregion,InCircleandInSphere(3)、Closestpointfromapointon（点到几何实体的最近点）-Segment,Line,Triangle,Quadix,Circle,SphereandAABB(4)、Closestpointon（几何实体之间的最近点）acircle/spherefroma2D/3Dsegmentorline（2D/3D线段或直线到圆/圆球的最近点）(5)、Mirroring2D/3D(reflection)aboutanaxisorplane（关于轴或平面的2D/3D的镜像或折射）-Point,Segment,Line,Triangle,Quadix,circle,Sphere,Polygon(6)、Nonsymmetricmirroring2D/3D(reflection)aboutanaxisorplane（关于轴或平面的2D/3D的非对称镜像或折射）-Point,Segment,Line,Triangle,Quadix,Circle,Sphere,Polygon(7)、Euclidean,Ley,Manhattan,ChebyshevandinverseChebyshevpairwisedistance（欧几里德，Ley，曼克顿，切比雪夫和逆切比雪夫距离）-Rays,Segments,Lines,Planes,Triangles,Quadii,Circles,Spheres,Rectangles,Boxes,CubicandQuadraticbeziers(8)、Minkowskipairwisesumanddifferencesbetween（明可夫斯基的和与差）-Rays,Segments,Triangles,Quadii,Circles,Spheres,Rectangles,BoxesandPolygons(9)、Clippingofsegmentsagains(线段的剪切)-Rectangles,Triangles,Quadii,BoxesandCircles(10)、AreaCalculation（面积计算）-Triangle,Quadix,Rectangle,CircleandPolygon17 (11)、PerimeterCalculation（周长计算）-Triangle,Quadix,Rectangle,CircleandPolygon(12)、Generaterandompointswithin（区域内随机点生成）-AABB,Triangle,Quadix,Circle,Pentagon,Hexagon,HeptagonandOctagon(13)、Projectionalonglinearpath（投影）-Point,Segment,Triangle,Quadix,Circle,SphereandPolygon(14)、Axisalignedboundingboxes-Segments,Triangles,Quadii,Circles,Sphereandpolygons(15)、Centeringof2Dgeometricprimitivesataspecifiedlocation(16)、2D/3DVectoraddition,subtraction,normalization,magnitude,dotproduct,crossproductcalculation（2D/3D向量的加，减，正规化，乘，点积和叉积计算）(17)、2D/3DRotations,fastrotations,translations,scalingandshear（2D/3D旋转，平移，缩放和剪切变换）(18)、Pointofreflection（点的折射）(19)、QuadraticandCubicBeziercurvecreation(2D/3D二次和三次贝塞尔曲线)(20)、QuadraticandCubicBeziercurvelengthcalculation（二次和三次贝塞尔曲线长度计算）(21)、Polygonapproximationofsupportedgeometricalobjects(22)、ConversionsbetweenCartesianandBarycentriccoordiantesystems（笛卡尔和重心坐标系统转换）(23)、Orientation,Collinear,CoplanarPerpendicularandParallelprimitives定向，共线，共面等操作(24)、VertexandrelativeCartesiananglecalculation（夹角计算）2、Algorithms计算几何(1)、ConvexHull凸包-Grahamscan,Jarvismarch,Melkman(2)、MinimumBoundingBall最小球-Randomized,Ritterandnaive（随机法，里特尔法和贪心法）(3)、PolygonClipping多边形剖分-SutherlandHodgman法，Polygonre-ording多18 边形重序算法(4)、PolygonTriangulation多边形三角化-EarClippingAlgorithmForSimplePolygons简单多边形的耳剪裁算法(5)、Statistical统计-Isotropicnormalization,Covariancematrix,Eigenvaluesandvectors(6)、各向同性正常化，协方差矩阵，特征值和向量(7)、GroupIntersections实体集求交-Naivepairwiseintersections2.2.3wykobi库的数据结构1、点2维点：templateclasspoint2d:publicgeometric_entity{};3维点：templateclasspoint3d:publicgeometric_entity{};n维点：templateclasspointnd:publicgeometric_entity{};2、直线templateclassline:publicgeometric_entity{};3、线段templateclasssegment:publicgeometric_entity{};4、射线templateclassray:publicgeometric_entity{};5、三角形templateclasstriangle:publicgeometric_entity{};6、矩形19 templateclassrectangle:publicgeometric_entity{};7、凸四边形templateclassquadix:publicgeometric_entity{};8、多边形templateclasspolygon:publicgeometric_entity{};2.2.4AutoCAD二次开发与wykobi库结合在AutoCAD的二次开发中，道路平面，纵断面，横断面，管线，排水等等，都要应用到几何计算，这些几何计算中，可以用到wykobi库。通过wykobi库的强有力的，高效的2D/3D计算几何后台来完成二次开发。2.2.5wykobi库在平面设计中的开发在道路平面设计里最基本的线形控制单元有三种：直线，圆曲线，缓和曲线。wykobi库中不存在缓和曲线这一单元。于是可在wykobi库的数据结构里扩充缓和曲线这一数据结构：templateclassspiral:publicgeometric_entity{};同时就需要扩充相应的算法：求几何实体间到缓和曲线的最近点；关于轴或者平面的2D/3D的镜像或折射；几何实体与缓和曲线的相交；缓和曲线的2D/3D旋转，平移，缩放和剪切变换；缓和曲线到圆/圆球的最近点等等。2.3BGL的应用研究2.3.1BGL介绍图在计算机科学中是用途非常广泛的数学抽象。自然，这种抽象也应该能用计算机程序表示。一个标准化的、用于图遍历的通用接口对于促进图算法和数据结构[19]的重用具有极其重要的意义。Boost图库（BoostGraphLibrary，BGL）的一部分是隐藏了实现细节，提供了能够访问图结构的通用接口。这是一个开放接口，任何实现了这个接口的图库都能够与BGL泛型算法以及其他使用这些接口的算法互操20 作。BGL提供了遵循这个接口的一些通用意义的图类，但它们不是惟一的图类；在某些情况下，会存在更好的图类。BGL的主要贡献，就是演绎形成了这个接口。BGL提供了一个全面的图算法框架，同时也提供了高质量的图数据结构与算法的实现，具有工业强度，应用这个良好的实现，可以专注于开发我们的应用。2.3.2BGL中的泛型[20]BGL图接口和图组件都是泛型的，与STL泛型一致，也有3种方式实现泛型。1、算法、数据结构互操作首先，BGL中的图算法是以抽取特定图数据结构的实现细节的方式给出。类似STL，BGL使用迭代器定义数据结构遍历的接口。有3种不同的图遍历方式：遍历图中所有顶点，遍历所有边，或以图中邻接结构方式遍历（从一个顶点到它所有的邻居）。对于每种遍历方式，有不同的迭代器。这种泛型接口使得模板函数能广泛应用在一系列图数据结构上，不论图是以指针链接的节点实现还是数组编码实现的图。借助外部适配器（externaladaptation）定制的，甚至遗留的图结构都能以它原来的样子，无需将数据放置到适配器对象。BGL接口的精心设计使得这种适配很方便。2、通过访问器的扩展BGL的算法是可以扩展的。BGL引入了访问器（visitor）的思想，它是一个有多重方法的函数对象。在图算法中，往往有几个关键的“事件点”（eventpoints），在这些点上，插入用于定义的操作非常有用。访问器对象在每个事件点都以不同的方法被调用。特定的事件点和对应的访问器依赖于特定的算法。他们通常包含诸如start_vertex()，discover_vertex()，examine_edge()，tree_edge()和finish_vertex()这样的方法。3、顶点和边属性的多重参数化BGL实现泛型的第3种方法是类似STL容器中元素类型的参数化，尽管，对于图，情况会复杂些。我们需要对图的顶点和边都关联值，它们称作属性。此外，常常需要对每个顶点和每条边关联多重属性，这就是多重参数化的含义。STL中的std::list类有一个针对它的元素类型的参数T。类似地，BGL图类有针对顶点和边“属性”的参数。一个属性制定了属性的参数化类型和分配给它的确认标签。这个21 标签用于在一个顶点或边拥有的多个属性之间彼此区分。关联到特定顶点或边的属性能够通过属性映射（propertymap）取得。对于每个属性有单独一个属性映射。2.3.3BGL中的图算法BGL算法包含算法模式的一个核心集合（以泛型算法实现），以及一个图算法的较大的集合。核心算法模式是：广度优先搜索；深度优先搜索；统一代价搜索。[20]BGL中的图算法目前包括：Dijkstra最短路径算法；Bellman-Ford最短路径算法；任意点之间最短路径Johnson算法；Kruskal最小生成树算法；Prim最小生成树算法；连通分量；强连通分量；动态连通分量；拓扑排序；转置；反向CuthillMckee排序；最小末顶点排序；顺序顶点着色等。2.3.4BGL实现的数据结构[21]BGL目前提供两个图类和一边列表适配器：adjacency_list；adjacency_matrix；edge_list；adjacency_list类是图类中通用的“瑞士军刀”。它高度参数化，这样它能优化不同情形：有向图或无向图、多重图或非多重图、仅支持高效地访问顶点的出边或同时支持入边，以及是否以额外的空间开销换取快速的顶点插入和删除操作等。adjacency_matrix类在|V|×|V|矩阵中存储边，|V|是图的顶点数。矩阵元素代表图的边。邻接矩阵表示尤其适合于稠密图，即图的边数接近于|V|×|V|。edge_list类是接收任意种类的边迭代器的适配器，它实现边列表图。2.3.5BGL在AutoCAD二次开发中的应用BGL在AutoCAD二次开发中的应用很广：BGL与图论结合的非常紧密，在道路设计中，在排水设计中，数字地面模型，管线综合中都可以应用到。本文建立的基于图论的约束模型后（见下文），采用BGL来实现这一数据结构。也通过BGL中的图算法来查找相应的元素及约束条件。22 3道路平面设计基本线元的研究3.1圆弧的拓展计算3.1.1问题的提出在实际道路平面设计中，一个弯道的圆弧的确定是千变万化的，有时要通过道路中线上的控制点来确定圆弧，有时要通过道路边线来控制圆弧的选取，有时则要[22]通过反复调整才能确定圆弧。在野外测设中，我们也经常会遇到这样的情况，当通过道路横断面分中确定了道路弯道两侧的两直线段时，需要在弯道上取控制点反求弯道的圆曲线半径。同样，在进行道路规划设计，特别是老路改造时，我们经常也是通过某些控制点反推圆曲线。在遇到这种问题时，通常是设法求出切线长或外矢距并利用公式(3-1)、(3-2)求出曲线半径。这样做既不方便又不精准，而且切线长外矢距往往很难得到。T(3-1)R=αtan2ER=(3-2)αsec−12式中α——交点偏角；T——切线长；E——外矢距。3.1.2求通过一个控制点并与两条直线相切的圆弧已知直线L1和L2以及控制点P，以L1和L2的角分线为x轴，L1和L2的交点为[22]原点建立局部坐标系。（如图3-1所示）。则圆心点的坐标为(,)x0，P点的坐标为(,)xy11；令圆弧半径为R，则建立如下方程组：222()xx−+=1yR1(3-3)xcosα=R(3-4)式中α——线段L1和L2的二分之一夹角。由式中(3-3)，(3-4)得以下关于x的一元二次方程。23 图3-1圆弧的拓展计算(1)2ax++=bxc0(3-5)2式中a=sinαbx=−2122cxy=+112222xxxy±−+()sinα1111则x12,=2sinα2由于x1>0，sinα>0，则取x的最大值为设计要求解，即2222xxxy+−+()sinα1111x=2sinα两个解的意义见图3-1所示。得到x后，再由式(3-4)即可求出圆弧半径R。3.1.3求通过一个控制点并分别与一条直线和一个圆弧相切的圆弧已知圆弧C1和直线L1以及控制点P，以L1为x轴，C1的圆心到L1的垂点为原点建立局部坐标系，如图3-2所示。则圆弧C1的圆心点坐标为(,)0y1，半径为R1；P点的坐标为(,)xy22。设待求圆弧的半径和圆心点坐标分别为R和(,)xy，根据几何关系建立以下方程组：yR=(3-6)222x+−=+()()yyRR(3-7)11222()()x−+−=xyyR(3-8)22由式(3-6)，(3-7)得24 222x−Ry+11(3-9)R=2(R+y)11由式(3-6)，(3-8)得：图3-2圆弧的拓展计算(2)22()x−xy+22R=(3-10)2y2又由式(3-9)，(3-10)得关于x的一元二次方程组2ax++=bxc0(3-11)式中aRyy=+112−bx=−2211()R+y2222cxyRyyRy=+()()()++−22112112−±bba−4c则X=1,22a以x的最大值为设计要求解。求得x，则由式(3-9)求得圆弧半径R，由式(3-6)求得y值。两个解的意义见图3-2所示。3.1.4求通过一个控制点与两个圆弧相切(外切)的圆弧已知两个圆弧C和C，半径分为R和R，以C的圆心点到C的圆心点的121212连线为x轴，C1的圆心点为原点，建立局部坐标系，如图3-3所示。则控制点P的坐为(,)xy，C和C的圆心点坐标分别为(0,0)和(,0)x由几何关系建立以下方程33122组：222x＋＝yRR()+(3-12)1222()x−+=+xy()RR(3-13)22222()()x−xy+−=yR(3-14)3325 图3-3圆弧的拓展计算(3)由式(3-12)-(3-13)得：222xR−R−x2212Rx=+(3-15)RR−−2(RR)1212x2222令a1=b=RRx212−−RR12−12(RR−)12则式(3-15)改写为：Raxb=11+(3-16)由(3-12)-(3-14)得2++22(3-17)222xx331+yy−RR=Rxy133由(13)-(14)得222222()xxxy32−+3yR−22RRxxy=+−+2323(3-18)由(3-17)×R－(3-18)×R得212222222RxR+−xRxRRxxyRRxy()+−+−(++)122313123232133yx=+(3-19)()RRy−−2()RRy123123令Rx+−RxRx122313a=2()RRy−1232222222R()RxxyRRxy+−+−(++)123232133b=22(RRy−)123则式(3-19)改写为yaxb=22+(3-20)将式(3-16)和式(3-20)分别代入式(3-12)得2++=++()2()2(3-21)xa22xbRa111xb26 令bbR111′=+则式(3-21)为关x的一元二次方程:()12+−aaxa222+()ba−bxbb′+−2′2=021221121令aa=+−12a221ba=−2()22ba11b′cbb=−2′2212−±bba−4c则x=1,22a以上x的最大值为设计要求解。求得x，则由式(3-16)和式(3-20)分别求得圆弧的半径R和圆心点y坐标。两个解的意义图3-3所示。3.1.5已知n个控制点，求与两条直线相切的圆弧半径。已知n个控制点P1，P2，⋯⋯Pn，先分别求出通过其一控制点Pi与两直线相切的圆曲线半径Ri，再求出它们的平均半径即为所求解。RR+LL+R12nR=n同样方法可求：已知n个控制点求分别与一条直线和一个圆弧相切的圆弧；已知n上控制点，求分别与两个圆弧相切（外切）的圆弧。3.1.6圆弧拓展计算在道路平面软件中的应用已知控制点反推圆曲线的问题在平面设计软件开发中的应用即是：选择第一个实体，选择第二个实体，然后输入一个控制点或多个控制点。在选择实体时，程序能自动识别选取实体的类型，即线和圆弧，同时自动获取实体的几何信息，例如线的起终点、圆弧的圆心坐标及半径等。获取这些原始数据后，再利用以上推导的公[20]式，即可求得圆弧的半径以及圆心坐标，并自动绘出该圆弧。3.2缓和曲线坐标公式及精度的分析以前，在道路平面线形设计中使用的回旋线坐标计算公式只取其展开的前二、三项，在立交的平面设计中也不过四、五项。这样做的主要目的是为了计算上的方27 便，但是，目前在以曲线为主的平面设计方法中经常遇到大回转角的回旋线，近似[1]计算公式难免会出现不容忽视的误差。随着计算机硬件及软件环境的不断改善，在计算机辅助设计中，计算的繁复已不成问题，而对精度的要求却越来越高。特别是在交互式平面设计中，仅用近似公式进行回旋线的计算时远远不够的。因此，很有必要推导出回旋线坐标计算的精确公式，并对各种情况的计算精度加以分析。3.2.1完整缓和曲线的坐标计算公式随着计算机功能及道路设计水平的不断发展提高，缓和曲线（回旋线）的坐标[1]公式到目前为止经历了三个阶段：1、计算器阶段2内移值：∆=RL/(24)R外移距：X=L/2m式中L—回旋线的长度（完整）；R—终点曲率半径。这也是传统《道路勘测设计》教材中提到的公式，是一个近似的公式，主要用于传统对称型导线法的平曲线计算。为了便于手工计算，它只取用回旋线计算公式的前一项或前二项，其技术精度极低，只适用于小回旋转角的情况。2、计算机初级阶段80年代中后期，计算机技术有了进一步发展，我国改革开放和经济发展要求加强道路交通建设，越来越多的人认识到CAD技术的应用。在这些因素的促进下，交通部组织了道路CAD科技攻关，一些技术较强的设计科研单位也自行组织研发。此时，由于计算机的图形功能还不是很强，道路CAD系统也只侧重于计算，这使得回旋线的复杂计算已不成问题。在此期间，通过对回旋线坐标计算公式重新进行推导整理，得出了以下计算公式：2LAR=/(3-22)22τ=A/(2R)(3-23)28 481216LLLLxL=−+(1++)48121640AA3456599040A175472640A3481216LLLLLy=−+−(1+)24812166A56AA70401612800A588349440A∆RyR=+cos()τ−RXxR=−sin()τm上述公式中，回旋线坐标计算公式已达到了5项，基本能满足道路及立交设计的需要，并且由此产生了“积木法”及第一代非交互式立交设计软件。3、计算机的高级阶段进入90年代，我国道路交通等基础建设速度加快，规模也越来越大；以微机为代表的计算机技术的迅猛发展，给计算机的普及创造了条件，这些因素极大促进了道路CAD的发展。至90年代中期，随着计算机图形功能的加强，道路CAD才实现了真正意义上的辅助设计功能。此时，计算机辅助成图功能的作用及其在CAD系统中所占的比例，已远远超过了计算机辅助计算。然而，低精度的回旋线坐标计算公式的致命缺陷在成图时暴露无疑，由于计算精度不够，回旋线在成图时产生了较大偏差。交互式道路及立交计算辅助设计的需要，使得高精度回旋线坐标计算公式的推导迫在眉睫。图3-4回旋线坐标计算公式分析如图3-4所示，已知回旋线参数为A，终点曲率半径为R，曲线长度为L。则根2据回旋线的参数方程有：A=RL29 按几何关系有：dL=Rdτdx=dLcos()τdy=dLsin()τ由sin()τ及cos()τ的级数展开式：23nn−−121sin()τ=−ττ3!+τ5!−LL+−(1)τ/(2nR−+1)!()τ21n−24nn2cos()1τ=−ττ2!+4!−LL+−(1)τ(2)!nR+()τ2n代入dx=dLcos()τ和dy=dLsin()τ中得：24nn2dx=−dL[11−+−+τ2!ττ4!LL(1)−(2)!n+R()]τ2n23nn−−121dy=−+−+dL[3τττ!5!(LL−1)/τ(2n−1)!(+Rτ)]21n−通过积分和整理，可得回旋线的计算通式：n22k−k+1Lτx=−∑(1)∏()k=143kj−j=1通试：(3-24)n21k−k+1Lτy=−∑(1)∏()k=141kj−j=122n−n+1LτRxn()(1)=−∏()43ki−i=1余式：(3-25)21n−n+1LτRyn()(1=−)∏()41ki−i=1内移值：∆=+RyRcos()τ−R(3-26)外移距：XxR=−sin()τ(3-27)m其中：n，k，i，j为正整数，L为回旋线的长度，τ为回旋线的转角。用以上回旋线坐标计算公式进行回旋线计算可以保证不产生大数溢出，以余项来控制精度，可以保证所得坐标值满足精度要求。3.2.2不完整缓和曲线的坐标计算公式尽管我们已经有了完整的回旋线坐标计算通试，但它并不能直接满足所有高等级公路与立交平面设计需求，因为在高等级公路及互通式立交的平面线形中存在大30 量的不完整回旋线（卵形线）。为了满足曲线型设计方法的需要，我们要根据完整回旋线坐标计算公式来推导卵形线的坐标计算公式。根据完整的回旋线坐标计算公式，可以分别求得曲率半径为R1、R2点的坐标值：(,)xy、(,)xy。1122dx则dx=−x21x，dy=−y21y，a=arcos()22dx+dy当RR<时：β=−aτ；当RR>时：β=τ−a于是有卵形线的坐211211标计算公式：xd′=+xd22ycos()β22yd′=+xdysin()β22AA回转角：τττ′=−=||−122222RR1222AA曲线长：LLL′=−=−12RR12卵形线坐标计算公式大大拓展了回旋线坐标计算公式的适应范围，当R为无穷1大时，它既是完整的回旋线的计算公式。3.2.3缓和曲线的精度分析如上所述，缓和曲线的坐标计算通式是一个多项式，在进行计算的时候，具体取多少项才适合呢？取的项数少，但精度难以保证，取得项数越多，计算精度越高，[23]但计算速度也会大大降低。特别是在动态交互式平面设计中，对回旋线坐标计算通式的项数取舍更应慎重考虑。在动态拖动过程中，应首先考虑计算速度的要求，使得参数搜索及线位显示连续而不能停顿间隔时间太长；而在确定拖动参数后，对于回旋线参数的搜索计算应将满足精度要求放在第一位，在决定取项的时候应充分满足精度要求。缓和曲线的精度主要是受坐标计算精度的影响，其它有关计算式的误差多是由它引起的。分析回旋线外移距及内移值的计算式(3-26)，(3-27)。显而易见，回旋线外移距及内移值的计算精度主要取决于回旋线坐标x，y的计算精度。在进行回旋线31 [1]的坐标计算的时候，公式取项数的多少直接影响到回旋线的位置及形状。现在通过对缓和曲线坐标计算通式(3-24)分析来对缓和曲线坐标计算精度进行分析：22nn−−21Rx()LLττn=∏∏()(())Ryn()43ki−−ii==1141ki(2nn−1)(4−1)=>1τ(4n−3)所以分析回旋线坐标计算公式的精度只要判断R()x是否满足精度要求就可n以了。在计算x，y时，其精度主要受项数n及转角值τ的影响。下面分别以项数n及转角τ及精度ε分别作为不同控制条件加以讨论。(1)、确定控制精度ε，分析取不同项数n时满足精度的转角值τ。下表中各值是取A=1000，利用坐标余式计算求得。表3-1不同取项时满足精度的回转角值（表中转角值为角度值）-3-4-5-6-7项数nε=10ε=10ε=10ε=10ε=1020.498780.198570.079050.031470.01252426.476118.578413.03659.14776.419048154.637131.931112.56096.032581.931911271.427242.590216.816193.781173.19313352.532320.910292.123265.919242.06614393.622360.864330.832303.300278.05915434.966401.206370.067341.344314.851从表3-1可以看出，在满足一定精度的要求的前提下，回旋线转角τ增大，项也应增大。为了最大限度地满足设计的需要，转角τ的取值应接近360度，则此时不同-3-4的精度控制所需的计算项数也是不大一样的。当ε=10时，需要13项；当ε=10-5时，需要14项；当ε=10时，需要15项。(2)、确定转角值τ，分析取不同项数n时计算精度ε。32 下表中为坐标计算时取项各值是取A=1000，利用坐标余式计算求得。表3-2精度分析项Rn(x)的值数τ=2πτ=πτ=π/2τ=π/4423302.80996063257.46210849792.84458129402290.03142848004128209.56402881560.009044442496840.000000390343420.00000000001684930.29348877380.000326854421040.000000003526620.00000000000003110.32680886270.000000220383410.000000000001480.00000000000000120.02544385600.000000004289510.000000000000070.00000000000000140.00009383970.000000000000980.000000000000000.00000000000000分析表3-2中的值可以看出，不同的转角、相同的计算项数，计算精度是不同的。在不同的设计方法中，对于不同的回转角要求应取用不同的计算项数。特别是在“拖动”设计中的过程中，过多的取项会造成计算速度的降低而使“拖动”过程不连续。同样，不同的回旋线转角对坐标计算取项的要求是不同的。取项增加，在相同的计算精度下，可以保证转角增大。在满足设计要求的专角情况下，用较多的项数来进行计算，可以保证有较高的精度。但是也不能为了追求较高的计算精度而一味地增加计算项数。因为，若一味的增加计算项数，在提高精度的同时也降低了计算速度。所以要处理好精度与项数的关系。3.3缓和曲线组合的算法研究3.3.1模式法的基本原理及其分类当平面各参数已确定时，可以采用导线法来进行布线完成设计工作。但在实际的设计当中，由于各种条件的限制，不经过精确的计算很难给出所需的设计参数，而由人工计算更是困难，特别是线形较为复杂的卵形线、回头曲线等。对于平面设计来说，如果能根据线形的需要或某些地形条件的限制，由人工初步拟定部分平曲线的控制参数，这将给平面设计工作带来极大的便利，对提高设计质量、缩短设计周期是非常重要的。为了满足这一要求，为了编程和使用上方便，本文对各种控制33 条件的研究组合，根据“交互式模式法”的设计理念，对模式法中的各种模式重新[24]进行了分类。具体分类如下：双线模式凸形曲线两单元双圆模式S形、C形、卵形曲线模式直圆模式基本形插入直线类双圆S形、C形曲线模式法由两种基本三单元单元接回三直线模式S形、C形曲线模式旋线组合而成基本型平曲线插入圆弧类回头曲线双圆S形曲线直线与点双圆C形曲线其他知T反求基本型平曲线知圆弧反求基本型平曲线图3-5模式法分类图[1]基本模式法：无论是立交匝道布线，还是公路线位布设；无论是简单的线形，还是复杂的线形，各种线形当中都包含两种最基本的线形控制单元：直线及圆弧。如果将这两种基本的线形控制单元任意组合，中间用一条或者两条缓和曲线加以顺接，由此便可形成三种最基本的双控制单元模式：双线模式（拱形线）、双圆模式（卵形、S形及C形曲线）及直圆模式。如果在进一步：由三个控制单元三三组合，前后两组的两控制单元之间分别用一段或者两段缓和曲线顺接，由此又可形成插入直线类、插入圆弧类、三直线模式。34 3.3.2各种组合的算法研究1、圆与直线（基本型）：图3-6圆与直线当圆与直线的位置已定，亦即已知直线上两点坐标(,)x11y，(,)xy22，圆心坐标(,)xccy，圆的半径R，可以求出圆心到直线的垂点(,)xppy。则圆与直线的最短距离为：∆=+RyRcos()τ−R22∆=RxxyyR()−+−()−1cpcp精确的A值求出的内移值∆R应与图3-6求出的∆R相等。因此我们可以根据1∆R的单调性，来限制迭代。即定义τmax=10π，τmin=0，τ=()ττmax+min/2.0。以τ作为初始值，ε=∆−∆||RR作为目标函数，根据二分法求出精确的A值。1利用二分法进行迭代计算出满足精度要求的A值。有了满足精度的A值，根据圆与直线的位置，便可以计算出该缓和曲线的长度L，偏转角τ等参数，以及其起终点坐标信息，最终定出该缓和曲线的位置。35 2、圆与圆（卵形曲线）：图3-7卵形曲线如图3-7所示，当两个圆的位置已定，即已知两个圆的圆心坐标：(,)xy，cc11(,)xy和半径R，R。cc2212圆心距离：22cc=−+−()xx()yycc12cc1222cc=+()Rd−−+−Rd(bb)1112221则根据内移值∆R的单调性，将限制条件转换成圆心间的距离cc来控制迭代。即1定义τmax=10π，τmin=0，τ=+()ττmaxmin/2.0。以τ作为初始值，ε=−||cccc1作为目标函数，根据二分法求出精确的A值。有了满足精度的A值，根据两个圆的圆心坐标以及半径，便可以计算出该缓和曲线的长度L，偏转角τ等参数，以及其起终点坐标信息，最终定出该缓和曲线的位置。36 3、圆与圆（S形曲线插入直线）：图3-8S形曲线插入直线S形曲线如图3-8所示，为用两段完整回旋线反向连接两个圆。由于这两段回旋参数A与A肯能相等也可能不相等，因此，为了搜索确定的A值必须首先输入A121与A比值或确定确定其中的一个值，否则无法求解。2此时，两圆的圆心位置及半径都为已知，由此可以求出两个圆心的距离：22cc=−+−()xx()yycc12cc12而给定A1与A2值，根据回旋线计算公式即可求出d1、b1、d2和d2，从而可以求出两个圆心的距离：22cc=+()Rd++++Rd(bb+len)1112221则根据内移值∆R的单调性，将限制条件转换成圆心间的距离cc来控制迭代。1(1)、若已知一个确定的A，不妨设其为A1，则必须求出A2：定义Amax=100000，Amin=0，AAA2m=()axm+in/2.0。以A2作为初始值，lc=−||ccc作为目标函数，根据二分法求出精确的A值。1(2)、若已知A与A的比例：12定义A=100000，A=0，AAA=()+/2.0，A则由其比例计算maxmin2maxmin1出来。同样利用以上方法计算精确的值。有了满足精度的A与A值，根据已知条件便可最终定出所有缓和曲线的位置。12当插入直线长度为零时便是双圆模式S形。37 4、圆与圆（C形曲线插入直线）：图3-9C形曲线插入直线C形曲线如图3-9所示：同S形曲线一样，C形曲线也是用两段完整的回旋线连接两个分离或者相交的两个圆，只是这两段缓和曲线同S形的转向不同而形成了C形曲线。同样，为了搜索精确的A与A的值，也要确定A与A比值或确定确1212定其中的一个值，否则无法求解。此时，两圆的圆心位置及半径都为已知，由此可以求出两个圆心的距离：22cc=−+−()xx()yycc12cc12而给定A1与A2值，根据回旋线计算公式即可求出d1、b1、d2和d2，从而可以求出两个圆心的距离：cc122cc=+()Rd−−++Rd(bb+len)1112221求出精确的A与A的值，方法同S形曲线。有了满足精度的A与A值，1212根据已知条件便可最终定出所有缓和曲线的位置。当插入直线长度为零时便是双圆模式C形。38 5、圆与圆（S形曲线插入圆曲线）：图3-10S形曲线插入圆曲线S形插入圆曲线如图3-10所示：已知两个圆的圆心，以及半径；四段缓和曲线的长度L或者A值，第三个圆的半径R3。根据输入的参数，计算出cc1、cc2：22cc=+()Rd++++Rd(bb)111333122cc=+()Rd+R+++d(bb)2332232[25]再利用计算机图形几何算法，计算出第三个圆的圆心坐标，从而根据已知条件便可最终定出所有缓和曲线的位置。6、圆与圆（C形曲线插入圆曲线）：图3-11C形曲线插入圆曲线C形插入圆曲线如图3-11所示：已知两个圆的圆心，以及半径；两段缓和曲线的长度L或者A值，第三个圆的半径R3。根据输入的参数，计算出cc1、cc2：39 22cc=+()Rd−R−+−d(bb)111333122cc=+()Rd−R−+−d(bb)2223332[25]再利用计算机图形几何算法，计算出第三个圆的圆心坐标，从而根据已知条件便可最终定出所有缓和曲线的位置。7、直线类（凸形曲线）：基本型平曲线是在两个同向回旋线之间插入圆曲线，令两回旋线径向相接而成的平曲线。凸形曲线只有在路线严格受地形、地物限制时才使用。如图3-12所示，凸形曲线可以看成事基本平曲线中间圆曲线长度为零的特例。图3-12凸形曲线方法一：定两回旋线参数A、A，求圆曲线半径R。12已知：α=ττ+12A22由：τ=1A212R2τ2=22R22A+A12得：R=2α方法二：定圆曲线半径R，求两回旋线参数A、A1222A1A2α=ττ+由：τ1=2τ2=2122R2R此时需给定两回旋线参数的比值：A=kA122α2αA=RAk=R得：12221+k1+k40 有了满足精度的A与A值，根据已知条件便可最终定出所有缓和曲线的位12置。8、直线类（基本型平曲线）：目前广泛采用的道路常规平曲线计算图式，圆曲线前后都是完整的回旋线，且一般情况下前后回旋线非对称（AA≠），这是由传统的对称式导线法改进而来，12成之为“基本型导线”。它继承了传统对称导线法“简单、方便”的优点，克服“对称”的局限性，大大提高了其功能的实用性。基本型平曲线如图3-13所示：图3-13基本型平曲线根据两直线的坐标、交点坐标以及原始缓和曲线的参数A、A和中间圆曲线12半径R，由以下公式即可求得左右切线长T、T，进一步便可求得各主点的位12置。2222τ=A/(2R)τ=A/(2R)1122∆=+RyRRcos()τ−∆Ry=+RRcos(τ)−111222XxR=−sin()τXxR=−sin()τm111m222且OJ=+R∆ROJ=R+∆R1122OJ−OJcos()αδ=arctan(21)δ=αδ−121OJsin()α1得到：TO=+Jtan(δ)x1111m41 TO=+Jtan(δ)x2222m完成上述计算，再根据各单元参数便可求得各特征点坐标，便可生成该交点处的平面线位。9、直线类（回头曲线）：回头曲线是连接山坡上下两条路的一种特殊平曲线，特点是半径小，偏角（大于180度，其交点多为虚交），因此，回头曲线实质上属于交点虚交的曲线，如图3-14所示：图3-14回头曲线同基本型平曲线一样，可得：TO=−Jtan(δ)x1111mTO=−Jtan(δ)x2222m从而再根据各单元参数便可求得各特征点坐标，便可生成该交点处的平面线位。10、直线类（知T反求基本型平曲线）：知T反求基本型平曲线在求C形曲线与S形曲线的过程中将应用到，将其单独作为一个程序，方便平面设计。它是通过二分法迭代求出精确的半径，从而定出基本型平曲线。其具体算法如下：42 图3-15知T反求基本型平曲线如图3-15所示，已知T1或者T2（不妨设T1已知），根据两直线的坐标以及交点坐标计算出最大圆曲线的半径R，定义R=0.0，RRR=()+/2.0，根maxminmmaxmin据两缓和曲线参数得出切线长T′，以ε=−||TT′作为目标函数，根据二分法111求出精确的R值。再根据各单元参数便可求得各特征点坐标，便可生成该交点处的平面线位。11、直线类（S形曲线）：S形曲线是高等级公路线形设计中较多采用的一种组合线形，是两个反向圆曲线连以回旋线的结果。设计时，可将之作为两个基本型平曲线来进行计算，只是其中一个的平曲线必须满足切线长度控制而已。S形曲线如图3-16所示：图3-16直线S形曲线43 假定交点处J的偏转角及平曲线参数A、R、A已定，则T、T可求；1111121112在J处，根据其偏转角及平曲线参数A、R、A，由基本型平曲线的计算公221222式可求得T、T；如果中间直线长度不等于T与T之和，那么必须调整圆曲21121221线半径R（采用二分法搜索计算新的圆曲线半径），使得其相等，从而形成S形曲2线。《公路路线设计规范》对S形曲线相邻的两个回旋线参数A12、A21及圆曲线半径R、R有一定的要求：一般A与A宜相等，当采用不同的参数时，A与12122112A的比值小于2.0，有条件时以小于1.5为宜；两圆曲线半径之比不宜过大，其中21大圆半径与小圆半径之比为1～1/3为宜。所以，需对调整后的平曲线参数进行检查，对于不能满足规范要求的参数要重新考虑，以确保线形设计的合理性。然后，将交点J以新的圆曲线半径R及A、A作为独立的基本型平曲线进行计算，从而222122完成该S形曲线设计。12、直线类（C形曲线）：C形曲线是两个同向圆曲线连以两段回旋线的结果，如图3-17所示：图3-17直线C形曲线C形曲线与S形曲线的设计过程完全类似，不同之处只是两相邻平曲线的偏向不一致，C形曲线也可以分解为两个独立的基本型平曲线来进行计算。设计完成，亦需根据规范要求进行参数检查与调整。44 13、直线类（知圆弧反求基本型平曲线）：图3-18知圆弧反求基本型平曲线知圆弧反求基本型平曲线如图3-18所示：已知两直线坐标、交点坐标以及与两直线相切的圆曲线半径和圆心，当外距相等时反求基本型平曲线，具体算法如下：根据已知条件求得圆曲线的外距E1，以及最大圆曲线的半径Rmax，定义R=0.0，RRR=+()/2.0，根据两缓和曲线参数得出基本型平曲线中圆曲minmmaxmin线的外距E2，以ε=−||E12E作为目标函数，根据二分法求出精确的R2值。再根据各单元参数便可求得各特征点坐标，便可生成基本型平曲线。14、直线类（直线与点）：图3-19直线与点点与直线如图3-19所示：已知直线的坐标，以一端点作为缓和曲线的起点，在平面上获取任意一点为缓和曲线终点，从而得到缓和曲线的参数值，定出该缓和曲线。其具体算法如下：45 首先：定义A=10000，A=0.0，AAA=()+/2.0，τ=π，maxminmmaxmin以P为圆心，PP为半径作圆曲线C。根据定义的参数得出初始缓和曲线与圆曲223线C相交于点P4。定义η1为直线P23P与X轴的夹角，η2为直线P24P与X轴的夹角，再以εηη=−||作为目标函数，根据二分法求出精确的A。12其次：定义τ=π，τ=0.0，τ=()ττ+/2.0，根据精确的A值maxminmmaxmin得到缓和曲线的终点P，定义η=∠PPP，η=∠PPP再以εηη=−||53123412434作为目标函数，根据二分法求出精确的τ。于是再根据所得的缓和曲线参数，以及直线的坐标，生成该缓和曲线。46 4道路平面设计基于图论的约束模型的研究4.1图论概述[26]4.1.1图的相关概念定义1（图）G＝（V，E）是一个系统，其中V是非空有限集合，V中的元素称为节点；E中的元素称为边，且E中的元素与V中的一对元素相联系，则G＝（V，E）称为图。定义2（有向图）设G＝（V，E）为一个图，若图G中的每条边都有方向，则称G为有向图（digraph）。亦可以表示为D＝（V，E）。为了区别无向图，用一对尖括号来括住顶点的序对，表示一条有向边，vi是起点，vj是终点。定义3（路径）设G＝（V，E）为一个图，vp，vq属于V。vp与vq间的路径指顶点序列vp，vi1，vi2…，vq，其中，，…，分别为图中的边。定义4（连通图）在一个无向图中，如果每对顶点都存在连通它们的路径，则此图就是连通图（connectedgraph）。定义5（强连通图）设G=（V，E）为有向图，对于顶点u和v当且仅当在图G上存在有向路径u到v，则记为u→v，当且仅当任意的u→v和v→u都在图G上时，称图G为强连通图。定义6（强连通子图）设G=（V，E）为有向图，如果将顶点的集合V分成一些子集Vi并且在每个子集中的任两个顶点都是强连通的,则称由顶点子集Vi导出的子图Gi=（Vi,Ei）为图G=（V，E）的强连通子图。定义7（偏序关系）集合A上的一个关系P，若它是自反、反对称、可传递的，则称P是A上的一个偏序关系，或简称为偏序。定义8（偶图）：设G是一个图，如果存在V的一个划分X，Y，使得G的任何一条边的一个端点在X中，另一个端点在Y中，则称G为偶图，也称为二分图，记作G＝(X，Y，E)。如果G中X的每个顶点都与Y的每个顶点相邻，则称G为完全二分图。47 定义9（匹配）设G＝(V，E)是一个互补节点子集M和V的二分图，若M是G的一个子图，且M不含环且任意两边都不相邻，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。4.1.2图的数据结构与线性链表的优缺点采用线性链表的数据结构的优点在于：结点空间可以动态申请和动态释放，不会产生溢出；元素之间次序由指针来控制，可以在任何位置进行插入和删除。缺点在于：每个节点指针域需要增加额外的空间存储；且它是非随机存储结构，对任意的结点操作都要从开始指针顺链查找该节点。在数据庞大的情况下，增加了时间和空间的复杂度。而图的数据结构能高效处理数据庞大的情况，表达没有任何瓶颈，其处理数据的时间复杂度和空间复杂度远低于线型链表存储。例如在路网中，所有的道路都可以统一成图的模型，而采用链表时就需要多个链表，且链表不能高效处理交叉情况。缺点：当建立约束图模型及求解时复杂。4.1.3图的数据结构的表达矩阵是研究图的一种有力工具，特别是利用电子计算机来研究有关图的算法时，首先遇到的是如何让计算机来识别图，这就不得不借助于矩阵，主要有两种[27]矩阵表示法。ACBED图4-1简易图1、关联矩阵关联矩阵的行对应于图的顶点，列对应于图的边（弧）。当用关联矩阵A表示无向图时，其元素aij定义如下：48 0，若顶点i与边j不关联aij=1，若顶点i与边j相关联当用关联矩阵A表达有向图时，其元素aij定义为：1，若边j自顶点i射出aij=-1，若边j向顶点i射入0，若顶点i与边j不关联根据上述定义，图4-1关联矩阵为：1100-10000011-10-10000-11100000-10-1由上述矩阵可知：(1)、由于每条边（弧）均有两个顶点，故上述矩阵每列都有两个非零元素且每列元素和为0：(2)、各行非零元素的个数为与该顶点相关联的边数。2、邻接矩阵邻接矩阵（或称相邻矩阵）的行和列都与图的顶点相对应。当用邻接矩阵B表达无向图时，其因素bij可定义为：bij为连接顶点vi和vj的边数当用邻接矩阵B表达有向图时，其元素b可定义为：bij为以vi为起点vj为终点的弧数。根据上述定义，有向图4-1的邻接矩阵是：0011010001000000010100000可知邻接矩阵主对角线上的元素全为零，若为简单图，该矩阵的元素全为0或1。无向图的邻接矩阵为一对称阵，其每一行或每一列元素值之和，等于与相应顶点元49 素之和等于射入给顶点的弧数。当图的顶点和边（弧）的编号确定之后，关联矩阵和邻接矩阵就与图建立了确定的一一对应关系，因而可用关联矩阵或邻接矩阵来表达图。一般来说，图的邻接矩阵比关联矩阵小，而且还可将矩阵的元素定义为边或弧的权，因而在存储和计算时用的较多。[28]图还有一种表述方式是每一个顶点和邻接点关联，称邻接点关联模式。这种模式通常更有效，因为它准确地储存了图中真实边的信息。对于每一个顶点，邻接点集合元素是目标顶点和边组成的偶对。该关联模式表达简洁，清晰，数据空间占用量少，调用简单。4.1.4图的搜索算法[29]图的搜索算法也就是遍历算法，它有两种标准方法：广度优先搜索（Breadth-FirstSearch，BFS）与深度优先搜索（Depth-FirstSearch，DFS）。1、广度优先搜索：广度优先搜索是用于发现关于图的信息的算法，可以应用许多到不同的问题。广度优先搜索与图的层次遍历算法类似，它是通过一个给定顶点（源顶点）发现其所有可达顶点的一种图的遍历算法。顶点被发现的顺序由各顶点与源顶点之间的距离决定，距离近的顶点会早于距离远的顶点被发现。b/2a/3g/1e/2d/0c/2f/1h/2图4-2广度优先搜索图图4-2示意了对一个简单图应用BFS算法的情况。其BFS的发现顺序是{d}{f,g}{c,h,b,e}{a}（顶点依据它们与源点d的距离分组）。50 2、深度优先搜索：深度优先搜索时许多图算法的基础构造块，强联通分量和拓扑排序算法都是基于深度优先搜索。图的深度优先搜索与二叉树后序搜索相近，它一次性访问图中所有的顶点。当决定搜索的下一步访问那一条边时，DSF总是选择在图中走的更深（这也是算法名称的由来）。DFS会选择下一个未发现的邻接顶点，知道到达没有未发现邻接顶点的顶点。之后算法会回退到先前顶点并且继续沿着从该顶点未发现边往下走。在DFS访问了一个给定顶点的所有可达顶点之后，它选择一个余下的未发现顶点，继续搜索过程。这个过程产生出深度优先树（depth-firsttrees）集合，并组成深度优先森林（depth-firstforest）。ai1b8c5j26df47e3gh图4-3深度优先搜索图对于给定的图，通常有多个合法的深度优先森林，因此也有多种不同却同样有效的方法归类这些边。实现DFS的一种方法是使用先进后出堆栈。DSF再处理顶点时将它的邻接顶点压入堆栈，之后弹出栈顶顶点供下一步处理。实现DSF的另一种方法是使用递归函数。这两种方法在概念上是等同的。深度优先搜索的一个有趣属性是每个顶点的发现时间和结束时间组成括号结构（parentheticalstructure）。如果当一个顶点被发现时，我们赋予它开括号，顶点结束时，输出一个闭括号，则最终结果就能被正确嵌套进括号集。DFS用作一些算法的核心部分，包括拓扑排序和连通分量算法。它也可以探测回路。图4-3的DFS的括号结构是：(a(c(f(g(d(b(ee)b)d)g)(hh)f)c)a)(i(jj)i)51 4.2道路平面设计图模型的建立为了方便地进行设计和使设计成果更好地符合地形、地物对线位的要求，无论是曲线型设计法、导线法、模式法、积木法、还是线元法等，除了具备各种静态的功能以满足道路及立交常规布线的要求外，还需要实现动态的拖动设计和再设计要求。目前国内软件实现这一功能采用的是：动态交互式积木法，动态交互式模式法，动态交互式导线法等等。为实现动态设计与再设计的需求，这些软件采用了多个设计方法，这些方法各自为政，均采用了链表的数据结构，没有相互之间的联系。链表一般只能表达线性对象，这使得表达上存在局限性。例如：在道路工程设计中，线性链表不能很好表达路网交叉情况，离散情况，连接离散中心线等。且这些软件很少考虑整体的数据结构，系统不稳定，出错几率大。平面设计没有统一的模型，[30]且模型之间缺乏约束关系，这也使得这些软件重单线，无系统，忽视了道路网的设计；只考虑主线的设计，与主线相关联的对象却没有考虑；计算慢，出错率高等等。因此，迫切需要建立统一的新的平面模型来满足设计的需求。本文根据目前国内情况，以及动态设计与再设计的需要，分析并建立了平面设计的图模型。在市政设计中无论是立交匝道布线，还是公路线位布设；无论是简单的线形，还是复杂的线形，各种线形当中都包含三种最基本的线形控制单元：直线，圆曲线，缓和曲线。因此本文引进了图论的知识，分别从线元法模型和导线法模型中建立了图模型：4.2.1线元法模型的图模型图4-4线元法模型的抽象图模型线元法模型的抽象图模型的建立：我们将图4-4里的交点和端点进行标识，得到一个点集{N1,N2,N3,N4,N5,N6}。然后建立边的属性集合{1,2,3}其中1代表52 连接的是直线，2代表连接的是圆弧，3代表的是缓和曲线。这样就可以抽象成一个图模型。4.2.2导线法模型的图模型在任意的导线法模型中，我们将所有的边进行标识，得到一个边的集合。例如图4-5，在图4-5中我们可以得到边集{e1,e2,e3}。这时我们建立对应点的属性集合{0,1,2,3}。其中0代表无属性，1代表一单元模式（圆弧），2代表三单元模式（缓和曲线＋圆弧＋缓和曲线），3代表五单元模式（缓和曲线＋圆弧＋缓和曲线＋圆弧＋缓和曲线）。这样我们就可以建立抽象的图模型。图4-5导线法模型通过线元法模型和导线法模型中建立的图模型，满足了道路平面线形的各种组合方式，把握了整个路网的设计。在道路设计中，不管什么形式的路网，都可以用平面图的方式来表达。再利用图的搜索方法来求得所需的单元，实现动态设计与再设计的需求。4.3约束图模型建立与其求解算法的研究4.3.1约束分析及其图模型的建立在道路平面设计中，其平面线形的几何实体之间都可视为有约束关系，其约束类型如下：几何约束：平行、垂直、相切、相交等；空间约束：高、低、范围等；工程约束：坡度、坡长等。现将每个实体视为一个点，有约束关系视为边，所有的约束视为边的属性，于是可以得到约束集合：1、单约束（点、距离）2、多约束｛（点、距离）（点、距离）⋯｝53 与此同时可以设置约束状态：开，关（0/1）；约束时间：临时，永久。[30]通过以上的分析，我们可以用一个抽象的无向图很好的描述一个约束系统：G(=GC,)cg其中G称为几何约束图（GeometricConstraintGraph），G={g|g为组成cgG的几何体}，C为几何约束集，描述几何实体的约束关系。cgC={|P(g,g)(g,g∧∈G)}。ijijij定义1：（几何约束的自由度）在指定的几何空间中，自由几何元素e的独立运[31]动数目称为自由几何元素的自由度（degreeoffreedom），记为DOFe()。自由度也可解释为：描述自由几何元素e在指定空间中的方位的最少独立参量数据，称为自由几何元素的几何形位参数。约束是对几何元素间相对位置的限制。定义2：（几何约束的约束度）不同类型的约束对几何元素所限制的独立运动数[31]目不同，这一数目称为该约束的约束度（degreeofconstraint），记为()DOCe。[32]图形中每个元素的约束情况可根据自由度与约束度的大小关系来判断：1.当dof=doc时，该元素处于完全约束状态；2.当dofdoc时，该元素处于欠约束状态。欠约束会造成几何元素位置的不确定性，而过约束则存在不能同时满足的约束条件，两者都会使系统无法完成正确的推理求解，在实际工程中也都是不允许的。本文在约束图中，列出了典型的几何约束所对应的符号以及约束度如下所示[33]：54 表4-1几何约束对应的符号及约束度约束对应英文符号约束度无约束uncon0相交cross1垂直upright1平行parallel1相切tangent1高high1低low1范围range1坡长grlenth1坡度gradient1下图为矩形的G图：cg图4-6矩形的Gcg图在计算机中，约束图的存储采用邻接矩阵存储，BGL里已有相应的代码可供调用。用无向图结构表达平面约束系统不仅直观、清晰，而且图的有关算法稳定性好、[34]效率高。4.3.2约束求解算法的研究对几何约束求解问题,国内外许多学者提出了各种方法。这些方法大致可以分[35]为数值方法、符号方法、基于规则几何推理法、基于图的构造方法四类。1、数值方法是首先将约束转化为一组代数方程，继而采用Newton-Raphson等55 数值迭代方法进行求解。这种方法通用性好，可以处理复杂的约束关系，但却不能良好地处理过约束和欠约束问题，并且由于采用数值迭代方法，对初值的要求比较[36]高。2、符号方法也是先将约束转化为一组代数方程,然后采用符号推理的方法，如Wu-Ritt分解算法或Grobner基方法将方程转化为易解的形式，最后采用数值方法求解。这种方法可以求解一般的非线形方程，但是由于它一般具有指数阶复杂度，不[37]适宜于大型约束系统。3、基于规则几何推理法：约束集用符号或谓词的形式来表示，然后用人工智能[38]和几何推理的方法求解约束模型，这种方法系统庞大，速度慢，无法处理循环约束。4、基于图的求解方法效率高，且能处理过约束和欠约束，因而得到广泛应用，[39]现今国内外采用的方法有：Hoffmann和Owen提出了基于图论的三角分解方法，将几何约束图分解为具有递阶层次的图簇分别求解，该方法的缺点是存在无法分解[37]的几何约束图；基于图分解的方法：它通过加入虚约束进行扩展和过约束问题的一致性判定，以及引入分解树等来解决约束问题，不过计算量增大；偶图DM-分解[40]法：它将一个几何约束系统分解成一些具有偏序关系的几何约束子系统，然后按偏序关系给出一个构造序列，从而降低了求解的难度。[41]目前国内还存在其他的几何约束求解算法：变尺度混沌优化算法，该算法把[42][43]遗传算法和混沌算法混合了在一起；遗传蚂蚁算法，改进型蚂蚁算法，算法前过程采用遗传算法，其结果是产生有关问题的初始信息素分布，后期过程采用蚂蚁算法，在有一定初始信息素分布的情况下，充分利用蚂蚁算法并行性、正反馈性、求精解效率高等特点。本文采用的算法就是偶图DM-分解法。由于这个分解是Dulmage-Mendelsohn首先提出来的，所以将这个分解称为DM-分解。此算法首先将几何约束求解问题用偶[44]图表示出来，然后通过偶图的DM-分解，利用最大匹配的概念，可以将一个几何约束系统唯一的分为一些满足偏序关系的不可分的DM-偶子图，在每个DM-偶子图中，用几何体和几何约束能建立相应的几何约束求解问题的构造序列。具体算法如下：[38]首先：用偶图来表示一个几何约束求解问题：56 设G{cg=[gg1,,]2LLgmn[cc1,2,]c}为一个几何约束其中gi代表几何体，cj代表几何约束。+−++建立偶图BVVE=()，；。设VVi1LiPi代表gi，其中pi是gi的自由度g−−的个数，也就是i的独立参数的个数；VVj1Ljqj代表cj，其中qj是cj约++束度的个数也就是cj所需方程的个数。如果cj与gj有关，则在顶点VVi1LiPi−−E与顶点VVj1Ljqj之间都加上一条边iklj,(1kp=,1LLij；lq=,)这样，就得到一个几何约束求解问题的表示偶图G。cg定义的DM-偶子图的一个偏序：由图G(,)=VE的强连通子图G(,)=VE可以定义如下关于强连通子图iii的偏序关系，也就是说对于集合V的子集Vi有：VVvvijij<⇔>，其中vVvVii∈,jj∈，若VVij<，记GGij<通过最大匹配的概念，将此偶图唯一的分解成满足以上偏序关系的不可分的偶+−+++−子图：记BVVErrrr=()，；其中Vr由VVi1LiPi(1im=,)L组成；Vr由−−EVVj1Ljqj(1jn=,)L组成；Er由iklj,(1kp==,1LLij；lq,)组成。Br由B，B，B⋯B，B组成。其中B，B⋯B是B的相容部分，也就是r0r1r2rsr∞r1r2rsr独立可解的部分。在相应的几何体和几何约束的基础上构成了每个可独立求解的部分，可获得Gcg的求解序列。Br0和Br∞分别为最小不相容部分和最大不相容部分。命题：由偶图DM-分解的性质知，Br0和Br∞分别为Gcg的欠约束部分和过约束部分。+−证明：在B0中，按照DM-分解的性质，在B0中V的顶点的个数比B0中V的+顶点的个数多。相应的在Br0中，Br0中的V顶点的个数等于几何体的自由度的数−+−目，Br0中的V的顶点数等于几何约束的约束度，由于Vr的数目比Vr的数目多，所以Br0是欠约束的。类似的，Br∞是Gcg中过约束的部分。由以上命题，通过判断Br0和Br∞是否为空，可以提示设计者是否存在欠约束和过约束，并给出其存在的位置。若两者都为空，则按照相应的偏序关系，输出B，r1B⋯B中相应的几何体和几何约束。以上定义的偏序关系说明了在DM-偶子图r2rs中，先构造序较低的部分，然后再构造序较高的部分，即B首先被构造，B最后r1rs57 构造。事实上，Br0的序最低，故应最先构造。这就意味着对于一个几何图形Gcg，只有在G的欠约束的部分添加了正确的几何约束后，才能得到几何图形G的解，cgcg从这一点可看到，预先提示几何图形的欠约束部分是很重要的。在改变几何约束的参数的值时，利用该偏序关系，相应的几何约束求解问题的解不必完全重新构造，只需构造一部分解，从而节约了计算时间。58 5结论与展望5.1结论本文是在国内外土木工程CAD软件开发的现状基础上，结合现有的图论、计算几何等工具提出第三代土木工程CAD软件开发的构想，并将此构想应用到土木工程CAD软件平面的开发中。且进一步挖掘图形的内在关联，抽象出覆盖面广的几何基础对象，结合约束模型来表现实际对象的完整信息。具体结论如下：1、在道路平面设计研究中，可以任意在后台控制缓和曲线的坐标通式的余项，来控制缓和曲线的精度；突破了传统的缓和曲线的最大偏角为180度的极限，将最大偏角控制在900度，这满足了设计人员在动态设计中的需求；道路平面设计中的各种缓和曲线组合的算法进一步完善。2、建立了统一的数据模型——约束图模型。此数据模型可以将所有的设计工作集中在一个系统中，易于数据共享，使得软件的适用面更广。重视了整体路网的规划，降低了程序的时间复杂度和空间复杂度。3、提出了约束求解算法。该算法利用偶图的DM-分解将一个几何约束求解系统分解成一系列具有某种偏序关系的子系统,从而降低了求解的难度。该算法不仅能按给出的偏序关系给出构造序列,还可以提示设计者在几何约束系统中是否存在欠约束或过约束并指出其位置；同时,在改变几何约束的参数的值时,利用偏序关系,相应的几何约束求解问题的解不必完全重新构造,只需构造一部分解。4、在具体的开发过程中，使用泛型编程的方法，开发基于统一数据模型的泛型函数库，并在此基础上开发软件系统，可便于软件的制作升级和用户的二次开发。5.2工作展望软构件技术在国内的应用起步较晚。迄今为止，我国还没有比较完善的将软构件技术应用于市政工程CAD软件开发上的理论或实践成果，将软构件技术应用于市政工程CAD软件开发的思想还处于萌芽状态。总的来说，我国构件化市政工程CAD软件的开发研究具有以下特点：1、构件化市政工程CAD软件开发方法的理论很不完善，且没有现成的实践经59 验可循；2、适用于市政工程CAD软件业的应用软构件资源严重缺乏，并且没有开发软构件的统一标准；3、市政工程CAD软件开发人员大多数还没有意识到软构件技术的重要性，还不具备开发构件化道路CAD软件的技术能力；4、市政工程CAD软件行业还没有生产软构件或集成软构件的生产商。由于这些原因，国内市政工程CAD软件开发需要一个比较成熟的基础理论，便于细分对象，进行构件化编程，利于分工合作。本文是在提出第三代土木工程CAD软件开发的构想后，对道路平面设计研究与应用的一个初步探讨，在进行理论研究后完成了部分平面设计程序开发工作。限于本人的理论水平和条件所限，还有许多方面的问题状况不成熟，需要作更深入的研究：1、对平面线元的研究已经更深了一步，但是在实际工程当中会遇到各种不同的问题，这就需要更进一步与实际结合，将线元研究进一步完善。2、本文所提出的偶图-DM分解法，是目前所有求解约束模型算法中最优之一，但是这种方法在市政CAD开发中是否能满足三维空间的任何情况，这都需要进一步研究。3、统一模型的建立，这一模型同样可以应用到道路纵断面、横断面、排水、给水、数字地面模型等等中，这也需要进一步对其他模块进行研究与开发，通过实践来完善市政工程统一数据模型这一理论，为市政工程CAD软件软构件开发提供一个比较成熟的基础理论。4、图论在市政CAD中还有更多的应用：比如图的着色原理在场平中的应用；加权有向图在给排水中的应用等等，这都需要进一步将这一理论应用到市政CAD的软件开发中。60 致谢本文是在导师吴小平老师的悉心指导下完成的。从课题的选题、资料收集到研究方案的实施、论文的撰写和定稿，整个过程都得到了导师的关心和指导。吴老师大度的做人准则、渊博的知识、丰富的实际工程经验、严谨的治学态度，深深地影响了我。吴老师把我引进了工程领域计算机应用这个神奇而充满诱惑的殿堂。在导师的指导下，我的专业知识和计算机软件水平有了长足的进步，这些都将使我终生受益。在此，谨向恩师致以最诚挚的敬意和最衷心的感谢！衷心感谢在这两年来李杰老师、吴瑞麟老师、资建民老师、何漓江老师、李小青老师等对我的指点和帮助，同时感谢杨俊、王义鑫、高飞、许天会、颜岗、路庆昌、黄凯、李楠、蔡泽、万伟等给我的生活及学习上的帮助。最后，感谢我的父母对我二十多年的养育，他们含辛茹苦的工作，给我创造了良好的生活和学习环境，让我拥有了健全的人格、健康的体魄、奋发向上的精神，在这里，祝愿父母身体健康、幸福快乐！张军华2008年5月26日于喻园61 参考文献[1]朱照宏,符锌砂,李方等.道路勘测设计软件开发与应用指南.第一版.北京:人民交通出版社,2003:3-15[2]涂圣文.CAD、GIS及VR集成技术在工程领域的应用研究[硕士学位论文].保存地点:华中科技大学图书馆,2005:1-4[3]朱照宏,陈雨人.道路路线CAD.第一版.上海:同济大学出版社,1998:7-11[4]李方.公路平面线形的一种新方法.中国公路学报,1992,(2):44-50[5]王福建,邓学均,李方.三次几何样条曲线在立交平面线形设计中的应用研究.中国公路学报,1996,(6):34-41[6]吴国雄.公路平面线形曲线型设计方法综述.公路,1996,(9):21-23[7]丁建明,李方.公路平面线形设计的五单元导线法.东南大学学报,1998,(3):45-47[8]Autodesk.Civil3D2005vsMX_FINAL.AutodeskWhitepaper,Nov2004:1-8[9]Autodesk.C3D2005vsGeopakFINAL.AutodeskWhitepaper,Nov2004:1-9[10]朱照宏译.MOSS导论.公路工程计算机应用,1995,(1-2):24-26[11]丁建明,程建川,李方.德国道路设计软件CARD/1系统.国外公路,1997,17(5):19-22[12]田丰林.基于DEM的道路设计CAD系统.浙江大学,2004,19(7):1-2[13]孙江宏,丁立伟,米洁.AutoCADObjectARX开发工具及应用.北京:清华大学出版社,1999:9-41[14]MeyersS.EffectiveSTL(影印版).北京:中国电力出版社,2003:23-40[15]WilliamFord,WilliamTopp.数据结构C++语言描述－应用标准模板库（STL）.第一版.北京:清华大学出版社,2003:400-402[16]MatthewH.Austern.GenericProgrammingandtheSTL:UsingandExtendingtheC++StandardTemlateLibrary,2003.4:55-60[17]http://www.wykobi.com/[18]http://www.codeproject.com/KB/recipes/Wykobi.aspx62 [19][美]BjornKarlsson著,张杰良译.BeyondtheC++StandardLibraryAnIntroductiontoBoost.清华大学出版社,2007:2-15[20][美]JeremyG.Siek,Lie-QuanLee,AndrewLumsdaine.TheBoostGraphLibrary:UserGuideandReferenceManual.Addison-WesleyPub.Co,2002:23-26[21]李建学,李光元,吴春芳著.数据结构课程设计案例精编（用C/C++描述）第一版.清华大学出版社,2007:75-91[22]吴小平,徐爱军.已知控制点反推圆曲线的方法.公路,1997,(6):37-40[23]吴瑞麟,吕小柏.缓和曲线直角坐标计算公式精度分析.武汉城市建设学院学报.1997,14(1):28-31[24]凌九忠.立交平面交互式图形设计中模式法的应用研究.西安:中国公路学报,1994,(3):10-14[25]PhilipJ.Schneider,DavidH.Eberly.计算机图形学几何工具算法详解.第一版.北京:电子工业出版社,2005:495-506[26]DiestelReinhard.GraphTheory（第二版）.世界图书出版公司,2003.9:36-45[27]BelaBollobas.Moderngraphtheory.世界图书出版公司,2003:50-76[28]KinchoH.Law,StevenJ.FenvesSparseMatrices,GraphTheory,andReanalysisComputinginCivilEngineering,1981:234-249[29]DouglasB.West.IntroductiontoGraphTheory(SecondEdition).机械工业出版社,2006:2-26[30]Lee,J.Y,Kim,K.Geometricreasoningforknowledge－basedparametricdesignusinggraphrepresentationJ.Computer－AidedDesign.1996,28(10):831-841[31]黎华,欧宗瑛.面向对象的柔性约束关系几何系统的建模研究及实现.机械设计与研究,2001,17(1):16-19[32]张国伟,马庆贤,焦伟.基于图结构描述的几何约束模型的研究与建立.ChinaAcademicJournalElectronicPublishingHouse,1994-2006:28-30[33]B.Aldefeld.VariationofGeometriesBasedonaGeometricReasoningMethod.Computer-AidedDesign,1988,20(3):117-126[34]陈忠良,梅树立.二维图形参数化设计中几何约束模型改进的无向图存储结构.63 中国农业大学学报,2000,5(2):100-103[35]孙大松,孟凡超,孙立镌.一个基于约束图的参数化设计模型.计算机工程应用,2004,(3):87-89[36]LightRA,GosssardDC.Modificationofgeometricmodelsthroughvariationalgeometry.Computer-AidedDesign,1982,14(4):209-214[37]何伟,唐敏,董金祥等.一种基于图分解的几何约束求解方法.中国图象图形学报,2003,(8):926-930[38]罗浩,陈立平,涂重斌等.参数化设计中的动态约束管理.计算机辅助设计与制造,1995,(11):36-41[39]王波兴,陈立平.基于约束矩阵的几何约束传播研究.工程图学学报,2004,(2):1-7[40]蒋鲲,张岩,潘锲.用DM-分解求解几何约束问题.黑龙江大学自然科学学报,2005,22(5):674-679[41]WANGMiao,LIUJing-lu,SUNYi-kang.TheHybridGenticAlgorithmBasedontheMutativeScaleChaosOptimization.ControlandDecision,2002,17(6):958-960[42]DorigoM,GianniDiCaro,ThomasStutzle.Antalgorithm.FutureGenerationComputerSystem.2000,(16):5-7[43]曹春红,卢奕南,李文辉.改进的蚂蚁算法在几何约束求解中的应用.工程图学学报,2004,(4):46-50[44]MUTOTAK.SystemsAnalysisbyGraphsandMatroids.AlgorithmsandCombinatorics3.NewYork:Springer-Verlag,1987,(6):56-6064

您可能关注的文档

相关文档

最近下载