用于索引视域的凸多边形树

智能手机等设备在拍摄照片和录制视频时会将拍摄位置和光学参数记录到影像文件中,可以提取并利用这些信息,在二维平面空间中还原出图片所对应的扇形视域(field-of-view,FOV).将影像文件及其对应的FOV存储在计算机中,用来支持用户对影像文件的空间查询.一种典型的空间查询是用户在地图上指定查询区域,计算机找出拍摄到...     

圆弧和直线段组成的封闭曲线凸凹性快速判定

首先通过构造一中介凸多边形求出封闭曲线的方向，然后根据封闭曲线方向确定顶点及圆弧的凸凹性，进而确定封闭曲线的凸凹性．文中算法快速稳定，其时间复杂度为O(n)，计算量最多为15n 33k 25次判断、12n-6k 14次乘除法、10n 16k 21次加减法、2次求正余弦和k次开方运算，其中n为封闭曲线顶点和圆弧圆心的个数、k为圆弧个数．     

Optimal BSR Solutions to Several Convex Polygon Problems

This paper focuses on BSR (Broadcasting with Selective Reduction) implementation of algorithms solving basic convex polygon problems. More precisely, constant time solutions on a linear number, max(N, M) (where N and M are the number of edges of the two considered polygons), of processors for computing the maximum distance between two convex polygons, finding critical support lines of two convex polygons, computing the diameter, the width of a convex polygon and the vector sum of two convex polygons are described. These solutions are based on the merging slopes technique using one criterion BSR operations.     

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

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

简单多边形分解成凸多边形差组合的算法

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边，其内部在边的同一侧。本文依据凸多边形的这一特性，提出求解简单多边形凸包的新算法，进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点，得到极值点间的候选点子集，再求得相邻极值点间的有序凸包点列，最后顺序连接极值点间的有序凸包点列，得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h），其中，n为平面点集的点数，h为平面点集凸包的顶点数。相比相同复杂度的凸包算法，新算法简单、易于实现。又由于是顺序求得凸包上的点，新算法还具有更易于实现基于其上的有效空间算法的优点。     

对体可视化Marching Cube算法的改进

提出一个由三维数据计算等值面中点的算法,它在两方面对标准Ｍａｒｃｈｉｎｇ Ｃｕｂｅ算法进行了改进。第一个改进是：在等值面上样本点的状态依赖于它所连接的边同等值面相交的数目;第二个改进是：两相邻样本点中等值面多边形顶点被定位于中点,使得共面三角片合并为一个多边莆,减少了生成多边形的数量,提高了算法效率。     

An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon

The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log² n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log² n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure.     

确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

Parallel algorithms for separation of two sets of points and recognition of digital convex polygons

Given two finite sets of points in a plane, the polygon separation problem is to construct a separating convexk-gon with smallestk. In this paper, we present a parallel algorithm for the polygon separation problem. The algorithm runs inO(logn) time on a CREW PRAM withn processors, wheren is the number of points in the two given sets. The algorithm is cost-optimal, since (n logn) is a lower-bound for the time needed by any sequential algorithm. We apply this algorithm to the problem of finding a convex polygon, with the minimal number of edges, for which a given convex region is its digital image. The algorithm in this paper constructs one such polygon with possibly two more edges than the minimal one.The research is sponsored by NSERC Operating Grant OGPIN 007.     

Decomposition of Catalan numbers and convex polygon triangulations

In this paper we present a method for Catalan number decomposition in the expressions of the form (2+i). This method gives convex polygon triangulations in Hurtado–Noy ordering. Therefore, we made a relationship between the expressions and the ordering mentioned above. The corresponding algorithm for Catalan number decomposition is developed and implemented in Java, as well as the algorithm which generates convex polygon triangulations. At the end, we have provided the comparison of Hurtado's algorithm and our algorithm based on the decomposition method.     

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

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

中轴求凸多边形直径算法

在研究中轴性质的基础上,给出了一种全新的求解凸多边形直径算法。该算法首先求出凸多边形的中轴,再根据中轴的两个端点确定直径。算法简单,并在无预处理的情况下达到了O（n）。     

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

一种基于几何关系编码的高效凸多边形线裁剪算法

提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪.实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右.如果m的数值也较大时,该算法的速度还将大大提高.所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性.     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

Fast, Exact, Linear Booleans

We present a new system for robustly performing Boolean operations on linear, 3D polyhedra. Our system is exact, meaning that all internal numeric predicates are exactly decided in the sense of exact geometric computation. Our BSP-tree based system is 16-28× faster at performing iterative computations than CGAL's Nef Polyhedra based system, the current best practice in robust Boolean operations, while being only twice as slow as the non-robust modeler Maya. Meanwhile, we achieve a much smaller substrate of geometric subroutines than previous work, comprised of only 4 predicates, a convex polygon constructor, and a convex polygon splitting routine. The use of a BSP-tree based Boolean algorithm atop this substrate allows us to explicitly handle all geometric degeneracies without treating a large number of cases.     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段．在裁剪计算时，先根据二叉树快速地找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度，使其在O（logN）～O（N）之间自适应地变化，且大部分情况下时间复杂度小于O（N）．