Optimize order of objects within layer in Illustrator for reduced laser cutting time

Question

I'm trying to optimize the layer order of paths in Illustrator so that when sent to a laser cutter, the end of one path is close to the start of the next path reducing the travel time of the laser between each cut.

I've come up with the following code, which works, but could be further optimized considering length of lines, or through an annealing process. I'm posting it here in case anyone else is Googling 'Laser cutting optimization' and doesn't want to write their own code. Also if anyone can suggest improvements to the below code, I'd love to hear them.

// For this script to work, all paths to be optimised need to be on layer 0.
// Create a new empty layer in position 1 in the layer heirarchy.
// Run the script, all paths will move from layer 0 to layer 1 in an optimized order.
// Further optimisation possible with 'Annealing', but this will be a good first run optimization.

// Load into Visual Studio Code, follow steps on this website 
// https://medium.com/@jtnimoy/illustrator-scripting-in-visual-studio-code-cdcf4b97365d
// to get setup, then run code when linked to Illustrator.

function test() {

    if (!app.documents.length) {

        alert("You must have a document open.");

        return;

    }

    var docRef = app.activeDocument;

    function endToStartDistance(endPath, startPath) {
        var endPoint = endPath.pathPoints[endPath.pathPoints.length - 1].anchor;
        var startPoint = startPath.pathPoints[0].anchor;
        var dx = (endPoint[0] - startPoint[0]);
        var dy = (endPoint[1] - startPoint[1]);
        var dist = Math.pow((Math.pow(dx, 2) + Math.pow(dy, 2)), 0.5);
        return dist;
    }

    function Optimize(items) {

        var lastPath, closest, minDist, delIndex, curItem, tempItems = [];
        var topLayer = app.activeDocument.layers[0];
        var newLayer = app.activeDocument.layers[1];

        for (var x = 1, len = items.length; x < len; x++) {

            tempItems.push(items[x]);
        }

        lastPath = items[0];

        lastPath.move(newLayer, ElementPlacement.PLACEATBEGINNING);

        while (tempItems.length) {

            closest = tempItems[0];

            minDist = endToStartDistance(lastPath, closest);

            delIndex = 0;

            for (var y = 1, len = tempItems.length; y < len; y++) {

                curItem = tempItems[y];

                if (endToStartDistance(lastPath, curItem) < minDist) {

                    closest = curItem;

                    minDist = endToStartDistance(lastPath, closest);

                    delIndex = y;
                }
            }
            $.writeln(minDist);
            //closest.zOrder(ZOrderMethod.BRINGTOFRONT);
            closest.move(newLayer, ElementPlacement.PLACEATBEGINNING);

            lastPath = closest;

            tempItems.splice(delIndex, 1);
        }

    }

    var allPaths = [];

    for (var i = 0; i < documents[0].pathItems.length; i++) {
        allPaths.push(documents[0].pathItems[i]);
        //$.writeln(documents[0].pathItems[i].pathPoints[0].anchor[0])
    }

    Optimize(allPaths);
}

test();

Answer 1

Version 2 of the above code, some changes include the ability to reverse paths if this results in a reduced distance for the cutting head to move between paths, and added comments to make the code easier to read.

// Create a new empty layer in position 1 in the layer heirarchy.
// Run the script, all paths will move from their current layer to layer 1 in an optimized order.
// Further optimisation possible with 'Annealing', but this will be a good first run optimization.

// Load into Visual Studio Code, follow steps on this website 
// https://medium.com/@jtnimoy/illustrator-scripting-in-visual-studio-code-cdcf4b97365d
// to get setup, then run code when linked to Illustrator.aa

