一种基于小波的多边形变形算法

文章提出了一种基于小波分解算法和相应的重构算法的变形方法。先用小波分解算法作用于平面多边形,得到平面多边形的轮廓和细节。然后分别对多边形的轮廓和细节进行变形,得到从初始图形变换到目标图形的中间图形的轮廓和细节。最后用重构算法重构出中间图形。该文算法可以处理任意顶点数的多边形,减少同构三角剖分的计算量,并且能够得到很好的变形结果。     

全景视频最小变形双极方形映射研究

球面全景视频映射为矩形视频后才能使用现有编码标准进行编码.针对映射过程中存在内容变形和数据冗余的问题,提出一种最小变形双极方形映射(Minimize Deformation Bipolar Square Projection,MDBSP)算法.算法分三步:将球面按纬度展开成一个等面积的、边界与纬度呈余弦关系的平面图形;用两个三角形和一个矩形组成的多边形近似该平面图形,并使变形度最小;将多边形内像素重排列成一个矩形.实验结果表明,MDBSP算法能有效解决内容变形和数据冗余的问题,压缩效率比经纬图映射提高17.48％.     

多边形三角形分解的扇形扫描算法

讨论了任意多边形区域的三角形分解问题,提出了一种扇形扫描方法。该方法沿着多边形轮廓搜索各个可行的目标三角形,逐步将多边形未分解区域缩小,最终完成三角形分解。给出了分解实例。     

一种鲁棒性的2D矢量图形水印算法

为了解决空间信息网络传输和空间信息共享的版权保护问题,提出了一种具有鲁棒性的2D矢量图形的水印算法。在GIS中,矢量图形是其最基本的表达方式,常需针对2D矢量图形的大数据集进行水印嵌入处理,本方法先将空间矢量图层按照自身所含的多边形特征进行分解;对分解后的矢量多边形进行分析,选择合适的多边形的线段,在其顶点处嵌入水印;而提取水印的过程,则是对原矢量图形和水印图形进行分析,根据嵌入水印顶点的位置或坐标值得到水印信息的序列。实验结果证明,该方法对于空间信息的常规图形操作,如矢量图层的坐标变换、平移、旋转、缩放,以及图形的剪切,点的添加删除等,均具有较强的鲁棒性。     

区域划分在自相交多边形分解算法中的应用

多边形分解在计算机图形学、CAD软件和路径规划等领域中得到广泛应用.其自相交多边形因存在交点导致后续计算和绘图操作中的错误和不准确性.自相交多边形分解算法是CAD应用中常见的难题之一,传统的自相交多边形分解算法主要基于三角剖分的方法,然而这种方法分解出的三角形数量较为庞大,增加了计算和存储的复杂度.针对自相交多边形的分解问题,提出了一种基于区域划分的分解算法.首先寻找多边形的所有交点;然后采用寻路方式遍历自相交多边形,将其划分为无重叠且无自相交的区域;最后通过判断每个区域是否属于多边形内部,并保留内部区域,舍弃外部区域,将自相交多边形分解成无重叠区域的简单多边形.在多个大型集成电路板上将文中算法和GluTess方法进行数值实验对比,实验结果表明,该算法相较于GluTess方法在时间效率上提高了约60%,同时在空间占用上也减少了约20%.     

实现逼近细分模式的统一分解架构

多边形是计算机图形学的一个普遍的建模原语,为渲染多边形而量身度制的图形硬件也已经成为现实。然而,在实现高度分片逼近光滑曲面时,使用多边形建模存在很多问题。这是因为这样的逼近往往含有数十万的多边形,使得设计者难以自由地控制形状。细分则是解决这个难题的新技术,细分曲面的生成也正被广泛地应用于计算机图形研究和几何建模应用,并将成为下一代几何建模原语。本文研究了使用具有分解因子的统一架构生成以逼近模式为例的多边形网格细分曲面建模,并且实现了基于四边形／三角形混合网格的细分。     

平面多边形的广义梯形分解算法

