Системы автоматизированного проектирования (САПР, CAD) – класс программных систем, которые поддерживают все этапы цифрового проектирования: от параметрического эскиза и твердотельного моделирования до проверки правил, подготовки спецификаций и обмена данными. С точки зрения информатики САПР – это совокупность строго определённых структур данных, алгоритмов вычислительной геометрии, решателей ограничений, графовых моделей зависимости операций и форматов представления (файловые протоколы).

Для подготовки к ЕГЭ по информатике тема САПР ценна тем, что тренирует:

• владение матрицами и векторами (аффинные преобразования),

• умение формализовывать ограничения и решать системы уравнений,

• работу с графами зависимостей (топологическая сортировка, ацикличность),

• анализ сложностей алгоритмов и корректность вычислений с плавающей точкой,

• файловые и структурные операции (кодирование, иерархия объектов, сериализация).

Формальная модель САПР

1. Объектная модель
   

   САПР оперирует набором объектов:

   Объект = <Геометрия, Параметры, Ограничения, Атрибуты, Связи>

   • Геометрия: кривые, поверхности, твёрдые тела.

   • Параметры: числовые величины (длины, радиусы), именованные.

   • Ограничения: равенства/неравенства (параллельность, совпадение, перпендикулярность, фиксированная длина).

   • Атрибуты: слой, цвет, материал, метки.

   • Связи: зависимость от других объектов (история построения, «дерево операций»).

2. Представления геометрии
   

   Основные структуры данных:

   • B-Rep (boundary representation) – тело как «герметичная» оболочка из граней/рёбер/вершин.

   • CSG (constructive solid geometry) – тело как дерево булевых операций над примитивами.

   • NURBS – рациональные B-сплайны/поверхности для точной кривизны.

   • Сеточная аппроксимация – треугольная тесселяция (например, для рендеринга/печати).

3. История построения как граф
   

   Дерево (на практике – DAG) операций:

   Вершина: операция (эскиз, выдавливание, вырез, скругление, массив)

   Ребро: «B» зависит от результатов «A»

   Требование ацикличности обеспечивает возможность топологической сортировки (порядок пересчёта).

Математическая основа (копируемые формулы)

1. Однородные координаты и аффинные преобразования
   

   Для 2D:

   [x' y' 1]^T = [x y 1]^T · T

   T = | a11 a12 tx |

       | a21 a22 ty |

       |  0   0  1  |

   Для 3D:

   [x' y' z' 1]^T = [x y z 1]^T · M

   Базовые матрицы (2D):

   Поворот на угол θ:

   R(θ) = | cosθ -sinθ 0 |

          | sinθ  cosθ 0 |

          |  0      0  1 |

   Масштаб s_x, s_y:

   S = | s_x  0  0 |

       |  0  s_y 0 |

       |  0   0  1 |

   Сдвиг (t_x, t_y):

   D = | 1 0 t_x |

       | 0 1 t_y |

       | 0 0  1  |

   Композиция преобразований – умножение матриц справа-налево.

2. Полиномиальные кривые (Бе́зье)
   

   Кривая Бе́зье степени n:

   B(t) = Σ_{i=0..n} (C(n,i) * (1 - t)^(n-i) * t^i * P_i),   t ∈ [0, 1]

   где P_i – контрольные точки, C(n,i) – биномиальные коэффициенты.

3. Параметризация и степени свободы
   

   Пусть p ∈ ℝ^k – вектор параметров, C(p) = 0 – система ограничений размерности m.
   Число степеней свободы:

   DoF = k - rank(J),  где  J = ∂C/∂p  – якобиан ограничений.

   Переопределённость (отрицательный DoF) или недоопределённость (положительный DoF) сигнализируют о проблемах модели.

Ключевые алгоритмы САПР

1. Решатели ограничений
   

   • Линейные – Гаусс/QR;

   • Нелинейные – Ньютон–Рафсон, Гаусс–Зейдель, декомпозиция на подграфы ограничений.
     Критерии завершения: ‖C(p)‖ ≤ ε и стабилизация ‖Δp‖ ≤ ε.

2. Булевы операции на твёрдых телах
   

   Для B-Rep: поиск пересечений граней, классификация, перестройка топологии.
   Для CSG: оценка по дереву с использованием BSP/октодеревьев (ускорение пересечений).

3. Тесселяция и оценка погрешности
   

   Аппроксимация поверхностей треугольниками по допуску δ:

   max расстояние(поверхность, сетка) ≤ δ

   Контроль кривизной и длины ребра для адаптивной сетки.

4. Пространственные индексы
   

   k-d-деревья, R-деревья, BVH – для ускорения поиска столкновений/выборок.
   Средняя сложность запросов близости: O(log n) при балансировке.

5. Топологическая сортировка истории
   

   Алгоритм Кана:

   1) in[v] := входная степень

   2) Q := { v | in[v]=0 }

   3) Пока Q не пуста: извлечь u, добавить в порядок, уменьшить in[w] для всех (u→w)

   4) Если порядок короче числа вершин – найден цикл (ошибка модели)

Стандарты данных и точность чисел с плавающей точкой

• Обмен геометрией: STEP, IGES, DXF, сетки – STL, PLY.

• Числовая устойчивость: избегать вычитания близких чисел; сравнивать с допуском: |a - b| ≤ ε

• Единицы измерения и допуски хранить явно; не смешивать системы.

Правила корректного параметрического моделирования

Правило 1. Именованные параметры. Каждому числовому параметру – осмысленное имя (H, W, R1).

