产权体^[1]是三维地籍的登记对象，对其建模和表达是构建三维地籍的基础。现实世界中的产权体主要有两类。一类是房产产权单元(如一套住宅)，另一类是空域。无论哪一类，在几何上绝大多数表现为立面垂直，顶面、底面水平的规则体。建模规则体的一个常用方式是沿着第三维方向“推拉”(extruding)二维图形到指定高度。“推拉”分为两种，一种是不考虑二维多边形之间的拓扑关系，视每个多边形为独立的对象。重建时，以多边形为底面，“推拉”多边形生成盒状模型。图 1(a)是由3个多边形f₁、f₂、f₃构成的平面图，q₁、q₂、q₃分别是它们对应的“推拉”高度；图 1(b)是将这3个多边形作为独立对象沿z轴“推拉”生成的体。由于没有考虑多边形之间的拓扑关系，生成的体相互独立，体的内拓扑(体的内部拓扑)完备，外拓扑(体与体之间的拓扑)丢失，引起了拓扑不一致与数据冗余。图 1(b)左侧体的右立面与右侧两个体的左立面相互独立，前者与后二者的重合区域构建了两次。此类重建获取的模型为非拓扑数据模型，主要用于可视化，难以进行拓扑查询与分析，尤其涉及体的删除、插入等操作时，难以维护数据的一致性。而产权体作为宗地在三维空间的对等物，不可避免地要进行产权空间的查询、空间分析等。因此，保留产权体之间的外拓扑具有重要的意义。

图  1  两种模型的对比^[2]

Figure  1.  Comparison of Two Models ^[2]

下载: 全尺寸图片 幻灯片

另一种“推拉”是考虑二维图形的拓扑关系，视平面图为结点(0-单形)、边(1-单形)、面(2-单形)构成的2-拓扑复形(2-TP_Complex，简写为2-复形)^[2]。以2-复形为数据源，对其进行“推拉”，生成由结点、边、面、体构成的3-拓扑复形(简写为3-复形)。在该重建模式下，图 1(c)左侧体的右立面不再是一个独立的面，而是4个小面。此类重建称为拓扑一致性重建^[3]，获取的模型为拓扑数据模型，保留了产权体之间的外拓扑。

1 研究基础

构建保留外拓扑产权体的基础是寻找一种能够表达其拓扑关系的数据结构。常用的数据结构有翼边数据结构^[4]与半边数据结构^[5]两种。这两种数据结构只能表达单个产权体内拓扑，无法表达产权体之间的外拓扑^[6]。另外，这两种数据结构仅表达了结点、边、面之间的拓扑关系，没有考虑体之间以及体与低维单形之间的拓扑关系。根据三维地籍的应用需求，产权体需要表达结点、边、面、体之间的拓扑关系。为满足这种需求，本文提出使用3-组合图来表达产权体的方法。

1.1   3-组合图的相关概念

组合图(combinatorial map)^[7]是一种非流形数据结构，由一组飞镖和β_i(i=1, 2, 3…)关系构成。根据表达对象的维度不同，使用的组合图也不同。产权体是三维对象，使用3-组合图表达。

3-组合图是一个四元组：M=(D，β₁，β₂，β₃)，具有以下属性^[7]：

(1) D是飞镖的有限集；

(2) β₁是D上的一个偏排列，β₀是β₁^-1；一个偏排列是一个函数$ f:D \cup \left\{ \emptyset \right\} \to D \cup \left\{ \emptyset \right\}$，使得: ${\rm{ }}\forall {d_1} \in D, {\rm{ }}\forall {d_2} \ne {d_1} \in D, f({d_1}){\rm{ }} \ne \emptyset $且$ f({d_2}){\rm{ }} \ne \emptyset $推出$f({d_1}){\rm{ }} \ne f({d_2}) $；

(3) $ {\rm{ }}\forall 2 \le i \le 3$，β_i是偏对合；一个偏对合f使得$\forall d \in D, f\left( d \right){\rm{ }} \ne \emptyset $可得$ f\left( {f\left( d \right)} \right) = d$；

