Каталог решений - Алгоритм “хвост змеи для заполнения прямоугольной области”.

Молочников Олег Spb. 2014.

Алгоритм “хвост змеи для заполнения прямоугольной области”.

При разработке //sale.itcity.ru/public/275582/ столкнулся с необходимостью распределить выделенные задания на прямоугольную область календаря. В результате родился алгоритм, который может пригодиться не только мне и не только в этой задаче.

Итак:  Есть прямоугольная область произвольного размера. Необходимо разделить ее на несколько областей , расположенных одна за другой по принципу движения змеи, следующим образом: 

Сначала создадим функцию Координаты хвоста змеи, которая,  возвратит нам смешение по горизонтальной и вертикальной оси от начала координат в верхнем левом углу, для любой произвольной прямоугольной области по номеру сегмента змеи.  (На рисунке вверху номер сегмента змеи отображен цифрами от 1 до 20).

Функция ПолучитьКоординатыХвостаЗмеи(ПравоОбласти,ЛевоОбласти,НизОбласти,ВерхОбласти,СегментХвоста)
    КоординатыСегментаХвостаЗмеи=Новый Структура("Лево, Верх");
    ВысотаОбласти= НизОбласти-ВерхОбласти+1;
    КоординатыСегментаХвостаЗмеи.Верх= (ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти+ВерхОбласти;
    КоординатыСегментаХвостаЗмеи.Лево= Цел((СегментХвоста-1)/ВысотаОбласти)+ЛевоОбласти;
    Возврат КоординатыСегментаХвостаЗмеи;
КонецФункции

Теперь  сам  алгоритм:

//Входные данные:

Лево,Право,Верх,Низ  - координаты области к заполнению.

КоличествоВыделенныхЭтапов –Количество этапов подлежащих распределению;

    КоличествоРядовКЗаполнению=Право-Лево+1;

    КоличествоСтрокКЗаполнению=Низ-Верх+1;

    КоличествоЯчеекКЗаполнению=КоличествоРядовКЗаполнению*КоличествоСтрокКЗаполнению;
    КоличествоЯчеекНаЭтап= Цел(КоличествоЯчеекКЗаполнению/КоличествоВыделенныхЭтапов);
    Если КоличествоЯчеекНаЭтап<1 Тогда
        Отказ=Истина;
        ОбщегоНазначения.СообщитьОбОшибке("Выбранная область слишком мала для размещения выбранных этапов!",Отказ);
        Возврат;
    КонецЕсли;
    НераспределенныеЯчейкиКЗаполнению=КоличествоЯчеекКЗаполнению%КоличествоВыделенныхЭтапов;
    ИндексВыделеннойСтроки=0;
    ТекущийСегментХвоста=1;
    Пока ТекущийСегментХвоста<=КоличествоЯчеекКЗаполнению Цикл
        Если НераспределенныеЯчейкиКЗаполнению >0 Тогда
            Шаг=КоличествоЯчеекНаЭтап+1;
            НераспределенныеЯчейкиКЗаполнению=НераспределенныеЯчейкиКЗаполнению-1;
        Иначе
            Шаг=КоличествоЯчеекНаЭтап;
        КонецЕсли;
        НомерПоследнегоСегмента=ТекущийСегментХвоста+Шаг-1;
        КординатыНачалаТекущегоЭтапа=ПолучитьКоординатыХвостаЗмеи(Право,Лево,Низ,Верх,ТекущийСегментХвоста);
        КординатыКонцаТекущегоЭтапа=ПолучитьКоординатыХвостаЗмеи(Право,Лево,Низ,Верх,НомерПоследнегоСегмента);
        ЧислоРядов=КординатыКонцаТекущегоЭтапа.Лево-КординатыНачалаТекущегоЭтапа.Лево+1;
        Для I=0 по ЧислоРядов-1 Цикл
            Если I=0  Тогда
                ЛевоРяда=КординатыНачалаТекущегоЭтапа.Лево;
                ВерхРяда=КординатыНачалаТекущегоЭтапа.Верх;
            Иначе
                ЛевоРяда=КординатыНачалаТекущегоЭтапа.Лево+I;
                ВерхРяда=Верх;
            КонецЕсли;
            Если I=ЧислоРядов-1 Тогда
                ПравоРяда=КординатыКонцаТекущегоЭтапа.Лево;
                НизРяда=КординатыКонцаТекущегоЭтапа.Верх;
            Иначе
                ПравоРяда=КординатыНачалаТекущегоЭтапа.Лево+I;
                НизРяда=Низ;
            КонецЕсли;
       // текст кода занимающий в таблице сам этап            

//ЗанятьИнтервалСервер(ПравоРяда,   ЛевоРяда,   НизРяда, ВерхРяда,НомерЭтапа);
        КонецЦикла;
        ТекущийСегментХвоста=НомерПоследнегоСегмента+1;
        ИндексВыделеннойСтроки =ИндексВыделеннойСтроки+1;
    КонецЦикла;

Пример работы алгоритма на распределении пяти этапов по произвольному интервалу времени:

PS: Надеюсь вам понравится эта и другие мои разработки на //sale.itcity.ru/profile/48714/.

Очень жду ваших комментариев  и пожеланий.

Молочников Олег Spb. 2014.