5.5. УЛУЧШЕННАЯ ПРОГРАММА

В нашей программе HIDLINPX большинство новых аспектов реализовано в функции Это очень сложная функция. Здесь уместно напомнить, что главное различие между нашей предыдущей программой HIDLIN и этой новой программой заключается в концепции полигонов и пикселов. Декомпозиция полигона на треугольники выполняется в основном так же, как в параграфе 3.5. Каждый раз, когда заканчивается считывание описания полигона, выполняется проверка, не является ли он задней гранью. Этот тест основывается на проверке треугольника, образуемого первыми тремя вершинами полигона. Тест подобен аналогичному тесту в программе HIDLIN и выполняется в функции counter_clock (отсюда и ее название — “против_часовой_стрелки”). Если первый треугольник ориентирован как задняя грань, то весь полигон игнорируется. В противном случае полигон не смотрит назад и придется определять ориентацию трех соседних вершин многократно. Таким же образом, как и в параграфе 3.5, находим треугольник, который должен быть отрезан от полигона. Попутно определяется длина диагонали, которая возвращается в программу через четвертый аргумент функции. Наконец, пятый аргумент является кодом, который

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

Если полигон не задний, то память должны быть записаны не только все треугольники, но и все ребра полигона, поскольку они являются отрезками прямых линий, которые, возможно, должны быть вычерчены, если они окажутся видимыми. Теперь предположим, что входными данными определены два полигона и и ни один из них не задний. Поскольку эти полигоны имеют одно общее ребро то этот отрезок будет записан в память дважды, если не предусматривать никаких мер против этого. С целью повышения эффективности необходимо предусмотреть условия, чтобы каждый такой отрезок PQ записывался только однажды. Это означает, что, прежде чем записывать отрезок PQ в память, следует проверить список записанных отрезков и, в случае если он уже имеется в этом списке, второй раз его не записывать. Все это должно быть выполнено эффективно с точки зрения затрат времени и занимаемой памяти, поскольку обычно вводится довольно большое количество отрезков. Есть несколько способов реализации такой операции. Вместо поиска желательно использовать один из номеров вершин допустим, меньший из них, в качестве индекса массива. Как и в программе у нас есть массив в который записываются прямоугольные координаты каждой вершины. Теперь дополним каждый элемент этого массива указателем на целое число. Фактически он будет указывать на первое из последовательности целых чисел. В языке Си имеются функции malloc и reallocy которые позволяют динамически отводить пространство памяти очень гибко и только на то время, когда оно действительно нужно. Поэтому здесь особенно полезной может оказаться функция realloc. Предположим, например, что заданы следующие пары номеров вершин именно в таком порядке, причем каждая пара обозначает отрезок, который нужно запомнить, если это еще не сделано

Эта информация запоминается в следующем виде:

Поле connect (“соединение") элемента массива например, указывает на последовательность 3, 2, 1, 3. Первое число 3 говорит о том, что далее следуют три номера вершин, а именно для отрезков и На языке Си можно записать

В этом примере имеем и

Заметим, что при необходимости записи в память отрезка (3 0) ради единообразия такая последовательность номеров заменяется на (0 3). Если такой последовательности еще нет, то она записывается в массив, начиная с элемента [0], вместо элемента Поиск каждого отрезка, который нужно записать в память, теперь обычно ограничен очень малой последовательностью, поэтому алгоритм работает очень быстро. Поскольку память отводится только в том объеме, который необходим, то этот способ экономичен и в отношении памяти. В программе эти операции выполняются в функции

Во многих отношениях программа HIDLINPX аналогична программе HIDLIN из параграфа 5.3. Это особенно касается основной части программы, а именно функции В программе HIDLIN она должна была проверять взаимосвязь каждого заданного отрезка со всеми треугольниками. В программе HIDLINPX набор треугольников, подлежащих анализу, обычно значительно меньше. Перед обращением к функции основная программа формирует этот набор на основе данного отрезка PQ и линейного списка, начинающегося в матрице Это выполняется в два этапа. На первом опять используются массивы и но теперь для обозначения пикселов, через которые проходит отрезок Это реализуется

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

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

Ниже приводится полный текст программы

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Эта программа использовала входные данные, приведенные в начале параграфа 5.4, и в результате получено изображение на рис. 5.20.

Рис. 5.20. Буква А в перспективе

УПРАЖНЕНИЯ

(см. скан)