src/ClothesGraph.Printing/AutoNester.cs - main - docNemo/clothes-graph

src/ClothesGraph.Printing/AutoNester.cs
267 строк11 KB
docNemo
Фундамент продукта: параметрическое построение выкроек, печать, установщик
08 авг 2026, 22:17
08 авг 2026, 22:17cd47cce
using System;
using System.Collections.Generic;
using System.Linq;
using ClothesGraph.Geometry;

namespace ClothesGraph.Printing;

/// <summary>Результат раскладки.</summary>
public sealed record NestingResult(int SheetsBefore, int SheetsAfter, int Columns)
{
    public bool Improved => SheetsAfter < SheetsBefore;

    public int Saved => Math.Max(0, SheetsBefore - SheetsAfter);
}

/// <summary>
/// Автоматическая раскладка деталей для экономии бумаги.
/// </summary>
/// <remarks>
/// Детали укладываются по габаритным прямоугольникам, а не по контурам.
/// Раскладка по контурам («вложенная») экономит заметно больше, но это задача
/// другого порядка сложности, и для печати на бумаге выигрыш от неё скромнее,
/// чем при раскрое рулона: лист всё равно расходуется целиком.
///
/// Повороты ограничены долевой нитью. Деталь с заданным направлением нити
/// можно развернуть только на пол-оборота: поворот на четверть поставил бы
/// нить поперёк, и готовая вещь повела бы себя иначе.
/// </remarks>
public sealed class AutoNester
{
    /// <summary>Технологический зазор между деталями.</summary>
    private readonly Length _gap;

    /// <summary>Сколько столбцов листов перебирать в поисках лучшей раскладки.</summary>
    private const int MaxColumnsToTry = 6;

    public AutoNester(Length? gap = null)
        => _gap = gap ?? Length.FromMillimetres(5);

    /// <summary>
    /// Раскладывает детали и возвращает, сколько листов удалось сэкономить.
    /// </summary>
    /// <remarks>
    /// Ширина полосы подбирается перебором: узкая полоса даёт длинную ленту,
    /// широкая — короткую и толстую, а листов при этом может уйти и больше,
    /// и меньше. Заранее предсказать выгодную ширину нельзя, а перебрать
    /// полдюжины вариантов дёшево.
    /// </remarks>
    public NestingResult Arrange(PrintContent content, PageLayout layout)
    {
        var pieces = content.Pieces.ToArray();

        if (pieces.Length == 0)
            return new NestingResult(0, 0, 1);

        var before = SheetGridFor(content, layout);

        var original = pieces
            .Select(piece => (piece.Offset, piece.RotationDegrees))
            .ToArray();

        var best = (Sheets: before, Columns: 1, State: original);

        for (var columns = 1; columns <= MaxColumnsToTry; columns++)
        {
            var width = layout.PrintableWidth + layout.StepX * (columns - 1);

            Pack(pieces, width);

            var sheets = SheetGridFor(content, layout);

            if (sheets < best.Sheets)
                best = (sheets, columns,
                    pieces.Select(piece => (piece.Offset, piece.RotationDegrees)).ToArray());
        }

        // Возвращаем лучшее из найденного, включая исходное размещение:
        // раскладка не должна делать хуже, чем было.
        for (var index = 0; index < pieces.Length; index++)
        {
            pieces[index].Offset = best.State[index].Offset;
            pieces[index].RotationDegrees = best.State[index].RotationDegrees;
        }

        return new NestingResult(before, best.Sheets, best.Columns);
    }

    /// <summary>
    /// Укладывает детали в полосу заданной ширины по методу нижней левой точки.
    /// </summary>
    /// <remarks>
    /// Горизонт хранится как ломаная высот: для каждой детали ищется самое
    /// низкое место, куда она помещается по ширине. Способ простой, но на
    /// десятке деталей выкройки даёт результат, близкий к ручной раскладке.
    /// </remarks>
    private void Pack(IReadOnlyList<PlacedPiece> pieces, Length stripWidth)
    {
        // Крупные детали кладутся первыми: мелкие потом заполняют промежутки,
        // а в обратном порядке крупная деталь уже никуда не влезает.
        var order = pieces
            .Select((piece, index) => (Piece: piece, Index: index))
            .OrderByDescending(item => Size(item.Piece).Height.Units)
            .ThenByDescending(item => Size(item.Piece).Width.Units)
            .ToArray();

        var skyline = new List<(long X, long Width, long Height)>
        {
            (0, stripWidth.Units, 0)
        };

        foreach (var (piece, _) in order)
        {
            var rotation = ChooseRotation(piece, stripWidth);
            piece.RotationDegrees = rotation;

            var size = Size(piece);
            var width = size.Width.Units + _gap.Units;
            var height = size.Height.Units + _gap.Units;

            var (x, y) = FindLowest(skyline, width, stripWidth.Units);

            // Смещение считается от текущего положения детали: у неё уже есть
            // собственные координаты, доставшиеся от чертежа.
            var (min, _) = piece.Bounds();

            piece.Offset = new Offset2(
                piece.Offset.X + Length.FromUnits(x - min.X.Units),
                piece.Offset.Y + Length.FromUnits(y - min.Y.Units));

            Raise(skyline, x, width, y + height);
        }
    }

