On a convex hull algorithm for polygons and its application to triangulation problems

A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.     

On geodesic properties of polygons relevant to linear time triangulation

Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.Research supported by Faculty of Graduate Studies and Research (McGill University) and NSERC under grant OGP0036737Research supported by FCAR grant EQ-1678 and NSERC grant A9293     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.     

Using extended feature objects for partial similarity retrieval

In this paper, we introduce the concept of extended feature objects for similarity retrieval. Conventional approaches for similarity search in databases map each object in the database to a point in some high-dimensional feature space and define similarity as some distance measure in this space. For many similarity search problems, this feature-based approach is not sufficient. When retrieving partially similar polygons, for example, the search cannot be restricted to edge sequences, since similar polygon sections may start and end anywhere on the edges of the polygons. In general, inherently continuous problems such as the partial similarity search cannot be solved by using point objects in feature space. In our solution, we therefore introduce extended feature objects consisting of an infinite set of feature points. For an efficient storage and retrieval of the extended feature objects, we determine the minimal bounding boxes of the feature objects in multidimensional space and store these boxes using a spatial access structure. In our concrete polygon problem, sets of polygon sections are mapped to 2D feature objects in high-dimensional space which are then approximated by minimal bounding boxes and stored in an R-tree. The selectivity of the index is improved by using an adaptive decomposition of very large feature objects and a dynamic joining of small feature objects. For the polygon problem, translation, rotation, and scaling invariance is achieved by using the Fourier-transformed curvature of the normalized polygon sections. In contrast to vertex-based algorithms, our algorithm guarantees that no false dismissals may occur and additionally provides fast search times for realistic database sizes. We evaluate our method using real polygon data of a supplier for the car manufacturing industry. Edited by R. Güting. Received October 7, 1996 / Accepted March 28, 1997     

一种基于单调多边形的三角剖分算法

提出了一种基于单调多边形三角化算法,被三角化的多边形可以含有任意 个内孔。先根据边界y(x)方向的局部极值顶点作水平（垂直）分割线,将多边形划分成单连 通y(x)单调多边形,然后再将各单调多边形三角化。算法考虑了各种几何奇异情况,因此比 较稳定。     

Representation and reconstruction of polygons and polyhedra using Hierarchical Extended Gaussian Images

In this paper, two new representation schemes called the Branched Gaussian Image (BGI) and the Hierarchical Extended Gaussian Image (HEGI) are proposed. They can be used for uniquely representing both concave and convex, two-dimensional figures and three-dimensional objects. The representation by the Branched Gaussian Image involves several Gaussian spheres connected by branches where the traversing directions might be different. Examples showing how the use of the BGI enables us to achieve the mapping and inverse mapping of concave polygons and polyhedra uniquely are presented. The Gaussian spheres in the BGI can be organized into a tree-like hierarchical structure known as the Hierarchical Extended Gaussian Image. A general procedure for mapping a polygon or polyhedron to its HEGI representation is described. An approach for reconstructing concave polygons from Branched Gaussian Images is presented. The reconstruction of a concave polyhedron from its Hierarchical Extended Gaussian Images by using an iterative method or a closed-form method for each convex component is also described.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take Θ(n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].     

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     

A fuzzy approach to digital image warping

Digital image warping addresses the problem of how to smoothly transform one digital image into another. The warping process has wide applications in computer animation and can be divided into two classes depending on the type of images being transformed. Gray image warping considers the transformation of one gray-scale image into another-a process also known as image metamorphosis. Binary image warping, on the other hand, addresses the transformation of binary images such as polygonal shapes. The focus in this article is on warping polygons. We can approach the warping of polygonal shapes in two steps. The first establishes a correspondence between the vertices of two given polygons. The second step interpolates the corresponding vertices to generate vertices of an intermediate polygon. This article presents new approaches to both steps. This new algorithm uses fuzzy techniques to warp polygons that have different locations, orientations, sizes and numbers of vertices. The algorithm is robust and extensible to curved shapes     

Translation separability of sets of polygons

We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons.The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.Research supported by NSERC under grant No. A9173 and A0392, respectively     

A note on the combinatorial structure of the visibility graph in simple polygons

Combinatorial structure of visibility is probably one of the most fascinating and interesting areas of engineering and computer science. The usefulness of visibility graphs in computational geometry and robotic navigation problems like motion planning, unknown-terrain learning, shortest-path planning, etc., cannot be overstressed. The visibility graph, apart from being an important data structure for storing and updating geometric information, is a valuable mathematical tool in probing and understanding the nature of shapes of polygonal and polyhedral objects. In this research we wish to initially focus our attention on a fundamental class of geometric objects. These geometric objects may be looked upon as building blocks for more complex geometric objects, and which offer an ideal balance between complexity and simplicity, namely simple polygons.

