Đang chuẩn bị liên kết để tải về tài liệu:
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 www.cs.unc.edu geom envelope.html 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 hrl.harvard.edu people postdocs rlo rlo.dir rlo-soft.html. Notes See HG95 for a thorough survey of algorithms for shape simplification. It is also available from http www.cs.cmu.edu afs cs user ph www heckbert.html along with implementations. The Douglas-Peucker incremental refinement algorithm DP73 is the basis for most shape simplification schemes with a faster implementation due to .