针对机器刺绣和平面型腔行切加工对图形分解的要求,定义了广义梯形的概念,提出了广义梯形分解平面多边形的算法.广义梯形结合了梯形的定义和单调链的思想,广义梯形分解算法以对顶点的分类为基础,借鉴文献（Lorenzetto G P,Datta A,Thomas R C.A fast trapezoidation technique for planar polygons.Computers ＆ Graphics,2002,26（2）：281～289）的快速梯形分解框架,通过扫描线方法将平面多边形分解为广义梯形.该算法能够分解内嵌多个环的复杂多边形,分析及测试表明,其时间复杂度为O（nlogn）.     

面向空间关系复合的矢量多边形图形拓扑叠置分析算法

矢量多边形图形拓扑叠置是挖掘和提取空间隐含信息的重要空间分析方法,现有方法主要针对简单要素模型,未考虑图形要素间空间关系的复合运算.为使矢量多边形图形空间叠置能在有利于空间关系复合的操作模式下进行,提出一种基于线-面运算的矢量多边形拓扑叠置分析算法.对参与叠置的2幅矢量多边形图形,分别将其中一幅图形的矢量链段与另一幅图形的面域图进行线-面叠置运算和空间关系复合处理,检测出矢量图形中跨越面域图多边形的链段并进行分解;通过面向叠置模式的链段筛选和结点匹配、空间关系构建等,最终生成含空间拓扑关系的结果多边形图形.实验结果表明,该算法具有较高的鲁棒性和效率,非常适用于面向空间关系复合的复杂矢量多边形图形空间拓扑叠置分析.     

复杂边界几何体的结构网格生成方法

高质量的结构网格能够有效地提高有限元分析的精度.针对受限于结构网格节点分布的特殊要求,使当前的结构网格生成方法无法直接应用于边界复杂的几何体这一问题,提出结构网格生成方法.对于边界复杂的多边形区域,依据边界顶点分类,在计算空间内将边界简化为规则形状,在简化的多边形区域内进行分割并填充结构网格,再将其映射回原区域;对于边界特殊的三角形、圆形区域,依据边界节点分布计算分割线,将原区域分割为简单的四边形区域组合,再对各四边形区域分别进行结构网格填充;对于不同区域网格的连接,将区域边界相连并设置棱边方向,通过转化相应的棱边方向矩阵得出棱边方向闭合的多边形边界,在多边形边界内填充结构网格形成不同区域网格间的有效过渡.实例验证结果表明,该方法稳定、高效,能够解决复杂边界几何体的结构网格划分问题.     

基于基元表示的多边形检测方法

特征检测是图像处理的经典问题,但多边形检测一直研究较少,针对这一现况,提出了一种简单有效的多边形检测方法——基于基元表示的多边形检测方法. 该方法的主要思想是:首先,检测图像关键点并计算关键点附近的边缘方向,利用关键点位置与边缘方向信息定义点基元(一维基元);其次,将满足组合条件的点基元进行组合, 获得线基元(二维基元);然后,将满足组合条件的线基元与点基元进行组合,获得三维基元或者三角形,实现三角形检测;同样,可将满足组合条件的n(n≥2)维基元与点基元进行组合,获得n+1维基元或者n+1边形,实现多边形检测. 实验结果表明,本文提出的基于基元表示的多边形检测方法可准确有效地检测出图像中包含的各种多边形. 此外,本文提出的基元表示方法也为其他由线条组成的复杂图形的检测提供了一种新的思路.     

一种加权剖分简单多边形为三角形和凸四边形子域的算法

针对计算几何与有限元网格自动剖分中多边形子域剖分问题，给出了一种适用于有限元网格子域单元（即大单元）剖分的标准，并提出了一种通过在可视点对之间引进适当的多边形剖分和根据子域单元的形状质量判定因子来引导剖分的算法。由于建立的权函数和凹角（凸角）本身有关，因此对同属于凹角（凸角）的权函数也可以加以权值上的区分。该算法通过分步进行剖分，即先将简单多边形剖分为凸多边形，然后再将凸多边形剖分为凸六边形和凸五边形，最后将凸六边形和凸五边形剖分为三角形和凸四边形，以得到满足要求的剖分结果。在以上的每个剖分过程中，都引进了权重来引导剖分，使得剖分结果更加优化、合理。     

