ТЕХНОЛОГИИ ПРИМЕНЕНИЯ ГЕОМЕТРИЧЕСКОГО ИНСТРУМЕНТА. ЛОГИЧЕСКИЙ СИНТЕЗ

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

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

Для решения проблемы информационного перенасыщения чертежа можно предложить два способа ее разрешения. Суть первого способа состоит в том, что все дополнительные построения лишь для единственного решения из всего множества альтернатив можно реализовать в отдельном алгоритме, превратив его в процедуру (преобразователь с закрытой структурой). Тогда суть комбинаторного построения будет заключаться в многократном обращении к множеству таких процедур из основного вызывающего алгоритма, в котором каждому из вызовов будет соответствовать вполне определенная комбинаторная перестановка исходных данных. Достоинством данного метода является то, что необходимые решения будут в конце концов получены, однако ответственность за правильную подготовку и полноту исходных данных лежит на программисте, реализующем конструктивную модель. Среди его недостатков наиболее значимыми являются следующие два аспекта. Во-первых, при процедурном подходе к решению задачи теряется возможность проследить органическую связь дополнительных построений различных альтернатив друг с другом, в то время как эта связь существует и может представлять большой научный и практический интерес. Второй недостаток заключается в том, что при описанном подходе количество перестановок исходных данных в принципе нельзя сделать переменным, находящимся в непосредственной зависимости от структуры и природы исходных данных. Особенно этот недостаток дает о себе знать при создании конструктивных моделей многомерных пространств, в которых алгоритмы, описывающие процессы взаимодействия объектов этих пространств, имеют переменную иерархическую структуру.

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

Возможности интеграции конструктивного геометрического моделирования с логическим программированием способствует то обстоятельство, что геометрическая модель проявляет реляционные качества по своей природе, а отношения геометрического алгоритма можно представить, как факты логической программы, которая будет выражаться обычными предикатами языка Prolog, обладающими "побочным  геометрическим" эффектом. Применительно к системе Симплекс  процесс автоматизированного синтеза конструктивной геометрической модели представляет собой не только формирование программы внутри проекта системы, но он оказывает влияние и на содержание базы данных подсистемы логического интерпретатора на языке Prolog, разработанного специально для этой системы. Любое изменение состава отношений в алгоритмах проекта системы Симплекс приводит к немедленному изменению базы данных подсистемы Prolog. А это значит, что содержимое этой базы может обрабатываться и изменяться всеми средствами, присущими языку логического программирования, чем и обусловлена та широта возможностей, которая открывается перед методами конструктивного геометрического моделирования. В рамках данной статьи рассмотрим реализацию нескольких простых задач. Эти задачи никоим образом не следует воспринимать, как предъявление каких-то новых достижений и результатов в геометрической теории.  Задачи должны продемонстрировать только суть предлагаемой методики проектирования и, возможно, определить новые направления исследований в области конструктивного геометрического моделирования.

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

Поскольку основным "строительным" элементом геометрических алгоритмов в системе Симплекс является отношение, то и в логической подсистеме отношению соответствует схожий по структуре предикат.

Предикат отношения в наиболее полной форме записывается следующим образом: @r(In,Out,Fm,Fun,Alg)., где In – список списков входных параметров отношения, Out – список выходных параметров отношения, Fm – признак согласования параметров, Alg – имя алгоритма, которому принадлежит данное отношение. Имена списочных переменных системы Симплекс соответствуют символьным термам. При использовании языка Prolog накладывается ограничение на названия имен списочных переменных системы Симплекс: поскольку все объекты языка Prolog, начинающиеся с прописной переменной, – суть переменные, а не термы, то во избежание недоразумений и ошибок, использование имен, начинающихся со строчной буквы, в Симплексе запрещается. Примером предиката, описывающего отношение для построения точки p1 с координатами 10 по X и 10 по Y будет запись следующего вида: @r([[10], [10]],   [p1],   '0', 'Точка задана координатами', 'Главный') (рис. 1).

Рис. 1. Конкретизированный результат вычислительной работы единственного отношения "Точка задана координатами"

