# 2d packing of closed polylines

I am trying to develop something that can pack a series of irregular 2d closed polylines into a set width area with the smallest possible x dimension.

The order of the shapes is predetermined and cannot be changed, so something like opennest will not work. Also shapes cannot be rotated.
I have worked out my code for fitting the polylines to the edge of the panel but I am struggling to find a solution to minimize the length. i.e moving panels in -x till they run into another panel (if there is a slight clash or gap that is fine as the shapes already have a buffer zone built in).
I have been told that I need a recursive python or vb script to achieve this but I have no experience writing these.
Would it be possible to do something like this using Kangaroo2 or Galapagos? or would something like hoopsnake work?
If anyone has any thoughts on some tools or workflows that could get me closer to my end result

Look for OpenNest on Food4Rhino

The important point here is that the panels must not be re-ordered. I don’t believe there is a way to do this with opennest, let me know if I am mistaken.

If you don’t have so many objects a pure Galapagos solution would be easy, just test for collisions between shapes and maybe boolean/region intersections. Or go fancy and implement packing that fits your needs, play with NoFitPolygons, hint Clipper has a Minkowski difference component and API, you will still need to optimize somehow, but the search space will be drastically reduced. I guess it depends on the number of objects you are dealing with.

Judging if polygons intersect is way easier & faster than calculating the intersected shape.

``````        public static bool HasSeparatingAxis(Polygon a, Polygon b)
{
// test each side of a in turn:
for (var i = 0; i < a.VerticeCount; i++)
{
var normal_x = a.Vertices[(i + 1) % a.VerticeCount].Y - a.Vertices[i].Y;
var normal_y = a.Vertices[i].X - a.Vertices[(i + 1) % a.VerticeCount].X;

for (var j = 0; j < b.VerticeCount; j++)
{
var dot_product = ((b.Vertices[j].X - a.Vertices[i].X) * normal_x) +
((b.Vertices[j].Y - a.Vertices[i].Y) * normal_y);
if (dot_product <= 0.0) // change sign of test based on winding order
break;
if (j == b.VerticeCount - 1)
return true; // all dots were +ve, we found a separating axis
}
}
return false;
}

public static bool IntersectWith(this Polygon a, Polygon b)
{
return !HasSeparatingAxis(a, b) && !HasSeparatingAxis(b, a);
}
``````

But computing the intersection gives a scalar that’s handy for the optimization algorithms, otherwise you won’t have a slope to climb/descend. Maybe if the polygons are convex just penalizing if they intersect and the distance between centroids can do.

Quantity varies from 20 odd to a few hundred shapes, so I guess Galapagos option might be a dead end.

If you mean naive brute force, yes. You have to come up with a optimization strategy to restrict the possible permutations. Something as simple as restricting the cross references between objects according to a ratio can do wonders!