Note: Descriptions are shown in the official language in which they were submitted.
CA 02436312 2003-08-O1
CLOSE-PACKED, UNIFORMLY ADJACENT,
MULTIRESOLUTIONAL, OVERLAPPING SPATIAL DATA
ORDERING
FIELD OF THE INVENTION
The invention refers generally to methods and digital information systems that
represent visual images of planar or near planar space. More particularly, the
methods
and systems pertain to images that are referenced to earth.
BACKGROUND OF THE INVENTION
References
US Patents: 4691291 Sep., 1987 Wolfram 364/717.
US Patents: 4809202 Feb., 1989 Wolfram 364/578.
Gibson, Laurie and Dean Lucas, "Spatial Data Processing Using Generalized
Balanced
Ternary ", Proceedings of the IEEE Computer Society Conference on Pattern
Recognition
and Image Processing, June 1982, p. 566-571
Koch, Niels Fabian Helge von, Une methode geometrique elementaire pour (etude
de
certaines questions de la theorie des courbes plane, 1904
Panu, U.S. and P.R. Peterson (1990): "Runoff Hydrographs by Hexagon Grid
Method"
Proceedings of the CSCE Annual Confe~°ence, Vol. V, pages 341-358.
Sahr, Kevin and Denis White, "Discrete Global Grid Systems", Computing Science
and
Statistics, 30, ed. S. Weisberg, Interface Foundation of North America, Inc.,
Farfax
Station, VA. 1998
Snyder, J. P. (1992). "An equal-area map projection for polyhedral globes."
Cartographica 29(1): 10-21.
1
' CA 02436312 2003-08-O1
Description of Prior Art
5'torir~g Images as Discrete Grids
A common method of representing spatial information in a digital device is the
division of space into a tessellation of discrete cells. Exaamples include
raster images and
pixel based visual devices. F',aster images are visual references to data in
the form of
"dots"-typically arranged in an array of rows and columns, along with an
attribute of that
dot-usually a number representing a sensor's spectral value.
Vector images are interpretations of spatial features using geometric shapes
described mathematically with coordinates. Identification of point locations,
the basic
unit of vector mathematics, is often based on the rectangular Cartesian grid.
Regular rectangular grids are commonly usf;d due to their immediate
transformation into simplified matrix or array operations, their compatibility
with well-
understood planar Euclidean geometry, and the prevalence of cardinal
directions in
mimetic spatial thought.
What is a Geographic Ihformatioh System?
A Geographic Information System [GIS] is a computer application that provides
for the creation, storage, visuali~.zation and analysis of georeferenced
spatial information.
A GIS can be raster or vector based. In a GIS, spatial references are made to
geographic
locations on the earth surface. This reference location is further enhanced
with descriptive
information regarding the feature or area it represents. Georeferenced spatial
infornlation
encompasses elements familiar to those using paper maps-such as roads and
contours and
place names, but also includes any data with a physical location description-
like street
addresses, cadastral boundaries and geographic coordinates and can include
space and
airborne imagery. Almost all data can contain geospatial elements.
2
CA 02436312 2003-08-O1
Same Geographic Information Systems incorporate 3-dimensions with a Digital
Elevation Model, a speciali:aed form of geospatial vector data that describes
the 3-
dimensions of a terrain and heights on features. A Discrete Global Grid System
is a type
of GIS that provides a tessellations of uniform cells placed over the earth as
a reference to
~ location and area of influence.
Hexagon Grids
Hexagon cells are documented as the preferred shape for many gridding
applications. A hexagonal grid is the most efficient method of dividing planar
space into
regions of equal area with the least total perimeter. For a given distance
between the
center of a polygon and its farthest perimeter points, the hexagon has the
largest area of
the three possible uniform cell grids, rectangle, triangle and hexagon. The
hexagon grid
provides a symmetric cell structure such that all adjacent cells are
equidistant to 6 edge
neighbours. Hexagons provide the peak efficiency for spatial data storage.
Hexagon
lattices have been shown to provide excellent modeling characteristics.
Indexing systems have been proposed for transposing spatial imagery on hexagon
grids, notably Generalized Balanced Ternary of Gibson and i,ucas. Hexagons can
be
used to define geographic location. Sahr, et. al. proposed a Discrete Global
Grid System
called the Ieosahedron Snyder Equal Area Aperture 3 Hexagon Grid as an
alternative to
rectangular graticule of latitudes and longitudes based on a projection from
the
icosahedron to the spheroid proposed by John Snyder.
Hexagon grids have been overlooked in many applications due to their
nonconformance, by definition, to rectangular gridding and the utility of
accompanying
rectangular mathematics as well as their inability to aggregate completely
into larger, or
3
CA 02436312 2003-08-O1
disaggregate completely into smaller, self similar cells in hierarchal B-Tree
divisions
such as the Quad Tree for rectangular and the Quaternary Ternary Mesh for
triangles.
Addressing with Hierarchal Ji:dices
On-Line Analytical Processing is a term used to define ;systems that promote
fast
analysis of shared multidimensional information. Prior art in the development
of
relational and spatial database place heavy reliance on balanced hierarchal
indexing for
efficient data search and retrieval. In rectangular coordinate systems
hierarchies are not
apparent.
Spatial Transformations
Spatial analysis, data fusion and modeling represent sophistication in
information
systems called transformations. In a Geographic Information System, spatial
analysis is
generally based on ideas of proximity, networks and neighbours along with
standard data
analysis techniques such as correlative analysis. Analytical transforms tend
to cut the
data in several ways to facilitate interpretation.
Data fusion has many definitions. Generally, it can be held to mean the
creation
or enhancement of georeferenced attributes based on the combination of two or
more
attributes. An example would be the use of high-resolution satellite imagery
to enhance
the values of low-resolution mufti-spectral satellite imagery..
Spatial modeling provides a means of predicting outcomes based on known
behaviors and the presence of specified factors. Modeling uses known behaviors
to
extrapolate or simulate possible outcomes. Finite difference methods can
utilize
standardized meshes to route partial differential equations to predict weather
patterns.
Cellular automata require simple rules and cell boundaries to predict future
behaviors and
patterns as demonstrated by Johrr Conway in his cellular automata discovery:
"the game
4
a CA 02436312 2003-08-O1
of Life". A practical use the hexagon grid as a framework to complete
environmental
systems modeling is introduced by L'.S. Panu et. al. in their gridded runoff
model.
Stephen Wolfram has shown the successful use of hexagon meshes for using
cellular automata to simulate systems described by partial differential
equations such as
those that describe the flow of fluid, diffusion or heat transfer.
Oh Deanas~d Oh-line Data ~'rahsmissi~da
Information systems .are ideally utilized when the data is available to the
maximum number of users. Earth observation systems proliferate global data
sets. On-
line on-demand data systems that promote file sharing can be used in a GIS
environment.
Means of storage, retrieval, searching and fording the data is necessary to
maximize data
utility. Peer-to-peer file sharing and data discovery applications are well
known in prior
art. Such systems require a client to search repositories of data describing
the address of
server and content of data files. When the search criteria are met, the
address of the
server where the data is stored is returned.
Since these data sets can be large, development of .data compression, peer-to-
peer
file sharing and grid computing application that provide opportunities for
efficient file
transfer and shared processing is beneficial. Progressive transmission and
continuous
transmission are useful ways of selectively transmitting data..
Current Situation ahd Present Need
The planet earth is a dynamic sphere containing interrelationships of
environmental systems: an arrangement of geophysical, meteorological and
biological
activity. Within these natural systems, we create divisions of human interest:
artificial
boundaries of geopolitical, functional or demographic areas, and natural
boundaries such
as watersheds or resource delineations. Also, human assets or infrastructure
like roads,
5
CA 02436312 2003-08-O1
buildings, sewers and landfill sites, serve as detailed areas of interest
within human
biological habitat.
Many areas of spatial understanding such as epidemiology, resource management
and biodiversity would improve with the availability of detailed geospatial
data at
multiple resolutions coupled with the behavioral understandings of stochastic
methods to
provide semi-deterministic modeling.
As space, airborne and ground-based sensors increase in number and
sophistication; there is a rapid, and potentially unlimited, growth of global
information
characterizing these environmental systems. There is a corresponding demand
for an
effective and practical way of handling these diverse and increasingly large,
spatial data
sets.
Typically Geographic Information Systems reference data to flat maps by
projecting geographic coordinates to a regular rectangular grid. The
distortion that results
from referencing the geodesic sphere onto a projected regular grid map, like
the Mercator
Projection, is a characteristic that school children are familiar with. A
similar condition
produces significant difficulties in global geospatial data storage.
Traditional geographic
coordinate systems, latitude and longitude, do not form uniform cells and
therefore are
not idealized for use where uniformity of cells is assumed or is beneficial.
Merging geospatial information of disparate sources, accuracies, precision >,
and
formats is complex. Unlike textual or fielded data, spatial temporal data
requires a
common spatial reference and significant background or rneta-data to
facilitate cut and
paste, overlay and mosaic operations. Solving the problem of integrating data
requires an
idealized common reference model. As raster, vector and digital elevation
models rely on
6
CA 02436312 2003-08-O1
a regular grid, a standard grid would serve as a framework for the compilation
and
enhancement of all geospatial information.
To access global data, an idealized model of the earth would best approximate
it,
as it is, an irregular spheroid. This idealized model would allow
characteristics of the
earth at any point in time and :at any location to be observed. An infinite
resolution of
uniform discrete cells provides ~ mechanism to build such a data model. A
digital version
of the globe as a visualization application could show the world in a space
view and, as
the user rotates the globe and zooms in to a specific point of interest, the
spatial data that
it represents would confer the curvature of the surface onto the computer
monitor in
increasing detail.
The invention disclosed provides such application.
SUMMARY OF THE II~IVEI~TT~OhT
As described more fully below, an object of the invention is to provide for an
efficient method of mapping two-dimensional spatially organized data to the
one-
dimensional linear space of a computer storage medium using an assignment of
spatial
attributes to a cellular tessellation. The linear indexing provides a
hierarchical data
structure for close-packed, uniformly adjacent, multiresolutional, overlapping
cells. The
method promotes the hexagon grid as a practical alternative to rectangular
grid use in a
digital computer environment.
According to one aspect of the invention there is provided a method for
storing
two-dimensional spatially organized data in one-dimensional space on a
computer storage
medium by mapping the attributes of continuous state planar space to a multi-
resolutional
tessellation of close-packed uniform cells, each cell being uniquely
identified with a
7
CA 02436312 2003-08-O1
sequential number whereas the number includes the identification of a parent
cell, the
parent cell encompassing a cluster of child cells in a spatial hierarchy of
specific order
thereby identification of neighbour cells and child cells comprising the
requirements:
1. Spatial attributes are assigned to a parent cell, whose centroid represents
its
location and the voronoi region created by the boundary with adjacent parent
centroids forming the closed area for which the properties of the cell are
represented;
2. A parent cell for which the centroid location is not a centroid location
for any
lower resolution cells defines the location of a single new child cell of the
next
highest resolution; alternatively,
3. A parent cell for which its centroid location is also a centroid location
for any
lower resolution cells defines the location of a single new child cell of the
next
highest resolution and multiple new child cells of the next highest
resolution, one
located at each of the vertices of the parent's boundary edge;
whereby during initial conditions, a parent cell will be assigned a general
hexagon shape
or the shape of the plane for which it represents, with a starting centroid
location that can
be considered the planar origin.
Embodiments of the invention include an on-line Discrete Global Grid System
featuring hexagon gridded data for efficient computational storage, retrieval,
integration,
transmission, visual display, analysis, fusion, and modeling.
BRIEF DESCRIPTION ~F'TIIE DRAWINGS
FIG. 1 illustrates an apparatus and operating environment in conjunction with
which
embodiments of the invention may be practiced.
8
CA 02436312 2003-08-O1
FIG. 2 illustrates prior art methods of locating spatial information on a
rectangular grid.
FIG. 3 Illustrates an alternative planar location scheme called the PYXIS
plane whereas
the points are closely packed.
FIG. 4a, 4b, 4c, 4d, 4e and 4f illustrate exemplary ordering; of the clustered
child cells.
FIG. Sa, Sb, Sc, ~d, Se and 5f illustrate six successive resolutions of the
PYXIS indexing
using a simple ordering.
FIG. 6a and 6b illustrate hierarchal views of the PYXIS indexing.
FIG. 7 illustrates an exemplary procedure with addition table for identifying
nearest
neighbour cells on the PYXIS plane.
FIG. 8 illustrates an exemplary procedure for identifying a PYXIS point as
spatial
contained, overlapping or excluded, from a specific cell area.
FIG. 9a, 9b, 9c, 9d, 9e and 9f illustrate an exemplary method for establishing
and
referencing multiresolutional close-packed cells on the earth spheroid by
projecting the
PYXIS plane from an icosahedron.
FIG. 10 is an illustration of the components of a Discrete Global Grid System.
FIG. 11 is an illustration of procedure for determining Point inclusion in
Cell.
DETAILED DESCRIPTION OF TIIE PREFERRED EMBODIMENT
Apparatus and Operating Ene~iron'nent
FIG. 1 is a diagram of the apparatus and operating environment in conjunction
with which embodiments of the invention may be practiced. The description of
FIG. 1 is
intended to provide a brief, general description of suitable computer
apparatus in
9
CA 02436312 2003-08-O1
conjunction with which the invention may be implemented. The computer, in
conjunction with which embodiments of the invention may be practiced, may be a
conventional computer, a distri'~uted computer, an embedded computer or any
other type
of computer; the invention is not so limited. Such a computer typically
includes one or
more processing units as its processor, and a computer-readable medium such as
a
memory. The computer may also include a communications device such as a
network
adapter or a modem, so that it is able to communicatively couple other
computers.
Although not required, the invention is described in the general context of
computer-executable instructions being executed by a computer. Generally,
program
modules include routines, programs, objects, components, data structures, etc.
that
perform particular tasks or implement particular abstract data types.
Moreover, those skilled in the art will appreciate that the invention rnay be
practiced with other computer system configurations, including hand-held
devices,
multiprocessor systems, microprocessor-based or programmable consumer
electronics,
network PCS, minicomputers, mainframe computers, and the like. 'The invention
may
also be practiced in distributed computing environments where tasks are
performed by
remote processing devices that are linked through a communications networlc.
In a
distributed computing enviromnent, program modules may be located in both
local and
remote memory storage devices.
The exemplary hardware and operating environment of FIG. 1 for implementing
the invention includes a general purpose computing device in the form of a
computer 1,
including a processing unit 2, a system memory 3, and a system bus 4 that
operatively
couples various system components, including the systenn memory 3, to the
processing
unit 2. There may be only one or there may be more than o:ne processing unit
2.
CA 02436312 2003-08-O1
The system bus 4 may be any of several types of bus structures including a
memory bus or memory controller, a peripheral bus, and a local bus using any
of a variety
of bus architectures. The system memory 3 includes read only memory ~ and
random
access memory 6. A basic input/output system (BIOS) 7, containing the basic
routines
that help to transfer information between elements within the computer 1, such
as during
start-up, is stored in random access memory 6. The computer 1 further includes
a hard
disk drive 8, a magnetic disk drive 9 and an optical disk drive 10, as memory
storage
devices.
The hard disk drive 8, magnetic disk drive 9, and optical disk drive 10 are
connected to the system bus 4 by a hard disk drive interface 11., a magnetic
disk drive
interface 12, and an optical di sk drive interface 13, rest>ectively. The
drives and their
associated computer-readable :media provide nonvolatile storage of computer-
readable
instructions, data structures, program modules and other data for the computer
1. It should
be appreciated by those skilled in the art that any type of computer-readable
media. whieh
can store data that is accessible by a computer, such as magnetic cassettes,
flash memory
cards, digital video disks, Bernoulli cartridges, random access memories
(RAMS), read
only memories (ROMs), and the like, may be used in the exemplary operating
environment.
A user may enter commands and information into the personal computer 1
through input devices such as a keyboard 14 and mouse; 15. Other input devices
(not
shown) may include a microphone, joystick, game pad, satellite dish, scanner,
or the like.
These and other input devices are often connected to the processing unit 2
through a serial
port interface 16 that is coupled to the System bus, but may be connected by
other
interfaces, such as a parallel port, game port, or a universal serial bus
(USB). A monitor
17 or other type of display device is also connected to the system bus 4 via
an interface,
11
CA 02436312 2003-08-O1
such as a video adapter 18. In addition to the monitor, computers typically
include other
peripheral output devices (not shown), such as speakers and printers.
The computer 1 may operate in a networked environment using logical
connections to one or more remote computers, such as remote computer 19. A
communication device coupled to or a part of the computer 1 achieves these
logical
connections; the invention is riot limited to a particular type of
communications device
The remote computer 19 may be another computer, a server, a router, a network
PC, a
client, a peer device or other common network node, and typically includes
many or all of
the elements described above; relative to the computer 1. The logical
connections
depicted in FIG. 1 include a local-area network (LAN) 20 and a wide-area
network
(WAN) 21. Such networkin ~ environments are commonplace in office networks,
enterprise-wide computer networks, intranets and the Ir.~temet, which are all
types of
networks.
When used in a LAN-networking environment, the computer 1 is connected to the
local network 20 through a network interface or adapter 22, which is one type
of
communications device. When used in a WAN-networking environment, the computer
1
typically includes a modem 2 3, a type of communications device, or any other
type of
communications device for establishing communications over the wide area
network 21,
such as the Internet. The modem 23 is connected to the system bus 4 via the
serial port
interface 16. In a networked environment, program modules depicted relative to
the
personal computer 1, or portions thereof, may be stored in the remote memory
storage
device. It is appreciated that the network connections shown are exemplary and
other
means of and communications devices for establishing a communications link
between
the computers may be used.
12
CA 02436312 2003-08-O1
A Method to Structure Spatial Data in the_f'orm o~'a Linear Index
Division of Space
FIG. 2 illustrates prior art methodology for locating spatial information on a
rectangular grid. A single spatial coordinate, Point 24, from a defined
rectangular Plane
25, with Attributes 26, such as on, off, red, blue, hot, cold, 20, 30, 40,
etc, shown. Point
24 and Attributes 26 have been created, collected or recorded by any of a
number of
analog and/or digital methods. Point 24 can be representative of any single
dot or a
singular dot within a large group of a Raster Image 27 located with a row and
column.
Alternatively, Point 24 could be a point of a mathematically defined Vector
Line 28
located with a Coordinate (6,7) 29 and an index Link 3f to Attributes 26.
Exemplary
linear and area constructs of the point include a Network 31 and Polygon 32.
Point 24, by its nature, also represents a centroid and a cell area that
encompasses
a distance between it and the next adjacent point or, on the basis of known
practice within
geometry and other mathematics, Point 24 is bound by its; accuracy, error and
precision
based on factors of its creation and record. It is exemplary that within this
cell area,
Attributes 26 can be considered homogenous. For the purpose of this
description, the
area, whether implied explicitly or implicitly, will be referred to as a
point's area of
influence.
FIG. 3 illustrates an alternative planar location scheme whereas the points
are
closely packed. Referring to FIG. 3, the single spatial Coordinate 29 of Point
24, is now
defined by a hexagonal PYXIS Plane 33, as Cell 34 with the same Attributes 26,
on, off,
red, blue, hot, cold, 20, 30, 40, etc.
Successive aperture three subdivisions of a general hexagon cell define
locations
on the PYXIS Plane 33. In an aperture three hexagon subdivision, at any given
resolution
13
CA 02436312 2003-08-O1
"n", the basic unit of distance ''a" which equates to one side of a general
hexagon or the
radius from the center to a vertex, is 1/3 the distance "a" of one resolution
lower, "n-1",
where "a" is known as the apothem of the hexagon
The Plane 33 is infinite in two-dimensional space. As also illustrated on FIG.
2,
Cell 34 can also be representative of any single dot or a singular dot within
a large group
of a Raster Image 35 or Cell 34 could be a point of a Vector Line 28, either
located with a
PYXIS Index (7277472) 36, which is explained in more detail below, and used as
the
index to Attribute 26. The area bound by Cell 34 becomes its area of
influence.
The division of space: on the PYXIS Plane 33, herein coined as the PYXIS
innovation, adheres to the follcswing requirements:
1. Spatial attributes are assigned to a parent cell, whose centroid represents
its
location and the voronoi region created by the boundary with adjacent parent
centroids forming the: closed area for which the properties of the cell are
represented;
2. A parent cell for which the centroid location is not a centroid location
for any
lower resolution cells defines the location of a single new child cell of the
next
highest resolution; alternatively,
3. A parent cell for which its centroid location is also a centroid location
for any
lower resolution cells defines the location of a single new child cell of the
next
highest resolution and multiple new child cells of the next highest
resolution, one
located at each of the vertices of the parent's boundary edge;
whereby during initial conditions, a parent cell will be assigned a general
hexagon shape
or the shape of the plane for which it represents, with a starting centroid
location that can
be considered the planar origin. A note of interest is that the resulting
outline is a figure
14
CA 02436312 2003-08-O1
with properties of the Koch Snowflake curve-amongst others, a infinite
perimeter with
finite area.
Addressing and Indexing
The system or procedure for addressing the cells is based on assigning a
number
consisting of the cell index of i.ts related parent plus the member
corresponding to its order
in the cluster of child cells. ~rdering of the cluster of child cells can
follow simple
sequential ordering or other exemplary methods shown: Generalized Balanced
Ternary
FIG. 4a, Gray Coding FIG. 4b, a hybridized Gray GBT FIG. 4c, various z curves
FIG. 4d,
4e, and 4f and other forms known to those versed in the art such as
modifications of
Morton, Hilbert, Koch, Peano curves and/or ordering that are not shown.
Child cells at a given k esolution (n+1 ) are uniquely related to a next lower
parent
cell at resolution (n) if they share the same centroid location or, if the
centroid of the child
cell is located on the vertex of the cell boundary of a next lower parent cell
at resolution
(n) whose centroid location is also a centroid location of its parent cells)
at any lower
resolution ([n-1).
FIG. Sa to Sf illustrate six successive resolutions of the PYXIS indexing
using a
simple ordering.
FIG. Sa. A generalized hexagon is set at the origin as an initial condition
with a
given Resolution 37 and assigned a value of 7.
FIG. Sb. The second Resolution 38 cell locations exist at all centroids and
vertices
of Resolution .37 cells, following rule 3, and are indexed with the 7 of the
parent and the ordering 1, 2, 3, 4, S, 6 (of the vertices) and following 7 (at
the centroid) resulting in new indices 71, 72, 73, 74, 75, 76 and 77.
IS
CA 02436312 2003-08-O1
FIG. 5c. The third Resolution 39 cell Locations follow the same pattern; new
cells
are given the value of the next lower Resolution 38 parent and a centroid
value (7) if they share the same centroid location, rule 2 (71, 72, 73, 74,
75, and 76 and 77 spawn centroid cells 717, 727, 737, 747, 757, and 767),
and if the centroid of the new cell is located on the vertex of the cell
boundary of a Resolution 38 cell whose centroid location is also a centroid
location for a Resolution 37 cell, rule 3, the new cells are given the parent
value and an order value (77 spawn verte~s; cells 771, 772, 773, 774, 775,
776 and 777).
FIG. 5d. The forth Resolution 40 cell division continues similarly, all new
cells are
given the value of the next lower Resolution 39 index if they share the
same centroid location, rule 2 (771, 772, 773, 774, 775, and 776 spawn
centroid cells 7'717, 7727, 7737, 7747, 7757, and 7767), and if the centroid
of a new cell is located on the vertex of the cell boundary of a Resolution
39 cell whose centroid location is also a centroid location for a Resolution
38 cell, rule 3, the new cells are given the parent value and an order value
(717, 727, 737, 747, 757, 767 and 777 spawn vertex cells 7171, 7172,
7173, 7174, 71'75, 7176, 7177, 7271, 7272, 7273, 7274, 7275, 7276, 7277,
7371, 7372, 73'73, 7374, 7375, 7376, 7377, 7471, 7472, 7473, 7474, 7475,
7476, 7477, 75'71, 7572, 7573, 7574, 7575, 7576, 7577, 7671, 7672, 7673,
7674, 7675, 76'76, 7677, 7771, 7772, 7773, 7774, 7775, 7776, and 7777).
FIG. Se. This division is continued with successively finer Resolution 41 and
FIG. Sf. Resolution 42.
16
CA 02436312 2003-08-O1
It should be noted that to facilitate available space, indices for new cells
located
on centroids used in lower resolutions are not shown on FIG. Sd, Se, and Sf.
These unique indices provide for the mapping of two-dimensional spatially
organized data in the form of multiple resolutions of close-packed uniformly
adjacent
cells to a linear index compatible for use in the one-dimensional linear space
of a
computer memory and/or storage medium, as a conventional file or relational,
multidimensional or other similar database system familiar to those versatile
in the art.
Also, the indexing is so structured as to provide a common addressing scheme
for
traditional forms of spatial data with an explicit indication of the spatial
data location and
its area of influence.
As spatial data structures require some flexibility, exceptions to these rules
of
division and indexing are required. It is straight forward to consider the
modification of
this system whereas cell shapes and sections of cells on the plane are
included or
excluded, bent, joined, stretched, rotated, scaled or translated to meet
specific spatial
I S requirements such as surface modeling or to create tessellations bounded
by specific
shapes.
Another flexibility provides for the introduction of one or more new point or
cells
at a specific resolution that do not fall on a regular PYXIS location for that
resolution.
PYXIS provides for a cell to be introduced at any unique location and specific
resolution.
Its ordering precedence superseding its neighbours and its behaviors are
considered as a
parent cell for which its centroid location is also a centroid location for
lower resolution
cells. If two or more cells are introduced at any unique location and specific
resolution
and the boundary of two or three of the new cells share vertices, such
vertices define the
location of new child cells and the child cells shall be uniquely indexed with
reference to
2S its three shared parents, and the behavior of these child cells are
considered as a parent
17
CA 02436312 2003-08-O1
cell for which their centroid location is not a centroid location for any
lower resolution
cells. An example of this and how it is treated is detailed below with the
indexing of the
first two resolutions of the icosahedron in a discrete global grid system.
Flierurchczl Data Structure
FIG. 6a and 6b illustrate two additional views of the PYXIS indexing. These
figures identify a balanced tree hierarchal data structure. To improve the
efficiency and
speed of access for the mos~~t probable queries the invention takes advantage
of the
hierarchical structure of the dimensions in spatial data. Tr~is hierarchical
structure reflects
the fact that a typical spatial query asks about members from the same parent
in the
hierarchy. Thus, the mapping of the present invention provides that records of
data with
dimension members belonging to the same parent are closer to each.
Such data hierarchies in various forms of B-trees and similar data structures
are
familiar to those versatile in the art of data management. Spatial data
hierarchies are the
basis for search tree algorithms that allow efficient retrieval of indexed
spatial data. The
identification of nearest neighbour cells is key to such spatial searches.
FIG. 7 illustrates
a procedure to identify nearest neighbour cells on the PYXIS Plane 43. A
simple
ordering is exemplary as shown with its accompanying Even Digit 44 and ~dd
Digit 45
Addition Table 46 whereas then Column I-Ieader 47 and Row F-Ieader 48 act as
the lookup
values. The Example 49 illu~.strates the addition of 6 unit vectors to the
index value
776771 resulting in the nearest neighbour list +1=77;'576, 7-2=776717,
+3=776772,
+4=776747, +5=776774 and +6=776777. Note in this simple ordering example the
digit
value 7 acts as a placeholder.
18
CA 02436312 2003-08-O1
Boolean ~peratio~s
Boolean logic plays a central role in spatial data structure algorithms.
Boolean
algebra is useful for performing operations on the attributes (which may be
positional or
descriptive) attached to geographic entities in a Geographic Information
System. Boolean
Logic is especially useful in computing (or modeling) new attributes in
topological
overlay processing for both vector and raster based systems, as they can be
applied to all
data types, be they Boolean, Ratio, Interval, Ordinal, or Nominal. A procedure
for
identifying a PYXIS point as spatially contained, overlapping or excluded,
from a specific
cell, the spatial data forms of Boolean algebra using the logical operators
AND, OR, and
NOT are outlined below and references FIG. 8.
In the PYXIS Plane 5C>, any indexed point can be defined as External To 51,
Overlapping 52, or Contained By 53, a Cell 54. Further, the following
conditions and
procedures apply in their determination:
Condition #1 - A point: indexed above a lower resolution containment Cell 54
is
considered "spatially contained at all resolutions" if its index is nested as
a child of the
containment Cell 54.
Test procedure for containment Condition #I
Given Cell 54 index of resolution n and point index of resolution r, if n ~' r
and
digits 1 to n of Cell 54 is equal to digits 1 to n of 'the point index then
Condition
# 1 is True.
Condition #2 - A poinl: indexed above a lower resolution Cell 54 is considered
"within the spatially overlapping area" if point is found to be "spatially
contained at all
resolutions" in one of the six neighbour Cells 56 adjacent to the containment
Cell's 54
centroid child Cell 55.
I9
CA 02436312 2003-08-O1
Test procedure for within the spatial overlapping area Condition #2
Given Cell 54 index of resolution n and point index; of resolution r, if n [ r
and if
digits 1 to n+1 of a neighbour Cell 56 to the centroid child Cell 55 (found
using
Addition matrix with unit vectors 1 to d from Cell 55), equals digits 1 to n+1
of
the point index then Condition #2 is True.
Condition #3 - A point indexed above a lower resolution containment Cell 54 is
considered "spatially external at all resolutions" if it is not "within the
spatially
overlapping area" and not "within the spatially overlapping; area" of the
containment Cell
54.
Test procedure for within the spatial external area Condition #2
Given Cell 54 index of resolution n and point of resolution r and Condition #1
is
False and Condition #2 is False then Condition #3 is True.
Note that, as a PYXIS indexed point on the PYXIS plane 50 explicitly
represents
an area of influence, a point within the spatially overlapping area 52 may
test True under
Condition #2 however, it's further determination to be spatially contained,
overlapping or
external to Cell 54 is dependant on the resolution of the point. The
containment
Condition #2 is therefore resolution dependant. Condition #2 only determines
that the
point is within the area of overlapping conditions. To determine if, at the
resolution of
the point, it is contained, overlapping or external to the Cell 54, further
test procedures are
required that determine where within the overlapping Cell 5e5 the point lies.
Within Condition #2, there are two test procedures for cell overlap: Condition
#2.1 whereas the overlap Cell 57 is on a vertex and Condition #~.2 whereas an
overlap
CeII 58 is on a straight boundary edge. The resoluticm dependant conditions
test
procedures are detailed below and refer to FIG. g.
CA 02436312 2003-08-O1
Test procedure for poiiut within a cell overlappin~,r a vertex Condition #2.1
or a
cell edge, Condition #2.2
Given point index of resolution r lies somewhere in overlapping n+1 C'.ell 56,
found at direction d from Cell 55, test for area that contains point.
For i = 3 to r:
Condition 2.I
2.1.1. Point contained in overlapping Area 59 on vertex
~ Check if point contained in n+i centroid child of Cell 57.
~ If point containment True, set i = i + 1 and loop condition #2.1.1 until n+i
Cell index equals point index and therefore "spatially overlapping at this
resolution".
~ If False, goto 2.1.2;
2.1.2. Overlapping Area 60 on edge
~ Use addition matrix to find cell area 60 defined by resolution n+i
overlapping at edge cells (n+i centroid cells of n+i-1 centroid child of Cell
57 d+2 and d-2 neighbours.).
~ If point containment True, set i = i + l and goto condition #2.2 below.
~ If False, goto 2.1.3;
2.1.3. Overlap Area 61 where all cells contained within the parent Cell 54
~ Use addition matrix to find the 3 resolution n+i contained cells (n+i
centroid cell of n+i-1 centroid child of Cell 57 d+3 neighbour AND n+i
centroid cells of n+i centroid child of Cell 57 d+4 and d+5 neighbours.).
21
CA 02436312 2003-08-O1
~ If point containment True, then point is "spatially contained at all
resolutions" of Cell 54, or;
~ If False, then point is "spatially external at all resolutions" of Cell 54.
Condition 2.2:
2.2.I . Point contained in overlapping Area 60 on cell edge
~ Check if point contained in n+i centroid child of Cell 58.
~ If point containment True, set i = i + 1 and loop condition #2.2.1 until n+i
Cell index equals point index and therefore "spatially overlapping at this
resolution".
~ If False, goto 2.2.2;
2.2.1. Cells 60 overlapping on edge
~ Use addition matrix to find cell area 60 defined by resolution n+i
overlapping at edge cells (n+i centroid cells of n+i-1 centroid child of Cell
57 d+2 and d-1 neighbours or d-2 and d+1 if 2.1.1 met in d-2 addition).
I 5 ~ If point containment True, set i = i + 1 and goto condition #2.2.1.
~ If False, goto 2.2.3;
2.2.2. Cells 61 contained within the parent Cell 54
Use addition matrix to find the 5 resolution n+i contained cells (n+i
centroid cells of n+i-I centroid child of Cell 57 d+3 and d+4 neighbour
AID n+i centroid cells of n+i centroid child of Cell 57 d+3, d+4 and d+5
neighbours.).
22
CA 02436312 2003-08-O1
~ If point containment True, then point i;~ "spatially contained at all
resolutions" of Cell S4, or;
~ If False, then point is "spatially external at all resolutions" of Cell S4.
Spatial Queries
An embodiment of the invention, as demonstrated above, is a method of
selecting
the spatial data once it resides within the computer device as a hierarchy of
indices.
Spatial queries on the multiresolutional close-packed PYXIS indexing using
standard
Boolean procedures familiar to those versatile in the art, provides a means of
selecting
and sorting spatial features and dimensions of their attributes. Examples of
practical
forms of these selections include:
~ Select all features of a given range of resolutions
~ Select features bound by a given spatial domain (area)
~ Select features bound by a given polygon shape
~ Select features from 2 desperate sources A and B, that are in A and in B.
(Features that exist in both sources)
~ Select features from 2 desperate sources A and B are in A and those in B
that
are not in A. (Add to A all features from B not in A)
In addition, a multitude of other possible data queries are possible, based on
combinations of resolution, location, cell area, occurrences, attributes,
distribution and
other dimensions of the data. This core functionality provides the basis for
further
embodiments detailed below that include data integration, transmission, visual
display,
analysis, fusion, and modeling
23
CA 02436312 2003-08-O1
Geographical Reference
Another preferred embodiment is a system that utilizes the PYXIS indexing to
spatially (geospatially) reference (georeference) data located on, around or
beneath the
surface of earth. Methods of projecting points from the .faces of a platonic
solid to the
earth spheroid as a geodesic reference are well know in various forms of
previous art. A
method for establishing and referencing multiresolutional close-packed cells
on the earth
spheroid by projecting the PYXIS plane from an icosahedron is exemplary of the
embodiment and used herein to illustrate the capability of the invention, not
limiting it to
such techniques.
Prior art described by Sahr, et. al. as the Snyder Equal Area Aperture 3
Hexagon
Grid (ISEA3H) can be used to orient and generate locations of the close-packed
tessellation of the icosahedron to the earth spheroid FIG. 9a shows 5
resolutions of a 3rd
aperture hexagon tessellation on a triangular. These cells are indexed in a
manner as
described above for linear storage and hierarchal reference. FIG 9b shows an
icosahedron
solid featuring 12 Vertices and 20 triangular Faces.
Reference to the vertices requires a modification of the PYXIS innovation such
that the shape of the original cell and all subsequent cells that are created
at the same
centroid (always at the icosahedrons vertex) will be a pentagonal as
illustrated in FIG. 9c.
Further, the cells are laid onto the five faces of the icosahedron. The
indices are modified
accordingly. Illustrated in FIG. 9d is a section of the icosahedron divided by
this
modified PYXIS plane. FIG. !3e shows this same plane reference projected to a
sphere.
In addition to the typical PYXIS tree hierarchy developed above and shown in
FIG. 6a and 6b, the indexing hierarchy in the georeference to the icosahedron
must be
modified to include two additional levels, one to index the vertices and a
second to index
2~
CA 02436312 2003-08-O1
the points on the faces. Exemplary of a simple ordering for these points, but
not limited
to these labels, would have the vertices labeled 1 through 12 and the faces
labeled A to J
and Q to Z as illustrated in the symbolized unfolded icosahedron of FIG. 9f.
This face
labels are further referenced to their three parents to provide georeference
and order. As
an example child cell A is related to parents 1, 3 and 5. Hierarchal
precedence is given to
the modified cells deemed to be resolution I created at the vertex of the
icosahedron
where the vertices of this modified cell are Located at each of the five
connected
icosahedron faces. Reference at subsequent resolutions returns to the regular
PYXIS
indices.
IO In this way, the PYXIS innovation is used to provide a close-packed,
uniformly
adjacent, multiresolutional, overlapping spatial data ordering that can be
used to
georeference the earth spheroid and allow spatial observations of the earth to
be transpose
from planar space to a one-dimensional space efficient for use in digital
computer storage.
A Discrete Global Grid Syste~e
System Envirohnrent
FIG. 10 illustrates the: components of a Discrete Global Grid System 63 as a
further embodiment of the irmention. The PYXIS innovation provides the
combined
utility of a close-packed, multiresolutional cell index with a georeference to
the earth
spheroid that has hierarchical features suitable for storage and selection by
structured
query. The PYXIS innovation is the basic framework for components of the
system:
localized and global spatial database 64 (storage 70 and query 71), retrieval
65
(conversion 72, georeferenceing 73 and integration 74), data discovery and
fate sharing 66
(compression 75 and transmission 76), data transformations 67 (visual display
77,
analysis 78, fusion 79, and modeling 80). Creation of imagery and data can be
completed
CA 02436312 2003-08-O1
by raster and vector image sensors, creators and editors 68 or as a product of
the Discrete
Global Grid System 63. Peer-to-peer networking of PYXIS data discovery
components
allow data to be advertised and shared between remote computers 69.
There are many specifrc methods known within i:he art of spatial data storage,
retrieval, transmission, visual display, integration, fusion, analysis, and
modeling suitable
for use with the PYXIS innovation. Further, there are other functions that
build on the
PYXIS innovation not specified. The following is summarily described
functionality and
it should not be interpreted as encompassing all functional applications of
the PYXIS
system.
Spatial d3uta Retrieval
The Spatial Data Retrieval System allows images and data of various formats,
sources, types and georeference to be converted to PYXIS geospatial indices,
through
binning and gridding algorithms, suitable for storage. The critical component
to this
procedure is the capability to convert a Point 81 with a rectangular
coordinate to a cell
with a PYXIS index. This can be accomplished by determining the index of the
PYXIS
cell that contains the point. The point's area of influence provides a basis
for assigning a
cell resolution.
With reference to FIG. 11, the following steps provide an exemplary method of
determining if a rectangular point is contained in a specific PYXIS cell:
1. Align the rectangular Plane 82 with the PYXIS Plane 83 such the rectangular
coordinate of at least one cell centroid is known. i,et ~ be the angle between
the
PYXIS Plane 83 and the rectangular Plane 82 and ~ is 308 for cell resolutions
with vertex oriented at the top and 608 for cell resolutions with cell edge
oriented
at the top of the PYXIS plane.
26
CA 02436312 2003-08-O1
2. Determine the intercepts of a ~' axis with two lines from Point 81, one at
an angle
-(a + ~), referred to as -~YintPO[NT and the other at a - ~, referred to as
YlntPOiNT.
3. Determine the intercepts of the same Y axis with two lines from the
centroid of
Cell 84, one at an angle -(a + ~), referred to as -Yint~ELL and the other at a
- ~,
referred to as YIntCELL
4. Where:
a is the length of one cell side
b 1S -YlntppINT ~nlnliS -YlntCELL
C 1S Ylntpp~NT I211nL1S YlntCgLL
1~ k = a/COS(a ~' ~3~
~=aJ COS(a - (~)
Then Point 81 is contained in Cell 65 if:
j>b>jANi?~-k>c>kANDb-c>a.
Note that in the example shovrn, Point 64 is found not contained in Cell 84.
Data Visualization
Data is indexed and can be stored in a database management system or PYXIS
file. As described above, spatial features can be efficiently selected by
their spatial
relationships, features and dimensions to complete further transformations of
the data.
Digital Globe Visualization is an embodiment achieved by transforming;
selected
features from a stored PYX1:S index to a rendered object for graphic. Selected
feature
geometry and attribute values are sent to a rendering pipeline. The
application returns to
a computer visualization device a representation of the spatially organized
data associated
27
CA 02436312 2003-08-O1
with a spatial area and range of resolutions in the form of a whole or partial
rendered
image of the geodesic globe. The resultant Digital Globe is capable of being
rotated,
translated, and scaled to produce zoom, pan, yaw, and rotation functions.
Exemplary data
types eligible for 3D display include PYXIS coded raster images, vector
features, map
S annotations, texture bitmaps and terrain surface models.
Cie~spatial Data Discovery
Another preferred embodiment of the PYXIS Discrete Global Grid System is an
Online Spatial Data Discovery and File Sharing Server. With the addition of
georeferenced PYXIS index to multidimensional attributed, fielded, and
textural or image
data, information can be discovered based on its content and geospatial
position. Prior art
forms using standards and protocols for data exchange and display, like HTML,
XML,
SOAP, and other peer-to-peer file sharing provide the basis for advertising
and
discovering spatial data.
Further, the file of data can then be transmitted from the server on demand in
its
entirety, progressively or continuously. PYXIS code data resides locally
and/or remotely
and can appear on demand, progressively transmitted or updated continuously
over a
network environment.
As an example, a schoolteacher, who wants to show her class of students a
computer view of the globe, searches, discovers, and then accesses a remote
site that
serves a vector file of world political boundaries gained at another server
site; she
overlays the globe with a recent mosaic of I~adarSat images. Setting
resolutions for
display, she downloads the image on-demand. The large satellite image is
served
"progressively", based on the ideal visual resolution and the extent of the
view on the
computer monitor. As the teacher zooms into a specific area, say downtown
Ottawa, the
zs
CA 02436312 2003-08-O1
extent of the satellite image is decreased and the resolution increases. At
same point a
high-resolution digital ortho photo of Ottawa replaces the l~~wer resolution
satellite image.
Level MapO vector file, a 1:100,000 digital topographic map of the world,
replaces the
boundary file.
Another form of file transfer, continuous transmission, is helpful when sensor
data
is used to update a real-time event. While observing a road intersection in
downtown
Ottawa, a round symbol is changed on the globe from red to green when a
traffac signal
changes, or a temperature sensor provides for changes in annotation from 22C
to 21 G.
Another example of a transformation embodiment is the basis for file
transmission. A feature of the; PYXIS innovation is the compactness of the
index. First
Level compression of a series of indices for transmission is accomplished by
noting that
cells of different resolutions but in the same area retain the same parent. By
ordering the
cells in their hierarchy from lowest resolution to highest the parent cell of
any index need
only be sent once if sent in ort3er. As an example and not limited to this
technique, given
the following indices:
717273, 717274, 71727471, 71727472, 71727475, 71727577, 71.727571,
71727572, 71727573, 717376, 7175
The following digits can be transmitted without losing data where 0 indicates
branching
back up to the last parent (last 7):
717273, 4, 71, 2, 5, 0, 577, 1, 2, 3, 0, 0, 736, 0, 0, 75
Further compression encoding, whether lossy or lossless, can be performed on
PYXIS indices by methods lmown by those versatile in the art.
Files encoded in this way can be transmitted in their entirety from a server
to a
client. An example of this would be a PYXIS index embedded in a HTML file
providing
29
CA 02436312 2003-08-O1
a georeference to the data contained in the file. In this w;ay, the digital
representation of
the globe can act as a Spatial Data Browser is an embodiment of the invention.
Data
stored in PYXIS format are identified in an on-Line environment as a search
query,
displaying at an automated or manually set resolution, a pictographic symbol
at 'the cell
location on the Digital Globe. Users can select this symbol with a cursor,
activating
further software instructions or viewing detailed data.
Or, the parts of the index and attributes may be transferred from a server to
a
client in response to a query that bounds the area and range or resolutions
described
above as a query of the PYXIS data. This "progressive transmission" would be
activated
manually or could be automated based on properties of the clients viewing
area. As a
user "zooms" from a larger to smaller area, the system returns data further
down the
resolution of the spatial hierarchy, less area, more detailed.
Or, the data could be continuously transmitted, wherein the client is
continuously
checking a server for changes to the attributes of a specific cell or group of
cells. An
IS example may be an updated RGB colour value from a georeferenced PYXIS
indexed
video, photometric or satellite image or any other sensor device that includes
PYXIS cell
reference.
.fpatial data Analysis
An embodiment of the system is Spatial Bata Analyzer. Data Analysis
'Transformations in PYXIS are achieved by Boolean query, performing operations
on the
attributes (which may be positional or descriptive to select, build and
enhance
geography. Spatial analysis with the PYXIS DG~aS relies heavily on the geo-
synchronization of the gridd.ed data. As an example, using the temporal
dimension of
census data, a comparison of population of a city in the year 2002 with its
population in
CA 02436312 2003-08-O1
1950 is strictly correct if the boundary of the city remained unchanged.
Gridded data
analysis provides an efficient method of modifying that query to a comparison
of the
population of a specific set of -cells in 2002 to those same cells in 1950. It
is thus that
PYXIS can perform analysis.
S Data Fusion Transformations in PYXIS provide real interpolation of data. The
fusion functionality allows the user to select features for 2 or more sources
of data,
similar to spatial analysis, and then create new attributes through
statistical methods
known to those versatile in the art of data fusion. Da9:a Integration
Transformations,
which are similar to data fusion, are achieved by selecting data that are
included in a
polygon and performing geometric transforms (move, scale, rotate) and
superimposition
(move data above or below, cut and paste, overlay and mosaicing).
Data Modeling Transformations in PYXIS provides real extrapolation of data.
Many studies of dynamic environmental systems can be semi-deterministically
modeled
with access to current accurate; data referenced to a common grid along with
formulation
of cellular behavior. Modeling methods such as finite difference and cellular
automata
rely on a defined mesh and or tessellation to frame the calculations.
An embodiment of the invention is a Geospatial Model building system, which
allows the close-packed, unifbrmly adjacent, multiresolutional, overlapping
spatial data
ordering to be used as a mesh and grid for the construction of stochastic and
deterministic
simulation of dynamic earth events. ~Jsers can access on-demand in a peer-to-
peer
environment a multitude of temporal geospatial data at each cell and extract
and utilize
this spatial data. Users can access properties of the grid and the data that
references it.
Formulas, with constants and variables with spatial and temporal values
assigned from
PYXIS data. Rules of behavior can be defined which al.iow extrapolation and
predictive
modeling, simulating future cull conditions.
31
CA 02436312 2003-08-O1
As an example, in a P~'XIS system, data pertinent to rainfall runoff modeling
is
discovered, extracted and transmitted from a variety of sources to the model
builder
including current rainfall conditions, temperature, vegetative cover, soil
types, terrain, ete.
The user builds formulas using these data fields and other coefficients as
variables for
calculating water budget, stage, storage and routing conditions. The
simulation of a
rainfall event results in the increase of simulated water flow over time in a
downstream
cell, emulating a rainfall/runoffhydrograph.
While the present invention has been described and illustrated herein with
reference to the preferred emb~7diment thereof it will be understood by those
skilled in the
art that various changes in form and details maybe made therein without
departing from
the spirit and scope of the invention.
It is to be understood that the embodiments and variations shown and described
herein are merely illustrative of the principles of this invention and that
various
modifications may be implemented by those skilled in the art without departing
from the
scope and spirit of the invention.
32