(4) $ \forall 1 \le i <i + 2 \le j \le 3, {\beta _i} \cdot {\beta _j}$也是一个偏对合。

符号$\emptyset $表示飞镖d在给定的关系β_i(i=0, 1, 2, 3)中不存在对应的飞镖。若β_i(d)= $\emptyset $，则称d是i-自由(i-free)。在不同的维度，i-自由代表不同的意义，0-自由表示d所描述的边没有前驱边；1-自由表示d所描述的边没有后续边；2-自由表示d所描述的边在边界上，仅属于一个面，没有被其他面共享；3-自由表示d所描述的面在体的边界上，仅属于一个体，没有被其他体共享。如图 2所示，图 2(a)是2-复形，图 2(b)是其对应的2-组合图，它由13个飞镖、13个β₁和3个β₂构成，每个飞镖表达了图 2(a)中的一条有向边及其起始结点，如飞镖1表达了边e₁与结点v₃。β₁用来连接飞镖，如飞镖1与飞镖2通过β₁连接在一起，β₁(1)=2，由于图 2(b)中的飞镖连成环，每个飞镖都有后继对象，不存在1-自由的飞镖。β₂是对合关系，用来连接两个方向相反的飞镖，如β₂(3)=9，β₂(9)=3；一对飞镖表达图 2(a)中的一条公共边，如飞镖3与9表达边e₃；边界的飞镖仅被一个面使用，表达边界上边的飞镖是2-自由，存在β₂(d)=$\emptyset $，如β₂(1)=$\emptyset $。

图  2  复形与组合图

Figure  2.  Topological Complex and Its Combinatorial Maps

下载: 全尺寸图片 幻灯片

