Domain Analysis

While the Partner system could conceivably be used to view any kind of zoomable, two-dimensional information, in practice we deal exclusively with representations of geography, facilities, and related data. Therefore the range of data we deal with is at the human scale rather than at microscopic or macroscopic scale. Optimizing map viewing requires a good deal of data compression. Many of our advantages over traditional GIS stem from the fact that we are free to use lossy compression, rather than retaining full accuracy as would be required of the data-source-of-record. Understanding the kinds of numbers involved is critical to the design of good lossy algorithms - those which throw away the unnecessary without sacrificing critical information. We need to choose good, compact datatypes, and massage the numbers in such a way that they are more amenable to compression. However, we must beware of pitfalls in floating-point representations and integer overflows that would lead to corrupt or degenerate graphics.

Units of Measure

Typically, we deal with three units of measure for coordinates.

  • feet on a plane
  • meters on a plane
  • degrees, minutes, and seconds on a sphere

Most other units can be derived from these. Spherical coordinates are fundamentally different from planar; however a map set could conceivably store coordinates in latitude and longitude, with longitude as x and latitude as y. The map viewer would just do a simple rectangular projection, but that may be sufficient for some uses, and who knows, maybe someday it will project on the fly or something.

Resolution

Resolution for maps is the minimum distance at which two distinct object’s locations can be differentiated.

A map with a resolution of one mile cannot differentiate the position of objects in the same square mile, for example. A one-foot resolution map could distinguish the positions of furniture in a room, but not silverware on a place setting. And so forth. Outdoor facilities, such as power poles, really don’t require more than one meter accuracy in most cases. Professional-grade GPS provides this much accuracy, so it is a common level of resolution. High-quality GPS and survey equipment can provide centimeter or better accuracy. This is generally overkill for most outdoor mapping, but can be useful in dense areas or with complex facilities. Anything more than that seems to be outside the realm of actual mapping scales, and more into the world of CAD.

However, there are uses for finer resolution. For example, for electric maps that don’t have separate icons for consumers, we create an artificial symbol for the customers attached to a transformer by “exploding” the symbols into a tight (10x10 or so) grid under the transformer. This can then be viewed by zooming in closer than normal base scale. This is a good example of the uses of a zoomable interface, but it does require better-than-normal resolution. For our system, several distinct cases are useful to consider. They vary from each other depending on situation and intent.

Base resolution
The base resolution is the resolution of the original map set. This is initially set by the resolution of the data collection method (GPS, tracing, hand-drawing, etc.) and can, of course, be greatly affected by errors in data management or storage.
Human resolution
This is the resolution at which the data “makes sense” when viewed or handled physically in the real world. For example, sub-centimeter resolution makes little sense when placing foot-thick electric poles. On the other hand, it’s nice to know which side of the road a pole is on - which the base resolution of some maps is not good enough to tell you.

Working resolution This is the resolution provided by our computer map interface. It might be coarser than that provided by the base maps, perhaps to save space. Or it might be finer, in order to artificially add detail (or allow improving the existing data). It may differ from human-oriented scaling to allow zooming in to view diagrams, extra details or other non-physical features.

Scalability

Scalability represents the meaningful range of values in a map set. In a practical sense, it is the difference between the coarsest viewing resolution and the finest viewing resolution for the map viewer. You can also think of it as the difference in area between the map set’s extreme bounding box and a square at the finest resolution.

Scalability has an enormous impact on the way we represent map coordinates. We must store them in such a way that we do not lose significant digits. For example, a map may reach from 1,200,000 ft. to 1,400,000 ft. on the x axis, but we may need to differentiate between items as close as 0.1 ft.

Primitive Numeric Types

Numbers can be stored in computers in a bewildering number of ways. However, there are some standard primitive types we should stick to if at all possible.

Integers are generally stored in binary format using some number of whole bytes, usually 1, 2, 4, or 8. We can also split values to store two coordinates - for example, store two two-byte values in a singe four-byte number.

The maximum number you can specify is pow(2, numberOfBits). There are 8 bits to the byte.

Here are some common unsigned ranges:

  • 1 bit can store 0-1
  • 2 bits can store 0-3
  • 3 bits can store 0-7
  • 4 bits can store 0-15
  • 8 bits can store 0-255
  • 10 bits can store 0-1023
  • 12 bits can store 0-4095
  • 16 bits can store 0-65535
  • 20 bits can store 0-1048576
  • 24 bits can store 0-16777216
  • 32 bits can store 0-4294967296
  • 64 bits can store 0-18446744073709551616

It’s easy to get into trouble. For example, notice that a US telephone number with area code higher than 429 cannot be stored as an unsigned four-byte, 32-bit int. And since Java types are all signed, you can’t store anything with area code higher than 200 or so without doing bit-banging.

Floating-point has its own problems. An excellent discussion is here: http://www.lahey.com/float.htm

To summarize:

  • decimal fractions (e.g. 0.1) can’t be stored accurately in binary floats, and
  • 32-bit (single precision) floats only have about 7 significant digits of accuracy
  • 64-bit (double precision) floats have about 16 significant digits of accuracy

Using floating point variables is like using a rubber ruler. They can very precisely measure a variation between 0.0 and 1.0; they are far less precise between 1000.0 and 1001.0, and they have very little precision between 1000000 and 1000001 - in fact, a single-precision float loses the ability to distinguish even 0.1 for values over a million. Often map sets have coordinates in excess of a million, so single-precision floats are marginal at best; they have an effective resolution of one foot or so in that range.

Latitude and Longitude

A minute of latitude is one nautical mile - 1.15077945 miles, or 6076.115496 feet. A second is therefore 101.2685916 ft. 100 feet is a good approximation.

Therefore, in order to represent 0.1 feet in circular coordinates, you need thousandths of a second, which we call a “fract”. 360 degrees is then 1,296,000,000 fracts, which stretches the ability of an integer. The earth is about 24,902 miles in circumference at the equator. This is 131,482,560 feet.

Table Of Contents

Previous topic

Overview

Next topic

Rover Model

This Page