Вторник, 13 Октябрь 2009 19:24

Алгоритм нумерации эпюр многогранников

Автор Александр Бушмелев
Оцените материал
(0 голосов)
Количество форм, порождаемых симметричными выпуклыми многогранниками огромно. Так, например, у икосаэдра насчитывается 59 форм. Для более сложных моделей звездчатых форм может насчитываться сотни и даже тысячи. Для того чтобы каким-то определенным образом идентифицировать звездчатые формы необходимо их каким-либо образом перенумеровать.

Одна из идей присваивания уникального кода звездчатой форме многогранника состоит в том, чтобы перенумеровать многоугольники эпюр исходного многогранника с учетом симметрий. У исходного многогранника может быть одна или несколько определяющих эпюр.

Эпюра может быть получена следующим образом. Выберем одну из граней исходного многогранника и проведем через нее плоскость. Продолжения остальные граней многогранника будут пересекать эту плоскость прямыми. Плоскость с набором прямых называется эпюрой.

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

Поскольку исходный многогранник может обладать набором пространственных симметрий, переводящих многогранник в себя, часть эпюр, будет совпадать друг с другом. Все множество эпюр (равное количеству граней исходного многогранника) разобьется на классы эквивалентности.

Количество этих разных классов эпюр дадут нам набор эпюр, описывающих пространство звездчатых форм. В дальнейшем, под разными эпюрами будем подразумевать эпюры из разных классов эквивалентности.

Каждая симметричная звездчатая форма полностью определяется набором многоугольников в каждой из эпюр. Остальные грани звездчатой формы можно получить используя симметрии исходного многогранника.

Таким образом, можно закодировать звездчатую форму, перенумеровав многоугольники в каждой из эпюр. Для каждой из форм будем записывать:

({i1,i2,...,in}, {j1,j2,...,jn}, ..., {k1,k2,...,kn} ),

где в первых фигурных скобочках перечислены все номера многоугольников, выбранных на первой эпюре, во вторых фигурных скобочках все номера многоугольников выбранных во второй эпюре и так далее для всех эпюр исходного многогранника.Подобная нумерация приведена в статье Звездчатые формы кубооктаэдра, где для случая кубооктаэдра приведены все найденные автором звездчатые формы кубооктаэдра.

Эпюра может содержать сотни многоугольников.

Эпюра треугольной грани ромбоикосододекаэдра

Пример одной из эпюр ромбоикосододекаэдра. Там в самой серцевине эпюры находится центральный треугольник.

Вручную произвести нумерацию довольно сложно и утомительно, поэтому был разработан алгоритм нумерации многоугольников, который реализован в программе PolyhedronEditor.

Алгоритм нумерации многоугольников в эпюре.

Центральному многоугольнику присваивается индекс 0

Центральный многоугольник помещается в очередь для обработки

Пока очередь не пуста

Текущий многоугольник - следующий из очереди

Обходим все ребра против часовой стрелки

Для каждого ребра ищем соседа текущего многоугольника

Если сосед существует и еще не перенумерован

Присвоить соседу следующий индекс

Поместить соседа в очередь для обработки

Всем симметричным соседу многоугольникам эпюры присваивается тот же индекс, что и соседа

Конец если

Конец Для каждого ребра

Конец Пока

Конец алгоритма нумерации многоугольников

Фокус с очередью позволяет получать нумерацию, которая распространяется концентрическими окружностями от центрального нуля до максимальных номеров на внешних многоугольниках.

На рисунке ниже приведен фрагмент эпюры ромбоикосододекаэдра с уже перенумерованными многоугольниками. Центральный треугольник с индексом 0 можно найти в левом нижнем углу. Максимальный индекс, найденный в этой эпюре - 202.

Фрагмент эпюры треугольной грани ромбоикосододекаэдра

 

В случае, когда центральный многоугольник является правильным нумерация будет однозначной. В случае двойственных архимедовым телам многогранников центральный многоугольник обладает неполной группой симметрии, поэтому нумерация будет зависеть от выбора первого ребра.

Фрагмент эпюры ромботриаконтаэдра

Центральный ромб с индексом 0 можно найти в левом нижнем углу. Легко понять, что от выбора первого ребра будет зависеть нумерация. Если выбрать начальным другое ребро индексы 2 и 3 поменяются местами.

Тем не менее, этот алгоритм позволяет получить индексацию эпюр многогранников, а следовательно, возможность кодирования многогранных форм.

Прочитано 6641 раз Последнее изменение Вторник, 13 Октябрь 2009 19:40
Авторизуйтесь, чтобы получить возможность оставлять комментарии