在β_i(i=1, 2, 3)的连接下，飞镖之间形成相互连通的网。从一个飞镖开始，经过一个或多个β_i到达其他飞镖。轨道(orbit)函数定义了组合图的连通关系。轨道函数$ < {\beta _i} > \left( d \right) = \{ P{\rm{ }}\left( d \right)|P \in < S' > , d \in D\} $是一个集合(P是一个排列)，它是从d开始使用任意β_i(i=1, 2, 3)排列的组合(包括逆组合)所能到达的元素集合^[8]，S′为D的子集。这里β_i可以只使用一种，如 < β₁>，也可以混合使用，如 < β₂·β₁>。在图 2(b)中，< β₁>(1)返回飞镖集{1，2，3，4}，它表示包含飞镖1的面； < β₂>(3)返回飞镖集{3，9}，它表示包含飞镖3的边； < β₂·β₁>(4)返回飞镖集{4，7，9}，它表示包含飞镖4的结点。在3-组合图中，β₁(d)、β₂(d)与2-组合图相同，β₃(d)返回d所表达体的邻接体对应的飞镖，若β₃(d)=null，表示d所表达的体不存在邻接体。3-组合图中的轨道函数具有以下意义： < β₁, β₂>(d)返回的飞镖集表示包含飞镖d的体，< β₁, β₃>(d)返回的飞镖集表示包含飞镖d的面。本文使用3-组合图数据结构来表达产权体，利用它的β_i(i=1, 2, 3)与轨道函数来记录和表达结点、边、面、体之间的拓扑关系。

1.2   “推拉”相关概念

使用3-组合图表达产权体的前提是已存在产权体的三维模型。但是，当前仅有二维图和高度信息，没有体。为此，本文提出“推拉”与构建同步的3-组合图生成方法，即在“推拉”二维单形的同时直接创建表达三维单形的飞镖，并为它们添加β_i(i=1, 2, 3)关系生成3-组合图。“推拉”是一种由低维对象生成高维对象的方法，已在地理信息系统、计算机辅助设计等领域中得到广泛应用。在“推拉”之前，需要为复形中的每个面指定一个“推拉”间隔，这个间隔的长度即为对应产权体的高度。当沿着间隔“推拉”面时，与它关联的边和结点都被“推拉”相同的间隔长度，这就需要将面的间隔传递给边和结点。由于面的“推拉”间隔可能不同，导致与多个面关联的边和结点可能获得多个间隔。如图 1(a)中结点v₄同时与3个面关联，v₄获得了3个间隔。怎样将面的间隔传递给边和结点是“推拉”需解决的一个问题。文献[8]给出了间隔传递的示例，但没有给出具体的解决方法。针对这个问题，本文提出基于带权关联图的间隔传递方法。

2 带权关联图

为了将2-复形中高维度单形的“推拉”间隔传递给低维度单形，使用以下定义：对于一个λ-复形，它的每个单形cⁱ (0≤i≤λ)对应一个三元组(q′，ID，q)表示的点v，并且每对关联的单形cⁱ与${c^{i + 1}}({c^{i + 1}} \in \partial {c^i}, \partial $表示取cⁱ的边界)对应的点v_i与点v_i+1构成边e(v_i，v_i+1)，由点集V与边集E构成的图M(V，E)称为带权关联图。其中，ID代表i-单形的标识符，q代表高维单形传递来的“推拉”间隔$q = \mathop \wedge \limits_{i = 1}^n {q_i} $，符号∧表示该单形同时与多个高维单形关联，对应了多个间隔；q′代表从q计算出来的新间隔集，在间隔传递前q′=$\emptyset $。图 3是图 1(a)对应的带权关联图，它反映了不同维度单形之间的关联关系。

图  3  带权关联图示例

Figure  3.  An Example of Weighted Incidence Graph

下载: 全尺寸图片 幻灯片

矩阵$ \mathit{\boldsymbol{Inc}}\left( {{c^\lambda }, {c^\mu }} \right) = \left[ {\begin{array}{*{20}{c}} {q_{1, 1}^{\lambda , \mu }}&{q_{1, 2}^{\lambda , \mu }}& \ldots &{q_{1, m}^{\lambda , \mu }}\\ {q_{2, 1}^{\lambda , \mu }}&{q_{2, 2}^{\lambda , \mu }}& \ldots &{q_{2, m}^{\lambda , \mu }}\\ \vdots&\vdots&\vdots&\vdots \\ {q_{t, 1}^{\lambda , \mu }}&{q_{t, 2}^{\lambda , \mu }}& \ldots &{q_{t, m}^{\lambda , \mu }} \end{array}} \right]$是c^λ与c^u的关联矩阵，Inc(c^λ, c^μ)表示λ-单形与μ-单形之间的关联关系；$ q_{i, j}^{\lambda , \mu }$表示第i个λ-单形c_i^λ与第j个μ-单形c_j^μ(μ < λ)之间的关联关系，若它们不关，联则该值为$\emptyset $，对应的间隔值为(-∞, ∞)；若关联，则该值为$ [q_{i, j\;\;{\rm{min}}}^{\lambda , \mu }, q_{i, j\;\;{\rm{max}}}^{\lambda , \mu }]$。

基于带权关联图，使用关联矩阵可求得不同维度单形之间的关联关系。如图 1(a)中面与边的关联矩阵为：

矩形中a~f取实数，它们形成了“推拉”关系，扫描关联矩阵中的每一列即可获得从高维单形传递到低维单形的间隔集合。如求图 1(a)中边e₄对应的间隔集，扫描上面关联矩阵的第4列，获得与它关联的间隔为q₁和q₂，e₄对应的间隔集为{ q₁，q₂}，即{[a，b]，[c，d]}。

取集合中所有间隔的最小值和最大值进行排序并生成新间隔集，利用新间隔集更新带权关联图对应结点的q′域。如对e₄间隔集合中的最值从小到大排序，获得a(或c)＜d＜b，生成新间隔集{[a，d]，[d，b]}，并更新e₄的q′域。

3 “推拉”2-复形生成3-组合图

3.1   “推拉”源结点

为了与“推拉”生成的新单形区分，称被“推拉”2-复形中的结点、边、面分别为源结点、源边、源面。与源面关联且仅有一个“推拉”间隔的源结点，“推拉”后将生成两个新结点和一条新边，如图 1(a)的源结点v₅“推拉”后生成图 1(c)中新结点v′₅与v″₅以及新边E₁，它们恰好对应3-组合图中两个方向相反的飞镖：d₁与d₂，d₁由v′₅与E₁构成，d₂由v″₅与E₁构成，它们分别用于构建面F₁和F₂。而对于关联两个或两个以上源面的源结点，计算关联矩阵Inc(c², c⁰)，扫描关联矩阵中的一列，即可获得每个源结点对应的间隔集q。对q中所有间隔的最值排序，计算新间隔集q′，更新带权关联图中各个源结点的q′区域。

为获取源结点“推拉”后的飞镖，采用老新间隔对照法。扫描关联矩阵的列获得源结点的老间隔。利用老间隔计算新间隔，并计算新间隔的中点(最小值与最大值的平均值)，根据中点判断老间隔与新间隔之间的对应关系。若中点落在某个老间隔内，说明该中点对应的新间隔是该老间隔的一部分。如为求图 1(a)源结点对应的飞镖，计算源面与源结点的关联矩阵：

生成老新间隔对应图，如图 4所示。虚线上方为各个结点对应的老间隔，虚线下方为新间隔。新间隔的正方形代表其中点，中点上的折线指示了新间隔对应的老间隔。老间隔与新间隔是多对多的关系。如v₄有3个老“推拉”间隔q₁、q₂与q₃，它们生成了3个新“推拉”间隔q′₁、q′₂与q′₃，q₁对应了两个新间隔q′₁与q′₂，q₂对应了一个新间隔q′₁，q₃对应了3个新间隔q′₁、q′₂与q′₃。

图  4  结点新旧间隔对应关系图示例

Figure  4.  An Example of Corresponding Relation Map of Old and New Intervals

下载: 全尺寸图片 幻灯片

根据老新间隔对应关系生成飞镖。在此之前，先创建用于构建飞镖的新结点。提取源结点对应新间隔集中所有不重复的最值(包括最大值和最小值，重复的最值取一个)，并以这些最值为z坐标，源结点所关联几何点的x和y坐标为横坐标和纵坐标，创建三维几何点。假设源结点c_i0的新间隔集为q′_i，提取的最值按照顺序排列后为${{q'}_{i1}} <{{q'}_{i2}} < \ldots < {{q'}_{in}} $，则“推拉”c_i0后生成的三维几何点为$ {p_{ji}}({x_i}, {y_i}, {{q'}_{ij}})\left( {1 \le j \le n, {\rm{ }}j \in Z} \right)$。在此基础上，分别为每个三维几何点创建一个对应的新结点$ {v_{ji}}\left( {1 \le j \le n, {\rm{ }}j \in Z} \right)$，每个新结点引用对应的几何点。以“推拉”图 1(a)中的v₄为例说明，如图 5(c)所示。v₄对应的老间隔集为$\left\{ {\left[ {a, b} \right], {\rm{ }}\left[ {c, d} \right], {\rm{ }}\left[ {e, f} \right]} \right\} $，生成的新间隔集为$ \left\{ {{\rm{ }}\left[ {a, d} \right], {\rm{ }}\left[ {d, b} \right], {\rm{ }}\left[ {b, f} \right]} \right\}$。从v₄的新间隔集中提取4个最值：a＜d＜b＜f，它们与v₄关联的几何点的横坐标x₄与纵坐标y₄构建了4个三维几何点(红色点)：$ p_1^4({x_4}, {y_4}, a), {\rm{ }}p_2^4({x_4}, {y_4}, d), {\rm{ }}p_3^4({x_4}, {y_4}, b)$和$ p_4^4({x_4}, {y_4}, f)$，然后再创建4个新结点(黑色点)：v₁⁴，v₂⁴，v₃⁴和v₄⁴，它们分别引用对应的几何点，以嵌入到欧氏空间。

