Deepnest Documentation

SVGNest uses an orbital approach combined with a genetic algorithm (GA) to solve the irregular shape nesting problem.

1. Placement Strategy (No Fit Polygon)

Instead of simple bounding boxes, SVGNest uses the No Fit Polygon (NFP) concept.

• NFP: An 'orbit' created by moving polygon B around polygon A such that they touch but do not intersect. The NFP represents all possible valid placement positions for B relative to A.
• Inner Fit Polygon: Similar to NFP, but ensures the orbiting polygon stays inside the bin boundaries.
• Union of NFPs: When multiple parts are already placed, the tool takes the union of their NFPs to find valid empty spaces.

2. Optimization Strategy (Genetic Algorithm)

To find the best order of parts and their rotations, SVGNest uses a Genetic Algorithm where the 'gene' consists of the insertion order and part rotation.

Heuristics used:

• First-fit-decreasing: Larger parts are placed first, and smaller parts are placed last (acting as 'sand' to fill gaps).
• Fitness Function: The algorithm evaluates 'fitness' by attempting to:
  1. Minimize unplaceable parts.
  2. Minimize the number of bins used.
  3. Minimize the width of all placed parts (to avoid long slivers of unused material).

You can tune the nesting algorithm using the following configuration parameters:

| Parameter | Description | | :--- | : | | Space between parts | The minimum distance to maintain between parts (useful for accounting for laser kerf or CNC offsets). | | Curve tolerance | The maximum error allowed for linear approximations of Bezier paths and arcs (in SVG units/pixels). Decrease this if curved parts appear to overlap. | | Part rotations | The number of possible rotations to evaluate for each part (e.g., 4 for cardinal directions). Higher values improve results but increase computation time. | | GA population | The population size for the Genetic Algorithm. | | GA mutation rate | The probability of mutation for each gene or part placement (values between 1 and 50). | | Part in part | When enabled, allows the tool to place parts inside the holes of other parts. This is off by default due to high resource intensity. | | Explore concave areas | When enabled, specifically solves for concave edge cases at the cost of performance and placement robustness. |

The application uses Electron's ipcMain to facilitate communication between the main process and the renderer processes (the main window and background windows).

Background Task Orchestration

To manage heavy computations or background tasks, the main process listens for specific events to route messages between the UI (mainWindow) and worker windows (backgroundWindows):

• background-start: Receives a payload and sends it to the first available (not busy) background window using webContents.send('background-start', payload). The background window is marked as isBusy = true.
• background-response: When a background window responds, the main process forwards the payload to the mainWindow via webContents.send('background-response', payload) and marks the background window as isBusy = false.
• background-progress: Forwards progress updates from background windows directly to the mainWindow via webContents.send('background-progress', payload).
• background-stop: Destroys all current background windows and restarts the background window creation cycle.

Application State Events

• login-success: Forwards login payloads from the renderer to the mainWindow.
• purchase-success: Forwards a purchase confirmation signal to the mainWindow.

// Example of how the main process handles background task starts
ipcMain.on('background-start', function(event, payload){
  for(var i=0; i<backgroundWindows.length; i++){
    if(backgroundWindows[i] && !backgroundWindows[i].isBusy){
      backgroundWindows[i].isBusy = true;
      backgroundWindows[i].webContents.send('background-start', payload);
      break;
    }
  }
});