I’m messing around with polygon arrangements and was hoping someone might give me some pointers on how I can pack polygons neatly together.
The attached screen is the polygons I’m working with, arranged on a grid. This is OK-ish, but I’d like to go denser, irregular and with no overlap – tough no need to go perfect, small gaps or minimum distances are fine. I’m hoping a optimised packing approach would be able to help. Though I’m failing to find usable resources on this topic.
My only ideas are to a) brute force it or b) go via circle packing and then set up the polygons within each circle. Neither of which would be ideal.
I’m also aware of me using concave polygons in the mix. I’d be fine to ignore that (and allow for corner gaps) and go for a convex-only approach if that is indeed simpler.
Also, summoning @micycle in particular: I’m suspecting that PGS might be able to help here, but I’m not finding the right documentation. (Sorry, bit of a noob with regards to API docs).
Yes it can … PGS offers PGS_Optimisation.binPack(). Have a go with that and report back. It should work quite well with your polygons given their low vertex count.
Progress report: I’m not yet confident with working using external libraries, so it’s all a bit messy.
My first approach was to use bin packing. Between reading the docs, checking PGS examples and ChatGPT… it kinda works – as seen in this in-process screenshot. Though I’m still stumped by the concept of bins, columns and how I control these better, e.g. make it that I define a space and then this is filled with a necessary amount of polygons. Also, rotating the shapes so they may fill up the gaps better. (But maybe that’s not what bin packing does?)
After all of this, the visual result doesn’t sit quite right with me. Too much directionality, "starting at the top left and then filling out the space. I think I want more even distribution.
Enter my next take, using PGS again. First, equal partitioning the square shape, then shrinking (aka offsetting curves inward) the child polygons.
This feels tidy and uniform. Possibly too tidy and too uniform. If I just could find a visual balance between bin packing and partitioning approach. Maybe adding noise variations to placement, size and rotation, could break up the rigidity?
And finally, there’s also the PGS dyson hatching example. Think away the color and motion and it has a foundational structure which is akin to what I’m looking for. Though I feel I want to build this up on my own, instead of just tweaking an already great result.
Bottom line: I’m still in the middle of it, but at least I have several paths I can follow. I still need more intuition for PShapes and PShape groups so that I can apply and control PGS better. Fun ahead!
One follow-up question with regards to the partition/shrink approach:
That straight border made by the outer ring of polygons can be very fitting visually, for some applications.
But what if I wanted a rough uneven edge? Essentially, get rid of every polygon that is part of making the flat border. How might I target those polygons in the PShape group?
The spontaneous idea I have is to iterate through every child Shape, get its vertices and calculate if any of its edges run exactly orthogonal or parallel to the base coordinate system of the sketch, i.e. horizontal and vertical vertex connections. If so, get rid of that Shape.
This might work for this application though may also provoke a false positive by pure change for inner Shapes. Also, no good if the base square is at an angle.
Too much directionality, "starting at the top left and then filling out the space. I think I want more evenness.
Ah I see, you’re after a shape arrangement for its visual effect, and not merely packing polygons tightly… In that case using voronoi-like tiles as a base, as you’re doing, is a good approach.
I should improve the docs for bin packing. The motivation behind having multiple bins is industrial: think about cutting out shapes from sheet metal where you have sheets of fixed dimensions. You’d try to pack as much into a single sheet of metal before moving on to second one (once the first is about to overflow). For packing in generative art, I’d think a single bin (“the plane”), parameterised with a maximum width, is most desirable.
Lastly, the ripplingTriangles example has some ideas about adding variation to shapes that are members of an arrangement. You might find fieldWarp() handy (in addition to other warping or simplification methods in PGS_Morphology).
But what if I wanted a rough uneven edge? Essentially, get rid of every polygon that is part of making the flat border. How might I target those polygons in the PShape group?
Yes, looking for shapes with at least on axis-aligned edge would work. Could have false positives, but very unlikely!
I think I have a cleverer solution though: convert the shape (before shrinking the faces) into a dual graph with PGS_Conversion.toDualGraph(). Then each face is interior if its number of graph edges equals its number of geometric edges (or vertices). Basically it’s a robust way of finding out if the face is completely surrounded (at every edge) by other faces.
Second: Yup, I’m strictly in it for the visuals. Also, no Math-y or CS-y background here, so I’m winging it most of the time and approaching new concepts possibly with a different expectation on what they can deliver.
Thank you for introducing all of these new concepts, that solution indeed does sound clever. That is, it was exactly now that I became aware on the idea of a dual graph or conforming mesh, so I’ll first have to investigate that, before I know just how clever it is…
… PGS offers 
