5.85. cumulative_two_d

DESCRIPTIONLINKS
Origin

Inspired by πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ and πšπš’πšπšπš—.

Constraint

πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍(πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚,π™»π™Έπ™Όπ™Έπšƒ)

Arguments
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πšœπšπšŠπš›πš1-πšπšŸπšŠπš›,πšœπš’πš£πšŽ1-πšπšŸπšŠπš›,πš•πšŠπšœπš1-πšπšŸπšŠπš›,πšœπšπšŠπš›πš2-πšπšŸπšŠπš›,πšœπš’πš£πšŽ2-πšπšŸπšŠπš›,πš•πšŠπšœπš2-πšπšŸπšŠπš›,πš‘πšŽπš’πšπš‘πš-πšπšŸπšŠπš›
π™»π™Έπ™Όπ™Έπšƒπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚,[πšœπšπšŠπš›πš1,πšœπš’πš£πšŽ1,πš•πšŠπšœπš1])
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚,[πšœπšπšŠπš›πš2,πšœπš’πš£πšŽ2,πš•πšŠπšœπš2])
πš›πšŽπššπšžπš’πš›πšŽπš(πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚,πš‘πšŽπš’πšπš‘πš)
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πšœπš’πš£πšŽ1β‰₯0
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πšœπš’πš£πšŽ2β‰₯0
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πš‘πšŽπš’πšπš‘πšβ‰₯0
π™»π™Έπ™Όπ™Έπšƒβ‰₯0
Purpose

Consider a set β„› of rectangles described by the πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚ collection. Enforces that at each point of the plane, the cumulated height of the set of rectangles that overlap that point, does not exceed a given limit.

Example
πšœπšπšŠπš›πš1-1πšœπš’πš£πšŽ1-4πš•πšŠπšœπš1-4πšœπšπšŠπš›πš2-3πšœπš’πš£πšŽ2-3πš•πšŠπšœπš2-5πš‘πšŽπš’πšπš‘πš-4,πšœπšπšŠπš›πš1-3πšœπš’πš£πšŽ1-2πš•πšŠπšœπš1-4πšœπšπšŠπš›πš2-1πšœπš’πš£πšŽ2-2πš•πšŠπšœπš2-2πš‘πšŽπš’πšπš‘πš-2,πšœπšπšŠπš›πš1-1πšœπš’πš£πšŽ1-2πš•πšŠπšœπš1-2πšœπšπšŠπš›πš2-1πšœπš’πš£πšŽ2-2πš•πšŠπšœπš2-2πš‘πšŽπš’πšπš‘πš-3,πšœπšπšŠπš›πš1-4πšœπš’πš£πšŽ1-1πš•πšŠπšœπš1-4πšœπšπšŠπš›πš2-1πšœπš’πš£πšŽ2-1πš•πšŠπšœπš2-1πš‘πšŽπš’πšπš‘πš-1,4

PartΒ (A) of FigureΒ 5.85.1 shows the 4 parallelepipeds of height 4, 2, 3 and 1 associated with the items of the πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚ collection (parallelepipeds since each rectangle also has a height). PartΒ (B) gives the corresponding cumulated 2-dimensional profile, where each number is the cumulated height of all the rectangles that contain the corresponding region. The πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍 constraint holds since the highest peak of the cumulated 2-dimensional profile does not exceed the upper limit 4 imposed by the last argument of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍 constraint.

Figure 5.85.1. Two representations of a 2-dimensional cumulated profile
ctrs/cumulative_two_d1
Typical
|πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚|>1
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πšœπš’πš£πšŽ1>0
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πšœπš’πš£πšŽ2>0
πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πš‘πšŽπš’πšπš‘πš>0
π™»π™Έπ™Όπ™Έπšƒ<πšœπšžπš–(πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πš‘πšŽπš’πšπš‘πš)
Symmetries
  • Items of πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚ are permutable.

  • Attributes of πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚ are permutable w.r.t. permutation (πšœπšπšŠπš›πš1,πšœπšπšŠπš›πš2) (πšœπš’πš£πšŽ1,πšœπš’πš£πšŽ2) (πš•πšŠπšœπš1,πš•πšŠπšœπš2) (πš‘πšŽπš’πšπš‘πš) (permutation applied to all items).

  • πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.πš‘πšŽπš’πšπš‘πš can be decreased to any value β‰₯0.

  • One and the same constant can be added to the πšœπšπšŠπš›πš1 and πš•πšŠπšœπš1 attributes of all items of πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.

  • One and the same constant can be added to the πšœπšπšŠπš›πš2 and πš•πšŠπšœπš2 attributes of all items of πšπ™΄π™²πšƒπ™°π™½π™Άπ™»π™΄πš‚.

  • π™»π™Έπ™Όπ™Έπšƒ can be increased.

Usage

The πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍 constraint is a necessary condition for the πšπš’πšπšπš— constraint in 3 dimensions (i.e.,Β the placement of parallelepipeds in such a way that they do not pairwise overlap and that each parallelepiped has his sides parallel to the sides of the placement space).

Algorithm

A first natural way to handle this constraint would be to accumulate the compulsory partΒ [Lahrichi82] of the different rectangles in a quadtreeΒ [Samet89]. To each leave of the quadtree we associate the cumulated height of the rectangles containing the corresponding region.

Systems

geost in Choco.

See also

related: πšπš’πšπšπš—Β (πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍 is a necessary condition for πšπš’πšπšπš—: forget one dimension when the number of dimensions is equal to 3).

specialisation: πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πšΒ (πšœπššπšžπšŠπš›πšŽ of size 1 with a πš‘πšŽπš’πšπš‘πš replaced by πšπšŠπšœπš” of πšπšžπš›πšŠπšπš’πš˜πš— 1), πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (πš›πšŽπšŒπšπšŠπš—πšπš•πšŽ with a πš‘πšŽπš’πšπš‘πš replaced by πšπšŠπšœπš” with same πš‘πšŽπš’πšπš‘πš).

Keywords

characteristic of a constraint: derived collection.

constraint type: predefined constraint.

filtering: quadtree, compulsory part.

geometry: geometrical constraint.