An algorithm for triangulating multiple 3D polygons

We present an algorithm for obtaining a triangulation of multiple, non‐planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non‐manifold outputs for two and more input polygons without compromising optimality. For better performance on real‐world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.     

Localizing overlapping parts by searching the interpretation tree

This paper discusses how local measurements of positions and surface normals may be used to identify and locate overlapping objects. The objects are modeled as polyhedra (or polygons) having up to six degrees of positional freedom relative to the sensors. The approach operates by examining all hypotheses about pairings between sensed data and object surfaces and efficiently discarding inconsistent ones by using local constraints on: distances between faces, angles between face normals, and angles (relative to the surface normals) of vectors between sensed points. The method described here is an extension of a method for recognition and localization of nonoverlapping parts previously described in [18] and [15].     

Solving camera parameters from the perspective projection of a parameterized curve

Given the two-dimensional perspective projection of a known conic or polygon of unknown size and position in three-dimensional space, we show how to determine the camera look angles relative to the plane where the curve lies. Separate cases are discussed for conic and polygons. We then show that this technique can be used to solve for any planar or nonplanar curves, as long as they can be represented in parametric forms.     

Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals

We investigate the following mesh refinement problem: Given a mesh of polygons in three-dimensional space, find a decomposition into strictly convex quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints. The conformal mesh refinement problem is shown to be feasible if and only if a certain system of linear equations over GF(2) has a solution. To improve mesh quality with respect to optimization criteria such as density, angles, and regularity, we introduce a reduction to a minimum cost bidirected flow problem. However, this model is only applicable if the mesh does not contain branching edges, that is, edges incident to more than two polygons. The general case with branchings, however, turns out to be strongly -hard. To enhance the mesh quality for meshes with branchings, we introduce a two-stage approach which first decomposes the whole mesh into components without branchings, and then uses minimum cost bidirected flows on the components in a second phase. Received March 10, 1997; revised August 15, 1997.     

Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we first study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. Finally we study maximal series-parallel graphs. Here we show that O(1)-sided rectilinear polygons are not possible unless we allow holes, but 6-sided polygons can be achieved with arbitrarily small holes.     

Angle counts for isothetic polygons and polyhedra

In the case of isothetic simple polyhedra there are only six different types of 3D angles. This article states and proofs a formula about counts of these angles. This complements formulas in combinatorial topology such as Euler’s polyhedron formula, or the previously known formula on angle counts for isothetic polygons. The latter formula and the shown equality for angle counts of isothetic simple polyhedra are useful formulas for analyzing isothetic boundaries in 2D digital images (e.g. classification into inner (boundary of a hole) or outer boundaries, see Voss [Discrete Images, Objects, and Functions in Zⁿ, Springer, Berlin, 1993]) and isothetic surfaces in 3D digital images (e.g. necessary condition for a complete surface scan).     

计算多边形交集、并集面积的算法

平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。     

Boolean Operations on Conic Polygons

An algorithm for Boolean operations on conic polygons is proposed.Conic polygons are polygons consisting of conic segments or bounded conics with directions.Preliminaries of Boolean operations on general polygons are presented.In our algorithm,the intersection points and the topological relationships between two conic polygons are computed.Boundaries are obtained by tracking path and selecting uncrossed boundaries following rule tables to build resulting conic polygons. We define a set of rules for the i...     

多边形的隐函数表示法

文章提出了一种方法,用一个隐函数表示一个多边形。先把被表示的多边形分解成树形结构,然后使用R函数对满足多边形边的连续函数F(x,y)=0进行交、并等布尔操作,以获得表示整个多边形的隐函数。