OOSE方法第二个项目：基于Delaunay三角剖分的基站位置识别工具

基于Delaunay图形识别方法的移动网位置区识别工具

1)2月8号完成第一版本的原始需求说明书。《插花站点需求分析书》

2） 2014年2月10号报完成正式版本  《基于Delaunay图形识别方法的移动网位置区识别工具0210》


3) 2014 年2月12日完成更新版本，完善领域对象模型。

4)2月18日，提供数据样例。 组织测试。







4) 2 月13日完成Delaunay三角剖分算法的实现
同时完成手工验证，确认算法实现的正确性。




5） 遇到一个难题
由于画图组件使用的是坐标系的形式，x轴y轴像素坐标（pixel coordinates）的方式，所以使用的是integer，请参考以下文章
http://stackoverflow.com/questions/15690579/make-oval-rectangle-using-float-double-values


如果是经纬度，需要有一个坐标转换算法，可以参考以下代码：
http://sf-library.googlecode.com/svn-history/r16/trunk/SF/src/com/studiofortress/sf/graphics/GraphicsGL.java

6) 2月27号完成了整个组件集成和测试。相关的设计文档和MDL文件见附件。



7)3月3号完成QC材料

8) QC材料最后定稿，2014年3月7号

9） 创新材料定稿   2014年3月10号

10) 创新材料完善    2014年3月14号





11) 完成各类创新资料的汇总


Delaunay三角剖分算
http://baike.baidu.com/link?url=r054C5y_my3hIU55Uw76Cmn_i_SNPti_JLwkFqvAYBs31PZ69iAUbhNFPAXaNPIURk9Nkl5-CpJbI44UHYzLN_#refIndex_3_1691145


点集的三角剖分（Triangulation），对数值分析（比如有限元分析）以及图形学来说，都是极为重要的一项预处理技术。尤其是Delaunay三角剖分，由于其独特性，关于点集的很多种几何图都和Delaunay三角剖分相关，如Voronoi图，EMST树，Gabriel图等。Delaunay三角剖分有最大化最小角，“最接近于规则化的“的三角网和唯一性（任意四点不能共圆）两个特点。
目录1定义
2准则特性
3计算方法
1定义编辑【定义】三角剖分[1]：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：
1.除了端点，平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。
在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
优化处理:
理论上为了构造Delaunay三角网[2]，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示：
1.将两个具有共同边的三角形合成一个多边形。
2.以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
3.如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。
LOP处理过程如下图所示：Delaunay剖分的算法
Delaunay剖分是一种三角剖分的标准，实现它有多种算法。
2准则特性编辑准则:
要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：
特性:
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
3计算方法编辑逐点插入的Lawson算法[3]是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程LOP进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。
上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，遇到非Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
如左图所示：当离散点集构成圆环时，Lawson算法产生的非法三角形  离散点集合
  正确的三角剖分
  Lawson算法产生的三角剖分
2.2.Bowyer-Watson算法
Lawson算法（Lawson???）的基本步骤是：
1、构造一个超级三角形，包含所有散点，放入三角形链表。
2、将点集中的散点依次插入，在三角形链表中找出外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形优化。将形成的三角形放入Delaunay三角形链表。
4、循环执行上述第2步，直到所有散点插入完毕。
这一算法的关键的第2步图示如下：
词条图册更多图册◆
词条图片(8张)

1/1

参考资料

2.3  专利汇总