Global Constraint Catalog: Ctwo_orth_are_in

5.408. two_orth_are_in_contact

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Roach84], used for defining $𝚘𝚛𝚝𝚑𝚜_𝚊𝚛𝚎_𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍$ .

Constraint

$𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝 (𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2)$

Type

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒 - 𝚍𝚟𝚊𝚛, 𝚜𝚒𝚣 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛)

Arguments

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$	$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴$
$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$	$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴$

Restrictions

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝

(2, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴, [𝚘𝚛𝚒, 𝚜𝚒𝚣, 𝚎𝚗𝚍])

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚜𝚒𝚣 > 0

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚘𝚛𝚒 \leq 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚎𝚗𝚍

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 | = | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2 |

𝚘𝚛𝚝𝚑_𝚕𝚒𝚗𝚔_𝚘𝚛𝚒_𝚜𝚒𝚣_𝚎𝚗𝚍

(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1)

𝚘𝚛𝚝𝚑_𝚕𝚒𝚗𝚔_𝚘𝚛𝚒_𝚜𝚒𝚣_𝚎𝚗𝚍

(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2)

Purpose

Enforce the following conditions on two orthotopes $O_{1}$ and $O_{2}$ :

For all dimensions $i$ , except one dimension, the projections of $O_{1}$ and $O_{2}$ onto $i$ have a non-empty intersection.
For all dimensions $i$ , the distance between the projections of $O_{1}$ and $O_{2}$ onto $i$ is equal to 0.

Example

(\begin{matrix} 〈𝚘𝚛𝚒 - 1 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 4, 𝚘𝚛𝚒 - 5 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 7〉, \\ 〈𝚘𝚛𝚒 - 3 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 5, 𝚘𝚛𝚒 - 2 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 5〉 \end{matrix})

Figure 5.408.1 shows the two rectangles of the example. The $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint holds since the two rectangles are in contact: the contact is depicted by a pink line-segment.

Figure 5.408.1. The two rectangles that are in contact of the Example slot where the contact is shown in pink

Typical

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 | > 1

Symmetries

Arguments are permutable w.r.t. permutation $(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2)$ .
Items of $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ and $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$ are permutable (same permutation used).

Used in

$𝚘𝚛𝚝𝚑𝚜_𝚊𝚛𝚎_𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: logic.

filtering: arc-consistency.

geometry: geometrical constraint, touch, contact, non-overlapping, orthotope.

Arc input(s)

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

(=) \mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2)

Arc arity

Arc constraint(s)

• 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚎𝚗𝚍 > 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2 . 𝚘𝚛𝚒

• 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2 . 𝚎𝚗𝚍 > 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚘𝚛𝚒

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 | - 1

Arc input(s)

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

(=) \mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2)

Arc arity

Arc constraint(s)

𝚖𝚊𝚡 (\begin{matrix} 0, \begin{matrix} 𝚖𝚊𝚡 (𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚘𝚛𝚒, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2 . 𝚘𝚛𝚒) - \\ 𝚖𝚒𝚗 (𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚎𝚗𝚍, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2 . 𝚎𝚗𝚍) \end{matrix} \end{matrix}) = 0

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 |

Graph model

Parts (A) and (B) of Figure 5.408.2 respectively show the initial and final graph associated with the first graph constraint of the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the unique arc of the final graph is stressed in bold. It corresponds to the fact that the projection onto dimension 1 of the two rectangles of the example overlap.

Figure 5.408.2. Initial and final graph of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint


(a)	(b)

Signature

Consider the second graph constraint. Since we use the arc generator $𝑃𝑅𝑂𝐷𝑈𝐶𝑇 (=)$ on the collections $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ and $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$ , and because of the restriction $| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 | = | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2 |$ , the maximum number of arcs of the corresponding final graph is equal to $| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 |$ . Therefore we can rewrite the graph property $𝐍𝐀𝐑𝐂 = | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 |$ to $𝐍𝐀𝐑𝐂 \geq | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 |$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton

Figure 5.408.3 depicts the automaton associated with the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint. Let $𝙾𝚁𝙸 1_{i}$ , $𝚂𝙸𝚉 1_{i}$ and $𝙴𝙽𝙳 1_{i}$ respectively be the $𝚘𝚛𝚒$ , the $𝚜𝚒𝚣$ and the $𝚎𝚗𝚍$ attributes of the $i^{t h}$ item of the $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ collection. Let $𝙾𝚁𝙸 2_{i}$ , $𝚂𝙸𝚉 2_{i}$ and $𝙴𝙽𝙳 2_{i}$ respectively be the $𝚘𝚛𝚒$ , the $𝚜𝚒𝚣$ and the $𝚎𝚗𝚍$ attributes of the $i^{t h}$ item of the $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$ collection. To each sextuple $(𝙾𝚁𝙸 1_{i}, 𝚂𝙸𝚉 1_{i}, 𝙴𝙽𝙳 1_{i}, 𝙾𝚁𝙸 2_{i}, 𝚂𝙸𝚉 2_{i}, 𝙴𝙽𝙳 2_{i})$ corresponds a signature variable $S_{i}$ , which takes its value in ${0, 1, 2}$ , as well as the following signature constraint:

$((𝚂𝙸𝚉 1_{i} > 0) \land (𝚂𝙸𝚉 2_{i} > 0) \land (𝙴𝙽𝙳 1_{i} > 𝙾𝚁𝙸 2_{i}) \land (𝙴𝙽𝙳 2_{i} > 𝙾𝚁𝙸 1_{i})) \Leftrightarrow S_{i} = 0$

$((𝚂𝙸𝚉 1_{i} > 0) \land (𝚂𝙸𝚉 2_{i} > 0) \land (𝙴𝙽𝙳 1_{i} = 𝙾𝚁𝙸 2_{i} \lor 𝙴𝙽𝙳 2_{i} = 𝙾𝚁𝙸 1_{i})) \Leftrightarrow S_{i} = 1$ .

Figure 5.408.3. Automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint

Figure 5.408.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.408. two_orth_are_in_contact

Figure 5.408.1. The two rectangles that are in contact of the Example slot where the contact is shown in pink

Figure 5.408.2. Initial and final graph of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝 constraint

Figure 5.408.3. Automaton of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝 constraint

Figure 5.408.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝 constraint

Figure 5.408.2. Initial and final graph of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint

Figure 5.408.3. Automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint

Figure 5.408.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚊𝚛𝚎_𝚒𝚗_𝚌𝚘𝚗𝚝𝚊𝚌𝚝$ constraint