The non-overlapping constraint between objects described by non-linear inequalities

Contrainte de non-chevauchement entre objets décrits par des inégalités non-linéaires

Ignacio Salas (1) , Gilles Chabert (1) , Alexandre Goldsztejn (2)

1 TASC - Theory, Algorithms and Systems for Constraints
2 LINA - Laboratoire d'Informatique de Nantes Atlantique

Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that it does not intersect a second, previously placed, object. This subproblem is called the non-overlapping constraint. The complexity of this non-overlapping constraint depends on the type of objects considered. It is simple in the case of rectangles. It has also been studied in the case of polygons. This paper proposes a numerical approach for the wide class of objects described by non-linear inequalities. Our goal here is to calculate the non-overlapping constraint, that is, to describe the set of all positions and orientations that can be assigned to the first object so that intersection with the second one is empty. This is done using a dedicated branch & bound approach. We first show that the non-overlapping constraint can be cast into a Minkowski sum, even if we take into account orientation. We derive from this an inner contractor, that is, an operator that removes from the current domain a subset of positions and orientations that necessarily violate the non-overlapping constraint. This inner contractor is then embedded in a sweeping loop, a pruning technique that was only used with discrete domains so far. We finally come up with a branch & bound algorithm that outperforms the generic state-of-the-art solver Rsolver.

Le placement d'objets 2D dans un espace limité est un problème omniprésent aussi bien sur le plan académique qu'industriel. Quel que soit le contexte, la résolution de ce problème exige la capacité de pouvoir déterminer où un premier objet peu être placé de telle façon qu'il ne chevauche pas un second objet, précédemment placé. Ce sous-problème s'appelle la contrainte de non-chevauchement. La complexité de cette contrainte de non-chevauchement dépend du type d'objets considérés. Elle est simple dans le cas de rectangles. Elle a également été étudiée dans le cas de polygones. Cet article propose une approche numérique pour la classe générale des objets décrits par des inégalités non-linéaires. Notre objectif ici est de calculer la contrainte de non-chevauchement, c'est à dire, de décrire l'ensemble de toutes les positions et orientations qui peuvent être attribuées au premier objet de telle sorte que l'intersection avec le second soit vide. Nous nous basons sur un algorithme de branch & prune dédié. Nous montrons d'abord que la contrainte de non-chevauchement, équivaut à une somme de Minkowski, même lorsque l'orientation est prise en compte. Nous en déduisons un contracteur intérieur, c'est à dire, un opérateur qui élimine du domaine courant un sous-ensemble de positions et orientations qui violent nécessairement la contrainte de non-chevauchement. Ce contracteur intérieur est intégré dans une boucle de sweep, une technique utilisée jusqu'ici uniquement pour les domaines discrets. Nous aboutissons ainsi à un algorithme de branch & prune présentant de bien meilleures performances que Rsolver, outil de référence pour la résolution de contraintes quantifiées en domaines continus.

Mots clés: non-overlapping constraint; packing problem; Minkowski sum; interval arithmetic

Domaines: Géométrie algorithmique [cs.CG]

Ignacio Salas, Gilles Chabert, Alexandre Goldsztejn. Contrainte de non-chevauchement entre objets décrits par des inégalités non-linéaires. Journées Francophones de Programmation par Contraintes (JFPC), Jun 2014, Angers, France. ⟨hal-01079579⟩