A major theme of the proposed paper is the investigation of the combinatorial structure of the visibility graph. More importantly, the goals of this paper are:

1. (i) To characterize the visibility graphs of simple polygons by obtaining necessary and sufficient conditions a graph must satisfy to qualify for the visibility graph of a simple polygon

2. (ii) To obtain hierarchical relationships between visibility graphs of simple polygons of a given number of vertices by treating them as representing simple polygons that are deformations of one another.

3. (iii) To exploit the potential of complete graphs to be natural coordinate systems for addressing the problem of reconstructing a simple polygon from visibility graph.

We intend to achieve this by defining appropriate “betweenness” relationships on points with respect to the edges of the complete graphs.     

Polygon Inflation for Animated Models: a Method for the Extrusion of Arbitrary Polygon Meshes

A method for the extrusion of arbitrary polygon meshes is introduced. This method can be applied to model a large class of complex 3-D closed surfaces. It consists of defining a (typically small) set of connected polygons in 3-D that form a skeleton of the final object, and assigning extrusion distances to all polygons. The two sides of a polygon may have different extrusion distances. An automatic extrusion algorithm constructs a closed 3-D polygon mesh around the skeleton, making use of the indicated extrusion distances. We call this process inflating the polygons of the skeleton. Unlike traditional extrusion, the method works for non-planar skeleton configurations, and it also supports branching skeleton structures (i.e. edges with more than two incident polygons). © 1997 by John Wiley & Sons, Ltd.     

An efficient algorithm for finding the CSG representation of a simple polygon

Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary.We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.The first author would like to acknowledge the support of the National Science Foundation under Grants CCR87-00917 and CCR90-02352. The fourth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the first author was visiting the DEC Systems Research Center.     

Minimum-Perimeter Intersecting Polygons

Given a set \(\mathcal{S}\) of segments in the plane, a polygon P is an intersecting polygon of \(\mathcal{S}\) if every segment in \(\mathcal{S}\) intersects the interior or the boundary of P. The problem MPIP of computing a minimum-perimeter intersecting polygon of a given set of n segments in the plane was first considered by Rappaport in 1995. This problem is not known to be polynomial, nor it is known to be NP-hard. Rappaport (Int. J. Comput. Geom. Appl. 5:243–265, 1995) gave an exponential-time exact algorithm for MPIP. Hassanzadeh and Rappaport (Proceedings of the 23rd International Workshop on Algorithms and Data Structures, LNCS, vol. 5664, pp. 363–374, 2009) gave a polynomial-time approximation algorithm with ratio \(\frac{\pi}{2} \approx 1.57\). In this paper, we present two improved approximation algorithms for MPIP: a 1.28-approximation algorithm by linear programming, and a polynomial-time approximation scheme by discretization and enumeration. Our algorithms can be generalized for computing an approximate minimum-perimeter intersecting polygon of a set of convex polygons in the plane. From the other direction, we show that computing a minimum-perimeter intersecting polygon of a set of (not necessarily convex) simple polygons is NP-hard.     

A dissimilarity function for geospatial polygons

Similarity plays an important role in many data mining tasks and information retrieval processes. Most of the supervised, semi-supervised, and unsupervised learning algorithms depend on using a dissimilarity function that measures the pair-wise similarity between the objects within the dataset. However, traditionally most of the similarity functions fail to adequately treat all the spatial attributes of the geospatial polygons due to the incomplete quantitative representation of structural and topological information contained within the polygonal datasets. In this paper, we propose a new dissimilarity function known as the polygonal dissimilarity function (PDF) that comprehensively integrates both the spatial and the non-spatial attributes of a polygon to specifically consider the density, distribution, and topological relationships that exist within the polygonal datasets. We represent a polygon as a set of intrinsic spatial attributes, extrinsic spatial attributes, and non-spatial attributes. Using this representation of the polygons, PDF is defined as a weighted function of the distance between two polygons in the different attribute spaces. In order to evaluate our dissimilarity function, we compare and contrast it with other distance functions proposed in the literature that work with both spatial and non-spatial attributes. In addition, we specifically investigate the effectiveness of our dissimilarity function in a clustering application using a partitional clustering technique (e.g. \(k\) -medoids) using two characteristically different sets of data: (a) Irregular geometric shapes determined by natural processes, i.e., watersheds and (b) semi-regular geometric shapes determined by human experts, i.e., counties.     

