Returns a list of objects found in a nest generated by Deepnest.io

idNestObjects.m

% Returns a list of objects found in a nest generated by Deepnest.io                                        
%                                         
%                                         
% Input(s)                                
%   svgDir:   Directory to individual curves
%   NestFile: Completed nest of objects by Deepnest.io                                      
%                                         
% Output(s)                               
%   Plot of nested objects with labels                                     
%                                         
% Example:
%{
% Provide an input Excel file name containing Bezier control points
    BezStruct = BezierHull(fName);
% Save curve files to .svg files in <svgDir>
    bez2svg(BezStruct,fName,svgDir); 
% Identify nested objects in nest.svg generated by Deepnest    
    NestFile = fullfile(svgDir,'Nested\nest.svg');
    idNestObjects(svgDir,NestFile) 
%}
%                                         
% See also: bez2svg                              
%                                         
%                                         
% Dependencies: svg2paths, normPaths, vnorm, v2struct, plotNested                         
                                          
%                                         
%                                         
% Written by: John Peach 21-Aug-2021      
% Wild Peaches                            
%                                         
% Revisions:                              
                                          
                                          
function idNestObjects(svgDir,NestFile)
    % List of individual svg objects
    svgFiles = dir(fullfile(svgDir,'*.svg'));
    nSVG = numel(svgFiles);
    
    % Load paths of individual objects, get properties
    for k = 1:nSVG
        curveName = svgFiles(k).name(1:end-4);
        path = svg2paths(fullfile(svgDir,svgFiles(k).name));
        svgPaths(k) = normPaths(path{1},curveName);
    endfor
    % Comparison statistics
    svg_nPoints = [svgPaths.nPoints];
    svg_whRatio = [svgPaths.whRatio];
    
    % Paths of nested objects
    nestCurves = svg2paths(NestFile);
    nNests = numel(nestCurves);
    % Center nested paths
    for j = 1:nNests
        curveName = ['nest_' num2str(j)];
        nestPaths(j) = normPaths(nestCurves{j},curveName);
    endfor
    
    % Compare number of points in nested paths to each object. If match, 
    % find solution with minimum distance
    nestedObjs = cell(nNests,1);
    for j = 1:nNests
        % For each possible point count match, choose best orientation, 
        % calculate minimum distance between points
        matches  = find(nestPaths(j).nPoints == svg_nPoints & ...
                        abs(nestPaths(j).whRatio - svg_whRatio) < 1e-5);
        nMatches = numel(matches);
        fitQual  = zeros(nMatches,1);
        for k = 1:nMatches
            % Rotation of nested object best matching original curve
            svgPath = svgPaths(matches(k)).normedPath;
            curvePath = nestPaths(j).normedPath;
            M = svgPath' * curvePath;
            % Singular value decomposition of product
            [U,S,V] = svd(M);
            % Rotation matrix fitting nested curve to original path curve
            R = U * V';
            % Apply rotation to nested path, distance to original
            nestRot = curvePath * R';
            fitQual(k) = norm(svgPath - nestRot);
        endfor
        % Select the best fit as solution
        [~,fitidx] = min(fitQual);
        nestedObjs{j} = svgFiles(matches(fitidx)).name;
        
    endfor
    
    % Plot labeled nested objects
    plotNested(NestFile,nestedObjs);
                                                                              
endfunction  

function paths = svg2paths(fName)
    % Load svg file as text (extract string from cell)
    svg = textload(fName);
    if numel(svg) > 1
        svg = strjoin(svg);
    else
        svg = svg{1};
    endif
    
    % Find all path instances
    pathStart = strfind(svg,'"M');
    pathEnd = strfind(svg,'z"');
    nPaths = numel(pathStart);
    
    % Extract path points
    paths = cell(nPaths,1);
    for p = 1:nPaths
        pathStr  = svg(pathStart(p)+1:pathEnd(p)-1);
        pathCell = parse2cell(pathStr, ' ');
        pathCell = reshape(pathCell,3,numel(pathCell)/3)';
        paths{p} = str2double(pathCell(:,2:3));        
    endfor
                                      
endfunction                              

function pathStruct = normPaths(path,curveName)

    translation = mean(path);
    scaling = vnorm(path,1);
    nPoints = size(path,1);
    normedPath = bsxfun(@rdivide, path - translation, scaling);
    [width,height] = disperse(max(normedPath));
    whRatio = width/height;
    if whRatio > 1
        whRatio = 1/whRatio;
    endif
    pathStruct = v2struct(path,curveName,normedPath,translation,scaling, ...
                 nPoints,width,height,whRatio);
    
endfunction

function paths = plotNested(NestFile,nestedObjs)
    
    % Load svg file as text (extract string from cell)
    svg = textload(NestFile);
    if numel(svg) > 1
        svg = strjoin(svg);
    else
        svg = svg{1};
    endif
    
    % Find all path instances
    pathStart = strfind(svg,'"M');
    pathEnd = strfind(svg,'z"');
    translateStart = strfind(svg,'translate');
    rotateStart = strfind(svg,'rotate');
    nPaths = numel(pathStart);
    
    pathStruct = struct('x',[],'y',[],'t',[],'r',[],'pathName','');
    paths = repmat(pathStruct,nPaths,1);
    
    % Extract path points
    for p = 1:nPaths
        % Path point coordinates
        pathStr  = svg(pathStart(p)+1:pathEnd(p)-1);
        pathCell = parse2cell(pathStr, ' ');
        pathCell = reshape(pathCell,3,numel(pathCell)/3)';
        path     = str2double(pathCell(:,2:3));  
        % Rotation angle
        rPos  = rotateStart(find(rotateStart < pathStart(p),1,'last'));
        rStr  = svg(rPos:rPos + 15);
        theta = str2double(rStr(isdigit(rStr)));
        c = cosd(theta);
        s = sind(theta);
        R = [c -s; s c];
        path = path * R';
        % Translation
        tPos = translateStart(find(translateStart < pathStart(p),1,'last'));
        tStr = svg(tPos:rPos);
        tCell = parse2cell(tStr,'( )');
        T = [str2double(tCell{2}) str2double(tCell{3})];
        path = path + T;
        % Save to paths structure
        paths(p).x = path(:,1);
        paths(p).y = path(:,2);
        paths(p).t = T;
        paths(p).r = R;
        if nargin == 2
            paths(p).pathName = strrmv(nestedObjs{p},'.svg');
        endif
                
    endfor
    
    % Plot curves after transformations
    figure; hold on;
    for p = 1:nPaths
        plot(paths(p).x,paths(p).y);
        if nargin == 2
            x0 = mean(paths(p).x);
            y0 = mean(paths(p).y);
            text(x0,y0,paths(p).pathName, ...
                 'horizontalalignment', 'center', ...
                 'verticalalignment', 'middle', ...
                 'interpreter', 'none');
        endif
    endfor
    set(gca,'YDir','reverse')
    axis equal;
    pubFig;                                       
                                       
endfunction             

function V = vnorm(A,dim)

    % Size of input array
    [r,c] = size(A);

    % Use 2nd dimension if only array is input
    if nargin == 1
        dim = 2;
    end

    % Calculate 2-norm of rows or columns
    if dim == 2
        V = zeros(r,1);
        for k = 1:r
            V(k) = norm(A(k,:));
        end
    elseif dim == 1
        V = zeros(1,c);
        for k = 1:c
            V(k) = norm(A(:,k));
        end
    else
        error('dim must be either 1 or 2');
    end  
    
endfunction