Как известно, получение решения от системы Prolog достигается в результате активизации цели, записанной в виде предиката или конъюнкции предикатов. Решением логической программы может быть ответ "Да", если предъявляемую цель на основе данных, фактов и правил логической программы, не содержащей переменных, системе удается успешно доказать, и "Нет", если цель оказывается недоказуемой. Если в активизируемом целевом утверждении содержатся переменные, то при успешном разрешении целевого утверждения системой в консоль будет выведена конкретизация значений переменных. Поэтому, подготовив заранее какое-либо геометрическое построение, к Prolog-системе можно обращаться с вопросами о его содержании и структуре, сформулированными в виде целевых утверждений. Например, для того, чтобы удостовериться в том, что в алгоритме 'Главный' действительно имеется отношение, которое строит точку p1 с координатами 10 10 с помощью функции "Точка задана координатами" при простом согласовании параметров (рис. 1), к Prolog-системе следует обратиться с вопросом @r([[10], [10]],   [p1],   '0', 'Точка задана координатами', 'Главный'). Ответом системы будет слово "Да", поскольку в ее базе данных действительно присутствует аналогичный факт. При попытке задать вопрос @r([[10], [10]],   [p2],   '0', 'Точка задана координатами', 'Главный'). будет выдан ответ "Нет", так как система не обнаружит необходимого факта по отношению к геометрическому объекту p2. При задании вопроса вида @r([[10], [10]],   [X],   '0', 'Точка задана координатами', 'Главный')., где X – суть логическая переменная, система, выполнив унификацию [4, 5], выдаст ответ X=p1. Таким образом, формулируя тем или иным образом целевые утверждения, от системы можно получать содержательные ответы на интересующие пользователя вопросы. Так, например, для того чтобы определить, имеются ли на чертежах проекта вертикальные прямые линии (заданные функцией 'Прямая задана координатами двух точек') следует сформировать и активизировать цель:  @r([[X], [_], [X], [_]],   [Name],  _, 'Прямая задана координатами двух точек', _). В результате, из всех отношений базы данных (если таковые имеются) будут отобраны лишь те, у которых в первом и третьем параметрах координаты идентичны. Таким образом относительно легко могут решаться задачи, например, распознавания и обнаружения идентичности геометрических структур.

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

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

Рис. 2. Конструктивная модель – образец для создания логической программы

Таблица 1. Содержимое базы данных логической подсистемы, соответствующих построению рис. 2

@r([[-111], [22]],   [p1],   '0', 'Точка задана координатами', 'Главный').
@r([[47], [166]],   [p2],   '0', 'Точка задана координатами', 'Главный').
@r([[129], [70]],   [p3],   '0', 'Точка задана координатами', 'Главный').
@r([[p1], [p2]],   [o1],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p1], [p3]],   [o2],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p2], [p3]],   [o3],   '0', 'Прямая задана двумя точками', 'Главный').

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

Таблица 2. Заготовка логической программы

@r([[P1], [P2]],   [O1],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[P1], [P3]],   [O2],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[P2], [P3]],   [O3],   '0', 'Прямая задана двумя точками', 'Главный').

Оформив записи, как конъюнкцию подцелей, сформируем из них тело логического правила. В качестве головы правила используем предикат triangle(P1,P2,P3), с помощью которого от логической подсистемы можно будет получать данные о вершинах распознанных треугольников.

Таблица 3. Логическое правило для распознавания вершин треугольников в произвольном геометрическом построении

triangle(P1,P2,P3) if
    @r([[P1], [P2]],   [O1],   '0', 'Прямая задана двумя точками', 'Главный'),
    @r([[P1], [P3]],   [O2],   '0', 'Прямая задана двумя точками', 'Главный'),
    @r([[P2], [P3]],   [O3],   '0', 'Прямая задана двумя точками', 'Главный').

Применив целевое утверждение triangle(P1,P2,P3)., получим ответ (табл. 4).

Таблица 4. Ответ к задаче о нахождении треугольников в построении, представленном на рис. 2

#    P1    P2    P3
1    p1    p2    p3

Усложним задачу – соединим отрезками четыре произвольные точки (рис. 3).

Рис. 3. Исходное построение, в котором выполнено парное соединение четырех точек плоскости друг с другом

Факты, составляющие базу данных в этом случае, представлены в табл. 5.

Таблица 5. База данных Prolog-подсистемы для построения, представленного на рис. 3

