Surety is performing system maintenance this weekend. Electronic date stamps on new Prior Art Database disclosures may be delayed.
Browse Prior Art Database

Smart Interpolation of Spherical Polygonal Segments for Robust Topological Computation on Projections

IP.com Disclosure Number: IPCOM000237573D
Publication Date: 2014-Jun-25
Document File: 7 page(s) / 374K

Publishing Venue

The IP.com Prior Art Database


The complication of solving geographic problems on a spherical model, as well as the distortion that is induced when projecting the data onto the plane for simpler computation makes the development of geographic software very challenging and error prone. As any projection introduce error in the data, interpolating it the sphere prior to the projection helps decreasing the errors. On the other hand, interpolating the data makes it more costly for further processing. Thus, the developer faces a trade of between the interpolation level and the data complexity when designing his solution. These parameters are also affected by other features of the model he works with: projection type, location on earth and more. The main idea of this disclosure is to provide the user with an easy and efficient tool to optimize the trade off between the interpolation level and the data complexity

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 22% of the total text.

Page 01 of 7

Smart Interpolation of Spherical Polygonal Segments for Robust Topological Computation on Projections

Problems with geographic aspects can be modeled with several alternatives. The elliptical model is the most accurate one but its computations are extremely hard and costly. The spherical model, on the other hand, while being less accurate than the elliptical model, is a relatively good approximation and its computations are much easier to implement. While some computations on the sphere are relatively easy to implement (e.g., distances), some are very complicated if not infeasible. Those computations (and in general any computation) become much easier if the data is projected onto the plane as planar computations are much easier. This is one of the main reasons that many earth projections have been introduced over the years (another major one is more effective visualization).

Below is an illustration of several projections copied from http://www.geocurrents.info/cartography/cartography-and-the-visua l-arts-turning-3-d-world-into-2-d-images.

Figure 1: several popular projections

The projections follow mathematical formulas and satisfy one-to-one and onto relationships. Thus, a good way to solve problems would have been to project the data onto the plane using one of the projections and carry out the computation using planar methods. We note that most of the projections have been developed in a way that they preserve some geometric features. However, it has been proved to be infeasible to preserve the geometric features distance, shapes, areas and directions simultaneously using projections. Moreover, the preservation is very limited:

Page 02 of 7

the projections usually preserve one or two features in a limited

way (e.g., preserving distances just from one specific point). Hence, projecting the data on the plane will result in erroneous result, unless the computation is limited to the regions where the projection yields robust data.

    An important feature of almost all the projections is the topology preservation (except at some specific location on earth where it is 'torn'): relationships such as containment and intersection are preserved. However, the preservation holds only if the projection is accurate: for example, if we project a line segment, it is crucial to project all the points of the segment and not only its end points (and then connecting the end points with straight lines). The same idea is true for any geometry (polygons, discs, etc.). Unfortunately, the projections are never linear as none such projection from the sphere to the plane exist, and thus it is difficult to implement exact projection. Even worse, it is difficult to infeasible to implement and very costly in space and time to execute the solutions that work on the projected data, even if the geometries are projected accurately.

    Many of the most popular geometries consist of line segments (great circles on the sphere): polygonal chains (that could represent...