United States Patent
`
`[19]
`
`[11] Patent Number:
`
`4,972,319
`
`Delorme
`
`[45] Date of Patent:
`
`Nov. 20, 1990
`
`[54] ELECTRONIC GLOBAL MAP GENERATING
`SYSTEM
`
`[76]
`
`Inventor: David M. Delorme, 356 Range Rd.,
`Cumberland, Me. 04021
`
`McBryde and Thomas, US. Dept. of Commerce, Coast
`and Geodetic Survey, Spec. Pub. 245, 1949.
`“The Quadtree and Related Hierarchical Data Struc-
`tures”, Hanan Samet, Computer Surveys, vol. 16, No. 2,
`Jun. 1984.
`
`[21] Appl. No.: 101,315
`
`[22] Filed:
`
`Sep. 25, 1987
`
`Int. Cl.5 ............................................ .. 6098 29/00
`[51]
`[52] US. Cl. .................................... 364/419; 434/150;
`340/990
`[58] Field of Search .............. .. 364/419, 449; 434/ 150,
`434/130; 340/990
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`400,642 4/1889 Beaumont ............................. 283/34
`751,226 10/1899 Van Der Grinten .
`283/34
`
`752,957 2/1904 Colas .........................
`283/34
`1,050,596
`1/1913 Bacon
`283/34
`
`1,610,413 12/1924 Balch
`283/34
`2,094,543 9/1937 Lackey ct
`353/11
`2,354,785
`8/1944 Von Rohl
`.. 434/150
`2,431,847 12/1947 Dusen ..... ..
`.. 353/11
`2,650,517 9/1953 Falk ...........
`...... .. 355/77
`
`3,248,806 5/1966 Schrader ........ ...
`...... 434/150
`3,724,079 4/ 1973
`Jasperson et a1.
`...... 33/15 B
`
`4,315,747 2/ 1982 McBryde .................... 434/150
`.................. 434/150
`4,673,197 6/1987 Stipelman et a1.
`.................... .. 364/449
`4,689,747 -8/1987 Krouse et a1.
`4,737,927 4/1988 Hanabusa et a1.
`.................1 340/990
`
`.
`
`OTHER PUBLICATIONS
`
`Primary Examiner—Jerry Smith
`Assistant Examiner—Kim T. Bui
`
`Attorney, Agent, or Firm—Sughrue, Mion, Zinn,
`Macpcak & Seas
`
`[57]
`
`ABSTRACT
`
`A global mapping system which organizes mapping
`data into a hierarchy of successive magnitudes or levels
`for presentation of the mapping data with variable reso-
`lution, starting from a first or highest magnitude with
`lowest resolution and progressing to a last or lowest
`magnitude with highest resolution. The idea of this
`hierarchical structure can be likened to a pyramid with
`fewer stones or “tiles” at the top, and where each suc-
`cessive descending horizontal level or magnitude con-
`tains four times as many “tiles” as the level or magni-
`tude directly above it. The top or first level of the
`pyramid contains 4 tiles, the second levle contains 16
`tiles, the third contains 64 tiles and so on, such that the
`base of a 16 magnitude or level pyramid would contain
`4 to the 16th power or 4,294,967,296 tiles. This total
`includes “hyperspace” which is later clipped or ig-
`nored. Digital data corresponding to each of the sepa-
`rate data base tiles is stored in the database under a
`unique filename.
`
`“Equal—Area Projections for World Statistical Maps”,
`
`33 Claims, 9 Drawing Sheets
`
`
`
`|fim
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet 1 of9
`
`4,972,319
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet 2 of9
`
`4,972,319
`
`FIG.3A
`
`'
`
`FIG.38
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent Nov. 20, 1990
`
`Sheet 3‘of9
`
`4,972,319
`
`FIG.5A
`
`FlG.58
`
`a E: '-.'.-.....'..1 .
`
`
`“““““““-‘
`r
`
`ATIST
`
`__
`
`
`
`
`
`
`'-- III-II
`I- II...
`"'""
`‘IIIII
`
`X __
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet 4 of 9
`
`4,972,319
`
` mammal“
`
`mwnulm‘— .
`mwm‘m‘
`mwmml‘“
`p“‘““
`\I“““‘
`\‘“““‘
`n““‘“
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet 5 of9
`
`4,972,319
`
`FIG.|IA
`
`FIG.||B
`
`\-
`
`
`fiM
`|““““\
`
`
`II“““
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`- US. Patent
`
`Nov. 20, 1990
`
`Sheet 6 of9 '
`
`4,972,319
`
`2560
`
`256°
`
`00
`
`ad ob
`
`0° be
`
`be
`
`bb
`
`256°
`
`256°
`
`FIGJS
`
`0C
`
`CC
`
`
` CO lug! anI.
`
`
`
`cd
`
`cb
`
`do
`
`dc
`
`2560
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`.Nov. 20, 1990
`
`Sheet 7 of 9
`
`4,972,319
`
`256°
`
`0°
`
`256°
`
`
`
`
`180° --_ 180°
`(glfingm-yi
`
`
`IIIQEMHM
`IIIUIIL'IIEII
`
`
`IE===='
`
`
`
`
`
`256°
`
`256°
`
`HG.”
`
`
`
`
`
`
`
`
`
`
`ll!!!!fl!!!l
`
`Ilfiiirammniilliqi 9° I
`llllilullfilllmlll
`Illllfifllfliramgdlfll 0°
`
`Illlllllnlllllllgflllll
`lIIIIIlfilIIIIIiIIIII
`III!!!!!!!!!!!!MI
`
`III-IIIIIIIIIIII
`
`
`256°
`0"
`IIIIIIIIIIIIIIII
`IIIIIIIIIIIIIIII
`IIIIIIIIIIIIIIII
`llllllllllllllll
`
`
`
`
`
`
`
`
`
`
`
`256°
`
`Microsbft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet 8 of 9
`
`4,972,319
`
`256°
`
`
`
`
`
`FIG.|8
`
`
`
`
`
`
`
`
`5;.
`Hfiflflfllfiufi 180300
`
`
`-III-IIIEMHEZ'Il-—!
`bll‘!:--E!l--t.'l------:‘L!d-—
`III-‘I-IIIIEEEI-I-fiII-I_
`IIl-flEfl‘IIIMIIIEEI!_IE
`
`III-m‘-I!IlhflnlI'-Ilv
`I II-I-Illil-I II-[I-IS
`.—
`II-I-IIIIIIIIH-Inh‘II-
`
`III-I-Itl'AIlllfdl--|EQIII—
`III-n-HIIII-II-—-III-
`IIII-III-II-II-_I III
`
`ll:==========:======= ===
`I
`---—IIII-IIII-IIII—I-I-II
`
`II-I—III—IIIIIIIIIIIIIIIIII
`
`
`---I—III-Il-IIIII-I-II-II
`III—II-III-IIIIIIII-IIII-I
`-III-III-IIIIII-IIIIIIIIIII-II
`
`
`-IIII—I-IIIII-IIIIII-IIIII-I
`---I--I---Il-I-III-IIII-II-II
`
`
`-IIII-IIII-IIIIIIIIIIIIII_II
`
`-IIII-IIIII-II-IIIIIIII-I-IIII
`
`
`III-II—IIIIIIIIIIIIIIIIIII-IIII 2560
`
`256°
`0°
`
`
`I-II—In-I-I-II-m-I— .
`Illn-I-IIIIl-III-III-
`
`II---I-II-II---IIIIIII
`
`II--l-II-II——IIIII-
`I_-I-IIIII-_III-
`
`—---l-IIIII-—---I-
`II—III-II-II-—-III-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. I9
`
`256°
`
`0°
`
`256°
`
`III-III-I-I-IIIIIIIIII-IIIIIIIIIIII-III-IllIIIOII-II-Il-I-II-I==
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`US. Patent
`
`Nov. 20, 1990
`
`Sheet_9 of9
`
`4,972,319
`
`FIG.20
`ILLUSTRATION 0F POLAR COMPRESSION
`AT THE Blh MAGNITUDE
`
`A
`
`'
`
`33°
`III\\\\ -
`IIIIII
`llllllllll
`
`,.
`
`Ei||\\\
`
`‘1'!"
`
`I
`
`I60
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`1
`
`4,972,319
`
`ELECTRONIC GLOBAL MAP GENERATING
`SYSTEM
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`This invention relates to a new variable resolution
`global map generating system for structuring digital
`mapping data in a new data base structure. managing
`and controlling the digital mapping data according to
`new mapping data access strategies, and displaying the
`mapping data in a new map projection of the earth.
`2. Background Art
`Numerous approaches have been forwarded to pro-
`vide improved geographical maps, for example:
`U.S. Pat. No. 4,315,747, issued to McBryde on Feb.
`16, 1982, describes a new map “projection” and inter-
`secting array of coordinate lines known as the “grati-
`cule”, which is a composite of two previously known
`forms of projection. In particular, the equatorial por-
`tions of the world are represented by a fusiforrn equal
`area projection in which the meridian curves, if ex-
`tended, would meet at points at the respective poles,
`referred to as “pointed poles”. In contrast, the polar
`regions of the world map are represented by a flat polar
`equal area projection in which the poles are depicted as
`straight horizontal lines with the meridians intersecting
`along its length. Thus, in a flat polar projection the
`meridian curves converge toward the poles but do not
`meet at a point and, instead, intersect a horizontal linear
`pole. The two component portions of the flat world
`map are joined where the parallels are of equal length.
`The composite is said to be “homolinear” because all of
`the meridian curves are similar curves, for example,
`sine, cosine or tangent curves, which merge where the
`two forms of projection are joined where the respective
`parallels are equal. The flat polar projections in the
`polar portions of the map provide a compromise with
`the Mercator cylinder projections, thereby greatly re-
`ducing distortion.
`U.S. Pat. No. 1,050,596, issued to Bacon on Jan. 14,
`1913, describes another composite projection for world
`maps and charts which uses a Mercator or cylindrical
`projection for the central latitudes of the earth and a
`convergent projection at the respective poles. In the
`central latitudes, the grids of the Mercator projection
`net or graticule are rectangular. In the polar regions, the
`converging meridians may be either straight or curved.
`U.S. Pat. No 1,620,413, issued to Balch on Dec. 14,
`1926, discusses gnomic projections from a conformal
`sphere to a tangent plane and Mercator or cylindrical
`projections from the conformal sphere to a tangent
`cylinder. Balch is concerned with taking into account
`the non-spherical shape of the earth, and therefore,
`devises the so-called “conformal sphere” which repre-
`sents the coordinates from the earth whose shape is
`actually that of a spheroid or ellipsoid of revolution,
`without material distortion.
`U.S. Pat. No. 752,957, issued to Colas on Feb. 23,
`1904, describes a map projection in which a map of the
`entire world is plotted or transcribed on an oval con-
`structed from two adjacent side by side circles with arcs
`joining the two circles. The meridians are smooth
`curves equally spaced at the equator, while the latitude
`lines are non-parallel curves.
`U.S. Pat. No. 400,642 issued to Beaumont on Apr. 2,
`1889, describes a map of the earth on two intersecting
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`2
`spheres, on which the coordinate lines of latitude and
`longitude are all arcs of circles.
`U.S. Pat. No. 751,226, issued to Grinten on Feb. 2,
`1904, represents the whole world upon the plane sur-
`face of a single circle with twice the diameter of the
`corresponding globe, the circle being delineated by a
`graticule of coordinates of latitude and longitude which
`are also arcs of circles.
`U.S. Pat. No. 3,248,806, issued to Schrader on May 3,
`1966, discloses a subdivision of the earth into a system
`of pivotally mounted flat maps, each map segment rep-
`resenting only a portion of the earth’s surface in spheri-
`cal projection on an equilateral spherical triangle to
`minimize distortion.
`
`'
`
`U.S. Pat. No. 2,094,543, issued to Lackey et al on
`Sept. 28, 1937, describes a projector for optically pro-
`ducing a variety of different map projections, including
`orthographic, stereographic and globular projections
`onto flat translucent screens and a variety of other pro-
`jections on shaped screens.
`U.S. Pat. No. 2,650,517, issued to Falk on Sept. 1,
`1953, describes a photographic method for making geo-
`graphical maps.
`U.S. Pat. No. 2,354,785, issued to Rohl on Aug. 1,
`1944, discloses two circular maps which are mounted
`side by side, and an arrangement for rotating the two
`maps in unison so that corresponding portions of the
`earth’s surface are at all times in proper relationship.
`U.S. Pat. No. 3,724,079, issued to Jasperson et al on
`Apr. 3, 1973, discloses a navigational chart display de-
`vice which is adapted to display a portion of a map and
`enable a pilot to fix his position, to plot courses and to
`measure distances.
`U.S. Pat. No. 2,431,847 issued to Van Dusen on Dec.
`2, 1947, discloses a projection arrangement, in which a
`portion of the surface of a spherical or curved map may
`be projected in exact scale and in exact proportional
`relationship.
`McBryde and Thomas, Equal Area Projections for
`World Statistical Maps, Special Publication No. 245,
`Coast & Geodetic Survey 1949.
`In addition to the above further teachings as to geo-
`graphical mapping can be found in the Elements of Car-
`tooraphy, 4th edition which was written by Arthur Rob-
`inson, Randall Sale and Joel Morrison, and published by
`John Wiley & Sons (1978).
`The present invention seeks to provide a low cost and
`efficient mapping system which allows the quick and
`easy manipulation of and access to an extraordinary
`amount of mapping information, i.e., a mapping system
`which allows a user to quickly and easily access a de-
`tailed map of any geographical area of the world.
`Map information can be stored using at least three
`different approaches,
`i.e., paper, analog storage and
`digital storage, each approach having its own advan-
`tages and disadvantages as detailed below.
`The paper mapping approach has been around since
`papyrus and will probably exist for the next thousand
`years.
`Advantages of paper storage:
`inexpensive.
`once printed, no further processing is required to
`access the map information, so not subject to processing
`breakdown.
`
`Disadvantages of paper storage:
`can become bulky and unwieldy when dealing with a
`large geographical area, or a large amount of maps.
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`4,972,319
`
`3
`paper does not have the processing capabilities or
`“intelligence” of computers, and therefore does not
`support automated search or data processing capabili-
`ties.
`
`cannot be updated cheaply and easily.
`The analog mapping approach is used to provide
`what is commonly known as videodisc maps. The infor-
`mation is stored as still frames under N.T.S.C. (National
`Television Standards Committee) conventions To
`make maps, a television camera moves across a paper
`map lying on a workbench. Every few inches a frame is
`recorded on videotape. After one row of the map is
`completely recorded, the camera is moved down to the
`next row of frames to be recorded. This process is re-
`peated until frames representing a checkerboard pattern
`of the entire map are recorded. The recorded videotape
`could be used to View the map: however, access time to
`scan to different areas of the recorded map is usually
`excessive. As a result, a videodisc, with its quicker ac-
`cess time, is typically used as the medium for analog
`map storage. The recorded videotape is sent to a pro-
`duction house which “stamps” out 8 inch or 12 inch
`diameter, videodiscs.
`Advantages of the analog storage approach:
`one side of a 12 inch videodisc can hold 54.000
`“frames” of a paper map. A frame is typically equal to
`2%)(3 inches of the paper map.
`access time to any frame can be fast usually under 5
`seconds.
`once located on the videodisc, the recorded analog
`map information will be used to control the raster scan
`of a monitor and to produce a reproduction of the map
`in 1/30th of a second.
`through additional hardware and software, mapping
`symbols, text and/or patterhsn can be overlaid on top of
`the recorded frame.
`Disadvantages of the analog storage approach:
`the “frames” are photographed from paper maps,
`which, as mentioned above, cannot be updated cheaply
`or easily.
`due to paper map projections, mechanical camera
`movements, lens distortions and analog recording elec—
`tronics, the videodisc image which is reproduced is not
`as accurate as the original paper map.
`as a result of the immediately above phenomena,
`latitude and longitude information which is extracted
`from the reproduced image cannot be fully trusted.
`if a major error is made in recording any one of the
`54,000 frames, it usually requires redoing and re-stamp-
`ing.
`since frames cannot be scrolled, most implementa-
`tions employ a 50% overlap technique. This allows the
`viewer to jump around the database with a degree of
`visual continuity: however, this is at a sacrifice of stor-
`age capacity. If the frame originally covered 2% X 3
`inches or approximately 8 square inches of the paper
`map,
`the redundant overlap information is 6 square
`inches, leaving only 2 square inches of new information
`in the centroid of each frame.
`as a result of the immediately above deficiency, a
`2X3 foot map containing 864
`square inches would
`require 432 frames; thus, only 125 paper maps could be
`stored on one side of a 12 inch videodisc.
`.
`must take hundreds of video screen dumps to make a
`hard copy of a map area of interest and, even then, the
`screens do not immediately splice together because of
`the overlap areas.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`the biggest disadvantage is that, since frames have to
`be arranged in a checkerboard fashion, there is no way
`to jump in directions other that north, south, east or
`west and maintain visual continuity. As an example, the
`visual discontinuity in viewing a “great circle” route
`from Alaska to New York would be unbearable for all
`but the most hearty.
`The digital mapping approach has been around for at
`least 20 years and is much more frequently used than the
`analog approach. Digital data bases are stored in com-
`puters in a format similar to text of other databases.
`Unlike map information on a videodisc, the outstanding
`map features are stored as a list of objects to be drawn,
`each object being defined by a plurality of vector “dot”
`coordinates which define the crude outline cf the ob-
`ject. As one example, a road is drawn by connecting a
`series of dots which were chosen to define the path (i.e.,
`the “outline”) of the road. Once drawn, further data and
`processing can be used to smooth the crude outline of
`the object, place text, such as the name or description of
`the object in a manner similar to what happens when
`drawing on a paper map.
`Advantages of the digital approach:
`digital maps are the purest form of geographical map-
`ping data: from them, paper and analog maps can be
`produced.
`'
`digital maps can be quickly and easily updated in near
`real-time, and this updating can be in response to data
`input from external sources (e. g., geographical monitor-
`ing devices such as satellite photography).
`digital maps can be easily modified to effect desirable
`mapping treatments such as uncluttering, enhancing,‘
`coloring, etc.
`digital maps can be easily and accurately scaled, ro-
`tated and drawn at any perspective view point.
`digital maps can be caused to reproduce maps in 3-D.
`digital maps can drive pen-plotters (for easy paper
`reproductions), robots, etc.
`digital maps can be stored on any mass storage de-
`vice.
`
`Disadvantages of the digital approach:
`digital maps require the use or creation of a digital
`database: this is a very time-consuming and expensive
`process, but once it is made, the data base can be very
`easily copied and used for many different projects.
`The digital approach is utilized with the present in-
`vention, as this approach provides overwhelming ad-
`vantages over the above-described paper and analog
`approaches.
`In designing any mapping system, several features are
`highly desirable:
`First, it is highly desirable that the mapping system be
`of low cost.
`Second, and probably most important, is access time.
`Not only is it generally desirable that the desired map
`section be accessible and displayed within a reasonable
`amount of time, but in some instances, this access time is
`critical.
`In addition to the above, the present invention (as
`mentioned above), seeks to provide a third important
`feature,——a mapping system which allows the manipula-
`tion of and access to an extraordinary amount of map-
`ping information, i.e., a mapping system which allows a
`user to quickly and easily access a detailed map of any
`geographical area of the world.
`A tremendous barrier is encountered in any attempt
`to provide this third feature. In utilizing the digital
`approach to map a large geographical area in detail
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`4,972,319
`
`6
`agencies. Prior art mapping systems have been deficient
`in this regard; hence, there still exists a need for such a
`mapping system.
`SUMMARY OF THE INVENTION
`
`5
`(e.g., the earth), one should be able to appreciate that
`the storage of mapping data sufficient to accurately
`define all the geographical features would represent a
`tremendous data base.
`While there have been digital mapping implementa~
`tions which have successfully been able to manipulate a
`tremendous data base, these implementations involve
`tremendous cost (i.e., for the operation and maintenance
`of massive mainframe computer and data storage facili-
`ties). Furthermore, there is much room for improve-
`ment in terms of access time as these mainframe imple-
`mentations result in access times which are only as
`quick as 20 seconds. Thus, there still exists a need for a
`low-cost digital mapping system which can allow the
`storage, manipulation and quick (i.e., “real time”) access
`and visual display of a desired map section from a tre-
`mendous mapping data base.
`There are several additional mapping system features
`which are attractive.
`It is highly desirable that a mapping system be sensi-
`tive to and compensate for distortions caused by map-
`ping curved geographical (i.e., earth) surfaces onto a
`flat,
`two-dimensional representation. While prior art
`approaches have provided numerous methods with
`varying degrees of success, there is a need for further
`improvements which are particularly applicable to the
`digital mapping system of the present invention.
`It is additionally attractive for a mapping system to
`easily allow a user to change his/her “relative viewing
`position”, and that in changing this relative position, the
`change in the map display should reflect a feeling of
`continuity. Note that the “relative viewing position
`should be able to be changed in a number of different
`ways. First, the mapping system should allow a user to
`selectively cause the map display to scroll or “fly”
`along the geographical map ’to view a different (i.e.,
`“lateral") position of the geographical map while main-
`taining the same degree of resolution as the starting
`position. Second, the mapping system should allow a
`user to selectively vary the size of the geographical area
`being displayed (i.e., “zoom”) while still maintaining an
`appropriate degree of resolution, i.e., allow a user to
`selectively zoom to a higher “relative viewing position”
`to view a larger geographical area with lower resolu-
`tion regarding geographical, political and cultural char-
`acteristics, or zoom to a lower “relative viewing posi-
`tion” to view a smaller geographical area with higher
`resolution.
`(Note that maintaining the appropriate
`amount of resolution is important to avoid map displays
`which are effectively barren or are cluttered with geo-
`graphical, political and cultural features.) Again, while
`prior art approaches have provided numerous methods
`with varying degrees of success, there is a need for
`further improvements which are particularly applicable
`to the digital mapping system of the present invention.
`The final feature concerns compatibility with existing
`mapping formats. As mentioned above, the creation of a
`digital database is a very tedious, time-consuming and
`expensive process. Tremendous bodies of mapping data
`are available from many important mapping authorities,
`for example, the U.S. Geological Survey (USGS), De-
`fense Mapping Agency (DMA), National Aeronautics
`and Space Administration (NASA), etc. In terms of
`both being able to easily utilize the mapping data pro-
`duced by these agencies, and represent an attractive
`mapping system to these mapping agencies, it would be
`highly desirable for a mapping system to be compatible
`with all of the mapping formats used by these respective
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`invention provides a digital mapping
`The present
`method and system of a unique implementation to sat-
`isfy the aforementioned needs.
`The present invention provides a computer imple-
`mented method and system for manipulating and ac-
`cessing digital mapping data in a tremendous data base,
`and for the reproduction and display of electronic dis-
`play maps which are representative of the geographical,
`political and cultural features of a selected geographical
`area. The system includes a digital computer, a mass
`storage device (optical or magnetic), a graphics moni-
`tor, a graphics controller, a pointing device, such as a
`mouse, and a unique approach for structuring, manag-
`ing, controlling and displaying the digital map data.
`The global map generating system organizes the map-
`ping data into a hierarchy of successive magnitudes or
`levels for presentation of the mapping data with vari-
`able resolution, starting from a first or highest magni~
`tude with lowest resolution and progressing to a last or
`lowest magnitude with highest resolution. The idea of
`this hierarchical structure can be likened to a pyramid
`with fewer stones or “tiles” at the top, and where each
`successive descending horizontal level or magnitude
`contains four times as many “tiles” as the level or mag-
`nitude directly above it. The top or first level of the
`pyramid contains 4 tiles, the second level contains 16
`tiles, the third contains 64 tiles and so on, such that the
`base of a 16 magnitude or level pyramid would contain
`4 to the 16th power or 4,294,967,296 tiles. This total
`includes “hyperspace” which is later clipped or ig-
`nored. Hyperspace is that excess imaginary space left
`over from mapping of 360 deg, space to a zero magni-
`tude virtual or imaginary space of 512 deg, square.
`A first object of the present invention is to provide a
`digital mapping method and system which are of low
`cost.
`
`A second and more important object of the present
`invention is to provide a unique digital mapping method
`and system which allow access to a display of the geo-
`graphical, political and cultural features of a selected
`geographical area within a minimum amount of time.
`A third object of the present invention is to provide a
`digital mapping method and system which allow the
`manipulation of and access to an extraordinary amount
`of mapping information,
`i.e., a mapping method and
`system which allow a user to quickly and easily access
`a detailed map of any geographical area of the world.
`Another object of the present invention is to provide
`a digital mapping method and system which recognize
`and compensate for distortion introduced by the repre-
`sentation of curved (i.e., earth) surfaces onto a flat two-
`dimensional display.
`Still a further object of the present invention is to
`provide a digital mapping method and system which
`allow a user to selectively change his/her “relative
`viewing position”, i.e., to cause the display monitor to
`scroll or “fly” to display a different “lateral” mapping
`position of the same resolution, and to cause the display
`monitor to “zoom” to a higher or lower position to
`display a greater or smaller geographical area, with an
`appropriate degree of resolution.
`A fifth object of the present invention is to provide a
`digital mapping method and system utilizing a unique
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`4,972,319
`
`7
`mapping graticule system which allows mapping data
`to be compatibly adopted from several widely utilized
`mapping graticule systems.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The foregoing and other objects, structures and fea-
`tures of the present invention will become more appar-
`ent from the following detailed description of the pre-
`ferred mode for carrying out the invention; in the de-
`scription to follow, reference will be made to the ac-
`companying drawings in which:
`FIG. 1 is an illustration corresponding to a flat pro-
`jection of the earth’s surface.
`FIG. 2 is an illustration of a digital computer and
`mass storage devices which can be utilized in imple-
`menting the present invention.
`FIGS. 3A—3F are illustrations of monitor displays
`showing the ability of the present invention to display
`varying sizes of geographical areas at varying degrees
`of resolution.
`FIG. 4 is a cross-sectional diagram of a simple build-
`ing example explaining the operation of the present
`invention.
`
`FIG. 5A and B are plan view representations of a
`paper 450 as it is viewed from the relative viewing
`position A shown in FIG. 4.
`FIG. 6 is a plan view representation of a paper 450 as
`it is viewed from the relative viewing position B shown
`in FIG. 4.
`FIG. 7 is a plan View representation of a paper 450 as
`it is viewed from the relative viewing position C shown
`in FIG. 4.
`
`FIG. 8 is a pyramidal hierarchy of the data base file
`structure showing an example of the ancestry which
`exits betWeen files.
`FIG. 9A is a plan view representation of a paper 450,
`with the paper being divided into a first level of quad-
`rant areas.
`
`FIG. 9B is an illustration of a monitor displaying a
`digital map of the area enclosed by the dashed portions
`in FIG. 9A.
`
`FIG. 10A is a plan view representation of a paper
`450, with the upper—left and lower-right paper quadrant
`areas being further divided into quadrants.
`FIG. 10B is an illustration of a monitor displaying a
`digital map of the area enclosed by the upper-left
`dashed portion in FIG. 10A.
`FIG. 11A is a plan view representation of a paper
`450, with several sections of the second level of quad-
`rants being further divided into additional quadrants.
`FIG. 11B is a higher resolution display of the area
`enclosed within the dashed portion in FIG. 11A.
`FIG. 12 is a plan view illustration of a quadrant area
`division, with a two-bit naming protocol being assigned
`to each of the quadrant areas.
`FIG. 13 is a pyramidal hierarchy of the data base files
`using the two-bit naming protocol of FIG. 12, and
`showing an example of the ancestry which exits be-
`tween files.
`FIG. 14 is a plan view illustration of a 360° X 180° flat
`projection of
`the earth being impressed in the
`512° X 512° mapping area of the present invention, with
`a first quadrant division dividing the mapping area into
`four equal 250°><256° mapping areas.
`FIG. 15 is the same plan view illustration of FIG. 14,
`with a second quadrant division dividing the mapping
`area into 16 equal 126°>< 128° mapping areas.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`8 1
`FIG. 16 is the same plan view illustration of FIG. 15,
`with a third quadrant division dividing the mapping
`area into 64 equal 64°><64° mapping areas.
`FIG. 17 is the same plan View illustration of FIG. 16,
`with a fourth quadrant division dividing the mapping
`area into 256 equal 32°><32° mapping, areas.
`FIG. 18 is the same plan view illustration of FIG. 17,
`with a fifth quadrant division dividing the mapping area
`into 1024 equal 16°X 16° mapping areas.
`FIG. 19 is the same plan view illustration of FIG. 18,
`with a sixth quadrant division dividing the mapping
`area into 4096 equal 8° >< 8° mapping areas.
`FIG. 20 is an illustration showing the application of
`polar compression at the 8th level or magnitude of reso-
`lution.
`‘
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS OF THE
`INVENTION
`
`Before turning to the detailed description of the pre—
`ferred embodiments of the invention, it should be noted
`that the map illustrations used throughout the drawings
`are only crude approximations which are only being
`used to illustrate important features and aspects and the
`operation of the present invention; therefore. the geo-
`graphical political and cultural outlines may very well
`differ from actual outlines.
`FIG. 1 is a crude representation of what the earth’s
`surface would look like if it Were laid flat and viewed
`from a “relative viewing position” which is a great
`distance in space. Shown as vertical lines are: 10, corre-
`sponding to the 0° meridian extending through Green-
`wich, England; 20, corresponding to the 180° west me-
`ridian: and, 30, corresponding to the 180° east meridian.
`Shown as horizontal lines are: 40, corresponding to the
`equator: 50, corresponding to 90° north (i.e.. the north
`pole): and 60, corresponding to 90° south (i.e.. the south
`pole).
`Note that at this “relative viewing position”, not
`much detail as to cultural features is seen; i.e., all that is
`seen is the general outline of the main geographical
`masses of the continents.
`The present invention seeks to provide a low cost and
`efficient computer-based mapping method and system
`having a unique approach for arranging and accessing a
`digital mapping database of unlimited size, i.e., a map-
`ping method and system which can manipulate and
`access a data base having sufficient data to allow the
`mapping system to reproduce digital maps of any geo-
`graphical area with different degrees of resolution. This
`can be most easily understood by viewing FIG. 2 and
`FIGS. 3A—F.
`Because of the overwhelming advantages over the
`paper and analog mapping approaches, the digital map-
`ping approach is utilized with the present invention;
`thus, there is shown in FIG. 2, a digital computer 200,
`having a disk or hard drive 280, a monitor 210, a key-
`board 220 (having a cursor control portion 230), and a
`mouse device 240. As mentioned previously, in a digital
`mapping approach, mapping information is stored in a
`format similar to the text of other databases, i.e., the
`outstanding map features are stored as a list of objects to
`be drawn, each object being defined by a plurality of
`vector “dot” coordinates which define the crude out-
`line of the object. (Note: the reproduction of a digital
`map from a list of objects and “dot” vectors is well
`known the art, and is not the subject matter of the pres-
`ent invention; instead, the invention relates to a unique
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`

`

`4,972,319 r
`
`10
`
`15
`
`35
`
`9
`method and system for storing and accessing the list of
`objects and “dot” vectors contained in a tremendous
`digital data base.)
`Once a geographical map has been “digitized”,—i.e.,
`converted to a list of objects to be drawn and a plurality 5
`of vector “dot” coordinate