@r([[-71], [37]],   [p1],   '0', 'Точка задана координатами', 'Главный').
@r([[-15], [131]],   [p2],   '0', 'Точка задана координатами', 'Главный').
@r([[81], [132]],   [p3],   '0', 'Точка задана координатами', 'Главный').
@r([[175], [39]],   [p4],   '0', 'Точка задана координатами', 'Главный').
@r([[p1], [p2]],   [o1],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p1], [p3]],   [o2],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p1], [p4]],   [o3],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p2], [p3]],   [o4],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p2], [p4]],   [o5],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[p3], [p4]],   [o6],   '0', 'Прямая задана двумя точками', 'Главный').

Активировав все ту же цель triangle(P1,P2,P3). применительно к той же логической программе, получим ответ (табл. 6).

Таблица 6. Ответ к задаче о нахождении треугольников в построении, представленном на рис. 3

#    P1    P2    P3
1    p1    p2    p3
2    p1    p2    p4
3    p1    p3    p4
4    p2    p3    p4

Разумеется, приведенный пример очень прост; он предназначен только для демонстрации принципа применения средств логического программирования в конструктивной геометрии и раскрывает лишь основы методики решения проектирования моделей. В нем, например, совершенно не учтено то обстоятельство, что отрезки могут задаваться двумя точками в обратном порядке, вершины сторон треугольника не должны совпадать, отрезки могут задаваться другими функциями, не проверяется колинейность вершин и т.п. В следующем примере (рис. 4) добавлена пятая вершина; условие же остается прежним. В табл. 7 приведена слегка усложненная программа, учитывающая возможность двунаправленного выбора вершин отрезков, а также введено условие упорядочения вершин в лексикографическом порядке для устранения ненужных дублирований. Полученный результат представлен в табл. 8.

Рис. 4.Исходное построение, в котором выполнено парное соединение пяти точек плоскости друг с другом

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

line (A,B) if
    @r([[A], [B]],   [_],   '0', 'Прямая задана двумя точками', 'Главный').
line (B,A) if
    @r([[A], [B]],   [_],   '0', 'Прямая задана двумя точками', 'Главный').

triangle(A,B,C) if
    line(A,B),
    line(B,C),
    line(A,C),
    lt(A,B),
    lt(B,C).

Таблица 8. Ответ к задаче о нахождении треугольников в построении, представленном на рис. 4

#    A    B    C
1    p1    p2    p3
2    p1    p2    p4
3    p1    p2    p5
4    p1    p3    p4
5    p1    p3    p5
6    p1    p4    p5
7    p2    p3    p4
8    p2    p3    p5
9    p2    p4    p5
10    p3    p4    p5

На основе анализа приведенных примеров следует сделать вывод о том, что конструктивная модель, имена объектов которой записаны с прописной буквы, могут быть интерпретированы не только как действующие геометрические машины, но и как прототипы логических программ.

Теперь рассмотрим задачу другого содержания. Она позволит нам понять возможности логического синтеза конструктивных геометрических моделей на простом примере: на построении всех паскалевых прямых для шести точек, принадлежащих конике.

Зададим какую-нибудь конику и произвольно разместим на ней шесть несовпадающих друг с другом точек a, b, c, d, e, f (рис. 5).

Рис. 5. Исходные данные к построению звезды Паскаля

Построим звезду Паскаля следующим образом:

Соединим точки a и e прямой o1.
Соединим точки a и d прямой o2.
Соединим точки b и f прямой o3.
Соединим точки b и d прямой o4.
Соединим точки c и f прямой o5.
Соединим точки c и e прямой o6.
Найдем точку пересечения p1 прямых o1 и o3.
Найдем точку пересечения p2 прямых o2 и o5.
Найдем точку пересечения p3 прямых o4 и o6.
Через триаду точек p1, p2 и p3 проведем прямую o7. Это возможно, поскольку по построению все три точки лежат на единой прямой Паскаля (рис. 6).

Рис. 6. Звезда и прямая Паскаля

Созданной геометрической конструкции соответствует следующий набор фактов в базе данных подсистемы Prolog. Та часть записей, которые непосредственно относятся к звезде и индуцируемой ею прямой Паскаля, выделены курсивом (табл. 9).

Таблица 9. Содержание базы данных, соответствующее построению, представленному на рис. 6

