Shape comparison language


Introduction

In the interest of supporting the OGIS and SQL3/MM initiatives, ESRI is implementing within SDE a language syntax for the evaluation of relationships between shapes, which will eventually replace the current use of SDE search methods and search masks for defining search criteria and for expressing relationships between shapes. The syntax of this language, referred to herein as SCL, is based on the Calculus-Based Method (CBM) as described and defined by Clementini and Felice, with extensions.
The CBM defines shape relationships by the intersection of their boundary, interior, and exterior, taking the dimensionality of the intersection into account. There are five basic relationships – Touch, Overlap, In, Cross, and Disjoint. These relationships are defined such that for any two given shapes only one of these five relationships is true. In addition, SCL supports the additional relationship IDENTICAL, which is true only when two shapes are geometrically identical and share correct topological integrity.
The CBM and SCL perform relationship comparison to a maximum of two dimensions, thus SCL can only be used to describe 0, 1, and 2-dimensional relationships. This is consistent with previous versions of SDE wherein the SDE search methods only described 2-D relationships.

Dimensionality

In order to use SCL you must thoroughly understand the concepts of shape boundary and interior, as well as dimensionality:
All point shapes are 0-dimensional.
All linear shapes are 1-dimensional.
All area shapes are 2-dimensional.
The above is true for the purposes of SCL regardless that the shape may have z-coordinates or not, or that it may have measures.
Interior:
The dimension of the interior of a shape is always that of the shape itself. Thus the dimension of the interior of a linear shape is one (1). All shapes have interior. The interior of a shape is defined as the entire shape minus its boundary.
Boundary:
The dimension of the boundary of a shape is always that of the shape minus 1. Thus the dimension of the boundary of a linear shape is zero (0) and the dimension of the boundary of any point shape is (-1), or NIL. Linear and area shapes have boundary, but point shapes do not. The boundary of linear shapes consists of the end points of all linear parts. The boundary of area shapes consists of the linear boundary of the polygon shell(s).
Exterior:
The dimension of the exterior of any shape is always 2. All shapes have an exterior.

Extensions to the CBM

The CBM does not differentiate between an intersection that occurs at a shape vertice and an intersection that occurs between shape vertices. Because it is often crucial to maintain topological integrity between shapes, and to know when there is a lack of topological integrity between shapes, SCL has been extended as follows:
TOPOFORM – A unary function which evaluates to TRUE if topological integrity exists between two shapes, and FALSE if there is a lack of topological integrity. A lack of topological integrity is defined as intersection that is other than topological adjacency.

SCL Syntactical Overview

SCL is used to describe the relationship between 2 specific or, in the case of spatial searches, hypothetical shapes. SCL expressions evaluate to TRUE or FALSE, except in the case of the DIM functions, which evaluate to a dimension value..
The general form of an SCL statement consists of one or more spatial assertions. Multiple assertions may be connected into a single assertion using the logical connecting operators AND, OR, and XOR. Parenthetical expression hierarchy is supported. SCL expressions are not case dependent.
Example 1: "G1 NOT DISJOINT G2"
The above case evaluates TRUE if the shapes g1 and g2 touch or overlap in any way. Both ‘G1’ and ‘G2’ are reserved words that refer, respectively, to shape #1 and shape #2.
Example 2: "(g1 overlap g2 and dim (g2) = area) or (g2 cross g1 and dim (g2) = linear)"
The above case evaluates TRUE if the ‘g2’ shape is an area and meets the intersection criteria defined by the keyword ‘overlap’ or if the ‘g2’ shape is linear and meets the intersection criteria defined by the keyword ‘cross’.
SCL uses the numeric constants TRUE, FALSE, POINT, LINEAR, AREA, NIL, and NULL, rather than numeric literals. SCL does not support user variables or numeric literals. The terms NIL and NULL may be used interchangeably and are used to refer to a lack of a specific type of intersection.
SCL allows binary spatial relationships to be expressed as a function or as an operation between the two shape constants G1 and G2. For example, the expression "G1 cross G2" is equivalent to the expression "cross (g1, g2) = true". The expression "G1 not cross G2" is equivalent to the expression "cross (g1, g2) = false" or "cross (g1, g2) != true".
In SCL the DIM function is actually two different functions, depending upon the number of arguments. If there is only one argument it returns the dimensionality of a shape or shape component, such as "dim (g1)" or "dim (g1.boundary)". If there are two arguments the dim function returns the dimension of intersection between the two expressed shapes or shape components, such as "dim (g1, g2)" or "dim (g1.interior, g2.boundary)".

