Method for determining an intuitively defined spatial relationship among physical entities

• US 4,969,114 A
• Filed: 11/14/1988
• Issued: 11/06/1990
• Est. Priority Date: 11/14/1988
• Status: Expired due to Term

• Current Assignee: Intergraph Corporation (Hexagon AB)
• Original Assignee: Intergraph Corporation (Hexagon AB)
• Inventors: Oliver, Dianne L., Cooke, Gary W., Herring, John R.
• Primary Examiner(s): Chin, Gary
• Assistant Examiner(s): Melnick, S. A.
• Application Number:
  US07/270,255
• Time in Patent Office: 722 Days
• Field of Search: 364/570, 364/420, 382/26, 382/25, 382/23
• US Class Current: 703/2
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

Apparatus and method for determining whether a specific spatial relationship exists among physical spatial entities. First, spatially significant descriptors such as the interior and boundary of the physical spatial entities are selected and sets of elements forming a representation of each of the descriptors for each spatial entity is determined. Intersections are then determined between the sets of elements for every combination of descriptors and these intersections are categorized. The categorized relationships are then combined to determine a unique mathematical relationship between the spatial entities. The specific spatial relationship to be analyzed is broken down into the set of desired mathetmatical relationships. According to the present invention, it is then determined whether the unique mathematical relationship between the spatial entities matches any of the desired mathematical relationships used to define the specific relationship, to determine whether or not the spatial entities have the specific relationship.

Claims

1. A method for determining whether a specified spatial relationship exists among physical spatial entities comprising the steps of:

(a) determining sets of elements forming a representation of each of a plurality of spatially significant descriptors which describe each of said physical spatial entities;

(b) determining with processing means intersections between the sets of elements of every combination of descriptors between different ones of said spatial entities;

(c) categorizing with said processing means relationships between every combination of descriptors based upon the intersections of the corresponding sets of elements and the descriptors themselves;

(d) combining with said processing means said relationships categorized in said step (c) to determine a unique mathematical relationship that exists between said spatial entities; and

(e) determining with said processing means 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

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 and symmetric difference.

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 set difference.

9. 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.

10. 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.

11. 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.

12. 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).

13. 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).

14. 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).

15. 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.

16. 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.

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

18. A method for determining whether a specific spatial relationship exists between first and second physical spatial entities comprising the steps of:

(a) determining, with processing mans, sets of elements forming a representation of a boundary for each of said first and second spatial entities;

(b) determining with processing means sets of elements forming a representation of an interior for each of said first and second spatial entities;

(c) determining with said processing means intersections between the sets of elements of;

(1) said boundary of said first spatial entity and said boundary of said second spatial entity, (2) said interior of said first spatial entity and said interior of said second spatial entity;

(3) said boundary of said first spatial entity and said interior of said second spatial entity and (4) said interior of said first spatial entity and said boundary of said second spatial entity;

(d) determining with said processing means the number of elements in each set specifying the boundary and interior of said first and second spatial entities;

(e) categorizing with said processing means 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 determining step (c) and said generating step (d);

(f) generating with said processing means a unique one of a plurality of codes, based upon said categorizing step (e), which uniquely identifies said relationships; and

(g) determining with said processing means 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

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

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

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

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

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

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

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

43. 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.

44. 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.

45. 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.

46. 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.

47. 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.

48. 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.

49. 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.

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