Narrow Results

An efficient method for rectangular boundary extraction from aerial image data is proposed in this paper. A centroid neural network (CNN) with a metric utilizing line segments is adopted to group low-level line segments for detecting rectangular objects. The proposed method extracts rectangular boundaries for building rooftops from 3D edge images with various types of noises arising from the stereo matching process. In order to overcome the noises in 3D edge images including line segments of shadows, a clustering method utilizes the constraint where the heights of building rooftops are similar and the clustering process is performed with candidate 3D line segments with similar heights. Experiments are performed with a set of high-resolution satellite image data. The results show that the proposed method can remove noisy segments including shadow lines efficiently and thus find more accurate rectangular boundaries and building information.

A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E³ such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimum set of spanning line segments for an arbitrary polyhedron . When the number of extreme vertices of is odd, the computed SLS is minimum; when the number of extreme vertices of is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity for a convex polyhedron, hence is optimal in this case; its time complexity is Θ(m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron.

The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n log n) or output sensitive O(n log h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n log h) time. Our algorithms are given in the Euclidean plane but they hold also in the general L_p metric, 1 ≤ p ≤ ∞.

We address the problem of reconstructing a polygon from the multiset of its edges. Given $n$ line segments in the plane, find a polygon with $n$ vertices whose edges are these segments, or report that none exists. It is easy to solve the problem in $O(nlogn)$ time if we seek an arbitrary polygon or a simple polygon. We show that the problem is NP-complete for weakly simple polygons, that is, a polygon whose vertices can be perturbed by at most $𝜀$, for any $𝜀>0$, to obtain a simple polygon. We give $O(n)$-time algorithms for reconstructing weakly simple polygons: when all segments are collinear or the segment endpoints are in general position. These results extend to the variant in which the segments are directed.

We study related problems for the case that the union of the $n$ input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems.