Search
Close this search box.

Snap Rounding on the Sphere

Abstract

A spherical grid inducedby an Isocube
A spherical grid induced by an Isocube

Snap rounding (SR for short) is a well known method for transforming a planar arrangement of segments given in some arbitrary-precision coordinates into a fixed-precision representation. We extend the method to transforming an arrangement of geodesic arcs on the sphere. We present two approaches for solving the problem. A simple approach of enclosing the sphere in an isocube and projecting the arrangement onto its faces and a more complex approach that makes use of tools from Discrete Global Grid Systems (DGGS) to create a better approximation to the sphere. We also generalize the Guibas-Marimont proof of the topological properties preserved by the standard SR for segments in the plane; the generalization is needed for the DGGS approach. We present in detail the implementation of both approaches and give rounding results for both methods, obtained with our CGAL (Computational Geometry Algorithms Library) based implementation.

An arrangement of segments before (L) and after (R) snap rounding

Experimental Results

The snap rounding algorithm was tested on real world inputs. Specifically, we ran the algorithm on the border and roads of USA, where the results for the former are depicted below.

The input arrangement is illustrated in Figure (a). In (b) the resulting arrangement of the snap rounding algorithm is given. In (c) we zoom in on the San Diego bay area. The input, isocube and DGGS rounded arcs (red, green and blue, respectively) are very close such that there is no substantial difference between the three arrangements.

(a)
(a)

(b)
(b)

(c)
(c)

Links

Contacts

Eitan Yaffe
Dan Halperin
@inproceedings{kh-srs-10,
  title        = {Boris Kozorovitzky and Dan Halperin},
  author       = {Snap Rounding on the Sphere},
  booktitle    = {Proceedings of the 26th European Workshop on Computational Geometry (EuroCG)},
  pages        = {213--216},
  year         = {2010},
  site         = {Nancy, France}
}
@masterthesis{k-srs-10,
  author       = {Boris Kozorovitzky},
  title        = {Snap Rounding on the Sphere},
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2010}
}

Yair Oz - Webcreator

Contact

Skip to content