Method for determining an intuitively defined spatial relationship among physical entities

Claim 3

A method as in claim 1, wherein said determining step (a) includes the step of determining sets forming representations of a plurality of spatially significant descriptors including at least two of boundary, interior and closure.

Claim 4

A method as in claim 2, wherein said determining step (a) includes the step of determining sets representing boundary and at least one of interior and closure.

Claim 5

A method as in claim 1, wherein said intersection determining step (b) includes the step of determining with said processing means intersections between the sets of elements of: (1) a boundary of one of said spatial entities and a boundary of another of said spatial entities, (2) an interior of said one spatial entity and an interior of said another spatial entity, (3) said boundary of said one spatial entity and said interior of said another spatial entity and (4) said interior of said one spatial entity and said boundary of said another spatial entity.

Claim 6

A method as in claim 4, wherein said interior of said one spatial entity includes the boundary of said one spatial entity and said interior of said another spatial entity includes said boundary of said another spatial entity.

Claim 7

A method as in claim 1, wherein said categorizing step (c) includes the step of categorizing with said processing means said relationships based upon set intersection.

Claim 8

A method as in claim 1, wherein said categorizing step (c) includes the step of categorizing with said processing means said relationships based upon set intersection and symmetric difference.

Claim 9

A method as in claim 1, wherein said categorizing step (c) includes the step of categorizing with said processing means said relationships based upon set intersection and set difference.

Claim 10

A method as in claim 6, wherein said categorizing step (c) also includes categorizing with said processing means said relationships based upon a largest dimension of set intersection.

Claim 11

A method as in claim 7, wherein said categorizing step (c) also categorizes with said processing means said relationships based upon a largest dimension of said set intersection and largest dimension of said symmetric difference.

Claim 12

A method as in claim 8, wherein said categorizing step (c) categorizes with said processing means said relationships also based upon a largest dimension of said set intersection and a largest dimension of said set difference.

Claim 13

A method as in claim 6, wherein said categorizing step (c) categorizes with said processing means said relationships also based upon the number of elements in each set determined in said determining step (a).

Claim 14

A method as in claim 7, wherein said categorizing step (c) categorizes with said processing means said relationships also based upon the number of elements in each set determined in said determining step (a).

Claim 15

A method as in claim 8, wherein said categorizing step (c) categorizes with said processing means said relationships also based upon the number of elements in each set determined in said determining step (a).

Claim 16

A method as in claim 1, wherein said combining step (d) includes the step of generating with said processing means a unique one of a plurality of codes, based upon said categorizing step (c), which uniquely identifies said relationship.

Claim 17

A method as in claim 15, wherein said determining step (e) includes the step of determining with said processing means said unique code matches any one of a plurality of desired codes used to define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 18

A method as in claim 1 further comprising the step of selecting said desired mathematical relationships which together define said specified spatial relationship.

Claim 21

A method as in claim 18, wherein said determining step (b), when determining elements forming a representation of said interior, also includes elements forming a representation of said boundary for each of said first and second spatial entities.

Claim 22

A method as in claim 18, wherein said categorizing step (e) categorizes with said processing means relationships based upon said set intersection and said symmetric difference.

Claim 23

A method as in claim 18, wherein said categorizing step (e) categorizes with said processing means said relationships based upon said set intersection and said set difference.

Claim 24

A method as in claim 18, wherein said categorizing step (e) categorizes with said processing means said relationships based upon at least set intersection and the largest dimension of intersection.

Claim 25

A method as in claim 20, wherein said categorizing step (e) categorizes with said processing means relationships also based upon a largest dimension of said intersection and a largest dimension of symmetric difference.

Claim 26

A method as in claim 21, wherein said categorizing step (e) categorizes with said processing means relationships also based upon a largest dimension of set intersection and a largest dimension of set difference.

Claim 27

A method as in claim 18, further comprising the step of selecting said desired codes which together define said specified spatial relationship.

