文章提出了一种健壮、简明和高效的约束三角剖分算法。该算法的基本思路是首先从组成约束曲线的有向线段的集合中任取一条有向线段，从该有向线段向左侧生成一个约束*大空圆凸多边形，从约束曲线所围区域内切去该多边形，对剩余区域重新计算约束曲线，然后重复**步直到区域被切割完毕，*后对多边形内部作三角剖分。文中称这一算法为切割算法。平面点集的约束*大空圆凸多边形剖分是**的。尽管在一般情况下，平面点集的约束三角剖分的结果不**，但是约束*大空圆凸多边形上的每一条边都会出现在约束三角剖分的任一可能的结果中，因此约束三角剖分的不**性仅仅体现在约束*大空圆凸多边形的内部。
图假设在经过若干次6/），）7三角形生成之后在一个圆的内部只生成了四个三角形，随后从三角形！的一条边生成三角形时完全有可能找到三角形的一个顶点导致三角形交叉基本概念散乱点：位置分布不规则的点称为散乱点。
约束曲线：对于边界由直线段组成的若干个有界区域，在区域边界上且左侧与区域邻接的全部有向直线段组成的集合称为一条约束曲线图。这些区域称为约束曲线所围的区平面散乱点集约束三角形剖分切割算法陈学工潘懋北京大学地质系，北京三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束*大空圆凸多边形剖分，然后对多边形的内部再作约束三角形剖分。文章还证明了平面散乱点集的约束*大空圆凸多边形剖分是**的以及约束三角剖分的不**性仅仅体现在约束*大空圆凸多边形的内部。使用约束*大空圆凸多边形的概念消除了由于退化现象三个以上的点共圆带来的算法上的潜在错误。
规则约束三角形约束*大空圆凸多边形散乱点计算机工程与应用域，约束曲线上线段的端点称为约束曲线的结点。
约束三角形的内部不包含约束曲线的结点、三个顶点彼此可见且三角形外接圆内部不包含从它的三个顶点都可见的散乱点作为生成三角形的一个约束条件，称为约束规则。这里一个点对另一个点可见是指这两个点的连线不穿过预先给定的约束曲线。约束规则的经典定义中不包括上面三个条件中的**个条件5！6.事实上**个条件并不隐含在后两个条件中图约束三角形：符合约束规则的三角形称为约束三角形。
约束*大空圆凸多边形：顶点来自散乱点集、各顶点彼此可见、各顶点在某个约束三角形外接圆上而且包含该约束三角形的*大凸多边形称为约束*大空圆凸多边形，取逆时针方向为该多边形的正方向。此定义隐含*大空圆凸多边形内部不包含约束曲线的结点。
：包含平面上一个点集在其所围的闭区域内的*小凸多边形称为这个平面点集的凸壳。
图！如图是由单独一条约束曲线所围的图在经典定义下，外若干个有界区域，其中阴影部分为这些区环三角形是一个约束‘（域的并。
算法描述设有向线段的集合是一条约束曲线。已知散乱点集包含约束曲线的各结点且包含在约束曲线所围的若干闭区域内。
初始化一个约束*大空圆凸多边形集合为空集，初始化一个约束三角形集合为空集。
从有向线段集合中任取一条有向线段，再从该有向线段的左方找一个散乱点，使该点与有向线段构成一个约束三角形。在该三角形的外接圆上且从三角形的三个顶点都可见的所有散乱点求凸壳后得到一个凸多边形，取逆时针方向为该多边形的正向。容易验证该多边形是一个约束*大空圆凸多边形。
将第步生成的约束*大空圆凸多边形加入到约束*大空圆凸多边形集合中。如果该多边形的一条有向边与有向线段集合中的某条有向线段相同，则从有向线段集合中删除该线段，否则将多边形的有向边反向，然后加入到有向线段集合中。这一步相当于从约束曲线所围的某个区域内切下一个约束*大空圆凸多边形，重新计算约束曲线。
重复步骤直到有向线段集合为空集。约束*大空圆凸多边形集合即为平面散乱点集的一个约束*大空圆凸多边形剖分。
对约束*大空圆凸多边形集合中每个多边形继续作约束三角剖分。*简单的方法是对多边形集合中的每一个多边形作如下处理：从多边形上任取一顶点，除该顶点两侧的两条边之外，该多边形上的每条边都与取定的顶点构成一个约束三角形。将这些约束三角形都加入到约束三角形集合之中。集合即为平面散乱点集的约束三角剖分。
约束*大空圆凸多边形剖分的**性在讨论约束*大空圆凸多边形剖分的**性之前，先证明不共外接圆的两个约束三角形不会部分重叠。反设三角形和三角形是两个不共外接圆但部分重叠的约束三角形，那么从约束三角形的定义，一个三角形的顶点不可能在另一个三角形内部。因为两个三角形不共外接圆且部分重叠，所以必有一个三角形的一个顶点在另一个三角形的外接圆的内部。这两个三角形只可能有三种相交形式图：没有共同的顶点、恰好共一个顶点或恰好共两个顶点。后两种情况可看成是**种情况的特例，下面只讨论**种情况。
设三角形的顶点在三角形的外接圆的内部图。由于两个三角形都是约束三角形，除非三角形或三角形内部有约束曲线的结点，否则点对于和三点都是可见的。从三角形和三角形内部的结点中取一个到线段距离*短的结点，那么这个结点对于和三点都是可见的。这结论与三角形是约束三角形相矛盾。可见两个不共外接圆的约束三角形不可能部分重叠。如果两个约束*大空圆凸多边形部分重叠，那么必可找出两个不共外接圆的约束三角形部分重叠，可见两个约束*大空圆凸多边形不可能部分重叠。由约束*大空圆凸多边形的定义，一个约束*大空圆凸多边形不可能是另一个约束*大空圆凸多边形的一部分，又因为两个约束*大空圆凸多边形不可能部分重叠，从而约束*大空圆凸多边形剖分是**的。
图约束三角剖分不**性的局部性一般情况下，平面散乱点集的约束三角剖分的结果不**。文章将证明这种不**性仅仅局限于约束*大空圆凸多边形的内部。要证明这一点只需要证明约束*大空圆凸多边形的每一条边都出现在约束三角剖分的任一可下转页计算机工程与应用上接页能的结果中。设是平面上某散乱点集的一个约束*大空圆凸多边形，集合是该散乱点集的任意一个约束三角剖分所得的三角形的集合。如果的某条边不出现在集合表示的剖分结果中，那么线段必定与集合中的某个三角形的一边相交，而且交点不在线段和线段的端点。
假设包含该三角形的约束*大空圆凸多边形为‘，那么和部分重叠。这结论与约束*大空圆凸多边形剖分的**性矛盾。可见约束三角剖分的不**性具有局部性。
结束语文章提出的约束*大空圆凸多边形的概念消除了退化现象平面三个以上的点共圆造成的算法上的潜在错误，同时得到了平面散乱点集的约束*大空圆凸多边形剖分具有**性的结论以及约束三角剖分不**性的局部性。作者已经实现了前面提出的平面散乱点约束三角剖分算法，并且成功地把它运用在三维空间信息系统的软件开发中。该算法的时间复杂度在*坏情况下为，这里为散乱点的个数。收稿日期：年月！闵卫东，唐泽圣二维任意域内点集的（），。三角划分的研究CDE分功能地来处理所有的键盘响应，这是不合面向对象思想的。
因此有必要像前面所说的那样重新规划类的功能。使类的存在方式更具有逻辑性。但考虑到性能和效率的因素，在调整中，也应为日后局部程序重组留下一定的空间。
调整继承、合成关系。例如，原来软件中使用了一个工具栏类的继承类，而现在发现，继承类所能完成的处理，父类也能胜任，于是舍弃继承类。再如，原来的单文档模式下，描述文档类的状态环境类是合成于应用程序类中的，而现在，多文档模式下，一个应用拥有多个文档，这就必须使状态环境类合成于文档类中。
调整类间的通信机制。原有的类间通信主要是通过直接访问相关类的公有变量或函数来实现的，这很容易破坏类的相对独立性，造成维护上的困难。而实际上，对一些系统相关类，完全可以利用提供的消息传递机制来达到通信的目的，作者就是利用这一机制，大大地简化了原有的类间通信机制。
设计层的工作主要是类结构框架的重构，而实现层主要是这些类的具体编码实现，包括新类代码的编写，旧类代码的整合、修改，等等。实现层还有一个任务是局部的程序重组实现，这是出于提高软件运行性能的考虑。
方法与流程由于项目的特殊性，诸如再工程的移植性质，与的相关性，原软件已具有的面向对象性，大爆炸的方法在这里不是很合适。
在增量方法与演进方法的选择上，作者采取了折中的办法，即大致不改变系统的整体结构，大部分地方仅作到的转换，在某些局部，如调用关系复杂、功能划分不清的地方，做局部的重整。同时，为了提高程序的性能表现，对相关的地方做了再规划。
图G一般面向对象开发及本项目开发过程对照采取这一方法，主要是为了使项目开发过程向一般的面向对象软件的开发过程靠拢。一般的面向对象的软件开发都经历初始、细化、构造迭代、移交几个阶段。在初始阶段进行需求的大致分析；在细化阶段进行各方面的分析包括风险、技术等；在构造迭代阶段进行各种用例的分析、设计、编码、测试和集成，多个用例就构成多次迭代；在移交阶段进行排错等工作。对于作者的改造项目，其初始阶段、细化阶段有别于对应的阶段，但在分析原系统中，改造其功能结构，尽量能产生一个符合面向对象模型的体系，使其驶入构造迭代的轨道，并在其中分阶段地进行迭代精化，直至移交如图。这样做，一方面可以尽可能利用成熟的面向对象的开发方法，降低开发风险，减小开发难度，另一方面，也适合现实中相对松散的开发组模式。
其实，对模型的描述和对方法的说明在某些地方存在着重复性，只不过模型侧重于对概念层次的阐述，而方法侧重于具体实践的动态说明。
由于篇幅的原因，具体的项目开发流程不在此赘述。实践证明，在软件工程的相关理论指导下，相关知识的灵活运用下，该项目是成功的，完全满足了用户的需求。
结束语软件再工程是一个很实用、很具体的课题，它有一套相应的理论、技术及工具。但对于一个具体的项目来说，光有这些还不行，还需要有与项目相关的知识。对所有相关知识的深入理解，透彻的把握、灵活的运用，是项目获得成功的关键。同时，对具体项目的实例研究，也将促进软件再工程学说的发展。
年月―实践者的研！刘超，张莉编著可视化面向对象建模技术：标准建模语言R0S教程C0E北京航空航天大学出版社，‘HT，K） UKV）著，刘宗田等译FWW编程思想C0E机械工业出版社，