The Dimension Functions

The dimension functions are the most powerful functions in SCL for the assertion of spatial relationships.
The dimension function "DIM" takes either one or two spatial object arguments and performs a different function depending upon the number of arguments used. It is interesting to note that all of the Clementini relationship operators can be defined using just these two DIM functions.
Note that the spatial object modifiers "boundary", "interior", and "exterior" can only be used as modifiers for the spatial entity arguments to the DIM function. The modifier use form is <spatial entity reference><period><spatial-modifier> in the form "g1.boundary".

DIM function form 1

Returns the spatial dimension of a spatial entity or a component (boundary, interior, or exterior) of a spatial entity.
Syntax: DIM (spatial-object)
Where spatial-object is one of the following:
G1
G1.BOUNDARY
G1.INTERIOR
G1.EXTERIOR
G2
G1.BOUNDARY
G1.INTERIOR
G1.EXTERIOR
Returns the spatial dimension of the referenced spatial object which evaluates to one of the following supported dimension constants:
NIL, NULL (-1)
POINT 0
LINEAR 1
AREA 2
Usage examples:
"dim (g1.interior) >= linear"
"dim (g1) = dim(g2)"
"dim (g1) >= dim(g2.interior)"

DIM function form 2

Returns the spatial dimension of intersection between two spatial entities or components (boundary, interior, or exterior) of the entities.
Syntax: DIM (spatial-object1, spatial-object2)
Where spatial-object1 and spatial-object2 are one of the following and both spatial objects may not refer to the same shape (G1 or G2):
G1
G1.BOUNDARY
G1.INTERIOR
G1.EXTERIOR
G2
G1.BOUNDARY
G1.INTERIOR
G1.EXTERIOR
Returns the spatial dimension of intersection between the referenced spatial objects which evaluates to one of the following supported dimension constants:
NULL (-1)
POINT 0
LINEAR 1
AREA 2
Usage examples:
"dim(g1.interior,g2) >= linear"
"dim(g1,g2) = dim(g2)"
"dim(g1.boundary,g2.boundary) > point"

Spatial Relationship Functions and Expressions

The CBM, and hence SCL, are not particularly intuitive. It is essential to commit the following definitions to memory before using SCL. Here are the criteria for relationship evaluation.
The seven spatial relationships may be expressed as functions or relations. For example we may express the TOUCH relationship as:
A relation: "G1 TOUCH G2"
Or as a function: "touch (g1,g2) = true"
Function form is "<function (spatial entity, spatial entity)> <equality operator> <truth constant>".
Relation form is "<spatial entity> <relation name> <spatial entity>"
The logic requirements of the relations TOUCH, CROSS, IN, CONTAIN, OVERLAP, and DISJOINT preclude the use of modifiers to spatial entity specifications. In other words, you must use G1 or G2 as spatial arguments, and the use of modifiers such as "G1.BOUNDARY" are not allowed.
The INTERSECT relation does allow the use of the modifiers BOUNDARY, INTERIOR, and EXTERIOR to the spatial arguments G1 and G2. Examples of appropriate usage form are "g1.interior intersects g2.exterior" and "g1.boundary intersect g2".
Note that if the relationship is expressed as a function you must compare the result of the function to the constants TRUE or FALSE, e.g., "intersect (g1,g2) = true".

TOUCH spatial relation

Applies to area/area, line/line, line/area, point/area, and point/line groups.
Criteria:
  • The dimension of intersection between G1 and G2 is not null.
  • The dimension of intersection between the interior of G1 and the interior of G2 is null.
"G1 TOUCH G2" is equivalent to the following statement:
"dim(g1.interior, g2.interior) = null and dim(g1,g2) != null"
Expression options and examples:
"G1 TOUCH G2"
"G1 TOUCHES G2"
"G1 =* G2"
"TOUCH (G1,G2) = TRUE"
"TOUCHES (G1,G2) = TRUE"

CROSS spatial relation

Applies to line/line, line/area, point/area, and point/line groups.
Criteria:
  • The dimension of intersection between G1 and the exterior of G2 is not null.
  • The dimension of intersection between G2 and the exterior of G1 is not null.
  • The dimension of intersection between the interior of G1 and the interior of G2 is not null and is less than the dimension of either or both of the interiors of G1 and G2.