@r([[-252.5], [-84], [1], [-226.5], [18], [1], [-40.5], [38], [1], [18.5], [-52], [1], [-70.5], [-138], [1]],   [y1],   '0', 'Свободная коника', 'Главный').
@r([[y1], [1.513]],   [a],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[y1], [1.317]],   [b],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[y1], [1.166]],   [c],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[y1], [1.029]],   [d],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[y1], [0.8953]],   [e],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[y1], [0.7538]],   [f],   '0', 'Точка принадлежит объекту', 'Главный').
@r([[a], [e]],   [o1],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[a], [d]],   [o2],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[b], [f]],   [o3],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[b], [d]],   [o4],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[c], [f]],   [o5],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[c], [e]],   [o6],   '0', 'Прямая задана двумя точками', 'Главный').
@r([[o1], [o3]],   [p1],   '0', 'Точка пересечения двух прямых', 'Главный').
@r([[o2], [o5]],   [p2],   '0', 'Точка пересечения двух прямых', 'Главный').
@r([[o4], [o6]],   [p3],   '0', 'Точка пересечения двух прямых', 'Главный').
@r([[p1], [p2], [p3]],   [o7],   '0', 'Прямая задана триадой точек', 'Главный').

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

Таблица 10. Логическое правило для синтеза конструктивной геометрической модели, реализующей построение звезды и прямой Паскаля

pascal(A,B,C,D,E,F) if

    lt(A,E),
    lt(A,D),
    lt(B,F),
    lt(B,D),
    lt(C,F),
    lt(C,E),
    nnf(O1,'o','Главный'),
    nnf(O2,'o','Главный'),
    nnf(O3,'o','Главный'),
    nnf(O4,'o','Главный'),
    nnf(O5,'o','Главный'),
    nnf(O6,'o','Главный'),
    nnf(O7,'o','Главный'),
    nnf(P1,'p','Главный'),
    nnf(P2,'p','Главный'),
    nnf(P3,'p','Главный'),
    addline([[E], [A]], [O1], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[D], [A]], [O2], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[F], [B]], [O3], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[D], [B]], [O4], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[F], [C]], [O5], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[E], [C]], [O6], '0', 'Прямая задана двумя точками', 'Главный'),
    addline([[O1], [O3]], [P1], '0', 'Точка пересечения двух прямых', 'Главный'),
    addline([[O2], [O5]], [P2], '0', 'Точка пересечения двух прямых', 'Главный'),
    addline([[O4], [O6]], [P3], '0', 'Точка пересечения двух прямых', 'Главный'),
    addline([[P1], [P2], [P3]], [O7], '0', 'Прямая задана триадой точек', 'Главный').

В представленном правиле все термы, обозначающие имена списочных переменных проекта Симплекса, замещены соответственными переменными языка Prolog и записаны с прописной буквы. Имя предиката отношения @r заменено на имя системного предиката addline, основное предназначение которого заключается в пополнении проекта Симплекса отношениями, соответствующими его аргументам. Предикат addline выполняет такое пополнение в результате возникновения побочного внелогического эффекта. Его действие схоже с действием стандартного предиката print. Поэтому к моменту применения предиката addline все переменные, входящие в состав его параметров, должны быть унифицированы конкретными значениями. Имеенно поэтому набору предикатов addline предшествует последовательность системных предикатов вида nnf(Name,Prefix,Alg), которые генерируют новые еще не использованные в алгоритме Alg имена с префиксом Prefix и унифицируют их с переменными, записываемыми в параметре Name. Голова правила, представленная записью pascal(A,B,C,D,E,F) содержит имена переменных, соответствующих точкам, на которых строится звезда Паскаля. Для того чтобы избежать повторяющихся построений, с помощью группы предикатов lt(X,Y)  (X меньше Y) устанавливается порядок следования имен точек. В версии языка Prolog, разработанной для системы Симплекс, предикат lt имеет расширенное действие (лексикографическое сравнение имен термов), в отличие от стандарта языка Prolog, в котором предикату lt предписывается сравнивать числовые значения.

