Cтраница 2
Из таблицы можно сделать заключение, что ни одно из ребер куба не будет отсечено, так как все они без изменений пропускаются алгоритмом отсечения. [16]
В алгоритме отсечения вначале рассматривается выпуклое множество, определенное линейными ограничениями и условиями неотрицательности переменных исходной задачи, и отыскивается экстремальная точка этого множества. Если такое решение оказывается пецелочисленным, то добавляют ограничение, отсекающее текущую экстремальную точку и уменьшающее объем выпуклого множества. Однако новое ограничение не отсекает ни одной экстремальной точки выпуклой оболочки, принадлежащей допустимым целочисленным решениям. В конце концов вводится такое число дополнительных ограничений, что экстремальная точка усеченного выпуклого множества совпадает с экстремальной точкой выпуклой оболочки. Геометрическая интерпретация работы алгоритма будет пояснена на примере, приведенном в этом разделе. [17]
Отображение Г является задачей линейного программирования. Изучение трех алгоритмов отсечений мы начнем с исследования отображения Г, которое одинаково для всех этих методов. [18]
При каждом приложении различных преобразований к одному и тому же элементу псевдодисплейного файла может генерироваться совершенно иная последовательность дисплейных команд. Рассмотрим пример, приведенный на рис. 8.4. Здесь использован лишь один символ, но вследствие применения различных масштабных коэффициентов, а также алгоритма отсечения все пять высвеченных на экране привязок изменены различными способами. Поэтому необходимы пять различных кодовых последовательностей. [19]
К сожалению, описанный выше алгоритм отсечения недостаточно эффективен, если окно повернуто относительно координатных осей. Поэтому отсечение невидимых частей повернутого изображения выполняется после преобразования и для отсечения используются границы поля индикации. Неповернутые изображения обрабатываются до преобразования, с использованием границ окна для работы алгоритма отсечения. Программы выполнения этих двух операций по отсечению практически идентичны. [20]
Однако такой метод требует чрезвычайно много времени. Видимая часть отрезка может быть однозначно определена своими двумя конечными точками; алгоритм отсечения должен лишь вычислить их координаты. Са-зерлендом, позволяет не только очень быстро отыскивать указанные конечные точки, но еще быстрее отбрасывать все явно невидимые линии. В связи с этим данный алгоритм очень удобен для отсечения частей изображения, значительно выходящих за пределы экрана. [21]
В некоторых дисплеях эта проблема решается с помощью простого отсечения части изображения, выходящего за пределы экрана. К сожалению, при этом способе непродуктивно затрачивается время на прочерчивание невидимых частей изображения. Поэтому если даже видимая его часть содержит мало линий, то картина на экране будет мелькать. В идеальном случае информация, подаваемая на дисплей, должна содержать лишь то, что отображается на экране. Следовательно, необходимо иметь алгоритм отсечения для отбрасывания тех частей изображения, которые лежат за пределами экрана. [22]