5.263. overlap_sboxes

DESCRIPTIONLINKSLOGIC
Origin

Geometry, derived from [RandellCuiCohn92]

Constraint

πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœ(𝙺,π™³π™Έπ™Όπš‚,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚)

Synonym

πš˜πšŸπšŽπš›πš•πšŠπš™.

Types
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πšπšŸπšŠπš›)
π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
Arguments
π™Ίπš’πš—πš
π™³π™Έπ™Όπš‚πšœπš’πš—πš
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš’πš-πš’πš—πš,πšœπš’πš-πš’πš—πš,𝚑-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
πš‚π™±π™Ύπš‡π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšœπš’πš-πš’πš—πš,𝚝-π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,πš•-π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝚟)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,𝚟)
|π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚,𝚟)
|π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚|=𝙺
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚.𝚟>0
𝙺>0
π™³π™Έπ™Όπš‚β‰₯0
π™³π™Έπ™Όπš‚<𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πš˜πš’πš,πšœπš’πš,𝚑])
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰€|π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™±π™Ύπš‡π™΄πš‚,[πšœπš’πš,𝚝,πš•])
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰₯1
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
Purpose

Holds if, for each pair of objects (O i ,O j ), i<j, O i overlaps O j with respect to a set of dimensions depicted by π™³π™Έπ™Όπš‚. O i and O j are objects that take a shape among a set of shapes. Each shape is defined as a finite set of shifted boxes, where each shifted box is described by a box in a 𝙺 -dimensional space at a given offset (from the origin of the shape) with given sizes. More precisely, a shifted box is an entity defined by its shape id πšœπš’πš, shift offset 𝚝, and sizes πš•. Then, a shape is defined as the union of shifted boxes sharing the same shape id. An object is an entity defined by its unique object identifier πš˜πš’πš, shape id πšœπš’πš and origin 𝚑.

An object O i overlaps an object O j with respect to a set of dimensions depicted by π™³π™Έπ™Όπš‚ if and only if, there exists a shifted box s i associated with O i and there exists a shifted box s j associated with O j , such that (1)Β there exists a dimension dβˆˆπ™³π™Έπ™Όπš‚ where the end of O i in dimension d is strictly greater than the start of O j in dimension d, and (2)Β the end of O j in dimension d is strictly greater than the start of O i in dimension d.

Example
2,{0,1},πš˜πš’πš-1πšœπš’πš-1𝚑-1,1,πš˜πš’πš-2πšœπš’πš-2𝚑-3,2,πš˜πš’πš-3πšœπš’πš-3𝚑-2,4,πšœπš’πš-1𝚝-0,0πš•-4,5,πšœπš’πš-2𝚝-0,0πš•-3,3,πšœπš’πš-3𝚝-0,0πš•-2,1

FigureΒ 5.263.1 shows the objects of the example. Since O 1 overlaps both O 2 and O 3 , and since O 2 overlaps O 3 , the πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœ constraint holds.

Figure 5.263.1. The three objects of the example
ctrs/overlap_sboxes1
Symmetries
  • Items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ are permutable.

  • Items of πš‚π™±π™Ύπš‡π™΄πš‚ are permutable.

  • Items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.𝚑, πš‚π™±π™Ύπš‡π™΄πš‚.𝚝 and πš‚π™±π™Ύπš‡π™΄πš‚.πš• are permutable (same permutation used).

  • πš‚π™±π™Ύπš‡π™΄πš‚.πš•.𝚟 can be increased.

Remark

One of the eight relations of the Region Connection CalculusΒ [RandellCuiCohn92].

See also

common keyword: πšŒπš˜πš—πšπšŠπš’πš—πšœ_πšœπš‹πš˜πš‘πšŽπšœ, πšŒπš˜πšŸπšŽπš›πšŽπšπš‹πš’_πšœπš‹πš˜πš‘πšŽπšœ, πšŒπš˜πšŸπšŽπš›πšœ_πšœπš‹πš˜πš‘πšŽπšœ, πšπš’πšœπš“πš˜πš’πš—πš_πšœπš‹πš˜πš‘πšŽπšœ, πšŽπššπšžπšŠπš•_πšœπš‹πš˜πš‘πšŽπšœ, πš’πš—πšœπš’πšπšŽ_πšœπš‹πš˜πš‘πšŽπšœ, πš–πšŽπšŽπš_πšœπš‹πš˜πš‘πšŽπšœΒ (rcc8), πš—πš˜πš—_πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœΒ (geometrical constraint,logic).

Keywords

constraint type: logic.

geometry: geometrical constraint, rcc8.

Logic
β€’ πš˜πš›πš’πšπš’πš—(𝙾1,πš‚1,𝙳)= def 𝙾1.𝚑(𝙳)+πš‚1.𝚝(𝙳)
β€’ πšŽπš—πš(𝙾1,πš‚1,𝙳)= def 𝙾1.𝚑(𝙳)+πš‚1.𝚝(𝙳)+πš‚1.πš•(𝙳)
β€’ πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœ(π™³πš’πš–πšœ,𝙾1,πš‚1,𝙾2,πš‚2)= def βˆ€π™³βˆˆπ™³πš’πš–πšœβ‹€πšŽπš—πš(𝙾1,πš‚1,𝙳)>πš˜πš›πš’πšπš’πš—(𝙾2,πš‚2,𝙳),πšŽπš—πš(𝙾2,πš‚2,𝙳)>πš˜πš›πš’πšπš’πš—(𝙾1,πš‚1,𝙳)
β€’ πš˜πšŸπšŽπš›πš•πšŠπš™_πš˜πš‹πš“πšŽπšŒπšπšœ(π™³πš’πš–πšœ,𝙾1,𝙾2)= def βˆ€πš‚1βˆˆπšœπš‹πš˜πš‘πšŽπšœ([𝙾1.πšœπš’πš])βˆƒπš‚2βˆˆπšœπš‹πš˜πš‘πšŽπšœπ™Ύ2.πšœπš’πšπš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœπ™³πš’πš–πšœ,𝙾1,πš‚1,𝙾2,πš‚2
β€’ πšŠπš•πš•_πš˜πšŸπšŽπš›πš•πšŠπš™(π™³πš’πš–πšœ,π™Ύπ™Έπ™³πš‚)= def βˆ€π™Ύ1βˆˆπš˜πš‹πš“πšŽπšŒπšπšœ(π™Ύπ™Έπ™³πš‚)βˆ€π™Ύ2βˆˆπš˜πš‹πš“πšŽπšŒπšπšœ(π™Ύπ™Έπ™³πš‚)𝙾1.πš˜πš’πš<𝙾2.πš˜πš’πšβ‡’πš˜πšŸπšŽπš›πš•πšŠπš™_πš˜πš‹πš“πšŽπšŒπšπšœπ™³πš’πš–πšœ,𝙾1,𝙾2
β€’ πšŠπš•πš•_πš˜πšŸπšŽπš›πš•πšŠπš™(π™³π™Έπ™Όπ™΄π™½πš‚π™Έπ™Ύπ™½πš‚,π™Ύπ™Έπ™³πš‚)