Представленное правило group(A,B,C,D,E,F) (табл. 10) пригодно для построения всех звезд и прямых Паскаля на всевозможных перестановках исходных данных. Однако правило формирования таких перестановок пока еще не определено. Такое правило можно записать, используя стандартный предикат member(X,L), который позволяет в переборе унифицировать с переменной X все элементы списка L. Поскольку в задаче имеется шесть точек, то для получения полного перечня их перестановок в переменных A,B,C,D,E,F следует использовать шесть предикатов member, указывая в качестве второго параметра каждого из них список из имен точек, расположенных на исходной кривой второго порядка. В получаемых выборках не должно быть одинаковых имен. За устранение возможных повторений отвечает предикат noduplicates. Нетрудно подсчитать, что число возможных выборок равно 1440. А это значит, что для получения всех прямых Паскаля требуется выполнить столько же построений. Естественно, выполнение такого количества чертежей вручную невозможно.

Таблица 10. Логическое правило для синтеза всех возможных выборок с неповторяющимися компонентами на множестве шести значений

group(A,B,C,D,E,F) if
    member(A,[a,b,c,d,e,f]),
    member(B,[a,b,c,d,e,f]),
    member(C,[a,b,c,d,e,f]),
    member(D,[a,b,c,d,e,f]),
    member(E,[a,b,c,d,e,f]),
    member(F,[a,b,c,d,e,f]),
    noduplicates([A,B,C,D,E,F]).

noduplicates([X|T]) if
    not_member(X,T),
    noduplicates(T).
noduplicates([X|[ ]]).
noduplicates([ ]).

not_member(X,T) if
    not(member(X,T)).

Применение логической программы для синтеза модели позволяет легко справиться с поставленной задачей. На рис. 7 представлен результат применения целевого утверждения group(A,B,C,D,E,F),pascal(A,B,C,D,E,F),execute. к исходным данным задачи. Как видно из иллюстрации, количество различимых решений, в принципе, невелико. Оно равно числу красных линий, представленных на чертеже.

Рис. 7. Все звезды и прямые Паскаля, построенные на множестве шести точек

Рисунок также дает ясно понять, что в процессе решения образовалось множество взаимосвязанных объектов (и конечно же отношений), многократно дублирующих друг друга. Для устранения этой избыточности применяется специальный инструмент системы Симплекс, также реализованный средствами логического программирования, который на основе сравнения структуры отношений и содержания их параметров выполняет необходимые сокращения и переименования объектов совокупного построения. Результат такого сокращения представлен на рис. 8.

Рис. 8. Звезды и прямые Паскаля после упрощения избыточной геометрической конструкции

Полученное решение позволяет сделать вывод о том, что конструктивная геометрическая модель, объекты которой представлены записями, начинающимися с прописной буквы, является прототипом логической программы, способной генерировать конструкцию геометрической модели по заранее созданному образцу. Эта особенность позволяет достаточно просто формулировать и реализовывать конструктивные геометрические задачи комбинаторного содержания.

И, наконец, последний пример. Задача, которая в нем представлена, может показаться трудной для понимания при общей простоте ее условия. Задачи именно такого рода становятся очень сложными для практического воплощения. В заключительной части статьи речь пойдет о динамическом синтезе конструктивных геометрических моделей по комплексу логических правил. Такая методика особенно ярко проявляет себя при решении задач многомерной геометрии средствами плоских проекционных геометрических моделей. Дело в том, что при увеличении размерности моделируемого пространства и объектов, порождающих в этих пространствах конструктивные геометрические схемы, неизменно подчиняются единым принципам синтеза, состоящим в рекурсивном обращении к схемам пространств более низкой размерности из пространств более высоких размерностей. Практическая реализация геометрических построений при размерности пространства выше четвертой представляет собой крайне трудоемкую и почти невыполнимую проблему. Но, несмотря на высокую трудоемкость, модель любого многомерного пространства обладает не только полноценным информационным наполнением, но и высокими характеристиками визуальности, которые не могут быть реализованы лишь по одной причине: они требуют создания для этих целей специальных инструментов, средств автоматизации и методики их применения к реальным практическим задачам.

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

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

Исходные данные формируются стандартными средствами системы. В принципе, они могут быть и результатом какого-то предварительного геометрического построения (рис. 9).

Рис. 9. Исходные данные к решению задачи о построении точек пересечения прямой линии и гиперсферы в пространстве произвольной размерности применительно к модели четырехмерного пространства

