Global Constraint Catalog: Cdisjoint

5.124. disjoint_sboxes

DESCRIPTION

LINKS

LOGIC

Origin

Geometry, derived from [RandellCuiCohn92]

Constraint

$𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚜𝚋𝚘𝚡𝚎𝚜 (𝙺, 𝙳𝙸𝙼𝚂, 𝙾𝙱𝙹𝙴𝙲𝚃𝚂, 𝚂𝙱𝙾𝚇𝙴𝚂)$

Synonym

$𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ .

Types

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟 - 𝚍𝚟𝚊𝚛)$
$𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟 - 𝚒𝚗𝚝)$
$𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟 - 𝚒𝚗𝚝)$

Arguments

$𝙺$	$𝚒𝚗𝚝$
$𝙳𝙸𝙼𝚂$	$𝚜𝚒𝚗𝚝$
$𝙾𝙱𝙹𝙴𝙲𝚃𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚒𝚍 - 𝚒𝚗𝚝, 𝚜𝚒𝚍 - 𝚍𝚟𝚊𝚛, 𝚡 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$
$𝚂𝙱𝙾𝚇𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚒𝚍 - 𝚒𝚗𝚝, 𝚝 - 𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂, 𝚕 - 𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂)$

Restrictions

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 1

| 𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂 | \geq 1

| 𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟)

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | = 𝙺

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂, 𝚟)

| 𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂 | = 𝙺

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂, 𝚟)

| 𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂 | = 𝙺

𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂 . 𝚟 > 0

𝙺 > 0

𝙳𝙸𝙼𝚂 \geq 0

𝙳𝙸𝙼𝚂 < 𝙺

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙾𝙱𝙹𝙴𝙲𝚃𝚂, [𝚘𝚒𝚍])

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙾𝙱𝙹𝙴𝙲𝚃𝚂, [𝚘𝚒𝚍, 𝚜𝚒𝚍, 𝚡])

𝙾𝙱𝙹𝙴𝙲𝚃𝚂 . 𝚘𝚒𝚍 \geq 1

𝙾𝙱𝙹𝙴𝙲𝚃𝚂 . 𝚘𝚒𝚍 \leq | 𝙾𝙱𝙹𝙴𝙲𝚃𝚂 |

𝙾𝙱𝙹𝙴𝙲𝚃𝚂 . 𝚜𝚒𝚍 \geq 1

𝙾𝙱𝙹𝙴𝙲𝚃𝚂 . 𝚜𝚒𝚍 \leq | 𝚂𝙱𝙾𝚇𝙴𝚂 |

| 𝚂𝙱𝙾𝚇𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙱𝙾𝚇𝙴𝚂, [𝚜𝚒𝚍, 𝚝, 𝚕])

𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚜𝚒𝚍 \geq 1

𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚜𝚒𝚍 \leq | 𝚂𝙱𝙾𝚇𝙴𝚂 |

𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙 (𝚂𝙱𝙾𝚇𝙴𝚂)

Purpose

Holds if, for each pair of objects $(O_{i}, O_{j})$ , $i \neq j$ , $O_{i}$ and $O_{j}$ are disjoint 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 $𝚡$ .

Two objects $O_{i}$ and object $O_{j}$ are disjoint with respect to a set of dimensions depicted by $𝙳𝙸𝙼𝚂$ if and only if for all shifted box $s_{i}$ associated with $O_{i}$ and for all shifted box $s_{j}$ associated with $O_{j}$ there exists at least one dimension $d \in 𝙳𝙸𝙼𝚂$ such that (1) the origin of $s_{i}$ in dimension $d$ is strictly greater than the end of $s_{j}$ in dimension $d$ , or (2) the origin of $s_{j}$ in dimension $d$ is strictly greater than the end of $s_{i}$ in dimension $d$ .

Example