function main() {

    if (!app.documents.length) {
        alert("You must have a document open.");
        return;
    }

    var docRef = app.activeDocument;

    //  The below function gets the distance between the end of the endPath vector object
    //  and the start of the startPath vector object.
    function endToStartDistance(endPath, startPath) {
        var endPoint = endPath.pathPoints[endPath.pathPoints.length - 1].anchor;
        var startPoint = startPath.pathPoints[0].anchor;
        var dx = (endPoint[0] - startPoint[0]);
        var dy = (endPoint[1] - startPoint[1]);
        var dist = Math.pow((Math.pow(dx, 2) + Math.pow(dy, 2)), 0.5);
        return dist;
    }

    //  The below function gets the distance between the end of the endPath vector object
    //  and the end of the startPath vector object.
    function endToEndDistance(endPath, startPath) {
        var endPoint = endPath.pathPoints[endPath.pathPoints.length - 1].anchor;
        var startPoint = startPath.pathPoints[startPath.pathPoints.length - 1].anchor;
        var dx = (endPoint[0] - startPoint[0]);
        var dy = (endPoint[1] - startPoint[1]);
        var dist = Math.pow((Math.pow(dx, 2) + Math.pow(dy, 2)), 0.5);
        return dist;
    }

    //  The below function iterates over the supplied list of tempItems (path objects) and checks the distance between
    //  the end of path objects and the start/end of all other path objects, ordering the objects in the layer heirarchy
    //  so that there is the shortest distance between the end of one path and the start of the next.
    //  The function can reverse the direciton of a path if this results in a smaller distance to the next object.
    function Optimize(tempItems) {

        var lastPath, closest, minDist, delIndex, curItem;
        var newLayer = app.activeDocument.layers[1];    //  There needs to be an empty layer in position 2 in the layer heirarchy
        //  This is where the path objects are moved as they are sorted.

        lastPath = tempItems[0];    //  Arbitrarily take the first item in the list of supplied items
        tempItems.splice(0, 1);     //  Remove the first item from the list of items to be iterated over
        lastPath.move(newLayer, ElementPlacement.PLACEATBEGINNING); //  Move the first item to the first position in the new layer

        while (tempItems.length) {  //  Loop over all supplied items while the length of this array is not 0.
            //  Items are removed from the list once sorted.
            closest = tempItems[0]; //  Start by checking the distance to the first item in the list

            minDist = Math.min(endToStartDistance(lastPath, closest), endToEndDistance(lastPath, closest));
            //  Find the smallest of the distances between the end of the previous path item
            //  and the start / end of this next item.
            delIndex = 0;           //  The delIndex is the index to be removed from the tempItems list after iterating through 
            //  the entire list.

            for (var y = 1, len = tempItems.length; y < len; y++) {
                //  Iterate over all items in the list, starting at item 1 (item 0 already being used above)
                curItem = tempItems[y];

                if (endToStartDistance(lastPath, curItem) < minDist || endToEndDistance(lastPath, curItem) < minDist) {
                    //  If either the end / start distance to the current item is smaller than the previously
                    //  measured minDistance, then the current path item becomes the new smallest entry
                    closest = curItem;

                    minDist = Math.min(endToStartDistance(lastPath, closest), endToEndDistance(lastPath, closest));
                    //  The new minDistace is set
                    delIndex = y;   //  And the item is marked for removal from the list at the end of the loop.
                }
            }

            if (endToEndDistance(lastPath, closest) < endToStartDistance(lastPath, closest)) {
                reversePaths(closest);  //  If the smallest distance is yielded from the end of the previous path
                //  To the end of the next path, reverse the next path so that the 
                //  end-to-start distance between paths is minimised.
            }
            closest.move(newLayer, ElementPlacement.PLACEATBEGINNING);  //  Move the closest path item to the beginning of the new layer

            lastPath = closest; //  The moved path item becomes the next item in the chain, and is stored as the previous item 
            //  (lastPath) for when the loop iterates again.

            tempItems.splice(delIndex, 1);  //  Remove the item identified as closest in the previous loop from the list of 
            //  items to iterate over. When there are no items left in the list
            //  The loop ends.
        }

    }

    function reversePaths(theItems) {   //  This code taken / adapted from https://gist.github.com/Grsmto/bfe1541957a0bb17972d
        if (theItems.typename == "PathItem" && !theItems.locked && !theItems.parent.locked && !theItems.layer.locked) {

            pathLen = theItems.pathPoints.length;

            for (k = 0; k < pathLen / 2; k++) {
                h = pathLen - k - 1;

                HintenAnchor = theItems.pathPoints[h].anchor;
                HintenLeft = theItems.pathPoints[h].leftDirection;
                HintenType = theItems.pathPoints[h].pointType;
                HintenRight = theItems.pathPoints[h].rightDirection;

                theItems.pathPoints[h].anchor = theItems.pathPoints[k].anchor;
                theItems.pathPoints[h].leftDirection = theItems.pathPoints[k].rightDirection;
                theItems.pathPoints[h].pointType = theItems.pathPoints[k].pointType;
                theItems.pathPoints[h].rightDirection = theItems.pathPoints[k].leftDirection;
                theItems.pathPoints[k].anchor = HintenAnchor;
                theItems.pathPoints[k].leftDirection = HintenRight;
                theItems.pathPoints[k].pointType = HintenType;
                theItems.pathPoints[k].rightDirection = HintenLeft;
            }
        }
    }


    var allPaths = [];  //  Grab every line in the document

    for (var i = 0; i < documents[0].pathItems.length; i++) {
        allPaths.push(documents[0].pathItems[i]);
        //  This could be better changed to the selected objects, or to filter only objects below a certain
        //  stroke weight so that raster paths are not affected, but cut paths are.
    }

    Optimize(allPaths); //  Feed all paths in the document into the optimize function.
}

main(); //  Call the main function, executing the above code.