10.8. ПРОГРАММА-РЕДАКТОР ТОЧЕК
При построении кривых по точкам в задачах машинной графики требуется такой набор параметров, чтобы полученная на их основе кривая имела заданную форму. Часто очень трудно заранее выбрать подходящие значения этих параметров, поэтому приходится работать в интерактивном режиме. При использовании многочленов Безье необходимы средства для ввода множества точек-ориентиров, определения и воспроизведения многочлена. Если форма полученной кривой нас не устраивает, мы должны иметь возможность изменить размещение точек-ориентиров, ввести новые точки-ориентиры или удалить какие-то из старых. Основным инструментом для осуществления подобных операций служит программа интерактивного редактирования графической информации — диалоговый графический редактор. Мы будем называть его программой-редактором точек (чтобы отделить его от программ-редакторов изображений или текстов). Программу-редактор точек можно применить в целом ряде задач, помимо построения кривых по точкам, а его рассмотрение в данной главе не следует считать признаком того, что определение многочленов Безье представляет основную область использования этого редактора.
При разработке программы-редактора точек возникают две основные проблемы: структура данных, используемая для хранения точек, и средства ввода и адресации (указывания) точек.
10.8.1. СТРУКТУРА ДАННЫХ ДЛЯ ПРОГРАММЫ-РЕДАКТОРА ТОЧЕК
Простейшей из возможных структур является двухмерный массив координат х, у точек. Однако ее использование приводит к тому, что операции ввода и удаления становятся очень громоздкими. Лучше применять связный список. Элементы такого списка состоят из четырех компонент: координаты х, координаты у, адреса предшествующего элемента списка 
и адреса следующего элемента списка 
Эту структуру можно реализовать в виде
четырех одномерных массивов, причем в качестве адреса используется индекс массива.
Пример 10.9. Пусть исходными служат точки (5,8), (11,22) и (14,18) В таком случае элементы списка имеют вид
Здесь 0 обозначает указатель несуществующего элемента — именно таким образом отмечаются первая и последняя точки списка (рис. 10.8, 
). Если ввести точку (9,10) между первой и второй точками, то список принимает вид
(рис 10.8, б). Удаление последней точки последовательности (третьей в списке) приводит к следующему преобразованию списка.
(рис. 10.8,в); здесь указание удаляемой точки содержится в описании самой точки. Взаимная перестановка второй и последней точек приводит к следующему преобразованию списка.
(рис. 108, г).
Рис. 10.8 Расположения точек, рассмотренные в примере 10.9
Еще лучший способ реализации связного списка обеспечивается использованием массивов структур и указателей В принципе, оперирование данными при этом производится так же, как в приведенном случае, однако описание алгоритма упрощается. Определим структуру точка следующим образом:
(Предполагается, что читатель знаком со структурами и указателями, используемыми во многих языках программирования.) Точки воспроизводимой кривой заносятся в массив, состоящий из таких структур. Мы, как и прежде, будем применять символы О (указание на несуществующий элемент) и 
для обозначения первой свободной ячейки памяти, которую можно занять; символ 
обозначает указатель текущей ячейки памяти 
Таким образом, для воспроизведения линии между текущей и предыдущей точками
можно воспользоваться следующими командами (см. разд. 1.7, табл 1.1):
Первая команда обеспечивает вывод текущей точки на графопостроитель с координатами, определяемыми точкой, предшествующей точке, определенной указателем 
Вторая команда обеспечивает соединение двух точек вектором.
Пример 10.10. Следующая последовательность операций обеспечивает введение в список точки, причем пользователь указывает как позицию, в которую точка вводится, так и местоположение новой точки.
(см. скан)
При решении многих прикладных задач важно оперировать с группами точек, например с дугами. Для этого можно воспользоваться какой-нибудь иерархической структурой данных. Кривую можно представить с помощью указателя массива, содержащего точки этой кривой, и т. д.
Лучше писать программы, реализующие редактор точек, не ориентируясь на конкретное устройство отображения. В частности, ведущая программа должна иметь дело лишь с адресами (парами координат 
командами (используя общие названия) и, естественно, именами файлов. Все процедуры, ориентированные на конкретное устройство отображения, должны быть выделены и явно определены как предназначенные для конкретной аппаратной реализации. (Более подробные сведения приведены в следующем подразделе.) Ниже приводится перечень типичных команд. Для выполнения каждой из перечисленных команд необходимо либо множество точек (число последних указывается в скобках), либо имя файла (в скобках помещается буква 
Буквы, набранные жирным шрифтом, обозначают сокращенные названия команд.
(см. скан)
(см. скан)
Введение команд insert и append предполагает, что пользователь предоставляет последовательность точек, добавляемых к списку. Необходима также специальная команда escape, указывающая, что процесс закончен.