"G1 CROSS G2" is equivalent to the following statement:
"dim(g1.interior, g2.interior) != NIL and (dim(g1.interior, g2.interior) < dim(g1.interior) or dim(g1.interior, g2.interior) < dim(g2.interior)) and dim(g1, g2.exterior) != NIL and dim(g2, g1.exterior) != NIL"
Expression options and examples:
"G1 CROSS G2"
"G1 CROSSES G2"
"G1 =/ G2"
"CROSS (G1, G2) = TRUE"
"CROSSES (G1, G2) = TRUE"

IN or CONTAIN spatial relations

Applies to all group types.
Criteria:
  • The intersection of the two shapes is equal to the shape defined as in or contained.
  • The intersection of the two shapes’ interiors is not null.
"G2 IN G1" is equivalent to the following statement:
"dim (g2, g1.exterior) = null and dim (g1.interior, g2.interior) != null"
Expression options and examples:
"G1 IN G2"
"G1 INSIDE G2"
"G1 CONTAIN G2"
"G1 CONTAINS G2"
"G1 =@ G2"
"IN (G1, G2) = TRUE" /* g1 contained by g2 */
"INSIDE (G1, G2) = TRUE" /* g1 contained by g2 */
"CONTAIN (G1, G2) = TRUE" /* g2 contained by g1 */
"CONTAINS (G1, G2) = TRUE" /* g2 contained by g1 */

OVERLAP spatial relation

Applies to area/area, line/line, and point/point groups.
Criteria:
  • The dimension of intersection between G1 and the exterior of G2 is not null.
  • The dimension of intersection between G2 and the exterior of G1 is not null.
  • The dimension of intersection of the two shapes’ interiors equals the dimension of the interior of both shapes.
"G1 OVERLAP G2" is equivalent to the following statement:
"dim (g1) = dim (g2) and dim (g1) = dim (g1.interior, g2.interior) and dim (g1, g2.exterior) != NULL and dim (g2, g1.exterior) != NULL"
Expression options and examples:
"G1 OVERLAP G2"
"G1 OVERLAPS G2"
"G1 =& G2"
"OVERLAP (G1, G2) = TRUE"
"OVERLAPS (G1, G2) = TRUE"

IDENTICAL spatial relation

Applies to area/area, line/line, and point/point groups.
Criteria:
  • The intersection between the two shapes equals each shape.
  • Topological integrity exists between the two shapes ("topoform").
"G1 IDENTICAL G2" is equivalent to the following statement:
"dim (g1) = dim (g2) and dim (g1,g2.exterior) = null and dim (g2,g1.exterior) = null and topoform = true"
Note that the expression "G1 contains G2 and G2 contains G1" can be true in certain cases where there is a lack of topological integrity. In such cases the expression "G1 identical G2" is false.
Expression options and examples:
"G1 IDENTICAL G2"
"G1 = G2"
"G1 == G2"
"IDENTICAL (G1, G2) = TRUE"

DISJOINT spatial relation

Applies to all group types.
Criteria: The intersection of G1 and G2 is NULL.
"G1 DISJOINT G2" is equivalent to "dim (g1, g2) = NULL"
Expression options and examples:
"G1 DISJOINT G2"
"G1 =! G2"
"DISJOINT (G1, G2) = TRUE"

INTERSECT spatial relation

Applies to all group types. Note that the INTERSECT relation allows the use of modifiers with its spatial arguments. These modifiers are BOUNDARY, INTERIOR, and EXTERIOR.
Criteria: Evaluates to TRUE if the dimension of the specified intersection is not NULL.
"G1 INTERSECT G2" is equivalent to "dim (g1, g2) != NULL"
Expression options and examples:
"G1 INTERSECT G2.BOUNDARY"
"G1 =? G2"
"INTERSECT (G1.INTERIOR, G2.INTERIOR) = TRUE"

TOPOFORM spatial relation

Applies to all group types.
This is a unary spatial relation that evaluates to TRUE or FALSE and must be compared with an equality operator and truth constant for evaluation.
Expression options and examples:
"TOPOFORM = TRUE"

Spatial Relate Function

