Recognizing polygons,or how to spy

A new class of so-called pseudo-starshaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well-known classes of convex, monotone and pseudostar-sphaped polygons. We give algorithms for testing whether a polygon is pseudostar-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-starshaped polygons.A preliminary version of this paper has been presented at the 24 th Allerton Conference on Communication, Control and Computing, Monticello, Ill, October 1986Research for this paper was done while the author was at Carleton UniversityResearch for this paper was done in part while the author was visiting Carleton UniversityThis research was supported in part by NSERC and by Carleton University     

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

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

Clamping a polygon

Aclamping hand has two opposing parallel edges; the distance between them can vary. We define what it means for the edges of a clamping hand and some edges of a polygon to form aclamp on the polygon. We conjecture that any polygon can be clamped by a hand if its edges are of positive length, but only provide proofs that clamps must exist for convex polygons and for certain polygons composed of two convex chains. The proofs involve extensive case analyses, and it is not obvious how to generalize them.     

Finding the convex hull of a simple polygon

We describe a new algorithm for finding the convex hull of any simple polygon specified by a sequence of m vertices.An earlier convex hull finder of ours is limited to polygons which remain simple (i.e., nonselfintersecting) when locally non-convex vertices are removed. In this paper we amend our earlier algorithm so that it finds with complexity O(m) the convex hull of any simple polygon, while retaining much of the simplicity of the earlier algorithm.     

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.     

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

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

Decomposition and intersection of simple splinegons

A splinegon is a polygon whose edges have been replaced by “well-behaved” curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.     

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

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

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

二维图形最狭长包络矩形的求解原理及方法

最狭长包络矩形是二维图形的一个潜在几何属性,可作为平面外形智能设 计、板料优化排样及图像自动识别的重要依据。目前国内外尚无此课题的专门深入研究。提 出了最狭长包络矩形的概念,将任意二维图形的最狭长包络矩形的求解转化为对其凸包的最 狭长包络矩形的求解。明确给出了过凸包上给定4 个顶点的包络矩形的包络角及长宽比求解 公式,并通过分析包络角及长宽比求解公式之间的关系,证明了凸多边形至少存在一条边与 其最狭长包络矩形的一条边共线。基于该定理,求解并比较与二维图形的凸包的n 条边分别 共线的n 个包络矩形的长宽比,得到了二维图形的最狭长包络矩形。最后用实例验证了定理 和求解方法的正确性和应用效率。     

基于夹边边对的凸多边形间快速相交检测算法

本文在对现有的相交检测算法进行研究的基础上,提出了基于夹边边对的空间平面凸多边形快速相交检测算法,为平面凸多边形间判交问题提供了一致的计算方法,并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步：第一步,确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对,如果至少一个凸多多边形中不存在相对于另一凸多边形所在平面的夹边边对,那么立即返回两个多边形不相交;第二步,根据前面计算得到的两个凸多边形中的夹边边对,计算两组边对间对应夹边的符号距离判断两个多边形是否相交     

图形裁剪算法研究

本文介绍和研究直线、曲线和多边形的最新裁剪算法,包括作者近期的研究成果。首先对于矩形窗口,介绍了直线裁剪算法,圆和椭圆裁剪算法以及参数曲线的裁剪算法。然后,介绍了多边形窗口的直线裁剪算法和多边形窗口的多边形裁剪算法以及区域间的“交”、“差”和“并”操作。最后,介绍了圆形和椭圆形窗口的直线裁剪算法。     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

一种新的凸多边形不干涉算法

求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O（n+m）。     

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.     

Approximate Guarding of Monotone and Rectilinear Polygons

We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT ²).     

一种全局优化的多边形变形方法及应用

通过对多边形的凸部分,并建立２种不同多边形的凸子集映射,提出了一种全新的基于凸多边形的全局优化方法,解决了任意非同拓扑结构（包括有孔及凸边形）的变形问题。理论上证明了此方法的正确性,讨论了不同凸剖分对变形的影响。实验证明此方法变形效果自然、质量好、速度快、自动化程度高,并可用于汉字的合成与二维动画关键帧的内插。     

A counterexample to a diameter algorithm for convex polygons

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in O(n) time.     

Optimality and competitiveness of exploring polygons by mobile robots

A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics.We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.     

Waste minimization in irregular stock cutting

This paper addresses a category of two dimensional NP-hard knapsack problem in which a given convex/non-convex planner items (polygons) have to be cut out of a single convex/non-convex master surface (stock). This cutting process is found in many industrial applications such as sheet metal processes, home-textile, garment, wood, leather and paper industries. An approach is proposed to solve this problem, which depends on the concept of the difference between the area of a collection of polygons and the area of their convex hull. The polygon assignment inside the stock is subjected to feasibility tests to avoid overlapping, namely, angle test, bound test, point inclusion and polygon intersection test. An iterative scheme is used to generate different polygon placements while optimizing the objective function. Computer software is developed to solve and optimize the problem under consideration. Few examples are conducted for different combinations of convex, non-convex items and stocks. Well-known benchmark problems from the literature are tested and compared with our approach. The results of our algorithm have an interesting computational time and can compete with the results of previous work in some particular problems. The computational performance of the developed software indicates the efficiency of the algorithm for solving 2-D irregular cutting of non-convex polygons out of non-convex stock.