Правило 2. Минимальность ограничений. Навязывайте только то, что необходимо; избегайте «жёстких» измерений там, где достаточно связей (параллельность/совпадение).

Правило 3. Контроль DoF. Стремитесь к DoF = 0 на эскизах/узлах.

Правило 4. Ацикличность дерева. Запрещайте ссылки «вперёд» по истории; при сомнении – выделяйте общие зависимости в ранние операции.

Правило 5. Допуски и единицы. Все сравнения – с допуском ε, все значения – в согласованных единицах.

Правило 6. Документирование. В комментарии к параметрам заносите диапазоны и смысл.

Правило 7. Декомпозиция. Сложную форму разбивайте на модули/подсборки с чёткими интерфейсами (аналог модульного программирования).

САПР и подготовка к ЕГЭ

• Матрицы/векторы – преобразования координат (задачи на линейную алгебру в программировании).

• Графы – порядок вычислений, обнаружение циклов (Кан/DFS).

• Ограничения – составление и решение систем уравнений; корректность по ε.

• Файлы/структуры – сериализация параметров, хранение таблиц спецификаций.

• Сложности – оценка O(n), O(n log n), O(n^2) для типовых геометрических задач (пересечения, сортировки рёбер и пр.).

Шпаргалка (основные формулы и схемы)

• Аффинное преобразование 2D:
  [x' y' 1]^T = [x y 1]^T · (D · R(θ) · S) 

• Кривая Бе́зье:
  B(t) = Σ_{i=0..n} C(n,i) (1-t)^(n-i) t^i P_i 

• Степени свободы:
  DoF = k - rank( ∂C/∂p ) 

• Сравнение с допуском:
  равно_с_точностью(a, b, ε) ⇔ |a - b| ≤ ε

Пять упражнений (академический формат)

Упражнение 1. Аффинные преобразования (матрицы и порядок умножения)

Задан отрезок AB в 2D: A(1, 2), B(5, 3). Требуется:
a) Выполнить масштаб s_x=2, s_y=0.5, затем поворот на θ=90° против часовой и сдвиг на t=(3, -1).
b) Записать единую матрицу T = D · R(θ) · S и вычислить новые координаты A', B' по формуле:  [x' y' 1]^T = [x y 1]^T · T

c) Объяснить, почему смена порядка (например, R · S · D) даёт иной результат (некоммутативность).

Упражнение 2. Контроль степеней свободы в эскизе

Эскиз прямоугольника задан вершинами P1..P4 и параметрами W (ширина), H (высота). Ограничения: P1P2 ⟂ P2P3, P1P2 ∥ OX, |P1P2| = W, |P2P3| = H, P1 фиксирован в (0,0).
a) Сформируйте вектор параметров p (координаты свободных точек + W, H).
b) Выпишите систему ограничений C(p)=0 (векторно).
c) Оцените DoF по формуле DoF = k - rank(J) на уровне рассуждений (какие переменные остаются свободными, какие связаны). Объясните, что означает DoF > 0/DoF < 0 для эскиза.

Упражнение 3. Топологическая сортировка дерева операций

Даны операции:

1. Эскиз S1, 2) Выдавливание E1 (зависит от S1), 3) Скругление R1 (зависит от E1),

2. Отверстие H1 (зависит от E1), 5) Массив M1 (зависит от H1).
   a) Постройте граф зависимостей и выполните алгоритм Кана: покажите шаги очереди нулевой входной степени.
   b) Добавьте связь R1 → S1. Объясните, почему возникает цикл, и как это проявится в алгоритме.
   c) Предложите корректировку модели для устранения цикла (перенос зависимостей, разбиение операции).

Упражнение 4. Тесселяция и допуск аппроксимации

Имеется дуга окружности радиуса R=10. Её аппроксимируют ломаной с шагом по углу Δθ.
a) Выведите оценку максимального отклонения дуги от хорды:

δ ≈ R * (1 - cos(Δθ/2))

b) Для заданного допуска δ_max = 0.01 найдите максимальный Δθ, удовлетворяющий неравенству δ ≤ δ_max.
c) Обсудите, как адаптивный шаг (зависимость Δθ от кривизны) уменьшает число сегментов.

Упражнение 5. Сравнение чисел с допуском и валидация пересечений

Даны два размера a и b, вычисленные разными ветвями алгоритма; допуск ε=1e-6.
a) Запишите предикат:

eq(a, b, ε) ⇔ |a - b| ≤ ε

b) В задаче пересечения отрезков используйте eq для проверки «коллинеарности» через векторное произведение. Объясните, почему прямое сравнение с нулём недопустимо при вещественной арифметике.
c) Предложите стратегию накопления ошибок: контроль величины шага, нормализация, периодическая переоценка точности.

Заключение

САПР – это строгая интеграция данных (B-Rep/CSG/NURBS/сетки), математики (аффинные преобразования, полиномиальные кривые, анализ степеней свободы), алгоритмов (решатели ограничений, тесселяция, булевы операции, пространственные индексы) и графов зависимостей. Освоение этих принципов напрямую укрепляет компетенции, проверяемые на ЕГЭ: от уверенной работы с матрицами и графами до аккуратного обращения с вещественной арифметикой и формальными инвариантами. Следуя изложенным правилам корректного моделирования и отрабатывая упражнения, вы получите не только теоретическое понимание САПР, но и практические алгоритмические навыки, необходимые для решения экзаменационных задач на высоком уровне.