Polygon packing

[eightohnine]

Hi all,

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).

Thanks for any input!

[micycle]

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.

[eightohnine]

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!

[eightohnine]

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.

[micycle]

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).

[micycle]

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.

[eightohnine]

First: You’re the best!

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…

[eightohnine]

Returning, with mild defeat.

I thought I understand the idea behind the dual graphs, but when it came time to implement, I hit a wall.

  // split the square into n polygons
  partitionedShape = PGS_Processing.equalPartition(square, numPolygonsInSquare);

  // Convert to dual graph
  dualGraph = PGS_Conversion.toDualGraph(partitionedShape);

I did this, but immediately received a type mismatch:

cannot convert from SimpleGraph<PShape,DefaultEdge> to PShape

Turns out I don’t understand what a dual graph is and that type confused me. But trying to find any more information about it yielded no results. I thought I just needed to initialize dualGraph as type SimpleGraph, but then it says that class “SimpleGraph” does not exist. Where does SimpleGraph come from? I know it’s returned by toDualGraph(), but that’s about all I know.

I feel I need to have a better understanding of all these elements with regards to dual graphs, before I can continue thinking about code.

///

It’s not all failure though, I did manage to achieve a result close to what I envisioned:

After partitioning I just check each polygon and see if any of it’s vertices lies ON or OUTSIDE of the original squares edges.

// determine if a polygon is an outer polygon
boolean isOuterPolygon(PShape polygon) {
  // Check if any of the vertices of the polygon are on or outside the edges of the square
  for (int j = 0; j < polygon.getVertexCount(); j++) {
    PVector vertex = polygon.getVertex(j);
    if (vertex.x <= 100 || vertex.x >= 700 || vertex.y <= 100 || vertex.y >= 700) {
      return true; // is on the outer ring
    }
  }
  return false; // is not on the outer ring
}

Minus the odd snaggle-tooth poking out, this is close to what I wanted. But… it only works for square orientantions, no slanted orientations.

So I’m still looking at understanding the dual graph approach.

[micycle]

.toDualGraph() is one of those rare methods that doesn’t return a PShape. It returns a org.jgrapht.graph.SimpleGraph (a type from the JGraphT library).

With an IDE it’s quite easy to discover what methods this type offers (i.e.navigating the graph, counting edges, etc), but hard in simple editors without digging around in JGraphT docs (likewise hovering the method in an IDE would show you what type it returns).

The result’s looking good though.

[micycle]

A small demo…

long seed = 8;
var points = PGS_PointSet.gaussian(500, 500, 300, 200, seed);
var voro = PGS_Voronoi.innerVoronoi(points, new double[] { 50, 50, 950, 950 });
var g = PGS_Conversion.toDualGraph(voro);

var interiorVoro = PGS_Processing.filterChildren(voro, face -> g.edgesOf(face).size() != face.getVertexCount());
interiorVoro = PGS_Meshing.stochasticMerge(interiorVoro, 20, seed);
interiorVoro = PGS_Meshing.areaMerge(interiorVoro, 1000); // merge very small faces into their neighbours
interiorVoro = PGS_Morphology.buffer(interiorVoro, -5);
interiorVoro = PGS_Morphology.fieldWarp(interiorVoro, 4, 0.1, 0, true, seed);

shape(interiorVoro);