一种快速相容三角剖分算法

提出了一种基于凹多边形凸分解的相容三角剖分方法。先将凹边形分解成凸多边形,再对子多边形进行三角剖分,即可实现相容三角剖分。在最坏的情况下添加O（jk)个辅助点,时间复杂度为O(jn+n log n+jk log n)     

基于局部单射的平面形状插值形变

在只给出用简单多边形表示的两输入形状的情况下,实现一种简单易用、自然高效的形状插值方法.首先利用基于形状感知的特征匹配算法生成源形状和目标形状之间的匹配;之后在源形状上构造三角剖分,并通过求解映射到目标形状上的尽量刚体的局部单射得到同构三角剖分;最后利用扭曲有界的插值方法得到中间序列.实验结果表明,该方法构造的形变结果能较好地体现源形状和目标形状的特征对应信息,形变过程自然,扭曲较小.     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

四次带参Bezier曲线的形状分析

为了明确形状参数对四次带参Bezier曲线形状的影响,利用基于包络理论与拓扑映射的方法对其进行了形状分析,得出了曲线上含有奇点、拐点和曲线为局部凸或全局凸的充分必要条件,这些条件完全由控制多边形边向量的相对位置所表示;并进一步讨论了形状参数对形状分布图的影响及其对曲线形状的调节能力．     

四次带参Bzier曲线的形状分析

为了明确形状参数对四次带参Bzier曲线形状的影响,利用基于包络理论与拓扑映射的方法对其进行了形状分析,得出了曲线上含有奇点、拐点和曲线为局部凸或全局凸的充分必要条件,这些条件完全由控制多边形边向量的相对位置所表示;并进一步讨论了形状参数对形状分布图的影响及其对曲线形状的调节能力.     

保内部相似性的平面形状混合算法

为了在计算机动画中可以得到较好的图形过渡效果,提出了一保持平面多边形内部相似性的形状混合算法,从而有效地避免了中间多边形发生局部萎缩或者膨胀的现象.此方法从源和目标多边形的同构三角剖分出发,对同构三角网格每一个夹角处表示边角关系的几何量线性插值得到相对应的中间几何量,通过这些中间几何量以及它们与顶点坐标之间的关系来建立线性方程组,给定初始条件后用现成的程序库快速求解来得到中间三角网格(其边界即为中间多边形).还通过引入特征多边形来保持混合多边形的全局视觉特征.该算法计算量小、运行效率高,对形状复杂的多边形仍然可以得到满意的结果,适合于实际应用中实时的要求.     

四次带参Bézier曲线的形状分析

为了明确形状参数对四次带参Bézier曲线形状的影响,利用基于包络理论与拓扑映射的方法对其进行了形状分析,得出了曲线上含有奇点、拐点和曲线为局部凸或全局凸的充分必要条件,这些条件完全由控制多边形边向量的相对位置所表示;并进一步讨论了形状参数对形状分布图的影响及其对曲线形状的调节能力.     

基于矢量游走的任意非自交图形合并算法

图形处理软件中,常常需要将许多非自交图形合并成一个图形,提出一种基于矢量游走的任意非自交多边形合并算法,提出了适合于多边形合并运算的改进矢量游走规则及交点转移条件.通过将交点和两相交矢量边联合处理,对交点分类,有效地去除了“伪交点”,进而简化了重合交点处理.提出用带凸度线段的方式来表示圆和舍圆弧边的多边形,成功地将矢量游走规则运用到这些复杂多边形的快速合并当中.     

多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.     

优化变形能的平面多边形同构剖分

平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.     

Voronoi diagrams of polygons: A framework for shape representation

This paper describes an efficient shape representation framework for planar shapes using Voronoi skeletons.This paper makes the following significant contributions. First a new algorithm for the construction of the Voronoi diagram of a polygon with holes is described. The main features of this algorithm are its robustness in handling the standard degenerate cases (colinearity of more than two points; co-circularity of more than three points), and its ease of implementation. It also features a robust numerical scheme to compute non-linear parabolic edges that avoids having to solve equations of degree greater than two. The algorithm has been fully implemented and tested in a variety of test inputs.Second, the Voronoi diagram of a polygon is used to derive accurate and robust skeletons for planar shapes. The shape representation scheme using Voronoi skeletons possesses the important properties of connectivity as well as Euclidean metrics. Redundant skeletal edges are deleted in a pruning step which guarantees that connectivity of the skeleton will be preserved. The resultant representation is stable with respect to being invariant to perturbations along the boundary of the shape. A number of examples of shapes with and without holes are presented to demonstrate the features of this approach.     