    /// <summary>
    /// Выбирает поворот детали.
    /// </summary>
    /// <remarks>
    /// Долевая нить допускает только пол-оборота. Без неё деталь можно
    /// положить поперёк, если так она укладывается в полосу, а вдоль — нет.
    /// </remarks>
    private static double ChooseRotation(PlacedPiece piece, Length stripWidth)
    {
        if (piece.Piece.Grainline is not null)
            return piece.RotationDegrees;

        var upright = SizeAt(piece, 0);

        if (upright.Width <= stripWidth)
            return 0;

        var turned = SizeAt(piece, 90);

        return turned.Width <= stripWidth ? 90 : 0;
    }

    private static (Length Width, Length Height) Size(PlacedPiece piece)
    {
        var (min, max) = piece.Bounds();
        return (max.X - min.X, max.Y - min.Y);
    }

    private static (Length Width, Length Height) SizeAt(PlacedPiece piece, double rotation)
    {
        var previous = piece.RotationDegrees;

        piece.RotationDegrees = rotation;
        var size = Size(piece);
        piece.RotationDegrees = previous;

        return size;
    }

    /// <summary>Самое низкое место в полосе, куда деталь помещается по ширине.</summary>
    private static (long X, long Y) FindLowest(
        List<(long X, long Width, long Height)> skyline, long width, long stripWidth)
    {
        var bestX = 0L;
        var bestY = long.MaxValue;

        for (var index = 0; index < skyline.Count; index++)
        {
            var x = skyline[index].X;

            if (x + width > stripWidth)
                break;

            // Деталь ложится на самый высокий из участков, которые она
            // перекрывает: ниже она просто не сядет.
            var y = 0L;
            var covered = 0L;

            for (var probe = index; probe < skyline.Count && covered < width; probe++)
            {
                y = Math.Max(y, skyline[probe].Height);
                covered += skyline[probe].Width;
            }

            if (covered < width)
                break;

            if (y < bestY)
            {
                bestY = y;
                bestX = x;
            }
        }

        // Деталь шире полосы: кладём её в начало новой строки, она всё равно
        // будет разбита между листами при печати.
        if (bestY == long.MaxValue)
            return (0, skyline.Max(segment => segment.Height));

        return (bestX, bestY);
    }

    /// <summary>Поднимает горизонт на участке, занятом деталью.</summary>
    private static void Raise(
        List<(long X, long Width, long Height)> skyline, long x, long width, long height)
    {
        var result = new List<(long X, long Width, long Height)>();
        var placedEnd = x + width;

        foreach (var segment in skyline)
        {
            var segmentEnd = segment.X + segment.Width;

            if (segmentEnd <= x || segment.X >= placedEnd)
            {
                result.Add(segment);
                continue;
            }

            if (segment.X < x)
                result.Add((segment.X, x - segment.X, segment.Height));

            if (segmentEnd > placedEnd)
                result.Add((placedEnd, segmentEnd - placedEnd, segment.Height));
        }

        result.Add((x, width, height));
        result.Sort((left, right) => left.X.CompareTo(right.X));

        skyline.Clear();
        skyline.AddRange(Merge(result));
    }

    /// <summary>Сливает соседние участки одинаковой высоты.</summary>
    private static IEnumerable<(long X, long Width, long Height)> Merge(
        List<(long X, long Width, long Height)> segments)
    {
        for (var index = 0; index < segments.Count; index++)
        {
            var current = segments[index];

            while (index + 1 < segments.Count && segments[index + 1].Height == current.Height)
            {
                current = (current.X, current.Width + segments[index + 1].Width, current.Height);
                index++;
            }

            yield return current;
        }
    }

    private static int SheetGridFor(PrintContent content, PageLayout layout)
        => PdfExporter.GridFor(content, layout).Count;
}