图  5  “推拉”结点与边的示例

Figure  5.  An Example of Extruding Node and Edge

下载: 全尺寸图片 幻灯片

利用老新间隔对照关系，分别为源结点中每个老间隔对应的各个新间隔创建一对方向相反的飞镖，无论这个新间隔是否已经创建了飞镖。创建方法如下：一个新间隔[q′_imin, q′_imax]恰好对应一对新结点v_p与v_q，它们形成两个方向相反的飞镖：[v_p，v_q)，[v_q，v_p)，左闭右开表示包含左侧的新结点。如图 5(c)所示，v₄的老间隔q₁对应了两个新间隔q′₁与q′₂，沿着它们“推拉”v₄，将创建两对飞镖：5与6，9与10(图 5(b))；v₄的老间隔q₂对应了一个新间隔q′₁，它创建了一对飞镖1与2(图 5(b))；v₄的老间隔q₃对应了3个新间隔q′₁、q′₂与q′₃，它们创建了3对飞镖：3与4，7与8，11与12(图 5(b))。

一对方向相反的飞镖恰好表达了两个邻接新面共享的新边，为保留新面之间的关系，需在它们之间添加β₂关系。为此，将飞镖的数据结构定义为包括Verter类型的一个四元组，具体为：对于一个飞镖d，startVertex表示d的起点，endVertex表示d的终点；Betas[4]是指向飞镖的指针数组，它分别用来指示通过β₀、β₁、β₂、β₃与d关联的飞镖的指针，若β_i(d)=null，表示飞镖d是i-自由；Marks^[3]是标记数组，它分别用于标记该飞镖是否与其他飞镖构建了β₁、β₂、β₃关系，已构建为true，未构建为false。

