`Delorme
`
`115
`
`[11] Patent Number:
`
`[45] Date of Patent:
`
`4,972,319
`Nov. 20, 1990
`
`(54] ELECTRONIC GLOBAL MAP GENERATING
`SYSTEM
`
`[76]
`
`Inventor: David M. Delorme, 356 Range Rd.,
`Cumberland, Me. 04021
`
`McBryde and Thomas, U.S. 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, CS oon esseeeeecenecreesesessonnes G09B 29/00
`(51)
`[52] US. Cy eessscsessssssesssssseneennee 364/419; 434/150;
`340/990
`(58] Field of Search ................ 364/419, 449; 434/150,
`434/130; 340/990
`
`Primary Examiner—Jerry Smith
`Assistant Examiner—Kim T. Bui
`Attorney, Agent, or Firm—Sughrue, Mion, Zinn,
`Macpeak & Seas
`
`ABSTRACT
`[57]
`A global mapping system which organizes mapping
`data into a hierarchy of successive magnitudesor levels
`References Cited
`[56]
`for presentation of the mapping data with variable reso-
`lution, starting fromafirst or highest magnitude with
`U.S. PATENT DOCUMENTS
`lowest resolution and progressing to a last or lowest
`400,642 4/1889 Beaumont ...........ccsssssessesecseee 283/34
`magnitude with highest resolution. The idea of this
`751,226 10/1899 Van Der Grinten .
`sane 283/34
`hierarchical structure can be likened to a pyramid with
`752,957 2/1904
`eee 283/34
`fewer stones or “tiles” at the top, and where each suc-
`1,050,596
`1/1913
`we 283/34
`cessive descending horizontal level or magnitude con-
`1,610,413 12/1924
`.. 283/34
`2,094,543 9/1937
`tains four times as many “tiles” as the level or magni-
`2,354,785
`8/1944
`tude directly above it. The top or first level of the
`2,431,847 12/1947
`pyramid contains 4 tiles, the second levle contains 16
`2,650,517 9/1953
`tiles, the third contains 64 tiles and so on, such that the
`3,248,806 5/1966
`base of a 16 magnitudeor level pyramid would contain
`3,724,079 4/1973
`....
`4 to the 16th power or 4,294,967,296 tiles. This total
`4,315,747 2/1982 McBryde ........sessseecereee 434/150
`includes “hyperspace” which is later clipped or ig-
`4,673,197 6/1987 Stipelman etal................0. 434/150
`nored. Digital data corresponding to each of the sepa-
`4,689,747 .8/1987 Krouse et al... 364/449
`rate data base tiles is stored in the database under a
`4,737,927 4/1988 Hanabusa etal................... 340/990
`unique filename.
`
` Jaspersonet al.
`
`OTHER PUBLICATIONS
`
`‘Equal-Area Projections for World Statistical Maps”,
`
`33 Claims, 9 Drawing Sheets
`
`300%
`
`1320
`
`LAAANAVACN
`
`(VVVVAAAS \\
`1330
`CELLET
`
`
`PiWEEE
`LN
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`
`US. Patent—Nov.20, 1990 Sheet 1 of 9 4,972,319
`
`
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`US. Patent—Nov.20, 1990 Sheet 2 of 9 4,972,319
`
`
`FIG.3A
`
`
`
`—_FIG.3B
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`Sheet 30f9
`
`4,972,319
`
`US. Patent Nov. 20, 1990
`
`FIG.5A
`
`FIG.58
`
`
`
`
`q See
`s a+P]||Sete
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`
`US. Patent—Nov.20, 1990 Sheet 4 of 9 4,972,319
`
`
`
`Nelenaea
`
`\mes\aaal\|AYAACA
`
`
`VietANS
`
`
` FIG.10B
`
`oO
`“1 Oo
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`
`US. Patent—Nov. 20, 1990 Sheet 5 of 9 4,972,319
`
`
`
`FIG.12
`[240 00|10 1210
`1300,
`
`0
`1230 Foi|a|1220
`
`FIG.AIA
`
`FG 118
`
` |
`
`
`
`SLTAANA
`PARAS
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`
`US.Patent—Nov. 20, 1990 Sheet 60f9 4,972,319
`
`
`
`256°
`
`256°
`
`,
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`
`US.Patent—Nov.20, 1990 Sheet 7 of 9 4,972,319
`
`
`
`
`
`
`
`
`FIG 17
`
`
` PE
`ptttetTEEEE
`
`PtTteTeetey
`
`
`COEeee
`eela0?
`
`
`
`
`PAATeeer
`TSSSAL[Toe||e
`COCNSe
`
`
`COCCICes
`
`EEEie
`
`
`
`
` 256°
`
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`US. Patent—Nov. 20, 1990 Sheet 8 of 9 4,972,319
`
`
`256°
`0°
`
`
`
`CC SS
`SOOOA
`Pityich “is
`Preityye
`
`0°
`
`256°
`
`0°
`
`256°
`
`FIG.I9
`
`256° FIG .18
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`oo LH 256°
`
`H
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`
`US. Patent—Nov. 20, 1990 Sheet9 of 9
`4,972,319
`IG.20
`ILLUSTRATION OF POLAR COMPRESSION
`AT THE 8th MAGNITUDE
`
`90
`
`ae
`
`\ioyHH,
`elit
`x a: tt
`
`STllneta
`
`May ~ “~ ~~ ~ ~
`
`.
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`1
`
`4,972,319
`
`ELECTRONIC GLOBAL MAP GENERATING
`SYSTEM
`
`BACKGROUNDOF THE INVENTION
`
`5
`
`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 knownas 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 fusiform 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 mapare represented bya flat polar
`equal area projection in which the poles are depicted as
`straight horizontal lines with the ineridians intersecting
`along its length. Thus, in a flat polar projection the
`meridian curves converge toward the poles but do not
`meetat 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 wherethe 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 beeitherstraight 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 Mercatoror 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 shapeis
`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 mapofthe
`entire world is plotted or transcribed on an oval con-
`structed from two adjacentside 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 twointersecting
`
`15
`
`39
`
`35
`
`40
`
`45
`
`30
`
`65
`
`.
`
`2
`spheres, on which the coordinate lines of latitude and
`longitudeareall 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 segmentrep-
`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 properrelationship.
`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 aroundsince
`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
`
`25
`
`30
`
`35
`
`4
`3
`the biggest disadvantage is that, since frames have to
`paper does not have the processing capabilities or
`be arranged in a checkerboard fashion, there is no way
`“intelligence” of computers, and therefore does not
`to jump in directions other that north, south, east or
`support automated search or data processing capabili-
`ties.
`west and maintain visual continuity. As an example, the
`visual discontinuity in viewing a “great circle” route
`cannot be updated cheaply and easily.
`from Alaska to New York would be unbearable forall
`The analog mapping approach is used to provide
`but the most hearty.
`what is commonly knownas videodisc maps. Theinfor-
`The digital mapping approach has been aroundforat
`mationis storedas still frames under N.T.S.C. (National
`least 20 years and is much morefrequently used than the
`Television Standards Committee) conventions. To
`analog approach. Digital data bases are stored in com-
`make maps, a television camera moves across a paper
`puters in a format similar to text of other databases.
`maplying on a workbench. Every few inches a frameis
`Unlike map information on a videodisc, the outstanding
`recorded on videotape. After one row of the map is
`map featuresare stored asalist of objects to be drawn,
`completely recorded, the camera is moved downto the
`each object being defined by a plurality of vector “dot”
`next row of frames to be recorded. This process is re-
`coordinates which define the crude outline of the ob-
`peated until frames representing a checkerboard pattern
`ject. As one example, a road is drawn by connecting a
`of the entire map are recorded. The recorded videotape
`series of dots which were chosento define the path (ie.,
`could be used to view the map: however, access time to
`the “outline’’) of the road. Once drawn, further data and
`scan to different areas of the recorded mapis usually
`processing can be used to smooth the crude outline of
`excessive. As a result, a videodisc, with its quicker ac-
`the object, place text, such as the nameor description of
`cess time, is typically used as the medium for analog
`the object in a manner similar to what happens when
`map storage. The recorded videotape is sent to a pro-
`drawing on a paper map.
`duction house which “stamps” out 8 inch or 12 inch
`Advantages of the digital approach:
`diameter, videodiscs.
`digital maps are the purest form of geographical map-
`Advantages of the analog storage approach:
`ping data: from them, paper and analog maps can be
`one side of a 12 inch videodisc can hold 54.000
`produced.
`‘
`“frames” of a paper map. A frameis typically equal to
`digital maps can be quickly and easily updated in near
`24 X3 inches of the paper map.
`real-time, and this updating can be in response to data
`access time to any frame can befast usually under 5
`input from external sources(e.g., geographical monitor-
`seconds.
`ing devices suchassatellite photography).
`once located on the videodisc, the recorded analog
`digital maps can be easily modified to effect desirable
`map information will be used to control the raster scan
`mapping treatments such as uncluttering, enhancing,:
`of a monitor and to produce a reproduction of the map
`coloring, etc.
`in 1/30th of a second.
`digital maps can be easily and accurately scaled, ro-
`through additional hardware and software, mapping
`tated and drawn at any perspective view point.
`symbols, text and/or patterhsn can be overlaid on top of
`digital maps can be caused to reproduce mapsin 3-D.
`the recorded frame.
`digital maps can drive pen-plotters (for easy paper
`Disadvantages of the analog storage approach:
`reproductions), robots, etc.
`the “frames” are photographed from paper maps,
`digital maps can be stored on any mass storage de-
`vice.
`which, as mentioned above, cannot be updated cheaply
`or easily.
`Disadvantagesof the digital approach:
`due to paper map projections, mechanical camera
`digital maps require the use or creation of a digital
`movements, lens distortions and analog recording elec-
`database: this is a very time-consuming and expensive
`tronics, the videodisc image which is reproduced is not
`process, but onceit is made, the data base can be very
`as accurate as the original paper map.
`easily copied and used for manydifferent projects.
`as a result of the immediately above phenomena,
`The digital approachis utilized with the present in-
`latitude and longitude information which is extracted
`vention, as this approach provides overwhelming ad-
`from the reproduced image cannot be fully trusted.
`vantages over the above-described paper and analog
`if a major error is made in recording any one ofthe
`approaches.
`54,000 frames, it usually requires redoing and re-stamp-
`In designing any mapping system,several features are
`ing.
`highly desirable:
`since frames cannot be scrolled, most implementa-
`First, it is highly desirable that the mapping system be
`of low cost.
`tions employ a 50% overlap technique. This allows the
`viewer to jump around the database with a degree of
`Second, and probably most important, is access time.
`visual continuity: however, this is at a sacrifice of stor-
`Not only is it generally desirable that the desired map
`age capacity. If the frame originally covered 243
`section be accessible and displayed within a reasonable
`inches or approximately 8 square inches of the paper
`amountof time, but in someinstances, this access time is
`critical.
`map,
`the redundant overlap information is 6 square
`inches, leaving only 2 square inches of new information
`In addition to the above, the present invention (as
`in the centroid of each frame.
`mentioned above), seeks to provide a third important
`as a result of the immediately above deficiency, a
`feature,—a mapping system which allows the manipula-
`2X3 foot map containing 864
`square inches would
`tion of and access to an extraordinary amount of map-
`require 432 frames; thus, only 125 paper maps could be
`ping information,i.e., a mapping system which allows a
`stored on oneside of a 12 inch videodisc.
`;
`user to quickly and easily access a detailed map of any
`must take hundreds of video screen dumps to make a
`geographical area of the world.
`hard copy of a maparea of interest and, even then, the
`A tremendous barrier is encountered in any attempt
`screens do not immediately splice together because of
`to provide this third feature. In utilizing the digital
`approach to map a large geographical area in detail
`the overlap areas.
`
`40
`
`45
`
`50
`
`55
`
`65
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`4,972,319
`
`6
`agencies. Prior art mapping systems havebeen deficient
`in this regard; hence,therestill exists a need for such a
`mapping system.
`SUMMARYOF 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 storagefacili-
`ties). Furthermore, there is much room for improve-
`mentin 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.
`Thereare 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 changehis/her “relative viewing
`position”, and that in changingthis 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 numberofdifferent
`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 stil] 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
`amountofresolution 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 whichare particularly applicable
`to the digital mapping system of the present invention.
`Thefinal 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 abie 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
`
`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 tremendousdata 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 oftime.
`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.
`Anotherobject 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, andto 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
`
`20
`
`25
`
`30
`
`40
`
`45
`
`55
`
`60
`
`65
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`7
`mapping graticule system which allows mapping data
`to be compatibly adopted from several widely utilized
`mapping graticule systems.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4,972,319
`
`8 +
`FIG.16 is the same plan view illustration of FIG.15,
`with a third quadrant division dividing the mapping
`area into 64 equal 64° x 64° mappingareas.
`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° mappingareas.
`FIG.18 is the same plan view illustration of FIG. 17,
`with a fifth quadrant division dividing the mapping area
`into 1024 equal 16° 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 compressionat the 8th level or magnitude of reso-
`lution.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS OF THE
`INVENTION
`
`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 modefor 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 areillustrations of monitor displays
`showing the ability of the present invention to display
`varying sizes of geographical areas at varying degrees
`Before turning to the detailed description of the pre-
`of resolution.
`ferred embodimentsof the invention, it should be noted
`FIG.4 is a cross-sectional diagram of a simple build-
`that the mapillustrations used throughout the drawings
`ing example explaining the operation of the present
`are only crude approximations which are only being
`invention.
`used toillustrate important features and aspects and the
`FIG. 5A and B are plan view representations of a
`operation of the present invention; therefore. the geo-
`paper 450 as it is viewed from the relative viewing
`graphical political and cultural outlines may very well
`position A shownin FIG.4.
`differ from actual outlines.
`FIG.6 is a plan view representation of a paper 450 as
`FIG.1 is a crude representation of what the earth’s
`it is viewed from the relative viewing position B shown
`surface would looklike if it were laid flat and viewed
`in FIG.4.
`from a “relative viewing position” which is a great
`FIG.7 is a plan view representation of a paper 450 as
`distance in space. Shownas verticallines are: 10, corre-
`it is viewed from the relative viewing position C shown
`sponding to the 0° meridian extending through Green-
`in FIG.4.
`wich, England; 20, corresponding to the 180° west me-
`FIG.8 is a pyramidal hierarchy of the data basefile
`ridian: and, 30, corresponding to the 180° east meridian.
`structure showing an example of the ancestry which
`Shownashorizontal lines are: 40, corresponding to the
`exits between files.
`equator: 50, corresponding to 90° north (i.e.. the north
`FIG.9Ais a plan view representation of a paper 450,
`pole): and 60, corresponding to 90° south (.e.. the south
`with the paper being divided into a first level of quad-
`pole).
`rant areas.
`Note that at this “relative viewing position”, not
`FIG. 9B is an illustration of a monitor displaying a
`muchdetail as to cultural features is seen; i.e., all that is
`digital map of the area enclosed by the dashed portions
`seen is the general outline of the main geographical
`in FIG. 9A.
`masses of the continents.
`FIG. 10A is a plan view representation of a paper
`The present invention seeks to provide a low cost and
`450, with the upper-left and lower-right paper quadrant
`efficient computer-based mapping method and system
`areas being further divided into quadrants.
`having a unique approachfor arranging and accessing a
`FIG.10Bis an illustration of a monitor displaying a
`digital mapping database of unlimited size, i.e., a map-
`digital map of the area enclosed by the upper-left
`ping method and system which can manipulate and
`dashed portion in FIG. 10A.
`access a data base having sufficient data to allow the
`FIG. 11A is a plan view representation of a paper
`mapping system to reproduce digital maps of any geo-
`450, with several sections of the second level of quad-
`graphical area with different degrees of resolution. This
`rants being further divided into additional quadrants.
`can be most easily understood by viewing FIG. 2 and
`FIGS. 3A-F.
`FIG. 11B is a higher resolution display of the area
`enclosed within the dashed portion in FIG. 11A.
`Because of the overwhelming advantages over the
`FIG.12 is a plan view illustration of a quadrant area
`paper and analog mapping approaches,the digital map-
`division, with a two-bit naming protocol being assigned
`ping approach is utilized with the present invention;
`to each of the quadrant areas.
`thus, there is shown in FIG.2, a digital computer 200,
`FIG.13 is a pyramidal hierarchyof the data basefiles
`having a disk or hard drive 280, a monitor 210, a key-
`using the two-bit naming protocol of FIG. 12, and
`board 220 (having a cursor control portion 230), and a
`showing an example of the ancestry which exits be-
`mouse device 240. As mentioned previously, in a digital
`tweenfiles.
`mapping approach, mapping information is stored in a
`FIG.14is a plan viewillustration of a 360° x 180° flat
`format similar to the text of other databases, i.e., the
`projection of
`the earth being impressed in the
`outstanding map features are stored asa list of objects to
`512° 512° mapping area of the present invention, with
`be drawn, each object being defined by a plurality of
`vector “dot” coordinates which define the crude out-
`a first quadrant division dividing the mapping area into
`65
`four equal 250° X 256° mapping areas.
`line of the object. (Note: the reproduction ofa digital
`FIG.15 is the same plan view illustration of FIG.14,
`map fromalist of objects and “dot” vectors is well
`knowntheart, and is not the subject matter of the pres-
`with a second quadrant division dividing the mapping
`ent invention; instead, the invention relates to a unique
`area into 16 equal 126° 128° mapping areas.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`35
`
`Microsoft Corp. Exhibit 1065
`
`Microsoft Corp. Exhibit 1065
`
`
`
`4,972,319 |
`
`20
`
`25
`
`30
`
`9
`10
`method and system for storing and accessing thelist of
`and features, it should be further appreciated that the
`objects and “dot” vectors contained in a tremendous
`present invention is by no meanslimited to this degree
`digital data base.)
`of resolution. In fact, the degree of resolution capable
`Once a geographical map has been “digitized”,—i.e.,
`with the present invention will be shown to be limited
`converted to a list of objects to be drawn andaplurality
`only by the operating system of the digital computer
`of vector “dot” coordinates which define the crude
`200 with which the present invention is used. In one
`outline of the object —, the mapping database must be
`demonstration, the monitor display has been shown to
`be able to zoom to resolution where the outlines of
`stored in the memory of a mass storage device. Thus,
`the digital computer 200, which is to be used with the
`streets were displayed. Even further degrees of resolu-
`mapping method and system of the the present inven-
`tion are possible as will be more fully understood after
`the discussions below.
`tion, is shown associated with the magnetic disk 260
`(which represents any well-known magnetic mass stor-
`In digitally mapping a large geographicalarea (e.g.,
`age medium, e.g., floppy disks, hard disks. magnetic
`the earth) in detail, —especially in the degree of resolu-
`tion mentioned above —, one should be able to appreci-
`tape, etc.), and the CD-ROM 270 (which represents any
`well-known optical storage medium, e.g. a laser-read
`ate that the storage of digital mapping datasufficient to
`compact disk). Alternatively, the digital mapping data-
`accurately define all
`the geographical, political and
`base can be stored on, and the digital computer can be
`cultural features would represent a tremendousdigital
`associate