The RELATE function is supported as unary function for testing against the entire 9IM array at once. The 9IM array has nine elements of comparison – three elements of each shape versus three elements of the other shape. These elements are boundary, interior, and exterior.
Each element for the first shape G1 may be tested against each element of the second shape G2 for truth or falsehood. Selected array elements may be selectively ignored.
Syntax of the RELATE function is as follows:
Example: "RELATE (G1, G2, ’FFFTTT***’)"
RELATE is a unary function and is not compared to true or false.
In the above example shapes G1 and G2 are compared. The string ‘FFFTTT***’, delimited in single quotes, is used to specify whether the intersection of each of the elements in the 9IM array is true (T), false (F), or not tested (*). Notice that there are exactly nine elements in the string which correspond, from left to right, to the following nine relationships:
1
G1.interior
G2.interior
2
G1.interior
G2.boundary
3
G1.interior
G2.exterior
4
G1.boundary
G2.interior
5
G1.boundary
G2.boundary
6
G1.boundary
G2.exterior
7
G1.exterior
G2.interior
8
G1.exterior
G2.boundary
9
G1.exterior
G2.exterior
In the above example relationships 1-3 must be false, relationships 4-6 must be true, and relationships 7-9 are not tested. The truth criteria for any given shape element relationship is that the dimension of intersection between the shape elements is not null . Note that this function does not evaluate the dimension of intersection between the shape elements, just whether the intersection exists or not.
Any two shapes' exteriors always intersect and the dimension of intersection is 2 (area).
It is not necessary to list G1 and G2 in that order in the syntax. If you list G2 first – for example,
"relate (g2, g1, ’****T****’)"
then simply juxtapose G2 for G1 in the above table, and vice-versa.

SCL Usage Examples

Scenario 1

You have a search area that is a voting district area shape (G1) and you want to find all census blocks that have common adjacent linear boundary (not just a point) and are not inside the voting district. It turns out that none of the relation words (in, touch, cross, overlap, identical, disjoint) will achieve this result. You know that both the voting district and the census blocks we’re looking for are area shapes so instead you use the following SCL syntax:
"dim (g1.boundary,g2.boundary) = linear and intersect (g1.interior, g2.interior) = false"
This statement requires that the two shapes must have co-linear boundary but their interiors do not intersect.

Scenario 2

You have a road segment (G1) and want to find all other road segments that connect to it at their mutual end points. You use the following syntax:
"G1 touch G2" -or- "g1.boundary intersect g2.boundary"

Scenario 3

You want to find all shapes that intersect shape G1 in any way and where there is a lack of topological integrity between the 2 shapes. . You use the following syntax:
"g1 intersects g2 and topoform = false"

Scenario 4

You are retrieving all shapes which overlap a window and so you want to find all shapes that intersect the interior of area shape G1. These shapes could be point, linear, or area shapes so, depending upon the G2 shape type the condition might be OVERLAP, CROSS, or IN. You could use the following syntax:
"g1 overlap g2 or g1 in g2 or g2 in g1 or g2 cross g1"
However, it’s a lot easier to use this syntax instead:
"g1.interior intersects g2" -or- "dim (g1.interior, g2) > null"

Scenario 5

You have a planning zone G1 (area shape) and want to find all land parcels:
wholly or partially inside G1: "dim(g1,interior, g2.interior) = area"
or completely inside G1: "g1 contains g2"
or partially but not wholly inside G1: "g2 overlaps g1"

Scenario 6

You are retrieving any and all shapes from a layer for display in a window (G1):
"dim(g1,interior, g2) != null"
-or-
"dim(g1,interior, g2.interior) != null"
-or-
"relate (g1 g2, ‘****T****’)"
-or-
"dim(g1,g2) = dim(g2)"

NOTES

Obviously shapes may intersect at many different locations and these intersections may occur in different dimensions. Wherever a dimension of intersection is referred to herein it refers to the maximum dimension of intersection which exists.


SCL Keywords and Operators

AND
AREA
BOUNDARY
CONTAIN
CONTAINS
CROSS
CROSSES
DIM
DISJOINT
EQUAL
EQUALS
EXTERIOR
FALSE
G1
G2
IDENTICAL
IN
INSIDE
INTERIOR
INTERSECT
INTERSECTS
INTERSECTION
LINEAR
NIL
NOT
NULL
OR
OVERLAP
OVERLAPS
POINT
TOPOFORM
TOUCH
TOUCHES
TRUE
XOR

Equality Operators

= equality operator, also IDENTICAL operator for shapes
== equality operator, also IDENTICAL operator for shapes
!= inequality operator, also NON-IDENTICAL operator for shapes

Spatial Operators

These operators may be used in lieu of the actual spatial relation word in the expression of spatial relations (not functions).
=! DISJOINT operator
=& OVERLAP operator
=@ IN operator
=* TOUCH operator
=/ CROSS operator
=? INTERSECT operator
Thus the expression "G1 =? G2" is equivalent to "G1 INTERSECT G2".