生成完一对飞镖d与d′后，为d的起点、终点字段赋值，将d′的引用赋给d，即d.Betas[2]=&d′，并使得Marks^[2]=true，表示d已经找到了通过β₂关联的飞镖。d′的处理方法与d相同。通过这种方式为每对飞镖建立了β₂关系，图 5(a)中的横线表示β₂关系。

除了添加β₂关系，还需要为纵向飞镖添加β₁关系。若一个老间隔对应多个新间隔，则需要将新间隔对应的多个同方向飞镖利用β₁关系连接起来。假设一个老间隔对应n个新间隔，则“推拉”源结点后创建了n对飞镖：d_i与d_i-1(i=1, 2…n)，d_i-1表示与d_i相反有向的飞镖。将d_i取出放入集合D中，利用以下步骤为D中的飞镖添加β₁关系：对于集合D中任意两个飞镖d与d′，若d.endVertex=d′.startVertex&&d.Betas[1]=null&& d′. Betas[0]=null，即第一个飞镖终点是第二个飞镖起点，且第一个飞镖是1-自由(没有后继边)，第二个飞镖是0-自由(没有前驱边)，使用β₁将它们连接起来，设置第一个飞镖的Betas[1]字段值为第二个飞镖的引用，并将第一个飞镖的Marks[1]设为true，表示d已经找到使用β₁关联的飞镖；连接后，第二个飞镖不再是0-自由，将第二个飞镖的Betas[0]字段值设置为非空。采用相同方法为d_i-1添加β₁关系, 如图 5(a)中5与9、10与6之间的β₁关系。

3.2   “推拉”源边

“推拉”一条源边将生成两条新边(横向)和一个新面。对于有多个新间隔的源边，由于不同位置的新间隔生成的飞镖数量可能不同，仍然需要使用老新间隔对照法求取新间隔对应的飞镖。首先根据关联矩阵Inc(c², c¹)求出每条源边对应的老间隔集，并计算对应的新间隔集，更新带权关联图中各条源边对应结点的q′区域。进一步求取每个新间隔的中点，计算它们与老间隔的对应关系。计算源边的每个老间隔对应的新间隔，并在新间隔的最小值和最大值处为每个新间隔创建两个方向相反的飞镖。创建方法如下：根据源边关联的两个源结点，查找这两个源结点对应的新结点(它们已在前面创建)，在新结点集中查找与新间隔最小值和最大值相同的新结点对。具体方法是：分别将最小值和最大值与新结点集中新结点引用的几何点z坐标比较，若某两个新结点v_i、v_j引用的z坐标与最小值(或最大值)相同，则创建一对方向相反的飞镖[v_i，v_j)与[v_j，v_i)；若老间隔对应的新间隔集中下侧的新间隔最大值q′_Lmax与上侧的新间隔最小值q′_Kmin相等，即q′_Lmax=q′_{K min}，则只在等值处创建一对方向相反的飞镖。

