Goatsheep NPM | npm.io

Goatsheep

Goatsheep provides placement Solutions of rectangles in a specified container with a foreground object such that they are visually pleasing.

Please see the example below and read solution calculation to get a better understanding of the expected solutions.

Install

npm install goatsheep --save

Example

Given some canvas rectangle, the contour/polygon of the foreground/important object and some rectangle object that needs to be placed on the canvas, Goatsheep will provide a solution for placing the latter such that it overlaps the foreground object as little as possible.

Below, the foreground object contour is green, the solutions for multiple objects in red:

example

Execute

const Goatsheep = require('goatsheep');

let goatsheep = new Goatsheep(payload);

Input

Goatsheep accepts a single payload object:

// Payload
{
    "debug": "boolean",     // Enable error logging
    "width": "number",      // Container width
    "height": "number",     // Container height
    "contours": "array",    // Contour(s) of foreground object(s)
    "objects": "array",     // Rect of objects to be placed
    "exclude": "array"      // Rect of areas where placing is prohibited
}

// Contours are arrays of coordinates
{
    "x": "number",
    "y": "number"
}

// Objects are arrays of rectangles
{
    "width": "number",
    "height": "number"
}

// Excluded areas are arrays of rectangles in space
{
    "top": "number",
    "left": "number",
    "width": "number",
    "height": "number"
}

For an example payload see here

Validation

You may want to pre-validate input before feeding it to Goatsheep as invalid input will throw when fed into Goatsheep.

const { validate } = require('goatsheep');

let validation = validate(payload);

if (validation !== true) {
    // validation is an Error
    console.error(validation);
}

Output

The Goatsheep object contains a lot of information, but most importantly an array with the solutions for each object.

Get the solution for the first object

// Best solution for i-th object (payload.objects[i])
let solution = goatsheep.solutions[i][0];

// _Important_ fields of solution:
{
    cell: {
        left: "number",
        top: "number"
    },
    score: "number"         // [0-1] 1 being best case
    excluded: "boolean"     // true if solution overlaps excluded areas, handle accordingly
}

Solutions

Solutions are basically 2D vectors, noting the coordinates where the objects could be placed. Goatsheep may calculate many solutions (see below), which are ranked by score, the first one being the best scoring.

Note that given restrictions, Goatsheep may fail to produce any solutions, a case for which the consumer should account for.

Calculation

Goatsheep serves a very specific design problem, where we have a container, some foreground objects and some other objects we want to place on the container with the following rules in mind:

Overlap the foreground object as little as possible
Be close to the contour of the foreground object
Do not overlap with the excluded areas
Objects placed should overlap with each other as little as possible

Quality vs Speed

To follow the rules above, calculating intersections of polygon/rectangle have to be done, which can be heavy operations, especially in NodeJS. Thus, to provide some speed while maintaining quality, Goatsheep takes a few steps:

Create a pool of possible solutions
Rank solutions using low cost heuristics
Starting from the high-ranking possible solutions do heavy calculations
Stop when the score of a solution passes a certain, acceptable, threshold
Gradually lower the threshold, basically lowering the standards when taking too long to calculate.

Goatsheep will not always yield the best solutions, but is guaranteed to give a good enough solution, if possible.