Claim 28

Apparatus for determining whether a specified spatial relationship exists among physical spatial entities comprising: means for storing representations of said spatial entities; means, coupled to said storing means, for entering said representations of said spatial entities into said storing means; and analyzing means, coupled to said storing means, for: (1) determining sets of elements forming a representation of each of a plurality of spatially significant descriptors which describe each of said physical spatial entities; (2) determining intersections between the sets of elements of every combination of descriptors between different ones of said spatial entities; (3) categorizing relationships between every combination of descriptors based upon the intersections of the corresponding sets of elements and the descriptors themselves; (4) combining said categorized relationships to determine a unique mathematical relationship that exists between said spatial entities; and (5) determining whether said unique mathematical relationship between said spatial entities matches any one of a plurality of desired mathematical relationships which collectively define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 29

Apparatus for determining whether a specified spatial relationship exists among physical spatial entities comprising: means for storing representations of said spatial entities; means, coupled to said storing means, for entering said representations of said spatial entities into said storing means; and analyzing means, coupled to said storing means, for: (1) determining sets of elements forming a representation of each of a plurality of spatially significant descriptors which describe each of said physical spatial entities; (2) determining intersections between the sets of elements of every combination of descriptors between different ones of said spatial entities; (3) categorizing relationships between every combination of descriptors based upon the intersections of the corresponding sets of elements and the descriptors themselves; (4) combining said categorized relationships to determine a unique mathematical relationship that exists between said spatial entities; and (5) determining whether said unique mathematical relationship between said spatial entities matches any one of a plurality of desired mathematical relationships which collectively define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 30

Apparatus as in claim 26, wherein said analyzing means, when performing said set determining function determines sets forming representations of a plurality of spatially significant descriptors including at least two of boundary, interior and closure.

Claim 31

Apparatus as in claim 27, wherein said analyzing means, when performing said set determining function, determines sets representing boundary and at least one of interior and closure.

Claim 32

Apparatus as in claim 26, wherein said analyzing means, when performing said intersection determining function, determines intersections between the sets of elements of: (1) a boundary of one of said spatial entities and a boundary of another of said spatial entities, (2) an interior of said one spatial entity and an interior of said another spatial entity, (3) said boundary of said one spatial entity and said interior of said another spatial entity and (4) said interior of said one spatial entity and said boundary of said another spatial entity.

Claim 33

Apparatus as in claim 29, wherein said interior of said one spatial entity includes the boundary of said one spatial entity and said interior of said another spatial entity includes said boundary of said another spatial entity.

Claim 34

Apparatus as in claim 26, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon set intersection.

Claim 35

Apparatus as in claim 26, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon set intersection and symmetric difference.

Claim 36

Apparatus as in claim 26, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon set intersection and set difference.

Claim 37

Apparatus as in claim 31, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon a largest dimension of set intersection.

Claim 38

Apparatus as in claim 32, wherein said analyzing means, when performing said categorizing function, also categorizes said relationships based upon a largest dimension of said set intersection and largest dimension of said symmetric difference.

Claim 39

Apparatus as in claim 33, wherein said analyzing means, when performing said categorizing function, categorizes said relationships also based upon a largest dimension of said set intersection and a largest dimension of said set difference.

Claim 40

Apparatus as in claim 31, wherein said analyzing means, when performing said categorizing function, categorizes said relationships also based upon the number of elements in each of said sets.

Claim 41

Apparatus as in claim 32, wherein said analyzing means, when performing said categorizing function, categorizes said relationships also based upon the number of elements in each of said sets.

Claim 42

Apparatus as in claim 33, wherein said analyzing means, when performing said categorizing function, categorizes said relationships also based upon the number of elements in each of said sets.

Claim 43

Apparatus as in claim 26, wherein said analyzing means, when performing said combining function, generates a unique one of a plurality of codes, based upon said categorizing function, which uniquely identifies said relationship.

Claim 44

