An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application t
- PDF / 286,149 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 211 Views
Springer 2006
An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing Evgeny Lipovetsky and Nira Dyn School of Mathematical Sciences, Tel-Aviv University, Israel E-mail: {eug;niradyn}@post.tau.ac.il
Received 14 March 2004; accepted 24 January 2005 Communicated by J. Carnicer and J.M. Peña
We wish our dear friend and colleague Mariano Gasca many more years of productive scientific work.
Motivated by the method for the reconstruction of 3D objects from a set of parallel cross sections, based on the binary operation between 2D sets termed “metric average”, we developed an algorithm for the computation of the metric average between two intersecting convex polygons in 2D. For two 1D sets there is an algorithm for the computation of the metric average, with linear time in the number of intervals in the two 1D sets. The proposed algorithm has linear computation time in the number of vertices of the two polygons. As an application of this algorithm, a new technique for morphing between two convex polygons is developed. The new algorithm performs morphing in a non-intuitive way. Keywords: convex polygons, metric average, morphing, linear time complexity. Mathematics subject classifications (2000): 65D18, 68U05.
1.
Introduction
In this work an algorithm for the computation of the metric average between two intersecting convex polygons in 2D is developed and studied. The metric average of two compact sets is a union of the weighted averages between any point from any set of the two, and the subset of all the closest points to it from the other set. The original application of the metric average is for “piecewise linear” approximation of set-valued functions [3]. It is applied in spline subdivision schemes for compact sets, a procedure which is motivated by the problem of the reconstruction of a 3D smooth object from its parallel cross-sections [6]. An algorithm for the computation of the met-
270
E. Lipovetsky, N. Dyn / Metric average of two intersecting polygons
ric average of 1D compact sets with computation time which is linear in the number of connected subsets in the two 1D sets is introduced in [5]. The metric average of two sets is a subset of the Minkowski average of the sets and generally is a nonconvex set (even for two convex sets). The Minkowski average is much bigger than the metric average. For example, the Minkowski average of a nonconvex set with itself is a larger set containing it, while the metric average is the set itself. The metric property of the metric average is that its Hausdorff distance from any one of the averaged sets changes linearly with the weight parameter in the average. For the reconstruction problem of a smooth 3D object from its parallel crosssections, the assumption that the projections of two consecutive cross-sections into a parallel plane intersect significantly, is natural. The choice of convex polygons was made although for such polygons the reconstruction from parallel cross-sections can be done b
Data Loading...
