Efficient Snap Rounding in Square and Hexagonal Grids using Integer Arithmetic

In this paper we present two efficient algorithms for snap rounding a set of segments to both square and hexagonal grids. The first algorithm takes n line segments as input and generates the set of snapped segments in O((n + k) log n + |I| + |I*_m|) time, where k is never more than the number of hot pixels (and may be substantially less), |I| is the complexity of the unrounded arrangement I, and |I*_m| is the multiset of snapped segment fragments. The second algorithm generates the rounded arrangement of segments in O(|I| + ( |I*| + Sigma_c is(c)) log n) time, where |I*| is the complexity of the rounded arrangement I* and is(c) is the number of segments that have an intersection or endpoint in pixel row or column c. Both use simple integer arithmetic to compute the rounded arrangement by sweeping a strip of unit width through the arrangement, are robust, and are practical to implement. They improve upon existing algorithms, since existing running times either include an |I| log n term, or depend upon the number of segments interacting within a particular hot pixel h (is(h) and ed(h), or |h|), whereas ours depend on |I| without the log n factor and are either independent of the number of segments interacting within a hot pixel (algorithm 1) or depend upon the number of segments interacting in an entire hot row or column (is(c)), which is a much coarser partition of the plane (algorithm 2).