蜂窝网格在光栅图形中的优点

321理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html18页“Honeycomb”瓦伦丁·E Brimkov布里姆科夫1，2东地中海大学Famagusta，TRNC，Via Mersin 10，土耳其Reneta P. Barneva3纽约州立大学弗雷多尼亚分校Fredonia，NY 14063，USA摘要在本文中，我们总结了一些意见的优点，使用六角形网格在光栅图形。我们开始研究蜂窝图形，其2D版本是基于一个六边形网格，而在其3D对应的体素是六棱柱。我们设计了线性对象的解析蜂窝几何，这与经典光栅图形中已知的类似发展相似[6]。我们还展示了蜂窝图形的某些优点，特别是它提供了一个更好的隧道无近似连续对象。1介绍Rn的凸多面体拼接P称为正规的，如果P的任何两个拼接的交集是空的或似乎是它们的公共（n-d）维刻面，对于某些d，1≤d≤n。 考虑Rn的正常平铺P，n=2或3，由相同瓦片P的副本，使得以下条件是met.(i) P是凸集;(ii) 对任意P1，P2∈P，存在平移τ使得τ（P1）=P2;(iii) 设p是瓦片P ∈ P上的一点。 则p的二重集在 所有来自P的瓦片在Rn中形成晶格。1作者感谢Jean-PierreRe veil l`es阅读本文的早期版本。2电子邮件：valentin. emu.edu.tr3电子邮件地址：barneva@cs.fredonia.edu2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。里姆科夫和巴尔涅瓦322(a)(b)（c）第（1）款图1.一、 a）用一个小工具贴瓷砖。b）砖砌瓷砖。c）通过准正六边形平铺。(a)(b)（c）第（1）款图二、a）正方形网格。b）规则的砖砌网格。c）正六边形网格。我们将这样的平铺称为均匀平铺。首先我们考虑R2的均匀平铺.众所周知（也很容易看到），只有在以下两种情况下才有可能实现均匀平铺• 情况1：瓦片P是一个瓦片（图1a，b）;• 例2：P是一个六边形，它的相对边相等且平行。 等六边形将被称为准规则的（图1c）。图块的顶点和边形成网格。瓷砖的中心是其对角线的交点。有时我们会用它的中心来识别瓷砖。一个网格可以看作是一个无限平面图G=（V，E），其顶点集V和边集E分别由多边形的顶点和边组成注意，图1c的六边形网格的图形与图1b的矩形网格的图形同构。因此，这两个网格具有相同的拓扑结构，尽管它们的瓦片形状不同。图1b中的平铺/网格将被称为砖砌平铺/网格。如果我们要求瓦片是正多边形，那么我们得到正方形图2a所示的规则砖砌网格、图2b所示的规则砖砌网格和图2c所示的规则六边形网格。如果我们考虑R3的均匀平铺，也会有类似的考虑. 不难看出，在这种情况下，瓦片P必须是平行六面体（图3a）或六棱柱，其底部是准正六边形（图3b）。网格和瓦片中心的概念与2D情况类似地定义。R2和R3中的正方形和立方体模型广泛应用于图像处理和计算机图形学中。光栅计算机图形是在正方形网格上建模的，其中正方形瓦片通常被称为像素。 方格网 都是在电脑屏幕上实现在三维空间中，里姆科夫和巴尔涅瓦323图3.第三章。R3的均匀平铺的两个可能的平铺。图形模型基于立方体网格，其中立方体被称为体素。六边形网格和图-基于这些模型。在本说明中，我们试图表明，这在某种程度上是不值得的。更重要的是，我们将展示使用六边形网格瓦片（称为2-hexels）的图形模型比传统的图形模型有一些优势类似的结论适用于3D空间，其中可以使用体素而不是立方体，体素是六棱柱（称为3-hexels）。基于hexels的图形模型将被称为蜂窝模型。本研究的基本目的是为蜂窝图形学的发展提供动力和理论依据。请注意，所提出的模型是现实的，并承认一个简单的硬件实现。实际上，六边形栅格在图像处理中是公知的（参见，例如， [8]）。 在这里，我们将展示：• 所提出的蜂窝模型采用简单的数学。• 在某些方面，它们比• 一些基本的欧几里得基元（如直线、线段、多边形、圆、平面等）允许一个简单的分析描述。• 蜂窝模型以比其他模型更直接的方式确保离散对象的隧道自由度• 它们确保了对连续对象的更好的无隧道近似• 有可能直接传递概念和结果从经典的离散几何到基于蜂窝模型的几何。本文件的结构如下。在下一节中，我们将回顾一些定义，并介绍一些将在下一节中使用的概念。在第3节中，我们提供了理论基础，发展二维离散解析几何的线性对象和圆。我们还揭示了我们的方法比经典的一些优点。在第4节中，我们将考虑扩展到3D空间。在第5节中，我们关注算法和复杂性问题。在最后一节6中，我们以一些评论结束。所提出的理论部分平行于传统光栅图形中已知的一些概念和结果。因此，我们省略了不必要的细节，并专注于与经典理论的本质区别，优势和优势。我们的一个重要目的是使所考虑的概念和事实直观地清楚。考虑到这一点，我们经常避免技术细节和计算，而是使用说明性的数字和例子。观察和陈述的验证要么是直截了当的，要么是相当技术性的，要么是两者兼而有之，留待练习。里姆科夫和巴尔涅瓦324T−∈ T≤ ≤−㈠㈡（一）㈠ ㈡㈢（b）图四、在正方形/立方体瓦片的情况下对定义1的说明：a）2D离散对象中的隧道(i)1-隧道，（ii）0-隧道。b）3D对象中的隧道：（i）2隧道，（ii）1隧道，（iii）0隧道。2基本定义和事实设T是Rn上的正规平铺，其中n= 2或3. 我们假设的瓦片是凸多面体。对于一组瓦片A，我们表示U（A）=P∈AP。一组图块将被视为一个离散对象。瓦片P的j维刻面将被称为j刻面，对于某个j，0jn1. 因此，P的0-刻面是它的顶点，1-刻面是它的顶点。边，而3D多面体的2-小平面是它的2D面。如果两个图块共享一个j面，则它们称为j相邻图块离散对象A中的k路径是来自A的瓦片序列，使得每两个连续瓦片是k相邻的。如果两个图块之间存在k路径，则它们是k连通的。 一个离散对象A是k-连通的，如果有一条k-路连接A的任意两个瓦片。如果一个离散对象至少是0-连通的，则称它是连通的。否则，它将断开连接。4设D是离散对象A的子集。 如果D不是k连通的则集合D被称为在A中k-分离。欧几里得对象M的超覆盖是所有被M包围的瓦片的集合S（M）。 设Γ为R2中的曲线或R3中的曲面。在非常一般的意义上，可以将超覆盖S（Γ）的每个子集视为Γ的离散化，或者视为对应于Γ的离散曲线/曲面。在离散几何中，隧道是一个重要的概念。直观地说，k通道是离散对象中的一个位置，离散k路径可以穿过该位置。 隧道离散对象（特别是离散曲线或曲面）通常基于可分性的概念来定义。更准确地说，让一组瓷砖A在离散对象B中是k-分离的，但在B中不是j-分离的。 然后对于任何j，k，A都有j-隧道<. 在考虑到集合A（R2中的离散曲线或R3中的离散曲面）不应该在另一个集合中分离，可以使用以下更一般的定义。定义2.1设A是Rn中的离散对象，其中n= 2或3。4经典，0-相邻/连通（分别为1-相邻/连接）像素被称为8-相邻/连接（分别4-相邻/连接）。在3维中，0-相邻/连接（分别为1或2-相邻/连接）体素称为26-相邻/连接（分别为18或6-相邻/连接）。里姆科夫和巴尔涅瓦325a) 如果n= 2，则：(i) 如果集合U（A）是断开的，则A具有1-隧道（图4a（i））;(ii) A有一个0-隧道，如果在A中存在两个瓦片共享一个顶点，并且没有来自A的其他瓦片共享同一个顶点（图4a（ii））。b) 如果n= 3，则：(i) A有一个2-隧道，如果U（A）不是一个单连通集（图4 b（i））;（这种隧道有时被称为洞。(ii) A有一个1-隧道，如果在A中存在两个瓦片，它们正好共享一个边，并且没有来自A的其他瓦片共享相同的边（图4 b（ii））;(iii) A有一个0-隧道，如果它包含一个顶点为q的瓦片P，使得集合U（A）-q不是单连通的（图4 b（iii））。没有k-隧道的离散对象称为无k-隧道。对于任意k（0≤k≤ 2）都没有隧道的对象，简称为无隧道。5隧道的概念在体素化场景的通过将离散光线从图像投射到场景[5]。正如Kaufman所说，更细的光线对光线遍历更有吸引力。因此，期望构造k-无隧道离散对象，其中k尽可能小理想的情况是对象是无隧道的。2D的情况下是比较简单的，因为一个离散的对象的连接完全表征的隧道的拓扑结构。 更准确地说，对象A包含1-隧道当且仅当它是断开的;A包含0-隧道但没有1-隧道当且仅当它是连接的但不是1-连接的;A是无隧道当且仅当它1连接。然而，在第三维中，情况更加复杂，因为人们可以从上面的定义中推断出来。有时这种复杂性对离散化算法的设计有一定的负面影响。特别地，控制对象连接性可能是困难的。此外，确保离散对象是连接的甚至可能是一个问题[2]。确保隧道自由度也是一项艰巨的任务[2，3，4]。此类问题的一个根源是正方形网格的拓扑结构。仍然在维度2中，两个像素的连接性存在三种可能性，并且因此两个像素的集合的隧道结构存在三种可能性。在3维中，对应的情况数为4（0、1、2-隧道和隧道自由度）。当构造更复杂对象的无k隧道离散化时，这种可能性可能会导致某些理论上的困难在第3节和第4节中，我们将展示如何通过使用蜂窝模型来克服这个问题。在此之前，我们回顾了解析离散几何的一些基本概念。5经典地，在二维空间中，一个0-隧道（ 1-tunnel）被称为8-tunnel（resp. 四-隧道）。在三维空间中，一个0-隧道（1-或2-隧道）被称为26-隧道（分别。18-或6-隧道）。里姆科夫和巴尔涅瓦326}∈∈{∈|≤|||||| ||||||||||解析离散几何光栅图形中的一种新方法是基于解析离散几何的方法[6]。这里的主要目标是获得基本欧几里得基元的简单分析并在此基础上创建工具，用于对由这些基元组成的更复杂的对象进行高效建模。接下来，我们回顾一些基本的定义。离散坐标平面由单位正方形（像素）组成，以平面中二维笛卡尔坐标系的整数点为中心。离散坐标空间由单位立方体（体素）组成，以空间中三维笛卡尔坐标系的整数点为中心。像素/体素的坐标是其中心的坐标。像素/体素的边缘平行于坐标轴。二维算术线是一组像素L（a1，a2，μ，ω）=（x，y）Z20 a1x + a2y + μ< ω，其中a1，a2，μZ，ωN。ω称为线的算术厚度或宽度，μ称为内部平移常数。向量（a1，a2）是直线的法向量。 算术线L（a1，a2，µ，ω）如果ω = max，则为0-conn ect d（经典y，8-conn ect d或朴素）（|的1|、|一个2|），以及1-连通（经典，4-连通或标准），如果ω = a1+ a2。 的标准线是最细的无隧道算术线。算术平面是一组像素P（a1，a2，a3，μ，ω）={（x，y，z）∈Z3|0≤a1x+a2y+a3z+μ <ω}，其中a1，a2，a3，μ ∈ Z，ω ∈ N。ω是平面的算术厚度而μ是它的内部平移常数。 向量（a1，a2，a3）是法线向量到平面。一个算术平面P（a1，a2，a3，μ，ω）如果ω= max（a1，a2，a3）则是朴素的，如果ω=a1+a2+a3则是标准的。 标准平面是最薄的无隧道算术平面。3二维蜂窝解析几何3.1纬向坐标系考虑图2c和2b的平铺。如上所述，相应的网格是同构的。这些平铺的一个重要属性是任何两个不相交的平铺都是1-相邻的。与经典矩形网格的情况相反，这里0-邻接是不可能的。因此，一个连通的离散对象总是1-连通且无隧道的。现在我们将在六边形网格上建立解析离散几何的基础2-hexel的中心形成晶格L，其单元是单位菱形（见图5a）。六角元素形成离散的六角空间。在它上面，我们定义了一个六边形坐标系。为此，我们选择一个hexel并将其中心O定义为坐标系的中心。中心的坐标都是零，即，O=（0， 0）.接下来，我们固定两个坐标轴，如图5a所示。系统的基向量b1和b2是晶格基的向量，与坐标轴对齐。六角坐标系里姆科夫和巴尔涅瓦327b2Quad IOB1−−（一）Quad IV(a)（b）第（1）款图五、a）半球形坐标系。b）四边形I、II、III、IV和锥体C1C2。直线g的法向量n=（a1，a2）属于C1。表示为yOb1b2。坐标轴Ob1和Ob2将平面分为四个象限，分别表示为Quad I、Quad II、Quad III和Quad IV。原点O是Quad II和Quad IV的共同点。Ob 1的阳性部分和Ob2的阴性部分属于四分体IV，而Ob2的阳性部分和Ob1的阴性部分属于四分体II。 相对于坐标系Ob1b2，人们可以建立笛卡尔解析几何的类似物。3.2直线、线段和多边形设a1x1+ a2x2+b= 0是六角坐标平面上直线g的方程。 我们将假定系数a1、a2和b是比值. 为了简化一些考虑，我们将假设它们是整数，并且gcd（a1，a2）整除b 这确保了行g包含无穷多个等距格点。向量n=（ a1， a2）是g的正规向量. 线g与向量VJ=（a2，a1）和vJJ=（a2，a1）.直线g的法向量（其中向量vJ和vJJ属于四边形I和四边形III）形成开锥C1（图5b）。类似地，向量vJ和vJJ属于四边形II和四边形IV的直线g的法向量形成闭合圆锥 C2（图5b）。显然，C1<$C2=R 1，C1<$C2= R2。现在我们定义一条对应于g的通用离散线，如下所示。gD（a1，a2，b）={x∈L：0≤a1x1+a2x2+b+[t/2<$t}，哪里|的1|+的|一个2|，若n=（a1，a2）∈C1，参见图6。最大值（|的1|、|一个2|），如果n=（a1，a2）∈C2.参数t被称为线的通用宽度gD。它等于平行等距直线的数量，这些直线包含来自gD的六角形的中心。B2nGB1C2C1t=里姆科夫和巴尔涅瓦328−||||| ||22B2B1图六、两个离散的线段。 一个有端点（2，1）和（4，7），而另一个有端点（0，0）和（6，14）。前者的法向量属于圆锥C1. 此离散线不具有包容属性。后者的法向量属于圆锥C2。这条离散线具有包容性。这样定义的离散线gD是这种类型的可能的最细的连通线。对于较小的t值，线变得不连通，而对于较大的值，它包含额外的六角，然而，不影响线的连通性。我们注意到，取决于法向量所属的象限，通用宽度等于标准或标准的厚度ω方形网格中的直线（见第2节）。还应注意，如果t=|a1+a2，则离散线具有包含性质[5]，即，它完全包含了对应的连续线。如果t= max（a1，a2），那么一般情况下，包容性不成立。给定两个hexelh1和h2，可以获得具有端点h1和h2的无隧道离散段。以同样的方式，可以构造无隧道的离散多边形。3.3离散圆圆是另一个基本的欧几里德本原，它承认一个简单的分析定义。在正方形网格中，离散圆已在[1]中解析定义。更准确地说，可以考虑以下离散圆，在O（0，0）和半径r∈N。C（r）=.（x，y）∈Z2：.Σ21r−2≤x+y<.Σ2Σ1R+2.（一）然而，请注意，上述定义不能直接应用于六边形网格，因为它可能定义了一组与圆的直观概念相距甚远的六角，实际上，可能是一组不连通的六角(see图7a）。因此，需要一个新的定义。为此，我们首先观察到六边形坐标系中的点（a，b）具有坐标里姆科夫和巴尔涅瓦32922√√B2OB1(a)（b）第（1）款见图7。a）满足条件（1）且r= 3的六角元素的集合。b）由公式（2）定义的同心离散圆，其中r= 1， 2， 3， 4， 5。（a+b，n =3b）关于具有相同单位的平方坐标系2 2那么六角系统中的欧几里得圆的方程变为.2002年X++.Σ23y=r2，2 2也就是说，x2+ xy +y2=r2.因此，我们得到以下关于圆心为O（0，0）、半径为r的离散圆的解析定义。CD（r）=.（x，y）∈L：.Σ21r−2≤x+xy+y<.Σ2Σ1R+2.（二）参见图7b。不难认识到，如此定义的离散圆总是连通的和无隧道的。此外，半径r = 1，2，3，. 填满整个飞机。3.4蜂巢模型为了在正方形或六边形网格上建立模型进行比较，我们假设正方形和六边形瓦片具有相同的面积1。我们将把这样的瓷砖称为单位正方形和单位2-hexel，re-hexel。可以计算出单位2-hexel的边长为：等于2a=0.3 ×0.4×0.3=0。6 2 0 4 0 .3.4.1近似的质量接下来我们将证明，在某种意义上，六边形网格比正方形网格和砖砌网里姆科夫和巴尔涅瓦330格更好地逼近连续线段。为此，我们首先回顾一下Hausdor距离的定义。让里姆科夫和巴尔涅瓦331XX1Xv3/4x(a)（b）第（1）款（c）第（1）款（d）其他事项图8.第八条。离散线的2-hexel与连续线有最大偏差的极端情况a）在正方形网格中。b）在规则的六边形网格中。c）在规则的砖砌网格中。d）在最佳砖砌网格中。E是具有度量d的度量空间，E是E的闭非空子集族。对任意x∈E和任意A∈E，设d（x，A）=inf{d（x，y）：y∈A}。设两个集合A，B∈ E，Hd（A，B）= max{ sup{d（a，B）：a∈A}，sup{d（A，b）：b∈B}}称为A和B之间的Hausdor距离我们假设d是欧几里德度量。我们将通过它们之间的Hausdor距离Hd（gD，g）来测量直线离散化gD与相应的连续线g的偏差我们首先比较六边形和正方形网格。 如图8a所示，无隧道扩散线可能包含其最远点距离为2 = 1。41421... 从线上。现在考虑六边形网格对于它，在图8b所示的极端情况下达到最大可能偏差。它等于√13u= a=2√132√21427=1。11844号 、这比方形栅格的情况小得多。现在考虑砖砌网格，其瓷砖是单位正方形。对于它，在图8c所示的情况下达到最大可能偏差，并且等于v = 1。25.该值小于正方形网格的相应值，但大于六边形网格的相应值请注意，在砖砌网格框架中，单位正方形瓦片不能提供最佳近似。为了确定最佳矩形的尺寸，参考图8d，让我们用x表示其水平边的长度。则另一边的长度为1。现在我们必须求出最小化函数的x1f（x）=x2+ 3x2。4使用简单的微积分，我们发现上述优化的解决方案uv3/4里姆科夫和巴尔涅瓦332X问题是2x= 103 = 1。15470……则另一边的长度为1=0。八六六○二... 具有这种瓦片的网格将被称为最优砖砌网格。对于它，最大偏差等于vJ=. .Σ2 1X.2019-01- 223+x4= 1。22474...很容易证明，正六边形网格中离散线的最大偏差在所有准正六边形网格上都是最小的类似地，最佳砖砌网格中的离散线的最大偏差在所有可能的砖砌网格上都是最小的。因此，我们得到正六边形网格为构造连续线性物体的无隧道近似提供了最佳基础。类似的结果和结论也适用于离散圆与相应欧氏圆的最大可能偏差。3.4.2电网成本我们用另一个观察来结束这一节，即六边形网格在某种意义上比正方形对于给定的网格H，其所有边的总长度将被称为H的成本，并表示为c（H）。我们可以计算出一个单位2-hexel的周长为6 a = 3。72241.. . ，它小于单位正方形的周长，即4。 这一事实可能对相应网格的成本产生有利影响，如通过以下示例所示。例3.1考虑一个正方形屏幕的网格，由n行组成，每行包含n个单位块。我们考虑正方形网格H1（图9a）和六边形网格H2（图9b）的情况。两个网格都覆盖了相同的区域n2.人们可以很容易地发现，在前一种情况下，电网成本是c（H1）=2n2+2n，而在后一种情况下，c（H2）=（3 n2+ 4 n − 1）a =（3 a）n2+ 4 an − a.由于n2在c（H2）中的系数为3a = 1. 86120... 2<，我们得到，c（H2）渐近小于c（H1）。很容易证明，一个单位2-hexel有一个最小的周长，所有面积为1的准正六边形。我们还可以证明，在所有可能的面积为1的准正六边形的镶嵌中，单位2-hexels的镶嵌具有最小的成本。同样，单位正方形的最小周长为里姆科夫和巴尔涅瓦333PP(a)（b）第（1）款图9.第九条。示例3.1的说明所有平行四边形的面积为1，单位正方形的平铺比所有可能的面积为1的正方形的平铺因此，可以得出结论，具有正六边形的平铺在所有可能的均匀平铺中具有最小的成本上述观察可能是关于可能的线栅制造的兴趣，用于新颖的计算机屏幕设计的目的，基于，例如，液晶、等离子面板或电致发光技术。43D蜂窝几何形状在本节中，我们将介绍两个3D蜂窝模型和相关的离散解析几何。在这两种情况下，3D空间都是由一个称为3-hexel的正六边形棱柱平铺的（见图11 b）。棱镜的底部是一个单位2-hexel，其高度为长度1。因此，3-hexel体积等于1。我们的目标是创建一个隧道的表面和线，特别是平面和直线的自由离散化的基础。为此，我们考虑了R3的两种特殊的3-hexels平铺，并在其中定义了相应的坐标系。4.1模型I设h0是R3中的一个3-hexel。其中心O被分配坐标（0，0），并将被视为坐标系的原点考虑图10a，b所示的R3的平铺该图显示了一组3-hexels在平面上的中心的正交投影 ，通过原点O，与六角星的高度正交。我们选择其中一个坐标轴作为通过O并正交于的直线e3。对在每个六边形投影中标记相应3-hexel中心的第三坐标hexel的中心相对于e3轴的坐标这些中心属于被选择为离散坐标平面之一的平面在其中，我们固定另外两个坐标轴e1和e2。原点O和轴e1、e2和e3确定坐标系Oe1e2e3（图10 b）。现在，对于来自离散坐标平面Oe1e2的每个3-hexelh，我们平铺里姆科夫和巴尔涅瓦334项目e2−2-5/3-4/3 −1−2/3 −1/301/32/31-5/3 -4/3−1−2/3 −1/301/32/314/3-4/3 −1−2/3 −1/301/32/314/3五分之三−1-2/3−1/301/32/314/35/3 2-2/3 −1/301/32/314/35/3 27/3项目1−1/301/32/314/35/3 27/3八分之三(a)（b）第（1）款见图10。图为模型I。a）3-hexel的中心在平面P上的正交投影。b）坐标系Oe1e2e3的轴。 光线e1和−e2成120度角。空间向上和向下的相邻副本的h。因此，我们得到R3的平铺。在离散坐标平面Oe1e2中，可以考虑四个象限QuadI、QuadII、QuadIII和QuadIV，由坐标轴确定通过构造，3-hexel的中心在R3中形成晶格H。注意，每两个相邻的3-hexel是2-相邻的。在3-hexels的连接集合中，没有0-或1-隧道是可能的。4.1.1解析离散平面考虑一个欧几里得平面P，a1x1+a2x2+a3x3=b，a1，a2，a3，b∈Z，在定义的坐标系中。如前所述，假设gcd（a1，a2，a3）整除b，即，P包含一个2维格L，L是H的一个子格.我们现在定义一个对应于P的通用离散平面，作为集合P D（a1，a2，a3，b）={x∈H：0≤a1x1+a2x2+a3x3+b+[t/2<$t}，（3）哪里|的1|+的|一个2|+的|一个3|，若n=（a1，a2）∈C1，最大值（|的1|、|一个2|、|一个3|），如果n=（a1，a2）∈C2.C1和C2是坐标平面Oe1e2中的圆锥，定义与前面类似。参数t称为平面的普适宽度PD。通过离散空间的构造，如此定义的离散平面总是无隧道的，并且似乎是最薄的可能无隧道离散平面。这是一个平面。 与2D情况类似，厚度t=|的1|+的|+的|一个3|2019 - 05 - 22 00：00：00 00：00|的1|、|一个2|、|一个3|），一般来说，不要。|),ingeneral,don’t.e3−e2e1Ot=里姆科夫和巴尔涅瓦335一项目e2-5/3-5/3-4/3−1-2/3−1/301/32/31-5/3-4/3−1-2/3−1/301/32/31四分之三-4/3−1-2/3−1/301/32/314/3 五分之三−1-2/3−1/301/32/314/35/32-2/3−1/301/32/314/35/327/3项目1−1/301/32/314/35/327/3 八分之三e3e1−e2OQB（一）P(b)见图11。a）点B与通过点A并与直线AB正交的欧几里德平面的距离为λ 3。b）对角线PQ一个3-hexel的长度比单位立方体的长度短，也就是3。(a)（b）第（1）款图12个。模型I的砖砌版本的插图4.1.2最优性问题首先，我们注意到一个3-hexel的surfels（面）的总面积等于6 ×a +2 × 1 = 3。七二四一... +2 = 5。72241...它小于单位立方体的一个，即6。这导致了与2D情况下类似的关于网格成本的结论，其可以定义为 所涉及的瓷砖表面的总面积最重要的是，模型I中离散平面的定义确保了与经典三次模型相比更好地逼近连续平面模型 在三维CT中，无隧道标准平面可以包含在三维CT中的体素。距离连续平面3（见图11 a），而在模型这个距离显然更小。这可以立即从3-hexel的最长对角线等于f=（1+（2 a）2）1/2= 1。59361...它小于1 = 1。七三二零五... （见图11b）。不难看出，具有正六边形基底的正棱柱比倾斜棱柱和/或具有准正六边形基底的正棱柱提供更好的近似。里姆科夫和巴尔涅瓦336e2项目e1O(a)（b）第（1）款图13岁图为模型II。a）坐标平面Oe1e2上3-hexel的两个连续切片的投影。b）坐标系Oe1e2e3的轴。类似的考虑和结论适用于砖砌模型的情况可以看出，就与连续平面的最大可能偏差值而言，蜂窝模型优于砖砌模型，而砖砌模型优于立方模型。4.2模型II考虑平面的正六边形平铺。在每一个瓷砖上，我们建立相应的3-hexel。这样我们就得到了一个离散平面P0.我们固定一个六角元素，并选择其中心O（0， 0）作为坐标系的原点。然后我们选择轴e1和e2，就像在2D情况下一样。 这样我们就得到了一个离散的坐标平面，即Oe1e2. 我们现在在离散平面P0的顶部构建下一个P0，并如图13a所示移位。类似地向上和向下进行，我们得到R3的平铺。我们注意到瓦片我们现在确定第三轴e3，如图13 b所示。类似在模型I中，一组3-hexels的连通集总是2-连通的，并且不包含任何0-和1-隧道。在所得到的离散空间中，我们可以用与模型I框架中相同的方法，相对于坐标系Oe1e2e3人们可以看到，它始终是无隧道的并且是这种类型的可能的最薄的无隧道离散平面。我们还可以证明，由（3）定义的离散平面比立方模型中的相应标准平面提供了对相应连续平面的更好近似（就与连续平面的最大偏差而言）。与砖砌模型（图14）的比较得出了与模型I类似的结论。离散球体可以定义为e3e2e13里姆科夫和巴尔涅瓦337O(a)（b）第（1）款图十四岁图为模型II的砖砌版本研究类似于离散的圆。我们用一个注释来结束关于3D蜂窝模型的讨论。在模型I中，3D离散空间的每个3-hexelh都有14个2-邻居：一个用于上六边形面，一个用于下六边形面，两个用于六个侧矩形面中的每一个。 在模型II中，3-hexel邻域是完全不同的：两个六边形面中的每一个都有四个邻域，六个矩形面中的每一个都有一个邻域。然而，相邻3-hexel的总数与模型I中相同，即，十四不难看出，在平铺是均匀的并且任何两个相邻的瓦片是2-相邻的条件下，分别相对于模型I和模型II的两个邻域结构是唯一可能的。5系统和复杂性问题所考虑的分析离散基元（离散直线和线段，离散圆和平面）承认一个高效的算法生成。它们可以在时间上获得，该时间在所生成的六角元素的数量上是线性的。这可以通过几种不同的方式来完成。我们将表明，众所周知的线性时间算法，在平方/立方模型的框架中工作，可以直接转移到所考虑的蜂窝模型的情况下。对于离散的直线和线段，这可以更容易地说明。设二维离散六角空间中的一条二维离散直线gD是给定的每个2-hexel对应一个菱形，该菱形具有相同的中心和由空间Ob1b2的基向量确定的边（见图15）。这种对应关系定义了一个（假想的）菱形离散空间Ob1b2具有相同的中心和基向量，如图15所示。其中，菱形的中心对应于给定的六边形，离散线gD构成离散线g'. 如果法向量n到连续线gb延伸到圆锥C1，则g′是标准离散线e2项目3e1e3e2e1里姆科夫和巴尔涅瓦338B2B1图十五岁其中有两条离散线段的半球面离散空间，以及相应的菱形离散空间。在Ob1b2. 否则，若n∈C2，则g<$是Ob1b2中的纯直线. 这类可以通过众所周知的高效线性算法生成线，分别产生标准和幼稚系（参见[6]）。由于上述的2-hexel和菱形之间的一一对应因此蜂窝离散线生成的时间复杂度与标准或朴素线生成的算法的时间复杂度相匹配，在法向量n所属的圆锥上。注意，如果n∈C2，我们需要在菱形模型中构造一条朴素的离散线因此在在这种情况下，算法效率将优于生成的算法效率0-无隧道（标准）线的经典平方模型。上述考虑很容易扩展到4.1节和4.2节的两个3D蜂窝模型。由于在这两种模型中，六角元素的这样我们就得到了一个具有相同中心的离散三维空间Oe1e2e3基为Oe1e2e3，晶胞为平行六面体。相对于该新的（虚的）空间，人们可以搜索一个平面离散化应用用于生成标准或朴素平面的公知算法，这取决于平面的法向量的投影所属的圆锥。6总结发言我们已经提出了蜂窝模型光栅图形的基础上，一个六边形的网格（分别。六棱柱镶嵌）。我们已经展示了如何在这些模型中开发解析离散几何。特别地，我们定义了线（在2D空间中）和平面（在3D空间中）。我们已经观察到，蜂窝模型确保离散化，这是优于经典的。人们可以开发离散化更复杂的对象的方法（特别是在R3中），如3D线段，多边形和多边形网格。为此，可以适当地修改某些离散化方案和算法。里姆科夫和巴尔涅瓦339已经为经典的正方形/立方形模型开发的RITHM（参见，例如，[9、2、3、4]）。请注意，在经典模型中需要长时间和复杂解决方案的一些问题（参见，例如，[2，3]），在新的模式可以更容易地处理。原因在于，在蜂窝环境中，由于蜂窝网格的性质，获得无隧道的对象更容易。在我们看来，蜂窝模型可以作为一个有用的替代经典的正方形和立方模型的广泛的一类问题。引用[1] Andres，E.，[2] Barneva，R.P.，V.E. Brimkov和Ph. Nehlig，[3] Brimkov，V.E.，R.P. Barneva和Ph. Nehlig，Chen，中国山核桃A.考夫曼河，巴西-地Yagel（Eds.），Springer Verlag（2000）Chapter 3，51[4] Brimkov，V.E.，和RP。Barneva，[5] 科恩，D.，和A. Kaufman，&“ 3D 线 体 素 化 和 连 接 控 制 ” ， 在 ： Pr o c .CG A （ 19 9 7 ） 1- 2 4 中 。[6] J. -Reveill`es，J.- P.，[7] Saha，P.，和A. Rosenfeld，[8] Sonka，M.，诉Hlavac和R.Boyle，“图像处理，分析和机器视觉”（第2版），ITPu。有限公司、1998年[9] 斯托伊梅诺维奇岛，和R.托西奇，“数字化方案和数字直线的识别”，超平面和单位在任意尺寸。 数字几何当代数学系列，Amer.数学Soc. Providence，RI119（1991）197