5.270. place_in_pyramid

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

πš™πš•πšŠπšŒπšŽ_πš’πš—_πš™πš’πš›πšŠπš–πš’πš(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚,πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼)

Type
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’-πšπšŸπšŠπš›,πšœπš’πš£-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Arguments
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πšπš‘-π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄)
πš…π™΄πšπšƒπ™Έπ™²π™°π™»_π™³π™Έπ™Όπš’πš—πš
Restrictions
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄|>0
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄,[πš˜πš›πš’,πšœπš’πš£,πšŽπš—πš])
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšœπš’πš£β‰₯0
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πš˜πš›πš’β‰€π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšŽπš—πš
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚,πš˜πš›πšπš‘)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚,πš˜πš›πšπš‘)
πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼β‰₯1
πšπš’πšπšπš—(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚)
Purpose

For each pair of orthotopes (O 1 ,O 2 ) of the collection π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚, O 1 and O 2 do not overlap (two orthotopes do not overlap if there exists at least one dimension where their projections do not overlap). In addition, each orthotope of the collection π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚ should be supported by one other orthotope or by the ground. The vertical dimension is given by the parameter πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼.

Example
πš˜πš›πšπš‘-πš˜πš›πš’-1πšœπš’πš£-3πšŽπš—πš-4,πš˜πš›πš’-1πšœπš’πš£-2πšŽπš—πš-3,πš˜πš›πšπš‘-πš˜πš›πš’-1πšœπš’πš£-2πšŽπš—πš-3,πš˜πš›πš’-3πšœπš’πš£-3πšŽπš—πš-6,πš˜πš›πšπš‘-πš˜πš›πš’-5πšœπš’πš£-6πšŽπš—πš-11,πš˜πš›πš’-1πšœπš’πš£-2πšŽπš—πš-3,πš˜πš›πšπš‘-πš˜πš›πš’-5πšœπš’πš£-2πšŽπš—πš-7,πš˜πš›πš’-3πšœπš’πš£-2πšŽπš—πš-5,πš˜πš›πšπš‘-πš˜πš›πš’-8πšœπš’πš£-3πšŽπš—πš-11,πš˜πš›πš’-3πšœπš’πš£-2πšŽπš—πš-5,πš˜πš›πšπš‘-πš˜πš›πš’-8πšœπš’πš£-2πšŽπš—πš-10,πš˜πš›πš’-5πšœπš’πš£-2πšŽπš—πš-7,2

FigureΒ 5.270.1 depicts the placement associated with the example, where the i th item of the π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚ collection is represented by the rectangle Ri. The πš™πš•πšŠπšŒπšŽ_πš’πš—_πš™πš’πš›πšŠπš–πš’πš constraint holds since the rectangles do not overlap and since rectangles R1, R2, R3, R4, R5, and R6 are respectively supported by the ground, R1, the ground, R3, R3, and R5.

Figure 5.270.1. Solution corresponding to the example
ctrs/place_in_pyramid1
Symmetry

Items of π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚ are permutable.

Usage

The πšπš’πšπšπš— constraint is not enough if one wants to produce a placement where no orthotope floats in the air. This constraint is usually handled with a heuristic during the enumeration phase.

See also

used in graph description: πš˜πš›πšπš‘_πš˜πš—_πšπš‘πšŽ_πšπš›πš˜πšžπš—πš, πš˜πš›πšπš‘_πš˜πš—_πšπš˜πš™_𝚘𝚏_πš˜πš›πšπš‘.

Keywords

geometry: geometrical constraint, non-overlapping, orthotope.

Arc input(s)

π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ1,πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ2)

Arc arity
Arc constraint(s)
β‹β‹€πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ1.πš”πšŽπš’=πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ2.πš”πšŽπš’,πš˜πš›πšπš‘_πš˜πš—_πšπš‘πšŽ_πšπš›πš˜πšžπš—πš(πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ1.πš˜πš›πšπš‘,πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼),β‹€πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ1.πš”πšŽπš’β‰ πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ2.πš”πšŽπš’,πš˜πš›πšπš‘_πš˜πš—_πšπš˜πš™_𝚘𝚏_πš˜πš›πšπš‘πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ1.πš˜πš›πšπš‘,πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽπšœ2.πš˜πš›πšπš‘,πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚|

Graph model

The arc constraint of the graph constraint enforces one of the following conditions:

  • If the arc connects the same orthotope O then the ground directly supports O,

  • Otherwise, if we have an arc from an orthotope O 1 to a distinct orthotope O 2 , the condition is: O 1 is on top of O 2 (i.e.,Β in all dimensions, except dimension πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼, the projection of O 1 is included in the projection of O 2 , while in dimension πš…π™΄πšπšƒπ™Έπ™²π™°π™»_𝙳𝙸𝙼 the projection of O 1 is located after the projection of O 2 ).

PartsΒ (A) andΒ (B) of FigureΒ 5.270.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.270.2. Initial and final graph of the πš™πš•πšŠπšŒπšŽ_πš’πš—_πš™πš’πš›πšŠπš–πš’πš constraint
ctrs/place_in_pyramidActrs/place_in_pyramidB
(a) (b)