A Parallel Algorithm for the Visibility of a Simple Polygon Using Scan Operations

This paper describes a parallel algorithm for computing the visible portion of a simple planar polygon with N vertices from a given point on or inside the polygon. The algorithm accomplishes this in O(k log N) time using O(N/log N) processors, where k is the link-diameter of the polygon in consideration. The link-diameter of a polygon is the maximum number of straight line segments needed to connect any two points within the polygon, where all line segments lie completely within the polygon. The algorithm can also be used to compute the visible portion of the plane given a point outside of the polygon. Except in this case, the parameter k in the asymptotic bounds would be the link diameter of a different polygon. The algorithm is optimal for sets of polygons that have a constant link diameter. It is a rather simple algorithm, and has a very small run time constant, making it fast and practical to implement. The interprocessor communication needed involves only local neighbor communication and scan operations (i.e., parallel prefix operations). Thus the algorithm can be implemented not only on an EREW PRAM, but also on a variety of other more practical machine architectures, such as hypercubes, trees, butterflies, and shuffle exchange networks. The algorithm was implemented on the Connection Machine as well as the MasPar MP- 1, and various performance tests were conducted.     

Opaque Sets

The problem of finding “small” sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an opaque set or a barrier for that region. We consider the problem of computing the shortest barrier for a given convex polygon with n vertices. No exact algorithm is currently known even for the simplest instances such as a square or an equilateral triangle. For general barriers, we present an approximation algorithm with ratio $\frac{1}{2}+ \frac{2 +\sqrt{2}}{\pi}=1.5867\ldots$ ?. For connected barriers we achieve the approximation ratio 1.5716, while for single-arc barriers we achieve the approximation ratio $\frac{\pi+5}{\pi+2} = 1.5834\ldots$ ?. All three algorithms run in O(n) time. We also show that if the barrier is restricted to the (interior and the boundary of the) input polygon, then the problem admits a fully polynomial-time approximation scheme for the connected case and a quadratic-time exact algorithm for the single-arc case.     

An exact algorithm for minimizing vertex guards on art galleries

We consider the problem [art gallery problem (AGP)] of minimizing the number of vertex guards required to monitor an art gallery whose boundary is an n‐vertex simple polygon. In this paper, we compile and extend our research on exact approaches for solving the AGP. In prior works, we proposed and tested an exact algorithm for the case of orthogonal polygons. In that algorithm, a discretization that approximates the polygon is used to formulate an instance of the set cover problem, which is subsequently solved to optimality. Either the set of guards that characterizes this solution solves the original instance of the AGP, and the algorithm halts, or the discretization is refined and a new iteration begins. This procedure always converges to an optimal solution of the AGP and, moreover, the number of iterations executed highly depends on the way we discretize the polygon. Notwithstanding that the best known theoretical bound for convergence is Θ(n³) iterations, our experiments show that an optimal solution is always found within a small number of them, even for random polygons of many hundreds of vertices. Herein, we broaden the family of polygon classes to which the algorithm is applied by including non‐orthogonal polygons. Furthermore, we propose new discretization strategies leading to additional trade‐off analysis of preprocessing vs. processing times and achieving, in the case of the novel Convex Vertices strategy, the most efficient overall performance so far. We report on experiments with both simple and orthogonal polygons of up to 2500 vertices showing that, in all cases, no more than 15 minutes are needed to reach an exact solution, on a standard desktop computer. Ultimately, we more than doubled the size of the largest instances solved to optimality compared with our previous experiments, which were already five times larger than those previously reported in the literature.     

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.     

Triangulating multiply-connected polygons: A simple, yet efficient algorithm.

We present a new, simple, yet efficient algorithm for triangulating multiply-connected polygons. The algorithm requires sorting only local concave minima (sags). The order in which triangles are created mimics a flooding process of the interior of the polygon. At each stage, the algorithm analyses the positions and neighborhoods of two vertices only, and possibly checks for active sags, so as to determine which of five possible actions to take. Actions are based on a local decomposition of the polygon into monotonic regions, or gorges (raise the water level in the current gorge, spill into an adjacent gorge, jump to the other bank of a filled gorge, divide a gorge into two, and fill a gorge to its top). The implementation is extremely simple and numerically robust for a large class of polygons. It has been tested on millions of cases as a preprocessing step of a walkthrough and inspection program for complex mechanical and architectural scenes. Extensive experimental results indicate that the observed complexity in terms of the number of vertices, remains under in all cases.