Optimal simplification of polygonal chains for subpixel-accurate rendering Export

@article{Buzer2009, abstract = {For a given polygonal chain, we study the min-\# problem, which consists of finding an approximate and ordered subchain with a minimum number of vertices under a given approximation criterion. We propose the first near-linear time algorithm for the min-\# problem that ensures optimality in the number of vertices and that retains the shape of the input polygonal chain at the same time. Previous algorithms with near-linear time performance produced geometrical inconsistencies and former methods used to preserve the features of the original chain required a quadratic time complexity. When we set the approximation error equal to the pixel pitch, our simplification criterion guarantees that the rendering of the simplification lies at most half a pixel away from the original chain, contrary to other methods that do not offer a direct control over the rendering. Thus, we avoid producing visible topological inconsistencies. Moreover, our method is based on basic data structures, which leads to a simple and efficient implementation.}, author = {Buzer, L.}, citeulike-article-id = {3681074}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.comgeo.2008.03.002}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S092577210800028X}, doi = {10.1016/j.comgeo.2008.03.002}, issn = {09257721}, journal = {Computational Geometry}, keywords = {computergraphics, geometry, profiles}, month = {January}, number = {1}, pages = {45--59}, posted-at = {2008-11-24 14:52:10}, priority = {2}, title = {Optimal simplification of polygonal chains for subpixel-accurate rendering}, url = {http://dx.doi.org/10.1016/j.comgeo.2008.03.002}, volume = {42}, year = {2009} }

TY - JOUR ID - Buzer2009 L3 - citeulike-article-id:3681074 N2 - For a given polygonal chain, we study the min-# problem, which consists of finding an approximate and ordered subchain with a minimum number of vertices under a given approximation criterion. We propose the first near-linear time algorithm for the min-# problem that ensures optimality in the number of vertices and that retains the shape of the input polygonal chain at the same time. Previous algorithms with near-linear time performance produced geometrical inconsistencies and former methods used to preserve the features of the original chain required a quadratic time complexity. When we set the approximation error equal to the pixel pitch, our simplification criterion guarantees that the rendering of the simplification lies at most half a pixel away from the original chain, contrary to other methods that do not offer a direct control over the rendering. Thus, we avoid producing visible topological inconsistencies. Moreover, our method is based on basic data structures, which leads to a simple and efficient implementation. IS - 1 JF - Computational Geometry SN - 09257721 EP - 59 TI - Optimal simplification of polygonal chains for subpixel-accurate rendering VL - 42 SP - 45 KW - computergraphics KW - geometry KW - profiles AU - Buzer, L PY - 2009/01// UR - http://dx.doi.org/10.1016/j.comgeo.2008.03.002 ER -