An algorithm for collision detection and 2D irregular nesting
Author guo-yong-zhi
7 Stars
Updated Last
1 Year Ago
Started In
March 2021


CI CI-nightly codecov DOI
This's an algorithm for solving 2D irregular nesting problems (also known as cutting problems or packing problems).
The algorithm accepts arbitrary binary or ternary raster masks as inputs and is good at handling the nesting problems of many gadgets. The implementation is based on quadtree & gradient optimization. Also, it can be parallelized if you start julia with julia --threads k. This package is used by WordCloud.jl.
Examples: collision detection, dynamic collision detection, packing
Benchmark: collision benchmark, fit benchmark



import Pkg; Pkg.add("Stuffing")

Algorithm Description

  • First, a ternary raster pyramid (implemented as AbstractStackedQTree) is built for every original binary raster mask. It consists of downsampled layers of the original mask. Each successive layer is downsampled at a scale of 2:1. In this way, the pyramid can also be seen as a set of hierarchical bounding boxes. The value of each pixel of each layer (the node of the tree) can be FULL, EMPTY or MIX.
    pyramid1 pyramid2
  • Second, a top-down method (collision) is used to detect collision between two pyramids (trees). On the level 𝑙 and coordinates (𝑎,𝑏), if one tree's node is FULL and the other's is NOT EMPTY, then these two trees collide at (𝑙,𝑎,𝑏). However, to detect collisions between many objects, pairwise detection would be time-consuming. So, we first locate the objects in hierarchical sub-regions (implemented as a HashSpacialQTree or LinkedSpacialQTree), and then detect the collision between objects within each sub-region and between the objects in the sub-regions and those in their ancestral regions (see totalcollisions_spacial, partialcollisions and locate!).
  • At last, each object in collision pair is moved according to the local gradient (calculated by grad2d) near the collision point (𝑙,𝑎,𝑏), that is, moving the object away from EMPTY region. This will enlarge space between them. After moving the objects, the AbstractStackedQTrees should be rebuilt for the next round of collision detection.

Required Packages

No packages found.

Used By Packages