The attractor-wrapping approach to approximation convex hulls of 2D affine IFS attractors
- Tomasz Martyn
We present an algorithm for approximating convex hulls of affine iterated function system (IFS) attractors in R2 at any accuracy required. The algorithm is based on the gift-wrapping technique. However, in order to make the computation efficient and with low memory requirements, we take advantage of self-similarity of IFS attractors. To accomplish this we engage the adaptive-cut approach in the process of the convex hull computation. In effect, the convex hull of an IFS attractor is approximated efficiently (our algorithm appears to run in expected View the MathML source time) with the guaranteed O(logN) storage, where h is the number of the approximate hull vertices, and N is the number of points of an ε-approximation of the attractor. Since the convex hull is the most ubiquitous structure in computational geometry, our algorithm opens the door to solving many geometrical problems concerning IFS attractors. As instances of possible applications in computer graphics we show how to compute the diameter of an IFS attractor and the smallest oriented rectangle to bound the attractor.
- Record ID
- Journal series
- Computers & Graphics -UK
- Issue year
- Keywords in English
- Fractal; Iterated function system; IFS attractor; Convex hull
- DOI:10.1016/j.cag.2008.08.003 Opening in a new tab
- (en) English
- Score (nominal)
- Publication indicators
- : 2009 = 0.787 (2) - 2009=0.978 (5); = 5; = 3
- Uniform Resource Identifier
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.