Перед синтезом модели, решающей задачу о нахождении точек пересечения прямой с гиперсферой, необходимо выделить  исходные объекты. В частности, сначала выделяются проекции прямой линии, а затем проекции очерков гиперсферы в соответственных полях проекций, в результате чего образуется единый список выделенных объектов, наполовину состоящий из имен прямых линий и наполовину из имен окружностей. В задачи предиката prepare входит разделение списка L выделенных объектов, считываемого системным предикатом  selected(L,'Главный',1) из первого окна главного алгоритма, на два списка L1 и L2 с равным количеством элементов, в первом из которых будут содержаться имена прямых, во втором – окружностей. Это условие достигается предикатами length(L,Length), is(A,div(Length,2)), append(L1,L2,L), length(L1,A). Корректность разделения обеспечивается при любой размерности решаемой задачи. Предикат prepare также строит две вертикальные линии и с помощью двукратного применения правила q опеределяет на исходных проекциях прямой линии по паре точек, которые необходимы для реализации преобразования проекций прямых в методе замены плоскостей проекции (в его многомерном варианте) [6, 7]. Полученные точки содержатся в списках W1 и W2, которые поступают в тело предиката build, ответственного за реализацию метода преобразования плоскостей проекций.

Предикат build осуществляет выбор первой пары точек X1 и X2, переданных ему предикатом prepare и использует их для построения новой оси O, по отношению к которой будет выполнено преобразование прямой в системе полей с размерностью, пониженной на единицу. Вслед за этим предикат определяет точки пересечения Q1 и Q2, через которые проходит проецирующая гиперсфера, для нахождения диаметра S отсекаемой ею от гиперсферы другой гипресферы, с размерностью на единицу меньшей, чем текущая. Затем предикат создает два отношения для пока еще не существующих линий связи G1 и G2, которые будут построены в результате возвращения в предикат точек QQ1 и QQ2 в результате обратного хода по рекурсии из вложенного вызова предиката build. На основании ожидаемой информации о прямых G1 и G2 формируются отношения для получения точек результата QQQ1 и QQQ2 от пересечения соответственных линий связи G1 и G2 с осью Axe системы заменяемых полей проекций.

Следует заметить, что в данной задаче предикат addline не применяется напрямую, как это было продемонстрировано в предыдущем примере. Поскольку информация о конкретных значениях многих имен объектов может быть получена лишь на этапе возврата из цепочки рекурсивных вызовов, побочный эффект предиката addline, выражающийся в добавлении к алгоритму проекта Симплекса новых отношений, привел бы к получению неверной конструкции алгоритма. Поэтому все предикаты addline представлены в виде одноименных составных термов, которые путем предварительной унификации с промежуточными переменными добавляются в накопительные списки. И только уже после окончания всех рекурсивных вызовов предикатов, конкретизации значений всех переменных и возвращения на верхний уровень логической программы, все элементы списков будут выбраны и к ним будет применен предикат addline посредством обращения к правилам make_program и make_attributes. Перечисленными здесь обстоятельствами еще раз подтверждается исключительная важность недетерминированного подхода к проектированию алгоритмов конструктивных геометрических моделей, который подробно обсуждался в [1, 2].

Обращение к предикату abc в теле предиката build позволяет выполнять построение проекций прямой в новых полях проекций. Построение ведется рекурсивно путем вызова предиката abc из самого себя. Преобразование заканчивается, когда список проекций прямых исчерпывается, то есть становится нулевым, что обнаруживается предикатом abc([ ], [ ], [ ], S, Axe, NAxe, A, B, C, M1, M1, M2, M2, M3, M3, K, K, _,_). В этом же условии выходные и накопительные списки унифицируются друг с другом, чем и обеспечивается возврат конкретизированных имен объектов в вызовы верхнего уровня. В этом же предикате выполняется создание двух отношений для построения проекций точек Z1 и Z2 пересечения прямой с гиперосферой на каждом из этапов понижения размерности пространства предикатом build.