例如，为求图 1(a)源边对应的飞镖，计算源面与源边的关联矩阵，见前面的Inc(c², c¹)。扫描每一列，一列中非$\emptyset $元素即为该源边对应的老间隔。如扫描第3列，可得e₃有两个老间隔。利用老间隔计算新间隔，并计算新间隔的中点，根据中点判断老间隔与新间隔之间的对应关系。如e₃有两个老间隔q₁与q₃，它们生成了两个新间隔q′₄与q′₅(图 5(c))，q₁对应了一个新间隔q′₄，在q′₄最小值和最大值处分别为e₃创建13与14、17与18两对飞镖(图 5(d))；q₃对应了两个新间隔q′₄与q′₅，在q′₄最小值和最大值处为e₃创建15与16、19与20两对飞镖(图 5(d))，在q′₅最小值和最大值处为e₃创建19与20、21与22两对飞镖(图 5(d))，由于q′₄最大值与q′₅最小值是同一个值，多创建了一对飞镖17与18，需删除。最终q₃对应的新间隔创建了3对飞镖：15与16、19与20、21与22。与结点类似，也需要为“推拉”源边生成的飞镖添加β₂关系，添加方法与上面相同。

上述过程仅生成了表达新边(横向)的飞镖，而“推拉”一条源边还会生成一个新面，这个新面是由横向新边对应的飞镖和前面生成的纵向新边对应的飞镖通过β₁关系“缝合”而成。为了在横向与纵向飞镖之间添加β₁关系，以横向与纵向飞镖组成的数组为输入，使用上面添加β₁的步骤为横向与纵向飞镖添加β₁关系。

3.3   添加β₃关系生成3-组合图

上述过程创建飞镖并为它们添加了β₁与β₂关系。β₁将孤立的飞镖连接起来“缝合”成面；β₂将孤立的面连接起来“缝合”成体。经β₁与β₂连接“缝合”后，飞镖相互连接形成多个孤立的体，体之间并没有连接起来。

进一步添加β₃关系。β₃连接的飞镖是面“劈开”后两个半面的对应部分，这些飞镖具有以下特征：每一对通过β₃连接的飞镖都能在对面找到自己的“影子”飞镖，即一个和它相同的飞镖(除了标识符不同)。根据这个特征，在飞镖集里任取一个飞镖d，判断它是否存在“影子”飞镖d′，若存在，则与d通过β₁直接或间接连接的飞镖形成的 < β₁ >(d)(面)必然存在 < β₁ >(d″)(面)，它们之间的飞镖通过β₃两两连接，其中，d″=β₂(d′)，d与d″表示“劈开”前的同一条边。将 < β₁ >(d)中的每个飞镖的Betas[3]值设置为 < β₁ >(d″)中对应飞镖的引用，如d.Betas[3]=&d″，d″.Betas[3]=&d，通过这种方法为飞镖添加β₃关系。添加完β₃关系后，存在β₃(d)= d″，β₃(d″)= d。如图 5(e)所示，飞镖19存在“影子”飞镖18，而β₂(18)=17，飞镖17与19属于同一个新边。由飞镖17、19形成的 < β₁ >(17)与 < β₁ >(19)中对应的飞镖可通过β₃连接；连接后，β₃(17)= 19，β₃(19)=17。

4 3-组合图在三维地籍中的应用

三维地籍的产权体主要有建筑(分层叠加)单元(户)和室外的空域两类，它们都可以通过“推拉”方式重建，以第一类为例说明。建筑单元通常有对应的楼层平面图，并且绝大多数住宅式建筑物除地下外所有楼层内部结构一致，使用同一张平面图。基于该特征，以一张平面图为基础，将平面图“推拉”n个间隔(n为楼层数)就可一次生成整个建筑物所有产权体的三维模型。如图 6所示，图 6(a)是一个楼层平面图及对应的“推拉”间隔；图 6(b)是“推拉”后的体；图 6(c)是对应的3-组合图，因每层结构相同，仅绘制了两层。在图 6(c)中，β_i(i=1, 2, 3)将飞镖连通起来，支持飞镖对应的结点、边、面、体之间的拓扑关系查询。如查询两个面是否邻接，只要判断两个面中是否有通过β₂连接的飞镖即可，如F₁与F₂存在β₂(4)=5，它们邻接；如查询F₁所有邻接面，可先获取F₁的任意飞镖(如飞镖1)，利用 < β₁>(1)获取1所在面的飞镖集{1, 2, 3, 4}，对飞镖集中的每个飞镖使用β₂(d)，如β₂(4)=5，获取邻接面的飞镖，再使用 < β₁>(5)，就可获取表达邻接面的飞镖集，通过这种方式获得所有邻接面。

