Using CP-SAT for "polygon packing"

[Thibault Thomas]

I would like to know if it is possible to use CP-SAT to place various polygons (without rotation) inside a polygon container.

Because the container and the items are polygons, its not as "simple" as solving the classical bin packing problem. I thought that maybe I could check, for each item, that no segment of the polygon intersects with any segment of the container (using a helper like that: https://stackoverflow.com/a/9997374). However since I'm working with OR-tools variables (like IntVar) I don't know how I could use such a helper function.

Below is the code I have for now, just for context, because I have no idea of what to do. I am not asking for a code implementation but I would like to know if achieving my goal is even possible, and if it is, I you have any direction to give for me. :)

Sorry if my explanation is not precise, it's my very first steps with OR-tools.

Thank you.

```

from ortools.sat.python import cp_model

from shapely.geometry import Polygon

from ortools.sat.python.cp_model import IntVar, IntervalVar

class Packing2D:

    def __init__(self, bin_polygon: Polygon, items: list[Polygon]):

        self.bin_polygon = bin_polygon

        self.items = items

        self.model = cp_model.CpModel()

        self.solver = cp_model.CpSolver()

        self.x: list[IntVar] = []

        self.y: list[IntVar] = []

        self.create_variables()

        self.add_constraints()

    def create_variables(self):

        for i, item in enumerate(self.items):

            min_x, min_y, max_x, max_y = item.bounds

            x = self.model.new_int_var(int(min_x), int(self.bin_polygon.bounds[2] - (max_x - min_x)), f'x_{i}')

            y = self.model.new_int_var(int(min_y), int(self.bin_polygon.bounds[3] - (max_y - min_y)), f'y_{i}')

            self.x.append(x)

            self.y.append(y)

    def add_within_bin_constraint(self, i: int):

        ...        

    def add_constraints(self):

        x_intervals: list[IntervalVar] = []

        y_intervals: list[IntervalVar] = []

        for i, item in enumerate(self.items):

            min_x, min_y, max_x, max_y = item.bounds

            x_interval = self.model.new_fixed_size_interval_var(self.x[i], int(max_x - min_x), f'x_interval_{i}')

            y_interval = self.model.new_fixed_size_interval_var(self.y[i], int(max_y - min_y), f'y_interval_{i}')

            x_intervals.append(x_interval)

            y_intervals.append(y_interval)

       

        self.model.add_no_overlap_2d(x_intervals, y_intervals)

        for i in range(len(self.items)):

            self.add_within_bin_constraint(i)

    def solve(self) -> list[tuple[int, int]] | None:

        status = self.solver.Solve(self.model)

        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

            solution = [(self.solver.Value(self.x[i]), self.solver.Value(self.y[i])) for i in range(len(self.items))]

            return solution

        return None

[Laurent Perron]

Do they have arbitrary shapes ? Or can they be decomposed as a union of disjoint rectangles ?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/3c4a4d8b-82e5-4309-aa8c-c2f2f0de11e9n%40googlegroups.com.

--

--Laurent

[Thibault Thomas]

The container has an arbitrary shape, but each item is a compound shape made of rectangles of same dimensions.

[Laurent Perron]

So, 

intervals variables can be expression of the form: a * var + b, a, b integral constants.

So if you have a L shape

you can have 2 rectangles, the tall part of the L, and the bottom part. There will only be two integer variables, the position of the top left  coordinates, the each rectangle of the decomposition is defined as a translation from the top level point.

Am I clear ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/552b26d6-ec9a-4b45-99d0-4f0e2be0a0d3n%40googlegroups.com.

[Thibault Thomas]

I think I understand, but I don't get how, with that, I could ensure the item shape (made of a certain amount of rectangles) would not overlap the container polygon which is not a rectangle.

[Laurent Perron]

Implement the shape of the outer rectangle with fixed rectangles.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/83489395-2c22-43b5-a054-e20aaafcd30en%40googlegroups.com.