International Journal of Computational Geometry & Applications

This paper presents a new method for reconstructing piecewise linear surfaces from planar polygonal contours that branch. For non-branching contours, experience has shown that the piecewise linear surface of minimum surface area which connects a pair of contours often provides a good solution. The current algorithm extends this idea by searching for the surface of minimal area which connects two contours comprised of more than one polygon. Several examples that justify this heuristic are provided.

Recognizing 3D objects from their 2D silhouettes is a popular topic in computer vision. Object reconstruction can be performed using the volume intersection approach. The visual hull of an object is the best approximation of an object that can be obtained by volume intersection. From the point of view of recognition from silhouettes, the visual hull can not be distinguished from the original object. In this paper, we present efficient algorithms for computing visual hulls. We start with the case of planar figures (polygons and curved objects) and base our approach on an efficient algorithm for computing the visibility graph of planar figures. We present and tackle many topics related to the query of visual hulls and to the recognition of objects equal to their visual hulls. We then move on to the 3-dimensional case and give a flavor of how it may be approached.

A new polygon decomposition problem, the anchored area partition problem, which has applications to a multiple-robot terrain-covering problem is presented. This problem concerns dividing a given polygon P into n polygonal pieces, each of a specified area and each containing a certain point (site) on its boundary or in its interior. First the algorithm for the case when P is convex and contains no holes is presented. Then the generalized version that handles nonconvex and nonsimply connected polygons is presented. The algorithm uses sweep-line and divide-and-conquer techniques to construct the polygon partition. The input polygon P is assumed to have been divided into a set of p convex pieces (p = 1 when P is convex), which can be done in O(v_Ploglog v_P) time, where v_P is the number of vertices of P and p = O(v_P), using algorithms presented elsewhere in the literature. Assuming this convex decomposition, the running time of the algorithm presented here is O(pn²+vn), where v is the sum of the number of vertices of the convex pieces.

In computational metrology one needs to compute whether an object satisfies specifications of shape within an acceptable tolerance. To this end positions on the object are measured, resulting in a collection of points in space. From this collection of points one wishes to extract information on flatness, roundness, etc. of the object. In this paper we study one particular feature of objects, the angularity. The angularity indicates how well a plane makes a specified angle with another plane. We study the problem in 2-dimensional space (where the planes become lines) and in 3-dimensional space. In 2-dimensional space the problem is equivalent to computing the smallest wedge of the given angle that contains all the points. We give an O(n²log n) algorithm for this problem. In 3-dimensional space we study the more restricted problem where one of the planes is known (a datum plane). In this case the problem is equivalent to asking for the smallest width 3-dimensional strip that contains all the points and makes a given angle with the datum plane. We give an O(n log n) algorithm to solve this version. We also show that in the case of uncertainty in the measured points, upperbounds and lowerbounds on the width can be computed in similar time bounds.