(\begin{matrix} 2, {0, 1}, \\ 〈\begin{matrix} 𝚘𝚒𝚍 - 1 & 𝚜𝚒𝚍 - 1 & 𝚡 - 〈1, 1〉, \\ 𝚘𝚒𝚍 - 2 & 𝚜𝚒𝚍 - 2 & 𝚡 - 〈4, 1〉, \\ 𝚘𝚒𝚍 - 3 & 𝚜𝚒𝚍 - 4 & 𝚡 - 〈2, 4〉 \end{matrix}〉, \\ 〈\begin{matrix} 𝚜𝚒𝚍 - 1 & 𝚝 - 〈0, 0〉 & 𝚕 - 〈1, 2〉, \\ 𝚜𝚒𝚍 - 2 & 𝚝 - 〈0, 0〉 & 𝚕 - 〈1, 1〉, \\ 𝚜𝚒𝚍 - 2 & 𝚝 - 〈1, 0〉 & 𝚕 - 〈1, 3〉, \\ 𝚜𝚒𝚍 - 2 & 𝚝 - 〈0, 2〉 & 𝚕 - 〈1, 1〉, \\ 𝚜𝚒𝚍 - 3 & 𝚝 - 〈0, 0〉 & 𝚕 - 〈3, 1〉, \\ 𝚜𝚒𝚍 - 3 & 𝚝 - 〈0, 1〉 & 𝚕 - 〈1, 1〉, \\ 𝚜𝚒𝚍 - 3 & 𝚝 - 〈2, 1〉 & 𝚕 - 〈1, 1〉, \\ 𝚜𝚒𝚍 - 4 & 𝚝 - 〈0, 0〉 & 𝚕 - 〈1, 1〉 \end{matrix}〉 \end{matrix})

Figure 5.124.1 shows the objects of the example. Since these objects are pairwise disjoint the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚜𝚋𝚘𝚡𝚎𝚜$ constraint holds.

Figure 5.124.1. (D) the three mutually disjoint objects $O_{1}$ , $O_{2}$ , $O_{3}$ of the Example slot respectively assigned shapes $S_{1}$ , $S_{2}$ , $S_{4}$ ; (A), (B), (C) shapes $S_{1}$ , $S_{2}$ , $S_{3}$ and $S_{4}$ are respectively made up from 1, 3, 3 and 1 disjoint shifted box.

Typical

| 𝙾𝙱𝙹𝙴𝙲𝚃𝚂 | > 1

Symmetries

Items of $𝙾𝙱𝙹𝙴𝙲𝚃𝚂$ are permutable.
Items of $𝚂𝙱𝙾𝚇𝙴𝚂$ are permutable.
$𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚕 . 𝚟$ can be decreased to any value $\geq 1$ .

Arg. properties

Suffix-contractible wrt. $𝙾𝙱𝙹𝙴𝙲𝚃𝚂$ .

Remark

One of the eight relations of the Region Connection Calculus [RandellCuiCohn92]. Unlike the $𝚗𝚘𝚗_𝚘𝚟𝚎𝚛𝚕𝚊𝚙_𝚜𝚋𝚘𝚡𝚎𝚜$ constraint, which just prevents objects from overlapping, the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚜𝚋𝚘𝚡𝚎𝚜$ constraint in addition enforces that borders and corners of objects are not directly in contact.

implies: $𝚗𝚘𝚗_𝚘𝚟𝚎𝚛𝚕𝚊𝚙_𝚜𝚋𝚘𝚡𝚎𝚜$ .

Keywords

constraint type: logic.

geometry: geometrical constraint, rcc8.

miscellaneous: obscure.

Logic

• 𝚘𝚛𝚒𝚐𝚒𝚗 (𝙾 1, 𝚂 1, 𝙳) \overset{def}{=} 𝙾 1 . 𝚡 (𝙳) + 𝚂 1 . 𝚝 (𝙳)

• 𝚎𝚗𝚍 (𝙾 1, 𝚂 1, 𝙳) \overset{def}{=} 𝙾 1 . 𝚡 (𝙳) + 𝚂 1 . 𝚝 (𝙳) + 𝚂 1 . 𝚕 (𝙳)