Вернемся теперь к предикату build. Последним компонентом конъюнкции подцелей, составляющих тело правила, является обращение к самому себе build(Out1,Out2,Out3,O,K4,K3,Q1,QQ1,Q2,QQ2), то есть здесь собственно и происходит итерационное понижение размерности пространства. Этот процесс будет повторяться до исчерпания списка входных данных, и это состояние будет распознано за счет унификации очередного вызова с альтернативным определение предиката build([ ], [ ], [ ], Axe, K, K, Q1, Q1, Q2, Q2). Также, как и в случае предиката abc, в этом описании происходит унификация накапливаемых и окончательных списков с последующим возвращением наколенных значений по обратной цепочке рекурсии в предикаты более высокого уровня. Таким образом в результате всех выполненных унификаций предикат build возвращает в предикат prepare список K термы addline, которые представляют собой копию синтезированного алгоритма проекта Симплекса, решающего задачу о построении точек пересечения прямой линии с гиперсферой при произвольной размерности пространства.

Таблица 11. Комплекс универсальных логических правил для синтеза конструкции геометрической модели, предназначенной для решения задачи о пересечении прямой с гиперсферой, для модели пространства произвольной размерности

abc([ ],[ ],[ ],S,Axe,NAxe,A,B,C,M1,M1,M2,M2,M3,M3,K,K,_,_).
abc([X1|T1],[X2|T2],[X3|T3],S,Axe,NAxe,A,B,C,L1,Out1,L2,Out2,L3,Out3,K1,K3,Q1,Q2) if
    nnf(P1,'p','Главный'),
    nnf(P2,'p','Главный'),
    nnf(P3,'p','Главный'),
    nnf(XX3,'p','Главный'),
    nnf(CC,'p','Главный'),
    nnf(OTR,'o','Главный'),
    nnf(D,'d','Главный'),
    nnf(Z1,'p','Главный'),
    nnf(Z2,'p','Главный'),
    eq(PR1,addline([[X1], [Axe], [A], [NAxe]],   [P1],   '0', 'Точка в замене плоскостей проекций', 'Главный')),
    eq(PR2,addline([[X2], [Axe], [B], [NAxe]],   [P2],   '0', 'Точка в замене плоскостей проекций', 'Главный')),
    eq(PR3,addline([[X1],[X2]],[OTR],'0','Прямая задана двумя точками','Главный')),
    eq(PR4,addline([[X3]],[XX3],'0','Центр объекта','Главный')),
    eq(PR5,addline([[C]],[CC],'0','Центр объекта','Главный')),
    eq(PR6,addline([[XX3], [Axe], [CC], [NAxe]],   [P3],   '0', 'Точка в замене плоскостей проекций', 'Главный')),
    eq(PR7,addline([[P3],[S]],[D],'0','Окружность задана центром и диаметром','Главный')),
    eq(PR8,attribute(OTR,'Главный',[@alv(5)])),
    eq(PR9,addline([[Q1],[OTR]],[Z1],'0','Точка пересечения двух прямых','Главный')),
    eq(PR10,addline([[Q2],[OTR]],[Z2],'0','Точка пересечения двух прямых','Главный')),
    eq(List1,[PR1,PR2,PR3,PR4,PR5,PR6,PR7,PR8,PR9,PR10]),
    append(K1,List1,K2),
    append(L1,[P1],M1),
    append(L2,[P2],M2),
    append(L3,[D],M3),
    abc(T1,T2,T3,S,Axe,NAxe,A,B,C,M1,Out1,M2,Out2,M3,Out3,K2,K3,Q1,Q2).

attributes_lines(X) if
    eq(X,attribute(A,B,C)),
    attribute(A,B,C).
attributes_lines(addline(_,_,_,_,_)).

build([X1|T1],[X2|T2],[X3|T3],Axe,K1,K3,DM1,QQQ1,DM2,QQQ2) if
    nnf(O,'o','Главный'),
    nnf(Q1,'p','Главный'),
    nnf(Q2,'p','Главный'),
    nnf(QQQ1,'p','Главный'),
    nnf(QQQ2,'p','Главный'),
    nnf(S,'c','Главный'),
    nnf(G1,'o','Главный'),
    nnf(G2,'o','Главный'),
    eq(PR1,addline([[X1], [X2]],   [O],   '0', 'Прямая задана двумя точками', 'Главный')),
    eq(PR2,attribute(O,'Главный',[@alv(5)])),
    eq(PR3,addline([[O],[X3]],[Q1,Q2],'0','Точки пересечения прямой и окружности','Главный')),
    eq(PR4,addline([[Q1],[Q2]],[S],'0','Расстояние между точками','Главный')),
    eq(PR5,addline([[Axe],[QQ1],[90]],[G1],'0','Прямая проведена через точку под углом к прямой','Главный')),
    eq(PR6,addline([[Axe],[QQ2],[90]],[G2],'0','Прямая проведена через точку под углом к прямой','Главный')),
    eq(PR7,addline([[Axe],[G1]],[QQQ1],'0','Точка пересечения двух прямых','Главный')),
    eq(PR8,addline([[Axe],[G2]],[QQQ2],'0','Точка пересечения двух прямых','Главный')),
    eq(List1,[PR1,PR2,PR3,PR4,PR5,PR6,PR7,PR8]),
    append(K1,List1,K11),
    abc(T1,T2,T3,S,Axe,O,X1,X2,X3,[ ],Out1,[ ],Out2,[ ],Out3,K11,K4,G1,G2),
    build(Out1,Out2,Out3,O,K4,K3,Q1,QQ1,Q2,QQ2).
