2.1.4. Построение алгоритма поиска нитей
Для решения поставленной задачи применим метод полного перебора. Рассмотрим куб (рисунок 2.6а). Он представлен 3 плоскостями, каждая из которых содержит 9 ячеек. Поместим в центр куба частицу.
Остальные ячейки заполним таким образом, чтобы они контактировали только с центральной ячейкой, и не имели контакта между собой. При этом постараемся заполнить максимально возможное число ячеек.
а б в
Рисунок 2.6 - Некоторые варианты заполнения куба.
Очевидно, что куб, заполненный как показано на рисунок 36., имеет максимально возможное заполнение, удовлетворяющее выше указанным условиям, т.к.:
очевидно, что максимально возможное число ячеек в плоскости не соприкасающихся между собой - 4, это ячейки №1, 3, 7, 9.
заполнив плоскости по способу, предложенному в п.1, необходимо оставить плоскость 2 незаполненной, т.к. заполнение в ней любой ячейки нарушит условие заполнение куба.
В кубе, заполненном как показано на рисунок 36., существует только 1
нить,
В кубе, заполненном как показано на рисунок Зв., возможно существование стольких нитей, связывающих ПЛОСКОСТЬІ и плоскость 3, сколько имеется заполненных ячеек в плоскости 2.
В кубе, у которого количество заполненных и незаполненных ячеек в плоскостях 1 и 3 не совпадают, максимальное возможное количество нитей будет равняться числу заполненных ячеек в наименее заполненной плоскости.
Рассмотрим куб, который полностью заполнен (рисунок 2.7):
Таблица 2.1 - Пример ошибочного прокладывания нитей.
нить ячейка 1 ячейка 2 ячейка 3 1 плоскость 1 - 7; плоскость 2 - 8; плоскость 3-8; 2 плоскость 1 -4; плоскость 2-5; плоскость 3 - 5; 3 плоскость 1 - 1; плоскость 2-2; плоскость 3-2; 4 плоскость 1-8; плоскость 2-9; плоскость 3-9; г
5 плоскость 1 - 5; плоскость 2-6; j плоскость 3-6; 6 плоскость 1-2; у - ?
плоскость 2-3; | плоскость 3-3;
Но если проложить нити путями, как указано в таблице 1, после удаления этих нитей получится следующая картина (рисунок 2.8):
Видно, что 3 нити оказались потерянными.
Вывод - в зависимости от протяжения нитей через куб некоторые нити могут быть потерянны, хотя количества заполненных ячеек достаточно для большего количества нитей, чем было удалено.
Причины: неоптимальное протягивание нитей в моделируемом образце.
Следствие: необходимо проводить анализ удаляемых нитей для предотвращения потери нитей или анализировать расположение частиц в кубе при протягивании нитей для их оптимального протягивания.
Проблема: достаточно ли для предсказания потери (или при протягивании) нитей анализировать расположение частиц в кубе при протягивании нитей для их оптимального протягивания или необходимо анализировать расположение заполненных ячеек в дополнительных объемах.
Анализ: сначала рассмотрим упрощенную модель - плоскую матрицу размером 3x3 вместо куба размером 3x3x3 (рисунок 2.9а).
а Б В
Рисунок 2.9 - К объяснению возможности потери нитей.
Пусть удаляемая нить проходит через ячейки 1-5-8 (рисунок 2.96).
Если рассматривать только данную матрицу то очевидно, что удаление рассматриваемой нити не приведет к удалению еще какой либо другой нити. Теперь расширим нашу матрицу до размера 4x3 и заполним ее как показано на рисунок 2.9в. возьмем нить с тем же путем, но продолжим ее на 1 ячейку: 1-5-8- 12. Очевидно, что удаление данной нити прервет нить 3-5-8-10.Вывод: для определения возможности потери нити необходимо анализировать не куб, а прямоугольник с расширением размера в сторону анализируемой ячейки.
Конечно, расположение нитей такими путями не оптимально, но чтобы выявить самое оптимально расположение необходимо рассматривать все возможные варианты, что при прокладывании нитей через 3 мерные матрицы больших объемов объемы вычислений становятся слишком большими и не решает проблемы обрыва одних нитей при удалении других.
Рассмотрим варианты соприкосновения нитей в какой либо точке
(частицами п) при условии, что частицы п+1 и п-1 между собой соприкасаться не
будут (рисунок 2.10),
Некоторые варианты являются отражением данных состояний по
вертикали, горизонтали и по вертикали с горизонталью одновременно (ячейки
пронумерованы исключительно для удобства объяснения). После удаления
одинаковых матриц получим 7 возможных состояний (рисунок 2.11).
Рисунок 2.11 -7 вариантов соприкосновения нитей в какой либо точке (частицами п) при условии, что частицы п+1 и п-1 между собой
соприкасаться не будут.
Итак имеем 7 возможных состояний.
Попробуем дать рекомендации по прокладыванию нитей через массив таким образом, чтобы по возможности избежать перехода из одной нити в другую.
Во-первых, очевидно, что преимущество должно иметь движение вверх.
Но этого недостаточно, т.к. не над всеми частицами имеются другие частицы,
пусть даже и не своей нити. Следовательно, необходимо выделять каким либо
образом приоритетное направление при движении в какую либо сторону. На
примере распространения нитей, отображенных на рисунке 2.11(а - з), можно
предложить следующий алгоритм (рисунок 2.12).
Уточнение: в отдельно взятом кубе, центр которого лежит в рассматриваемой частице может быть только 3 частицы (включая центральную) принадлежащие нити, т.к.
3 частиц достаточно для пресечения куба в любом направлении от одной плоскости к какой либо другой.Уточнение: плоскость раздела проводим между частицами перпендикулярно прямой их контакта.
Пример проведение плоскости разделяющей нити приведен на рисунке
2.13
Рисунок 2.13 - Плоскость раздела между частицами.
Для получения нити наименьшей длины первоначальная выборка частиц должна производится в направлении к первоначальной оси нити, которая имеет координаты по оси X и Y равными соответствующим координатам стартовой (начальной) ячейки (рисунок 2.14). Начальное движение в любую сторону начинается в сторону наименьшего индекса.
Определим последовательность проверки 8 частиц в зависимости от положения центральной частицы относительно стержня нити. Для этого разобьем плоскости перпендикулярные нити на сектора как показано на рисунке 2.16.
Рисунок 2.16 - К определению последовательности проверки 8 частиц в зависимости от положения центральной частицы относительно стержня нити.
Стержень нити (выделен белым цветом) имеет координаты X:Y. Любая другая ячейка имеет смещение соответственно n:m. Если от координат стержня отнять координаты другой ячейки, то знаки у координат соответствующих секторов будут соответствовать координатам на рисунке 2.17.
Будем считать, что начало координат соответствует началу перебора массива и перебор начинается с движения вдоль оси X. Тогда зададим следующий порядок сдвига координат при просмотре ячеек:
Сектор 1:(1;-1)(1;0) (0;-1) (0;0) (-1;-1) (-1;0) <-1;-1) (0;1) (1-І) Сектор 2: (-1;-1)(0;-1)(-1;0)(0;0)(1;-1)(-1;1)(1;0) (0;1)(1;1) Сектор 3:(-1;1)(-1;0)(0;1)(0;0) (-1;-1) (1;1) (0;-1) (1;-1) (1;0) Сектор 4: (1;1)(1;0)(0;1)(0;0)(1;-1)(-1;1)(0;-1)(-1;0) (-1;-Г)
С помощью разработанной программы было произведено моделирование объемов с различной размерностью - 1 ООх 100х( 10-100), заполненного двухкомпонентной смесью, при различном процентном содержании дополнительного компонента по объему. По результатам моделирования построен график (см. рисунок 2,19). Как можно наблюдать на графике, при уменьшении количества дополнительного компонента до некоторых значений и при достижении определенной толщины образца образующиеся нити перестают достигать противоположенных граничных плоскостей.