tailieunhanh - Skiena - The Algorithm Design Manual [Springer-Verlag 1997] Episode 6

Tham khảo tài liệu 'skiena - the algorithm design manual [springer-verlag 1997] episode 6', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Simplifying Polygons vertices and of polygon P and propose the degenerate polygon uii as a simple approximation P. Scan through each of the vertices of P and select the one that is farthest from the corresponding edge of the polygon P. Inserting this vertex adds the triangle to P so as to minimize the maximum deviation from P. Points can be inserted until satisfactory results are achieved. This takes O kn to insert k points when P n. Simplification becomes considerably more difficult in three dimensions. For example it is NP-complete to find the minimum-size surface separating two polyhedra. Higher-dimensional analogies of the planar algorithms discussed here can be used to heuristically simplify polyhedra. See the references below. Implementations A program for automatically generating level-of-detail hierarchies for polygonal models is available from http geom and is free for noncommercial use. The user specifies a single error tolerance and the maximum surface deviation of the simplified model from the original model and a new simplified model is generated. This code preserves holes and prevents self-intersection. Yet another approach to polygonal simplification is based on simplifying and expanding the medial-axis transform of the polygon. The medial-axis transform see Section produces a skeleton of the polygon which can be trimmed before inverting the transform to yield a simpler polygon. MAT Ogn93 is a medial-axis transform code designed for 2D skeletonization and inversion of binary images written by Robert Ogniewicz and available from http people postdocs rlo . Notes See HG95 for a thorough survey of algorithms for shape simplification. It is also available from http afs cs user ph www along with implementations. The Douglas-Peucker incremental refinement algorithm DP73 is the basis for most shape simplification schemes with a faster implementation due to .