终于,我们进入了算法的核心地带。
在《第二回:漫谈新思路,是我们自己干的时候了》中我们说到整个算法的处理过程包括三个大块:寻找辅助线、寻找交点、寻找三角形。交点的寻找及其结果的组织,是能否找到三角形的关键,因而本回会用较长的篇幅把这个过程阐述清楚,为后文打下坚实的基础。
由于内容实在过多,为了避免冗长造成的疲倦,我将本回分成两个部分。本文的主题是介绍寻找交点和寻找三角形两个大块的纽带——二维表Point2Table,还记得《第二回:漫谈新思路,是我们自己干的时候了》“二、寻找相交点”小节中提到的二维表吗,没错,就是它!
一、 类图和代码
这里是整个类的代码,行数逾百,后面会进行逐段的分析。
二、 两个缓冲的宿主
容易看出属性中的IndexBuffer和VertexBuffer正是上篇文章中设计的数据结构,客户代码可以直接调用这两个只读属性获得处理完毕的两个缓冲,进而加以利用,所以说Point2Table除了是寻找交点和寻找三角形的纽带外,还有另一重身份,那就是整个算法和客户代码的纽带,这里是算法的出口。在调用IndexBuffer属性时,程序会去调用寻找三角形的逻辑,这部分内容我们将在下一回中详细介绍。在调用VertexBuffer属性时,程序直接返回顶点缓冲vb,这个缓冲是用户在寻找交点的过程中填充的,这部分内容我们将在本回的下一部分中详细介绍。
三、嵌套类PointIndexWithT
在上面的类图中,有一个可爱的棒糖,棒糖下面是一个名字古怪的私有嵌套类PointIndexWithT,翻译过来就是带着T的点索引,索引就是上文VertexBuffer中的索引,T就是《第四回:掌握数学工具,没个好帮手怎么行》“三、用向量描述直线”小节中提到的T。下图可以直观的看出Index和T的含义:
该类的引入只有一个目的,将某条扫描线上的所有交点从左至右进行排序,注意一点,这里参与排序的是T,而排序的实体(我们要的结果)是点的索引。
2 If Not (TypeOf obj Is PointIndexWithT) Then
3 MsgBox("PointWithU中传入参数有误")
4 Return 0
5 End If
6 Dim pwu As PointIndexWithT = CType(obj, PointIndexWithT)
7 Return Me.t.CompareTo(pwu.t)
8 End Function
上面的这段代码实现了IComparable接口的CompateTo方法,目的是让PointIndexWithT的数组可以使用框架提供的Sort函数。代码很简单,只是简单的比较了一下T,我们已经说过了,T就是为了排序而生。如果你还不是太清楚,没关系,下面我就用一个例子来说明。
四、例说排序
下图是三角剖分一个凹多边形的过程,图中的VB代表VertexBuffer,也就是顶点缓冲。每一行后面会有几个矩形框,每个矩形框代表一个加入到Point2Table的点,框中上面一个值代表Index,下面的值为该点的T。
上图中的T只是一个示意值,请不要用尺子丈量。
五、排序的实现
有了上面直观的了解,相信下面的内容很容易理解。
Private rows As New List(Of List(Of Integer))
2