Apparatus as in claim 40, wherein said analyzing means, when performing said relationship determining function, determines whether said unique code matches any one of a plurality of desired codes used to define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 45

Apparatus as in claim 26, wherein said analyzing means also selects said desired mathematical relationships which together define said specified spatial relationship.

Claim 46

Apparatus for determining whether a specific spatial relationship exists between first and second physical spatial entities comprising: means for storing representations of said physical spatial entities; means, coupled to said storing means, for entering said representations into said storing means; and analyzing means, coupled to said storing means, for: (1) determining sets of elements forming a representation of a boundary for each of said first and second spatial entities; (2) determining sets of elements forming a representation of an interior for each of said first and second spatial entities; (3) determining intersections between the sets of elements of: (a) said boundary of said first spatial entity and said boundary of said second spatial entity, (b) said interior of said first spatial entity and said interior of said second spatial entity, (c) said boundary of said first spatial entity and said interior of said second spatial entity and (d) said interior of said first spatial entity and said boundary of said second spatial entity; (4) determining the number of elements in each set specifying the boundary and interior of said first and second spatial entities; (5) categorizing relationships between each of boundary and interior of said first spatial entity and both of boundary and interior of said second spatial entity, respectively, based upon at least one of set intersection, symmetric difference, set differences and dimension, said categorizing being based on said intersection determining function and said data generating function; (6) generating a unique one of a plurality of codes, based upon said categorization, which uniquely identifies said relationships; and (7) determining whether said unique code matches any one of a plurality of desired codes which collectively define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 47

Apparatus for determining whether a specific spatial relationship exists between first and second physical spatial entities comprising: means for storing representations of said physical spatial entities; means, coupled to said storing means, for entering said representations into said storing means; and analyzing means, coupled to said storing means, for: (1) determining sets of elements forming a representation of a boundary for each of said first and second spatial entities; (2) determining sets of elements forming a representation of an interior for each of said first and second spatial entities; (3) determining intersections between the sets of elements of: (a) said boundary of said first spatial entity and said boundary of said second spatial entity, (b) said interior of said first spatial entity and said interior of said second spatial entity, (c) said boundary of said first spatial entity and said interior of said second spatial entity and (d) said interior of said first spatial entity and said boundary of said second spatial entity; (4) determining the number of elements in each set specifying the boundary and interior of said first and second spatial entities; (5) categorizing relationships between each of boundary and interior of said first spatial entity and both of boundary and interior of said second spatial entity, respectively, based upon at least one of set intersection, symmetric difference, set differences and dimension, said categorizing being based on said intersection determining function and said data generating function; (6) generating a unique one of a plurality of codes, based upon said categorization, which uniquely identifies said relationships; and (7) determining whether said unique code matches any one of a plurality of desired codes which collectively define said specified spatial relationship, to determine that said spatial entities have said specified spatial relationship.

Claim 48

Apparatus as in claim 43, wherein said analyzing means, when determining elements forming a representation of said interior also includes elements forming a representation of said boundary for each of said first and second spatial entities.

Claim 49

Apparatus as in claim 43, wherein said analyzing means, when performing said categorizing function, categorizes relationships based upon said set intersection and said symmetric difference.

Claim 50

Apparatus as in claim 43, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon said set intersection and said set difference.

Claim 51

Apparatus as in claim 43, wherein said analyzing means, when performing said categorizing function, categorizes said relationships based upon at least set intersection and the largest dimension of intersection.

Claim 52

Apparatus as in claim 45, wherein said analyzing means, when performing said categorizing function, categorizes relationships also based upon a largest dimension of said intersection and a largest dimension of symmetric difference.

Claim 53

Apparatus as in claim 46, wherein said analyzing means, when performing said categorizing function, categorizes relationships also based upon a largest dimension of set intersection and a largest dimension of set difference.

Claim 54

Apparatus as in claim 43, wherein said analyzing means also selects said desired codes which together define said specified spatial relationship.