Global Constraint Catalog: Coverlap

5.314. overlap_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 < 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 \in 𝙳𝙸𝙼𝚂$ 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

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

Figure 5.314.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.314.1. (D) the three mutually overlapping objects $O_{1}$ , $O_{2}$ , $O_{3}$ of the Example slot respectively assigned shapes $S_{1}$ , $S_{2}$ , $S_{3}$ ; (A), (B), (C) shapes $S_{1}$ , $S_{2}$ and $S_{3}$ are made up from a single shifted box.

Typical

| 𝙾𝙱𝙹𝙴𝙲𝚃𝚂 | > 1

Symmetries

Items of $𝙾𝙱𝙹𝙴𝙲𝚃𝚂$ are permutable.
Items of $𝚂𝙱𝙾𝚇𝙴𝚂$ are permutable.
Items of $𝙾𝙱𝙹𝙴𝙲𝚃𝚂 . 𝚡$ , $𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚝$ and $𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚕$ are permutable (same permutation used).
$𝚂𝙱𝙾𝚇𝙴𝚂 . 𝚕 . 𝚟$ can be increased.

Arg. properties