A spatial index (SPAS == Spatially Associative Substrate) is used
to store the regions occupied by the primitives and higher-level
objects in a diagram. The basic collection of cells is typically
a 64x64 square array, covering the space occupied by the diagram.
Each object is *installed* in the array by creating an object reference in every array cell
that the object occupies or passes through. The spatial array
operates as an associative index mapping from 2-space to objects.
In addition, two linear spatial projection arrays for the x and
the y axes are also filled in the same way. The spatial array
is used to efficiently compute spatial relations that are important
in parsing. For example, finding out whether two objects *A* and *B* are *near* one another is done by inspecting the cells occupied by *A* for the presence of a *B* object (or vice-versa). To avoid near misses that can occur in
such computations, objects are also installed in the 8-neighbors
of each cell. That is, two objects can be very close together
but happen to be in two distinct but adjacent cells. They should
be considered near in such a case, and the strategy we have used
is to look in the eight nearest neighbor cells. This, in effect,
essentially "coarsens" the grid, but that can be overcome simply
by using a finer grid (deeper pyramid). Important relations such
as *horizontally-aligned* can be computed immediately from the projection arrays. Though
it is obvious how to compute predicates, such as, are *A* and *B* near one another?, it is often more important to *generate* sets of objects that satisfy a given spatial relation. This is
also easily accomplished using SPAS -- to find all objects near
*A* we form the union of all other occupants of cells occupied by
*A*. To accommodate spatial predicates that operate at various levels
of resolution, SPAS is actually a pyramid of arrays of size 2^{i}x2^{i}, i=0,6 (the last figure, 6, is a settable parameter) and the
objects are installed in all levels of the pyramid. Generated
sets are typically used to restrict the context that is passed
to a constituent rule.

Multiple copies of higher-level objects may be constructed during a parse, but only one copy of a given constituent with identical leaf nodes is installed in the SPAS and referred to in the solution. This retains object integrity for all constituents. In the future, it may be possible to exploit this to even avoid rediscovering constituents, much as natural language chart parsers do. But diagram parsing cannot rely on the simple linear position index that natural language chart parsers do, so this will be a challenging efficiency issue. (We have experimented with memoization, but that also needs further work.)

One of the benefits of the spatial index is that once objects are installed, geometric computations can be done based on cells, ignoring the objects' geometric structure, so that it is as easy to find objects near a Bezier curve as it is to find objects near a straight line or a text item. Higher-level objects are installed in SPAS as the parsing process proceeds and each higher-level object occupies the cells that are the union of the cells occupied by the primitives descendants.

In the figure below, we show how the diagram viewer can display the cells occupied by an arbitrary object, in this case the higher-level object DATA-LINE.

When lines or Bezier curves are installed, their endpoints are
also installed as distinct, but related, objects. In the figure
above it is clear that a connected sequence of data lines has
been identified by the parser. This is done by using the spatial
index to look in the neighborhood of a line end-point to see if
the (starting) end-point of another line is there. In this way,
a *chain* of connected lines or curves can be built up.

Next: Finite-state automata diagrams -- using sharing for context |

Back to Index page |