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.     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

Fast Range Searching with Delaunay Triangulations

This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon and walk along the boundary of the polygon in the Delaunay Triangulation and report all the points enclosed by the query polygon. For a set of uniformly distributed random points in 2-D and a query polygon the expected query time of this algorithm is O(n ^1/3 + Q + E K + L _r n ^1/2), where Q is the size of the query polygon , {\bf E}K = O(n\bcdot area is the expected number of output points, L _r is a parameter related to the shape of the query polygon and n, and L _r is always bounded by the sum of the edge lengths of . Theoretically, when L _r = O(1/n^1/6) the expected query time is O(n^1/3 + Q + E K), which improves the best known average query time for general range searching. Besides the theoretical meaning, the good property of this algorithm is that once the Delaunay Triangulation is given, no additional preprocessing is needed. In order to obtain empirical results, we design a new algorithm for generating random simple polygons within a given domain. Our empirical results show that the constant coefficient of the algorithm is small, at least for the special (practical) cases when the query polygon is either a triangle (simplex range searching) or an axis-parallel box (orthogonal range searching) and for the general case when the query polygons are generated by our new polygon-generating algorithms and their sizes are relatively small.     

Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD

We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and satisfies a strict set of post conditions suitable for immediate processing of output polygons by downstream tools. The algorithm uses sweepline to compute a Riemann–Stieltjes integral over polygon overlaps in O((n+s)log(n)) time given n polygon edges with s intersections. The algorithm is efficient and general, handling degenerate inputs implicitly. Particular care was taken in implementing the algorithm to ensure numerical robustness without sacrificing efficiency. We present performance comparisons with other polygon clipping algorithms and give examples of real world applications of our algorithm in an industrial software setting.     

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.     

Skeleton computation of orthogonal polyhedra

Skeletons are powerful geometric abstractions that provide useful representations for a number of geometric operations. The straight skeleton has a lower combinatorial complexity compared with the medial axis. Moreover, while the medial axis of a polyhedron is composed of quadric surfaces the straight skeleton just consist of planar faces. Although there exist several methods to compute the straight skeleton of a polygon, the straight skeleton of polyhedra has been paid much less attention. We require to compute the skeleton of very large datasets storing orthogonal polyhedra. Furthermore, we need to treat geometric degeneracies that usually arise when dealing with orthogonal polyhedra. We present a new approach so as to robustly compute the straight skeleton of orthogonal polyhedra. We follow a geometric technique that works directly with the boundary of an orthogonal polyhedron. Our approach is output sensitive with respect to the number of vertices of the skeleton and solves geometric degeneracies. Unlike the existing straight skeleton algorithms that shrink the object boundary to obtain the skeleton, our algorithm relies on the plane sweep paradigm. The resulting skeleton is only composed of axis‐aligned and 45° rotated planar faces and edges.     

A worst-case efficient algorithm for hidden-line elimination †

Many practical algorithms for hidden-line and surface elimination in a 2-dimensional projection of a 3-dimensional scene have been proposed. However surprisingly little theoretical analysis of the algorithms has been carried out. Indeed no non-trivial lower bounds for the problem are known. We present a plane-sweep-based hidden-line-elimination algorithm for 2-dimensional projections of scenes consiting of arbitrary polyhedra. It requires, in the worst case0(n log n) space and 0((n + k) log² n) time, where n is the number of edges in the 3-dimensional scene, and k is the number of edge intersections in the specific projection.     

Improved Bounds for Wireless Localization

We consider a novel class of art gallery problems inspired by wireless localization that has recently been introduced by Eppstein, Goodrich, and Sitchinava. Given a simple polygon P, place and orient guards each of which broadcasts a unique key within a fixed angular range. In contrast to the classical art gallery setting, broadcasts are not blocked by the edges of P. At any point in the plane one must be able to tell whether or not one is located inside P only by looking at the set of keys received. In other words, the interior of the polygon must be described by a monotone Boolean formula composed from the keys. We improve both upper and lower bounds for the general problem where guards may be placed anywhere by showing that the maximum number of guards to describe any simple polygon on n vertices is between roughly \frac35n\frac{3}{5}n and \frac45n\frac{4}{5}n . A guarding that uses at most \frac45n\frac{4}{5}n guards can be obtained in O(nlog n) time. For the natural setting where guards may be placed aligned to one edge or two consecutive edges of P only, we prove that n−2 guards are always sufficient and sometimes necessary.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

In 1922, Steinitz’s theorem gave a complete characterization of the topological structure of the vertices, edges, and faces of convex polyhedra as triconnected planar graphs. In this paper, we generalize Steinitz’s theorem to non-convex polyhedra. More specifically, we introduce a new class of polyhedra, wider than convex polyhedra, called upward star-shaped polyhedra and spherical polyhedra, and present graph-theoretic characterization for both polyhedra. Upward star-shaped polyhedra are polyhedra where each face is star-shaped, all faces except the bottom face are visible from a view point, and any two faces sharing two vertices are non-coplanar. Spherical polyhedra are non-singular, non-coplanar polyhedra with no holes.     

Hidden-surface removal in polyhedral cross-sections

Many of the fundamental problems in computer graphics involve the notion of visibility. In one approach to the hiddensurface problem, priorities are assigned to the faces of a scene. A realistic image is then rendered by displaying the faces with the resulting priority ordering. We introduce a tree-based formalism for describing priority orderings that simplifies an existing algorithm. As well, a decompositionbased algorithm is presented for classes of scenes that do not in general admit priority orderings. The algorithm requiresO(n logn) time ift=1 andO(tn logn+n logn logm) time ift>1, wheren andm are respectively the number of faces and polyhedra in the scene, andt is a minimum decomposition factor of the scene. Finally, the tree-based formalism is used in the development ofO(n) time insertion and deletion algorithms that solve the problem of dynamically maintaining a priority ordering.     

Shortest path between two simple polygons

Consider a collection of mutually disjoint simple polygons in the plane containing a total of n edges. Two of them are specified as a source polygon S and a target polygon T. We present an efficient algorithm for finding a shortest path between S and T avoiding the other polygons. We show that it runs in O(n²) time, using a linear-time algorithm for computing the visibility polygon of a point. This problem is related to a wire routing design of a certain type of LSI for which terminals are of polygonal shape and larger than a wire segment.     

Efficient ray shooting and hidden surface removal

In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n ²⁺) preprocessing, for any fixed > 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn ⁴⁺) preprocessing and has a query time ofO(logn).We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any > 0, we can obtain an algorithm with running time , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.This research was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The first and third authors were also supported by the Dutch Organization for Scientific Research (N.W.O.).     

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

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

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

