Jitter packing results in overlaps for some parameter ranges

[mogres]

Description

Packing a recipe with the jitter algorithm results in overlaps as detected by the analysis workflow. These overlaps can be identified in the packing image.

Expected Behavior

We expect the analysis workflow to not detect any overlaps.

Reproduction

pack -r cellpack/tests/recipes/test_spheres.json -c cellpack/tests/packing-configs/test_config.json
analyze -a cellpack/tests/analysis-configs/PR_analysis_config.json

#78 (comment)

Information

The overlaps are dependent on grid spacing. For a sufficiently fine grid, there are no overlaps.

Questions/directions to try:

• Adding an option to test distances at every packing step, and throw a trace if discrepancy is detected
• check if distance stored in the grid is reduced if an ingredient fails to pack
• check how far an ingredient jitters from the grid point
  • square vs circle
  • radius of jitter

[mogres]

After some discussion involving @meganrm, @gj210, @mogres, @toloudis, we came to the conclusion that the jitter algorithm essentially uses a signed distance function created by the grid to recreate the shapes of already packed objects. This recreation is imperfect due to the inherent granularity of the grid, and it is possible for a grid-object check to pass even when it should identify a collision. This is illustrated by the following applet created by @toloudis: https://editor.p5js.org/toloudis/sketches/3JIhRhpHZ

Suggestions for moving forward:

1. Store the identity of the nearest object (in addition to the distance to the nearest surface) within the grid points
2. Implement a local object-object collision check