Алгоритм вырезки части векторного изображения в виде выпуклого ν-угольника

Секция автоматизированных систем научных исследований

УДК 681.3:528

О. А, Конюхов

АЛГОРИТМ ВЫРЕЗКИ ЧАСТИ ВЕКТОРНОГО ИЗОБРАЖЕНИЯ В ВИДЕ ВЫПУКЛОГО 14-УГОЛЬНИКА

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

— задание контура вырезки;

— отбор объектов, попадающих в контур, и обработка объектов, пересекающих грани;

— запись сформированной совокупности объектов в отдельный файл.

Наибольшую сложность составляет обнаружение объектов, пересекающих

контур, и их обрезка. Алгоритм отбора объектов многократно упрощается, если анализ на пересечение объекта с контуром вырезки проводится из известной точки, расположенной внутри выпуклого контура. Координаты такой точки определяются по формулам:

шин многоугольника.

Если многоугольник выпуклый, то точка М с координатами (Хт, Ут) будет всегда находиться внутри контура.

Задание контура вырезки осуществляется в диалоговом режиме. При этом обеспечивается контроль выпуклости задаваемого пользователем контура. После ввода вершин многоугольника, рассчитываются координаты Хт и Ут. Графические объекты могут располагаться относительно контура вырезки следующим образом:

— находиться внутри;

— располагаться вне контура; •

— пересекать одну или две грани.

Анализ положения объекта относительно контура производится следующим образом:

— строится точка М1—зеркальное отображение точки М относительно, грани;

— измеряются длины векторов О и Ш, проведенных из точек М и М1 к первому концу объекта;

— измеряются длины векторов Е и £1, проведенных из Точек М и М1 ко второму концу объекта.

Если И < 01 и Е < £1, то объект находится внутри контура и не пересекает его. Такие объекты сразу включаются в совокупность отбора. Если О > 01 и Е > Е1, то графический примитив расположен вне контура. Такие объекты исключаются из дальнейшей обработки. Из условий: О > 01 и £<£1 или О < 01 и £>£1 следует, что объект частично пересекает контур вырезки. Выступающие части объекта обзезаются по границе контура и примитив включается в совокупность отбора.

п

п

где X; и УI — абсцисса и ордината вершины многоугольника; п — число вер-

Известия ТРТУ

Специальный выпуск

Сформированная совокупность объектов графического изображения помещается в отдельный файл и может обрабатываться отдельно от основного чертежа. Для вырезки контура произвольной формы необходимо разделить его на многоугольники выпуклой формы и повторить алгоритм вырезки для каждого выпуклого контура.

УДК 681.3.06:681.518.3

С. В. Николаев

О ПРИНЦИПАХ ПОСТРОЕНИЯ ЛЕГКО НАРАЩИВАЕМОЙ

Возможны два подхода к созданию моделирующих программ при разработке систем: 1) создавать заново модель под каждую вновь проектируемую систему; 2) создать одну универсальную программу, которая может быть настроена на моделирование любой системы из заданного класса.

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

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

Предлагается компромиссный подход: разрабатывать моделирующую программу для частных задач, но с условием, чтобы она легко изменялась или наращивалась для создания на ее основе в последствии (путем настройки или генерации) других частных моделей с максимальным использованием уже имеющихся функциональных возможностей. Основная цель при этом — возможность развития с сохранением устойчивого «ядра». Для этого должны быть реализованы следующие принципы.

1. Программа должна строиться из модулей с минимальной зависимостью между ними.

2. Вызов всех модулей должен осуществляться единообразно.

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

4. Должны быть разработаны и соблюдены стандарты на данные межмодульного обмена (способ порождения имен файлов, размещение их в каталогах, вид хранимой информации и способы, кодирования).

Имеется определенный практический опыт создания моделирующих программ с учетом предложенных принципов. В качестве примера рассматривается программа МАС20 [1], которая первоначально была создана для моделирования измерительных систем с адаптивной дискретизацией сигналов на основе апертурных алгоритмов сжатия. Затем ее функциональные возможности были расширены без какой бы то ни было переделки, а только путем