Probing a scene of nonconvex polyhedra

We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that \(\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k\) probes are sufficient to compute the exact shapes of the polyhedra.     

Reconstructing domain boundaries within a given set of points,using Delaunay triangulation

Given an input set of planar points, which occupy a non-convex polygon area, possibly with holes, we reconstruct the shape of its boundary domain, without previous knowledge of which points or edges belong to the boundary. Our approach is based on different qualities of the Delaunay triangles inside and outside the domain. This method is heuristic and does not ensure success in all cases but it is very simple and there is no other method for this problem known to us. The method was derived on real GIS data but experiments show that it could also be used for mechanical engineering data, with positive results.     

Haptic perception of shape and hollowness of deformable objects using the anthrobot‐III robot hand

This article presents a methodology for the haptic perception of contour shapes of almost planar objects grasped by a five‐fingered robot hand as well as the detection of any object cavity. The originality of our approach resides in (1) finding the reaction force patterns at the fingertips of a five‐fingered robot hand that grasps different deformable objects (forward problem) and (2) using these contact force patterns to find the shapes of grasped objects (inverse problem) and (3) to determine material defects such as holes in an object with identified shape. Contact force patterns are generated in the forward problem by the finite element method (FEM) and the shape identification in the inverse problem is realized by a supervised neural network architecture using the backpropagation algorithm. Following shape identification, detection of holes is performed by clustering actual and prototypical contact force patterns using the self‐organizing feature maps of neural gas networks as an unsupervised hole‐screening method. ©1999 John Wiley & Sons, Inc.     

Probing a scene of nonconvex polyhedra

We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that probes are sufficient to compute the exact shapes of the polyhedra.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

多连通多边形的内部Voronoi图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.     

On Shape of Plane Elastic Curves

We study shapes of planar arcs and closed contours modeled on elastic curves obtained by bending, stretching or compressing line segments non-uniformly along their extensions. Shapes are represented as elements of a quotient space of curves obtained by identifying those that differ by shape-preserving transformations. The elastic properties of the curves are encoded in Riemannian metrics on these spaces. Geodesics in shape spaces are used to quantify shape divergence and to develop morphing techniques. The shape spaces and metrics constructed are novel and offer an environment for the study of shape statistics. Elasticity leads to shape correspondences and deformations that are more natural and intuitive than those obtained in several existing models. Applications of shape geodesics to the definition and calculation of mean shapes and to the development of shape clustering techniques are also investigated.     

Multimorphing: A tool for shape synthesis and analysis

Morphing is a shape transformation where the shape of one object is deformed to the shape of the other object. It is used as an animation or a modeling technique. Classical morphing operates between two input objects but this concept can be extended to multiple input objects – the so called multimorphing. Shapes generated by the multimorphing form a space of shapes motivated by an affine space. Besides the analogy with an affine space we also introduce an inner product and a concept of an orthogonal projection. We also show how to explore space of shapes and how to systematically generate new shapes. The paper focuses on the boundary representation, although some ideas are more general and can be used for other representations, too.     

Analysis of planar shapes using geodesic paths on shape spaces

For analyzing shapes of planar, closed curves, we propose differential geometric representations of curves using their direction functions and curvature functions. Shapes are represented as elements of infinite-dimensional spaces and their pairwise differences are quantified using the lengths of geodesics connecting them on these spaces. We use a Fourier basis to represent tangents to the shape spaces and then use a gradient-based shooting method to solve for the tangent that connects any two shapes via a geodesic. Using the Surrey fish database, we demonstrate some applications of this approach: 1) interpolation and extrapolations of shape changes, 2) clustering of objects according to their shapes, 3) statistics on shape spaces, and 4) Bayesian extraction of shapes in low-quality images.