build([ ],[ ],[ ],Axe,K,K,Q1,Q1,Q2,Q2).

make_attributes([X|T]) if
    attributes_lines(X),
    make_attributes(T).
make_attributes([ ]).

make_program([X|T]) if
    program_lines(X),
    make_program(T).
make_program([ ]).

prepare(L1,L2,K) if
    selected(L,'Главный',1),
    length(L,Length),
    is(A,div(Length,2)),
    append(L1,L2,L),
    length(L1,A),
    nnf(E1,'o','Главный'),
    nnf(E2,'o','Главный'),
    addline([[-248.9], [106.8], [-248.9], [206.8]],   [E1],   '0', 'Прямая задана координатами двух точек', 'Главный'),
    addline([[-15.11], [65.83], [-15.11], [165.8]],   [E2],   '0', 'Прямая задана координатами двух точек', 'Главный'),
    attribute(E1,'Главный',[@alv(5)]),
    attribute(E2,'Главный',[@alv(5)]),
    q(E1,L1,[ ],W1),
    q(E2,L1,[ ],W2),
    build(W1,W2,L2,ox,[],K,_,QQ1,_,QQ2),
    execute.

program_lines(addline(A,B,C,D,E)) if
    addline(A,B,C,D,E).
program_lines(attribute(_,_,_)).

q(E,[X|T],A,W) if
    nnf(P,'p','Главный'),
    addline([[E],[X]],[P],'0','Точка пересечения двух прямых','Главный'),
    append(A,[P],M),
    q(E,T,M,W).
q(E,[ ],W,W).

Целевое утверждение, активирующее процесс логического синтеза конструктивной геометрической модели: prepare(M1,M2,K),make_program(K),make_attributes(K),execute. Напомним, что системный предикат execute предназначается для принуждения системы Симплекс к выполнению вычислительной работы всех алгоритмов проекта. Результат построения модели представлен на рис. 10.

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

Применим теперь логическую программу к задаче, представленной в пространстве седьмой размерности. Исходные данные к этой задаче представлены на рис. 11, а полученный результат на рис. 12.

Рис. 11. Исходные данные для решения задачи о пересечении прямой линии игиперсферы в семимерном пространстве

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

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

Список литературы

Бойков Алексей Александрович (28 марта 2019 г. 0:49)	Здравствуйте, Денис Вячеславович и Елена Петровна! Большое спасибо за статьи, которые наверняка будут интересны не только тем, кто хочет лучше понять принципы работы "Симплекса", но и так или иначе решает задачи разработки систем конструктивной геометрии. с уважением, А.Бойков
Волошинов Денис Вячеславович (29 марта 2019 г. 13:35)	Большое спасибо за добрые слова! Мы очень надеемся, что наш опыт будет полезен молодым разработчикам новых средств геометрического моделирования. В СПбГУТ  в этом году в рамках направления 09.03.02 на нашей кафедре будет открыт профиль бакалавриата, в рамках которого будут изучаться дисциплины, связанные с изучением конструктивного геометрического моделирования, начертательной геометрии (в том числе многомерной), других сопутствующих дисциплин, необходимых при разработке графических интерфейсов информационных систем, обрабатывающих большие потоки данных. Аналогичные, но, разумеется, более сложные вопросы составляют предмет рабочих программ магистратуры 09.04.02 и аспирантуры по специальности 05.13.18 (направление 09.06.01), которые уже действуют на кафедре.