Reconstruction of Curves
There are several ways to define a curve in the plane. For example, explicitly parameterized as a continuous function f:[0,1]→ℝ2, or (as in the case of an affine algebraic curve) implicitly as the zero set of a bivariate polynomial. For some technical app
- PDF / 303,586 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 183 Views
Reconstruction of Curves
There are several ways to define a curve in the plane. For example, explicitly parameterized as a continuous function f : [0, 1] → R2 , or (as in the case of an affine algebraic curve) implicitly as the zero set of a bivariate polynomial. For some technical applications, there are different ways of representing a curve which are more useful in those contexts, for example the representation as a Bézier curve in computer aided design (CAD). A different approach is necessary when we want to represent curves which are the result of a measurement, i.e., when they are only partially known, or the description is not exact. We study the problem of reconstructing a curve from a given unordered set of points. Clearly, there are infinitely many curves that contain a given finite set of points. The question arises if one of these curves is privileged in any way. As an example, consider a scan of a curve drawn by hand (see Fig. 11.1). Here, the (finitely many) scanned points lie so densely that the trajectory of the curve is easy to see. A key aspect of curve reconstruction is to develop criteria for sets of points to be “sufficiently dense”. For this, we introduce in the first part of this chapter the medial axis and the local feature size as intrinsic properties of a curve. After this, we define the surprisingly simple curve reconstruction method NN-Crust. The fundamental concept behind this method is the Delone subdivision of the given points.
11.1 Preliminary Considerations We focus on the simplest case where each connected component of the curve is closed. Furthermore, we restrict ourselves to the problem of partitioning the given point set into connected components, and to order the points within each component. Then, we obtain the (re-)constructed curve by connecting the ordered points with line segments in each component. In particular, the reconstructed curve is piecewise linear. A closed Jordan curve J is the image of a continuous function f : [0, 1] → R2 which is homeomorphic to the circle S1 . By the Jordan curve theorem, we know that M. Joswig, T. Theobald, Polyhedral and Algebraic Methods in Computational Geometry, Universitext, DOI 10.1007/978-1-4471-4817-3_11, © Springer-Verlag London 2013
181
182
11
Reconstruction of Curves
Fig. 11.1 A scan of a curve
R2 \ J has exactly two connected components, i.e., that the curve divides the plane into an inner and an outer part. A subset of J that is homeomorphic to the interval [0, 1] is called a curve arc of J . A sample S on J is a finite subset of J such that |S| ≥ 3. Two points s (1) , s (2) ∈ S are called neighbors on J with respect to S if one of the curve arcs between s (1) and s (2) contains no other point of S. Since |S| ≥ 3, there exists exactly one such connecting curve arc for each set of neighboring points s (1) and s (2) . A polygonal reconstruction P of a curve J is a closed polygonal chain whose vertices S form a sample on J , such that the points s (1) , s (2) ∈ S are neighbors in P if and only if they are neighbors in J .
Data Loading...