图 6(d)至图 6(f)是三维地籍的典型案例骑街楼。其中，图 6(d)是平面图与“推拉”间隔；图 6(e)是“推拉”后的体；图 6(f)是对应的3-组合图，图 6(g)是图 6(f)中间体的单独展示。基于生成的3-组合图可以进行体之间的拓扑查询。如判断图 6(e)左侧两个体是否邻接，可使用β₃(d)判断, 其中d为一个体中的飞镖，若在另一个体中存在飞镖d′，使得β₃(d)= d″，则这两个体邻接。如取图 6(f)中的飞镖1，使用β₃(1)= 2，2为另一个体上的飞镖，则这两个体邻接。

图  6  “推拉”2-复形构建产权体3-组合图示例

Figure  6.  An Example of Creating 3-Combinatorial Maps for Property Solids by Extruding 2-Complex

下载: 全尺寸图片 幻灯片

使用组合图表达产权体具有较高的构体效率。构体是将围成每个体的面找出并组织在一起。使用“推拉”生成的面集虽然围成体(集)，但并没有显式地表达哪些面属于哪个体，需要将隶属于每个体的面找出组织成体。现有的构体方法是基于最小角的自动构体算法^[9-10]，它从任意面开始，找到与之邻接的所有面，计算当前面与所有邻接面的二面角，并选最小角(或最大角)的面继续搜索，直到没有发现新面为止。该方法的时间复杂度为O(m×n×c)，其中m为建筑物三维模型中面的个数；n为平均每个面的边数(立面一般为矩形，n=4；上下底面一般由产权体的形态决定，上下底面一般取n≥4)；c为平均每条边关联的公共面个数(一般而言, 几个产权体的面共享一条公共边，在正常的建筑物结构中c≤4)。

3-组合图使用β关系将飞镖连接起来，使用轨道函数 < β₁，β₂>(d)就能将每个体的飞镖找出来，不再需要计算二面角。对于图 6(g)使用 < β₁，β₂>(1)将获得构成整个体的飞镖集。在构体效率方面，由于β₁、β₂预先记录了飞镖之间的关系，对于给定的 < β₁，β₂>(d)，可以直接获取所有通过β₁、β₂关联的飞镖，所以构体的时间复杂度为O(1)。而对整个建筑物中所有体的构体时间复杂度为O(a×b)，其中a为组合图中飞镖环的个数，b为每个飞镖环关联的其他飞镖环的个数。对比$ O\left( {m \times n \times c} \right)$与$O\left( {a \times b} \right) $，因每一个面都对应一个飞镖环，a=m；对于某一条具体飞镖环而言，关联的其他飞镖环个数小于该飞镖环的边数，b < n，显然，$O\left( {m \times n \times c} \right) > O\left( {a \times b} \right) $。因此，使用3-组合图构体效率更高。

5 结语

产权体的建模与表达是三维地籍的基础。传统的半边等数据结构只能表达单个产权体，无法表达多个邻接的产权体，为此，本文引入3-组合图来解决该问题。3-组合图的优势在于使用β关系将飞镖连接起来，支持不同维度拓扑单形之间的拓扑查询，并具有较高的构体效率。本文使用“推拉”2-复形的方式生成表达产权体的3-组合图，提出了带权关联图间隔传递方法、3-组合图生成方法等。然而，构建组合图是一个复杂的任务，本文仅在理论上做了探讨，还没有实现所提出的方法。下一步的工作是将该方法实现并应用到三维地籍领域，解决三维产权的建模和表达等问题。