A linear-time algorithm for constructing a circular visibility diagram

To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices.     

Visibility between two edges of a simple polygon

One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simplen-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There existO(nlogn) algorithms and complicatedO(nlog logn) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.     

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.     

Pictures as Boolean Formulas

Both labellability and realizability problems of planar projections of polyhedra (i.e., pictures) are known to be NP-complete problems. This is true, even in the case of trihedral polyhedra, where exactly three faces meet at every vertex. In this paper, we examine pictures that are taken to be projections of trihedral polyhedra without holes, and contain the projections of all edges (hidden and visible) of a polyhedron. In other words, we examine pictures which represent the entire shape of a trihedral polyhedron without holes. Such a picture is a connected graph P=(V,E) with |E| edges and |V| nodes, each of degree 3 ( $|E| = \frac{3|V|}{2}$ ). We propose a mathematical scheme that constructs from the picture a Boolean formula Φ _P , which is a conjunction of clauses, each consisting of at most two literals. Based on the satisfiability of Φ _P , we show that both labellability and realizability problems can be solved efficiently in polynomial time. The category of pictures with hidden lines consists of the first category of pictures, where the labellability problem is solved in polynomial time, and, moreover, its solution implies the solution of the realizability problem in polynomial time too. Our approach may also prove useful in other applications of scene analysis.