• \begin{matrix} 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚜𝚋𝚘𝚡𝚎𝚜 (𝙳𝚒𝚖𝚜, 𝙾 1, 𝚂 1, 𝙾 2, 𝚂 2) \overset{def}{=} \\ \begin{matrix} \exists 𝙳 \in 𝙳𝚒𝚖𝚜 \\ ⋁ (\begin{matrix} \begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 (𝙾 1, 𝚂 1, 𝙳) > \\ 𝚎𝚗𝚍 (𝙾 2, 𝚂 2, 𝙳) \end{matrix}, \\ \begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 (𝙾 2, 𝚂 2, 𝙳) > \\ 𝚎𝚗𝚍 (𝙾 1, 𝚂 1, 𝙳) \end{matrix} \end{matrix}) \end{matrix} \end{matrix}

• \begin{matrix} 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚘𝚋𝚓𝚎𝚌𝚝𝚜 (𝙳𝚒𝚖𝚜, 𝙾 1, 𝙾 2) \overset{def}{=} \\ \begin{matrix} \forall 𝚂 1 \in 𝚜𝚋𝚘𝚡𝚎𝚜 ([𝙾 1 . 𝚜𝚒𝚍]) \\ \begin{matrix} \forall 𝚂 2 \in 𝚜𝚋𝚘𝚡𝚎𝚜 (\begin{matrix} [\begin{matrix} 𝙾 2 . 𝚜𝚒𝚍 \end{matrix}] \end{matrix}) \\ 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚜𝚋𝚘𝚡𝚎𝚜 (\begin{matrix} 𝙳𝚒𝚖𝚜, \\ 𝙾 1, \\ 𝚂 1, \\ 𝙾 2, \\ 𝚂 2 \end{matrix}) \end{matrix} \end{matrix} \end{matrix}

• \begin{matrix} 𝚊𝚕𝚕_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝 (𝙳𝚒𝚖𝚜, 𝙾𝙸𝙳𝚂) \overset{def}{=} \\ \begin{matrix} \forall 𝙾 1 \in 𝚘𝚋𝚓𝚎𝚌𝚝𝚜 (𝙾𝙸𝙳𝚂) \\ \begin{matrix} \forall 𝙾 2 \in 𝚘𝚋𝚓𝚎𝚌𝚝𝚜 (𝙾𝙸𝙳𝚂) \\ \begin{matrix} \begin{matrix} 𝙾 1 . 𝚘𝚒𝚍 < \\ 𝙾 2 . 𝚘𝚒𝚍 \end{matrix} \Rightarrow \\ 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝_𝚘𝚋𝚓𝚎𝚌𝚝𝚜 (\begin{matrix} 𝙳𝚒𝚖𝚜, \\ 𝙾 1, \\ 𝙾 2 \end{matrix}) \end{matrix} \end{matrix} \end{matrix} \end{matrix}

• 𝚊𝚕𝚕_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝 (𝙳𝙸𝙼𝙴𝙽𝚂𝙸𝙾𝙽𝚂, 𝙾𝙸𝙳𝚂)

Global Constraint Catalog

5. Global Constraint Catalogue

5.124. disjoint_sboxes

Figure 5.124.1. (D) the three mutually disjoint objects O 1 , O 2 , O 3 of the Example slot respectively assigned shapes S 1 , S 2 , S 4 ; (A), (B), (C) shapes S 1 , S 2 , S 3 and S 4 are respectively made up from 1, 3, 3 and 1 disjoint shifted box.

Figure 5.124.1. (D) the three mutually disjoint objects $O_{1}$ , $O_{2}$ , $O_{3}$ of the Example slot respectively assigned shapes $S_{1}$ , $S_{2}$ , $S_{4}$ ; (A), (B), (C) shapes $S_{1}$ , $S_{2}$ , $S_{3}$ and $S_{4}$ are respectively made up from 1, 3, 3 and 1 disjoint shifted box.