35208

Графические информационные системы. Компьютерная графика

Шпаргалка

Информатика, кибернетика и программирование

Тесты ориентации точки относительно полигона. Тесты ориентации точки относительно полигона. Тесты ориентации точки относительно полигона. Тесты ориентации точки относительно полигона.

Русский

2013-09-09

970.5 KB

49 чел.

  1.  Геоинформационные системы. Общие принципы построения ГИС.
  2.  Особенности организации данных в ГИС. Технологии моделирования в ГИС.
  3.  Инструментальные средства ГИС. Применение ГИС.
  4.  Графические системы САПР и решение графических задач.
  5.  Классификация и общие принципы построения графических систем САПР.
  6.  Cовременная концепция проектирования. ЕСКД.
  7.  Методы улучшения растровых изображений: антиэлайзинг и дизеринг.
  8.  Основные понятия геометрического моделирования.
  9.  Системы координат.
  10.  Аффинные преобразования систем координат на плоскости и в пространстве.
  11.  Аффинные преобразования объектов на плоскости и в пространстве.
  12.  Геометрические модели плоских объектов. Основные понятия.
  13.  Способы описания (модели) прямой линии.
  14.  Взаимное расположение графических элементов на плоскости.
  15.  Уравнения пучка прямых и биссектрис угла.
  16.  Кривые 2-го порядка.
  17.  Сплайны. Кривые Безье.
  18.  Геометрический алгоритм кривой Безье.
  19.  Свойства кривой Безье.
  20.  Понятие полигона. Геометрическая модель плоского полигона.
  21.  Свойства плоских много-угольников.
  22.  Тесты ориентации точки относительно полигона. Выпуклый тест.
  23.  Тесты ориентации точки относительно полигона. Габаритный тест.
  24.  Тесты ориентации точки относительно полигона. Угловой тест.
  25.  Тесты ориентации точки относительно полигона. Лучевой тест.
  26.  Задача графического вывода фигур.
  27.  Простейший алгоритм закрашивания.
  28.  Волновой алгоритм закрашивания.
  29.  Алгоритм закрашивания линиями.
  30.  Алгоритмы заполнения, использующие математическое описание контура. Заполнение прямоугольника и круга.
  31.  Алгоритмы заполнения, использующие математическое описание контура. Заполнение полигона.

  1.  45 Геоинформационные системы. Общие принципы построения ГИС.

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

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

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

ГИС характеризуются следующими положительными моментами:

  •  наглядность представления семантической информации из БД за счет отображения взаимного пространственного расположения данных
  •  увеличение информационной емкости продукта за счет связи пространственно-ориентированных изображений с семантической информацией из БД
  •  улучшение структурированности информации и, как следствие, повышение эффективности ее анализа и обработки

Традиционный набор функций ГИС при работе с картой включает:

  •  показ карты в различных масштабах
  •  выбор набора слоев информации для показа
  •  зависимость внешнего вида объектов от их семантических характеристик
  •  оперативное получение информации об объекте при выборе его курсором мыши
  •  возможность распечатки любых фрагментов карты

Перечислить все области возможного применения ГИС затруднительно. Наибольшее распространение они получили в следующих отраслях:

  •  землеустройство (земельные кадастры)
  •  муниципальное хозяйство
  •  энергетика
  •  транспорт и связь

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

  1.  46 Особенности организации данных в ГИС. Технологии моделирования в ГИС.

Основой визуального представления данных при помощи ГИС-технологий служит так называемая графическая среда. Основу графической среды и соответственно визуализации базы данных ГИС составляют векторные и растровые модели.

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

  •  
    растровая модель;
  •  
    векторная нетопологическая модель;
  •  
    векторная топологическая модель.


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

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

Виды моделирования в ГИС.

Принципы моделирования в ГИС:

  1.  Создание и применение единой комплексной геоинформационной подосновы
  2.  Обеспечение единства модели на всех этапах и стадиях обработки информации
  3.  Проведение многовариантного проектирования и комплексной оценки проекта с использованием методов оптимизации.
  4.  Интерактивное взаимодействие с цифровой моделью.
  5.  Обеспечение максимальной инвариантности организации информационных ресурсов и простота их настройки на отраслевую специфику.

Виды моделирования в ГИС:

  1.  1) Операции преобразования форматов и представление данных
  2.  2) Проекционные преобразования
  3.  3) Геометрический анализ
  4.  4) Оверлейные операции
  5.  5) Функционально-моделирующие операции

  1.  47 Инструментальные средства ГИС. Применение ГИС.

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

 

Инструментальные ГИС
Это в наибольшем числе случаев самодостаточный пакет, включающий такой набор функционала, который покрывает все стадии технологической цепочки:
ввод - обработка-анализ - вывод результатов.
Самые мощные представители этого класса именуются "full GIS" (полнофункциональная ГИС).

Наиболее известными представителями этого класса являются:
- линия пакетов ARC/INFO компании ESRI, США (ARC/INFO, PC ARC/INFO, ArcCAD);
- линия пакетов компании Intergraph, США;
- SMALLWORLD (SmallWorld System, Великобритания);
- MapInfo (MapInfo Corporation, США).

 

ГИС-вьюверы
Это недорогие (по сравнению с full GIS), облегченные пакеты, с ограниченной возможностью редактирования данных, предназначенные в основном для визуализации и выполнения запросов к базам данных (в том числе и графическим), подготовленным в среде инструментальных ГИС. Большинство из них позволяют оформить и вычертить карту.
Как правило, все разработчики полнофункциональных ГИС предлагают и ГИС-вьюверы: ArcView1 и 2 ( ESRI, США), WinCAT( Simens Nixdorf, Германия).

 

Средства обработки данных дистанционного зондирования
Материалы, получаемые в результате аэро- и космических съемок, требуют большой предварительной обработки, которая и производится с помощью продуктов этого класса.
ГИС эффективны во всех областях, где осуществляется учет и управление территорией и объектами на ней. Это практически все направления деятельности органов управления и администраций: земельные ресурсы и объекты недвижимости, транспорт, инженерные коммуникации, развитие бизнеса, обеспечение правопорядка и безопасности, управление ЧС, демография, экология, здравоохранение и т.д.
ГИС позволяют точнейшим образом учитывать координаты объектов и площади участков. Благодаря возможности комплексного (с учетом множества географических, социальных и других факторов) анализа информации о качестве и ценности территории и объектов на ней, эти системы позволяют наиболее объективно оценивать участки и объекты, а также могут давать точную информацию о налогооблагаемой базе.

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

  1.   48 Графические системы САПР и решение графических задач.

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

Цели создания и задачи

В рамках жизненного цикла промышленных изделий САПР решает задачи автоматизации работ на стадиях проектирования и подготовки производства.

Основная цель создания САПР — повышение эффективности труда инженеров, включая:

  •  сокращения трудоёмкости проектирования и планирования;
  •  сокращения сроков проектирования;
  •  сокращения себестоимости проектирования и изготовления, уменьшение затрат на эксплуатацию;
  •  повышения качества и технико-экономического уровня результатов проектирования;
  •  сокращения затрат на натурное моделирование и испытания.

В автоматизации проектирования выделяют 2 уровня. Первый, более низкий, связан с атоматизацией, преимущественно, инженерно-графических работ и не затрагивает инженерных расчетов элементов конструкций, информационного обеспечения систем и ряда других важнейших вопросов проектирования изделий. Тем не менее, в настоящеее время наибольшее распространение получили графические системы, обеспечивающие именно такой уровень автоматизации. Это интерактивные графические редакторы, используемые в качестве высокомеханизированных электронных кульманов. В машиностроении они успешно применяются при проектировании оригинальных изделий на стадии их деталирования и реже в компоновочных работах. Примерами высокоразвитых графических систем, используемых для создания и редактирования чертежей, и получивших широкое распространение на Российском рынке, являются AutoCAD, КОМПАС и некоторые другие.

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

  1.   49 Классификация и общие принципы построения графических систем САПР.

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

По приложениям наиболее представительными и широко используемыми являются следующие группы САПР:

  •  САПР для применения в отраслях общего машиностроения. Их часто называют машиностроительными САПР или системами MCAD (Mechanical CAD);
  •  САПР для радиоэлектроники: системы ECAD (Electronic CAD) или EDA (Electronic Design Automation);
  •  САПР в области архитектуры и строительства.
  •  Кроме того, известно большое число специализированных САПР, или выделяемых в указанных группах, или представляющих самостоятельную ветвь классификации. Примерами таких систем являются САПР больших интегральных схем (БИС); САПР летательных аппаратов; САПР электрических машин и т. п.

По целевому назначению различают САПР или подсистемы САПР, обеспечивающие разные аспекты проектирования. Так, в составе MCAD появляются рассмотренные выше CAE/CAD/CAM-системы. По масштабам различают отдельные программно-методические комплексы (ПМК) САПР; системы ПМК; системы с уникальными архитектурами не только программного (software), но и технического (hardware) обеспечений.

По характеру базовой подсистемы различают следующие разновидности САПР:

  1.  САПР на базе подсистемы машинной графики и геометрического моделирования. Эти САПР ориентированы на приложения, где основной процедурой проектирования является конструирование, т. е. определение пространственных форм и взаимного расположения объектов. К этой группе систем относится большинство САПР в области машиностроения, построенных на базе графических ядер.
  2.  САПР на базе СУБД. Они ориентированы на приложения, в которых при сравнительно несложных математических расчетах перерабатывается большой объем данных. Такие САПР преимущественно встречаются в технико-экономических приложениях, например при проектировании бизнес-планов, но они имеются также при проектировании объектов, подобных щитам управления в системах автоматики.
  3.  САПР на базе конкретного прикладного пакета. Фактически это автономно используемые ПМК, например имитационного моделирования производственных процессов, расчета прочности по МКЭ, синтеза и анализа систем автоматического управления и т. п. Часто такие САПР относятся к системам САЕ. Примерами могут служить программы логического проектирования на базе языка VHDL, математические пакеты типа MathCAD.
  4.  Комплексные (интегрированные) САПР, состоящие из совокупности подсистем предыдущих видов. Характерными примерами комплексных САПР являются CAE/CAD/CAM-системы в машиностроении или САПР БИС. Так, САПР БИС включает в себя СУБД и подсистемы проектирования компонентов, принципиальных, логических и функциональных схем, топологии кристаллов, тестов для проверки годности изделий. Для управления столь сложными системами применяют специализированные системные среды.

ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ САПР

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

1. САПР — человеко-машинная система. Все созданные и создаваемые системы проектирования с помощью ЭВМ являются автоматизированными, важную роль в них играет человек — инженер, разрабатывающий проект технического средства.

В настоящее время и по крайней мере в ближайшие годы создание систем автоматического проектирования не предвидится, и ничто не угрожает монополии человека при принятии узловых решении в процессе проектирования. Человек в САПР должен решать, во-первых, все задачи, которые не формализованы, во-вторых, задачи, решение которых человек осуществляет на основе своих эвристических способностей более эффективно, чем современная ЭВМ на основе своих вычислительных возможностей. Тесное взаимодействие человека и ЭВМ в процессе проектирования — один из принципов построения и эксплуатации САПР.

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

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

  1.   50 Cовременная концепция проектирования. ЕСКД.

Определение и назначение 

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

*Конструкторская документация является товаром и на нее распространяются все нормативно-технические акты, как на товарную продукцию

Основное назначение стандартов ЕСКД состоит в установлении единых оптимальных правил выполнения, оформления и обращения конструкторской документации, которые обеспечивают:

1) применение современных методов и средств при проектировании изделий;

2) возможность взаимообмена конструкторской документацией без ее переоформления;

3) оптимальную комплектность конструкторской документации;

4) механизацию и автоматизацию обработки конструкторских документов и содержащейся в них информации;

5) высокое качество изделий;

6) наличие в конструкторской документации требований, обеспечивающих безопасность использования изделий для жизни и здоровья потребителей, окружающей среды, а также предотвращение причинения вреда имуществу;

7) возможность расширения унификации и стандартизации при проектировании изделий;

8) возможность проведения сертификации изделий;

9) сокращение сроков и снижение трудоемкости подготовки производства;

10) правильную эксплуатацию изделий;

11) оперативную подготовку документации для быстрой переналадки действующего производства;

12) упрощение форм конструкторских документов и графических изображений;

13) возможность создания единой информационной базы автоматизированных систем (САПР, АСУП и др.);

14) гармонизацию с соответствующими международными стандартами. Область распространения стандартов ЕСКД

Установленные стандартами ЕСКД правила и положения по разработке, оформлению и обращению документации распространяются на:

а) все виды конструкторских документов;

б) учетно-регистрационную документацию и документацию по внесению изменений в конструкторские документы;

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

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

Установленные в стандартах ЕСКД нормы и правила распространяются на указанную в перечислениях 1-4 документацию, разработанную предприятиями и предпринимателями (субъектами хозяйственной деятельности) стран-участников соглашения (СНГ), в том числе научно-техническими, инженерными обществами и другими общественными объединениями.

Состав и классификация стандартов ЕСКД

Межгосударственные стандарты ЕСКД распределяются по классификационным группировкам, приведенным в таблице 1.

Таблица 1.

0.

Общие положения

1.

Основные положения

2.

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

3.

Общие правила выполнения чертежей

4.

Правила выполнения чертежей изделий машиностроения и приборостроения

5.

Правила обращения конструкторских документов (учет, хранение, дублирование, внесение изменений)

6.

Правила выполнения эксплуатационной и ремонтной документации

7.

Правила выполнения схем

8.

Правила выполнения документов строительных и судостроения

9.

Прочие стандарты

  1.  65 Методы улучшения растровых изображений: антиэлайзинг и дизеринг.

Как уже отмечалось выше, основным недостатком растровой визуализации является эффект пикселизации.

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

Антиэлайзинг. В растровых системах при невысокой разрешающей способности (меньше 300 dpi) существует проблема ступенчатого эффекта (aliasing). Этот эффект особенно заметен на изображении наклонных линий – при большом шаге сетки растра пикселы образуют как бы ступени лестницы.

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

Устранение ступенчатого эффекта называется по-английски antialiasing. Для того чтобы растровое изображение линии выглядело более гладким, можно цвет угловых пикселов "ступенек лестницы" заменить на некоторый оттенок, промежуточный между цветом объекта и цветом фона.

Вычислим цвет пропорционально части площади ячейки растра, покрываемой идеальным контуром объекта. Если площадь всей ячейки обозначить как
 S,

а часть площади, покрываемой контуром, – Sx, то искомый цвет равен:

Методы сглаживания растровых изображений можно разделить на две группы:

● алгоритмы генерации сглаженных изображений отдельных простейших объектов (линий, фигур);

● методы обработки уже существующего изображения.

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

При сглаживании цветных изображений можно использовать модель RGB и производить фильтрацию по каждой компоненте.

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

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

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

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

Простейшим вариантом дизеринга можно считать создание оттенка цвета парами соседних пикселов.
 

Один из способов создания достаточно качественных изображений – диффузный дизеринг (diffused dithering). Он заключается в том, что ячейки создаются случайно (или псевдослучайно), поэтому даже для фрагмента растра пикселов с постоянным цветом не образуются регулярные структуры и изображение не выглядит созданным из ячеек.

  1.  66 Основные понятия геометрического моделирования.

Моделирование – один из основных методов познания, который заключается в выделении из сложного явления (объекта) некоторых частей и замещении их другими объектами, более понятными и удобными для описания, объяснения и разработки.

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

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

^ Геометрическое моделирование – раздел математического моделирования – позволяет решать разнообразные задачи в двумерном, трехмерном и, в общем случае, в многомерном пространстве.

^ Геометрическая модель включает в себя системы уравнений и алгоритмы их реализации. Математической основой построения модели являются уравнения, описывающие форму и движение объектов. Все многообразие геометрических объектов является комбинацией различных примитивов – простейших фигур, которые в свою очередь состоят из графических элементов - точек, линий и поверхностей. 

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

Геометрическое моделирование может использоваться при анализе числовых данных. В таких случаях исходным числовым данным ставится в соответствие некоторая геометрическая интерпретация, которая затем анализируется, а результаты анализа истолковываются в понятиях исходных данных.

^ Этапы геометрического моделирования:
● постановка геометрической задачи, соответствующая исходной прикладной задаче или ее части;
● разработка геометрического алгоритма решения поставленной задачи;
● реализация алгоритма при помощи инструментальных средств;
● анализ и интерпретация полученных результатов.


^ Методы геометрического моделирования:
● аналитический;
● графический;
● графический, с использованием средств машинной графики;
● графоаналитические методы.

  1.  67 Системы координат.

Система координат (СК) – совокупность базисных (линейно независимых) векторов и единиц измерения расстояния вдоль этих векторов (e1, e2, …, en).

Если базисные вектора нормированы (единичной длины) и взаимно ортогональны, то такая СК называется декартовой (ДСК).

^ Мировая система координат (МСК) – xyz – содержит точку отсчета (начало координат) и линейно независимый базис, благодаря которым становится возможным цифровое описание геометрических свойств любого графического объекта в абсолютных единицах.

^ Экранная система координат (ЭСК) – xэyэzэ. В ней задается положение проекций геометрических объектов на экране дисплея. Проекция точки в ЭСК имеет координату zэ = 0. Тем не менее, не следует отбрасывать эту координату, поскольку МСК 
и ЭСК часто выбираются совпадающими, а, вектор проекции 
[xэ, yэ, 0] может участвовать в преобразованиях, где нужны не две, а три координаты.

^ Система координат сцены (СКС) – xсyсzс –  описывает положение всех объектов сцены - некоторой части мирового пространства с собственным началом отсчета и базисом, которые используются для описания положения объектов независимо от МСК.

^ Объектная система координат (ОСК) – xоyоzо – связана с конкретным объектом и совершает с ним все движения в СКС или МСК.

П

равая ДСК – оси ориентированы так, что вращение ортов происходит в положительном направлении (против часовой стрелки с точки зрения наблюдателя, находящегося на конце третьего свободного орта):

^ Левая ДСК – оси ориентированы так, что вращение ортов происходит в отрицательном направлении.

В двумерном пространстве (R2) наиболее распространены декартова СК (x, y) и полярная СК (r, φ) (r – радиус-вектор точки, φ – угол поворота). Соотношение между ДСК и ПСК:



  1.  68 Аффинные преобразования систем координат на плоскости и в пространстве.

Аффинным называется преобразование, обладающее следующими свойствами:

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

Аффинные преобразования координат на плоскости:

(x, y) – двумерная система координат,

(X, Y) – координаты старой СК в новой системе координат.

Общий вид аффинного преобразования:


A, B, C, D, E, F – константы.

Обратное преобразование также является аффинным:

Простейшие аффинные преобразования системы координат.


   Параллельный сдвиг координат: 




Растяжение/сжатие осей:





Поворот системы координат (
x,y) на угол α:

Обратное преобразование – поворот системы (X,Y) на угол (-α):

Аффинные преобразования объектов на плоскости.

x, y – старые координаты точки, X, Y – новые координаты точки.

  1.  69 Аффинные преобразования объектов на плоскости и в пространстве.

x, y – старые координаты точки, X, Y – новые координаты точки.

1 Сдвиг:

Обратное преобразование:

  1.  Масштабирование объекта:



Обратное преобразование:

  1.  Поворот вокруг центра координат:



Обратное преобразование:

  1.  70 Геометрические модели плоских объектов. Основные понятия.

Положение точки в пространстве Rn (n-мерном пространстве) задается радиус-вектором p=[p1, p2, , pn], имеющим n координат p1, p2, , pn и разложение по n линейно-независимым базисным векторам e1, e2, , en : 
.
Таким образом положение точки на плоскости определяется радиус-вектором точки p=[px, py]= pxex +pyey или p=[r, φ] в полярной системе координат.
Расстояние между двумя точками p1 и p2 равно:

Линия на плоскости может быть задана с помощью уравнения в неявной форме: 
(НФ) f(x,y)=0;
или в параметрической форме:
(ПФ) p(t)=[x(t), y(t)].
В любой регулярной (гладкой и некратной) точке на линии p0=[x0, y0]=p(t0) возможна линеаризация кривой, т.е. проведение к ней касательной прямой, уравнения которой имеют вид
(НФ) Nx(x - x0) + Ny(y - y0) = 0 или N  (p - p0) = 0,
(ПФ) x(t) = x0 + Vx t, y(t)= y0 + Vy t или p(t) = p0 + Vt.
Вектор нормали N=[Nx, Ny] ортогонален линии и направлен в ту сторону, где f(p)> 0.
Направляющий вектор линии V=[Vx, Vy] начинается в точке p0 и направлен по касательной к p(t) в сторону увеличения t.
Векторы N и V ортогональны, т.е. N  V = 0 или NxVx + NyVy = 0.
Связь вектора нормали и направляющего вектора:
N=[Vy, - Vx], V=[-Ny, Nx]

  1.  71 Способы описания (модели) прямой линии.

Неявное уравнение прямой задается тремя коэффициентами A, B и D, составляющими вектор F=[A, B, D]:
(НФ): Ax+By+D=0.
Хотя бы одно из чисел A или B должно быть ненулевым. 
Если оба коэффициента ненулевые (A≠0 и B≠0), то прямая проходит наклонно к осям координат и пересекается с ними в точках (-D/A, 0) и (0, -D/B).
При A=0, B≠0 уравнение By+D=0 описывает горизонтальную прямую y= –D/B .
При A≠0, B=0 уравнение Ax+D=0 описывает вертикальную прямую x= –D/A.
Прямая проходит через начало координат: f(0,0)=0 при D=0.
Благодаря свойству прямой разделять плоскость на две полуплоскости с противоположными знаками, неявное уравнение позволяет определять положение точки (точек) на плоскости относительно прямой:
1) точка q лежит на прямой, если f(q)=0;
2) точки a и b лежат по одну сторону от прямой, если f(a)∙f(b)>0;
3) точки a и b лежат по разные стороны от прямой, если f(a)∙f(b)<0.
Для построения прямой по неявному уравнению необходимо и достаточно иметь либо две несовпадающие точки p0 и p1, через которые она проходит, либо точку p0 и направляющий векторV, с помощью которого вторая точка p1 вычисляется как p1=p0+V.

Из неявного уравнения прямой N=[A, B]  V=[-B, A].
Нормальное уравнение прямой – прямая описывается с помощью точки p0 и вектора нормали N и выводится из условия ортогональности векторов N и (p-p0) для всех точек p, принадлежащих прямой f(p)=N◦(p-p0).
Неявная функция позволяет оценить положение точки p относительно вектора нормали прямой:
● при f(a)>0 точка a лежит в том же полупространстве, куда направлена нормаль, а угол (a-p0, N) острый;
● при f(b)<0 угол (b-p0, N) тупой, а точка b и нормаль находятся по разные стороны от прямой.
Параметрическая функция прямой p(t)=p0+Vt, где 
V=[-Ny, Nx] удобна для задания и построения частей прямой – отрезков и лучей. Для этого необходимо указать пределы изменения параметра t:
● бесконечный интервал -<t< не ограничивает протяженность бесконечной прямой;
● при t0 получается луч, выходящий из точки p0 в бесконечность в направлении вектора V;
● конечный интервал t0≤t≤t1 определяет отрезок прямой между точками p0+Vt0 и p0+Vt1.
Благодаря левой ориентации направляющего вектора V относительно вектора нормали N эквивалентная нормальной форме функция

позволяет определить положение точки относительно направления движения по прямой:
● при f(a)>0 точка a лежит справа от точки p0, так что угол (a-p0, V) положительный;
● при f(b)<0 угол (b-p0, V) отрицательный, а точка b лежит слева от точки p0.
Неявная форма уравнения прямой, проходящей через две точки a=[ax, ay] и b=[bx,by], выводится из условия принадлежности прямой этих точек и точки p=[x,y].
Выбрав направление движения по прямой от точки a к точке b, получим направляющий вектор V=b-a и параметрическую модель линии:
(ПФ): x(t)=ax+(bx-ax)t, y(t)= ay+(by-ay)t или p(t)=a+(b-a)t.
Условие существования прямой очевидное: V≠0, т.е. a≠b.
При изменении параметра t от 0 до 1 движение точки происходит внутри отрезка ab от точки a до точки b.

  1.  72 Взаимное расположение графических элементов на плоскости.

1. Три точки p1, p2, p3 коллинеарны, т.е. лежат на одной прямой, если 


Взаимное расположение прямых.

  1.  Две прямые совпадают, если F1 × F2 =03 (векторное произведение равно нулевому вектору).
  2.  Две прямые параллельны, если 

 

  1.  Две прямые ортогональны, если N1◦ N2=0 или V1◦ V2=0.

Взаимное расположение точки и прямой

  1.  Уравнение перпендикуляра, опущенного из точки 
    q=[qx, qy] на прямую, выглядит следующим образом:

(НФ): Ny(x-qx)-Nx(y-qy)=0,
(ПФ): p(t)=q+Nt или p(t)=q+Vt , где V=[Vy, -Vx]=N.

  1.  Расстояние от точки q до прямой равно:

 
Зеркальное отражение точки 
q относительно прямой лежит на перпендикуляре к прямой на расстоянии 2d от q в сторону, противоположную проекции вектора q-p0 на нормаль N:

Пересечение двух прямых.
Пусть имеются две прямые, заданные уравнениями в НФ: 
A1x+B1y+D1=0 и A2x+B2y+D2=0,
тогда координаты точки пересечения вычисляются следующим образом:
 
Возможны следующие три случая:

  1.  A1B2-A2B1≠0, т.е. A1/A2≠B1/B2 – прямые не параллельны, точка пересечения единственная и ее координаты вычисляются по вышеприведенным формулам.
  2.  A1B2-A2B1=0, D1B2-D2B1≠0 или A1D2-A2D1≠0 – прямые параллельны и точек пересечения нет.
  3.  A1B2-A2B1=0, D1B2-D2B1=0 и A1D2-A2D1=0, т.е. прямые совпадают во всех точках.
  4.  73 Уравнения пучка прямых и биссектрис угла.

 Уравнение пучка прямых, заключенных между двумя, прямыми определяется следующим образом:
(НФ) 

(ПФ)

Изменение параметра пучка в интервале 0≤λ≤1 дает такие промежуточные прямые, что вращение происходит по кратчайшим углам.
Уравнение биссектрисы угла между двумя прямыми получается при λ=0,5, если |N1|=|N2| или |V1|=|V2|. В результате параметры биссектрисы можно найти по формулам 
Fбис=|N2|F1+|N1|F2, pбис(t)=q+Vбисt, Vбис=|V2|V1+|V1|V2.
Расчет биссектрис бывает необходим, например, при построении окружности, вписанной в треугольник. Как известно, ее центр лежит в точке пересечения биссектрис внутренних углов этого треугольника. При построении биссектрисы внутреннего угла следует учитывать направления подставляемых в формулу векторов сторон треугольника: они должны либо оба выходить из вершины, либо оба входить в нее. При несоблюдении этого правила по указанной формуле будет проведена биссектриса дополнительного угла треугольника, а окружность окажется вневписанной.

  1.  74 Кривые 2-го порядка.

Общий вид уравнения линии 2-го порядка:
a1x2+a2y2+a3xy+a4x+a5y+a6=0.
Рассмотрим различные формы линий 2-го порядка.
Уравнение окружности:
(x-x0)2+(y-y0)2=r2  нормальное уравнение окружности,
C(x0, y0) – центр окружности,
M(x,y) – произвольная точка окружности,
x2+y2+x+y+=0,
=-2x0; =-2y0; =x02+y02-r2.
Ax2+Ay2+Dx+Ey+F=0  общее уравнение окружности.
Действительная окружность при (2+2)/4-0, где =D/A; =E/A; =F/A.
Таким образом, действительная кривая 2-го порядка является окружностью тогда и только тогда, когда:
коэффициенты при квадратах текущих координат равны между собой;
отсутствует член, содержащий произведение текущих координат.                                

Центральные кривые 2-го порядка – кривые, имеющие собственный центр симметрии.
A(x-x0)2+C(y-y0)2=D, AC.
O(x0, y0) – центр симметрии кривой;
x=x0, y=y0 – оси симметрии кривой.
Пусть x0=0 и y0=0.
Кривая 2-го порядка принадлежит эллиптическому типу, если коэффициенты A и C имеют одинаковые знаки, т.е. A,C>0.
Пусть A>0 и C>0, тогда если:
● D>0 – действительный эллипс, x2/a2+y2/b2=1  каноническое уравнение эллипса;
● D=0 – вырожденный эллипс (кривая вырождается в точку);
● D<0 – мнимый эллипс.
Кривая 2-го порядка является кривой гиперболического типа, если коэффициенты A и C имеют противоположные знаки, т.е. AC<0.
Пусть A>0, тогда C<0:
● если D>0 – гипербола (рис. 7), x2/a2-y2/b2=1  каноническое уравнение гиперболы;
● если D=0 – вырожденная гипербола представляет собой пару пересекающихся прямых 
;

● если D<0 – сопряженная гипербола (рис. 7), xy=a2 (a>0) – обратная пропорциональность.
Нецентральные кривые 2-го порядка не имеют центра симметрии или имеют бесконечное множество центров, могут иметь ось симметрии.
(y-y0)2=2p(x-x0) – парабола, O(x0, y0) – вершина параболы, 
P – параметр параболы.
Если вершина параболы находится в начале координат и p>0, то y2=2px  каноническое уравнение параболы.

  1.  75 Сплайны. Кривые Безье.

Сплайн – гладкая кривая, которая проходит через две или более опорных точек, а также имеет расположенные вне ее управляющие точки, влияющие на форму сплайна. Наиболее общие типы сплайнов – кривые Безье и B-сплайны (B-spline curves). Типичным примером сплайнов являются также неоднородные рациональные B-сплайны (Non-Uniform Rational B-Spline – NURBS). Сплайны состоят из вершин (Vertices) и сегментов (Segments). Каждая вершина сплайна имеет касательные векторы (Tangents), снабженные на концах управляющими точками, или маркерами (Handels). Маркеры касательных векторов управляют кривизной сегментов сплайна при входе в вершину, которой принадлежат касательные векторы, и выходе из нее.
Кривые Безье разработаны математиком Пьером Безье. Кривые и поверхности Безье использовались в 60-х годах компанией "Рено" для компьютерного проектирования формы кузовов автомобилей. В настоящее время они широко используются в компьютерной графике.
Кривые Безье описываются в параметрической форме:
x=Px(t), y=Py(t).
Значение t выступает как параметр, которому отвечают координаты отдельной точки линии. 
Многочлены Безье для Px и Py имеют следующий вид:
  
где Cmi – сочетание m по i, а xi, yi – координаты точек ориентиров Pi. Значение m можно рассматривать и как степень полинома, и как значение, которое на единицу меньше количества точек-ориентиров.
Рассмотрим кривые Безье, классифицируя их по значениям m.
m=1 (по двум точкам). Кривая вырождается в отрезок прямой линии, определяемой концевыми точками P0 и P1. Параметрическое уравнение:
P(t)=(1-t)P0 + tP1.


m=2 (по трем точкам). Параметрическое уравнение:
P(t)=(1-t)2P0 + 2t(1-t)P1 + t2P2.


m=3 (по четырем точкам – кубическая). Используется довольно часто, в особенности в сплайновых кривых. Параметрическое уравнение:

P(t)=(1-t)3P0 + 3t(1-t)2P1 + 3t2(1-t)P2 + t3P3.


  1.  76 Геометрический алгоритм кривой Безье.

 Геометрический алгоритм для кривой Безье позволяет вычислить координаты (x, y) точки кривой Безье по значению параметра t (рис. 9).
Каждая сторона контура многоугольника, проходящего по точкам-ориентирам, делится пропорционально значению 
t.
Точки деления соединяются отрезками прямых и образуют новый многоугольник. Количество узлов нового контура на единицу меньше, чем количество узлов предыдущего контура.
Стороны нового контура снова делятся пропорционально значению 
t и т.д. Это продолжается до тех пор, пока не будет получена единственная точка деления – точка кривой Безье.


Сегмент кривой Безье 3-го порядка описывается положением четырех точек. Две из них являются опорными (узлами кривой): начальная точка P0 (x0, y0) и конечная P3 (x3, y3). Точки P1 (x1, y1) и P2 (x2, y2), определяющие положение касательных относительно отрезка, называются управляющими. Метод построения кривой Безье основан на использовании пары касательных (управляющих линий), проведенных к сегменту кривой в его окончаниях. На форму кривой влияют угол наклона касательной и длина ее отрезка.
Параметрическое уравнение Безье описывает положение точек и, тем самым, форму кривой. Уравнение решают относительно параметра t, принимающего значения от 0 (в начальной точке) до 1 (в конечной точке). При построении сегмента кривой Безье на плоскости рассчитывают координаты x и y (для четырех точек, из них двух управляющих):

R(t)=P0(1-t)3 + P1t(1-t)2 + P2t2(1-t) + P3t3, где 0<t<1;
x(t)=axt3 + bxt2 + cxt + x0;
x1=x0 + (cx:3); x2=x1 + [(cx+bx):3]; x3=x0 + cx + bx + ax;

y(t)= ayt3 + byt2 + cyt + y0;
y1=y0 + (cy:3); y2=y1 + [(cy+by):3]; y3=y0 + cy + by + ay.
Следовательно:
cx=3(x1-x0); bx=3(x2-x1)-cx; ax=x3 - x0 - cx - bx; 
cy=3(y1-y0); by=3(y2-y1)-cy; ay=y3 - y0 - cy - by.

Значение t определяет степень влияния точек на форму кривой. Например, при t=0,333 наибольший "вес" приобретает точка P1, а при t=0,666 – точка P2. Из приведенных уравнений вытекает, что кривая может проходить лишь через начальную и конечную опорные точки сегмента (P0, P3). Тем самым достигаются простота описания и стабильность кривой Безье.
Кривые Безье обладают рядом свойств, определяющих возможность их использования в векторной графике. С геометрической точки зрения, производной кривой Безье будет другая кривая Безье, векторы управляющих точек которой определяются вычислением разностей векторов управляющих точек исходной кривой.

  1.  77 Свойства кривой Безье.
    ● непрерывность заполнения сегмента между начальной и конечной точками;
    ● кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
    ● при наличии только двух контрольных точек сегмент представляет собой отрезок прямой линии;
    ● прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
    ● кривая Безье симметрична, т.е. обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
    ● масштабирование и изменение пропорций кривой Безье не нарушает ее стабильности, так как она, с математической точки зрения, "аффинно инвариантна";
    ● изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
    ● степень кривой всегда на единицу меньше числа опорных точек (т.е. при трех опорных точках форма кривой - парабола);
    ● размещение дополнительных опорных точек вблизи одной позиции увеличивает ее "вес" и приводит к приближению траектории кривой к данной позиции;
    ● окружность не может быть описана параметрическим уравнением кривой Безье;
    ● невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые).

  1.  78 Понятие полигона. Геометрическая модель плоского полигона.

Полигональная сетка (жарг. меш от англ. polygon mesh) — это совокупность вершин, рёбер и граней, которые определяют форму многогранного объекта в трехмерной компьютерной графике и объёмном моделировании. Гранями обычно являются треугольники, четырехугольники или другие простые выпуклые многоугольники (полигоны), так как это упрощает рендеринг, но сетки могут также состоять и из наиболее общих вогнутых многоугольников, или многоугольников с дырками.

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

 Контур полигона определяется вершинами, которые соединены отрезками прямых. В векторной форме полигон задается перечислением своих вершин: P={p1, p2, …, pn, p1}.С учетом принятого соглашения о правой ориентации нормали относительно направляющего вектора внешняя ориентация нормалей к сторонам полигона обеспечивается при его обходе против часовой стрелки.

  1.  79 Свойства плоских многоугольников.

 Пересечение прямой линии с полигоном. Прямая пересекает полигон, если существует хотя бы одна пара вершин, лежащих от нее по разные стороны (это свойство предполагает сравнение длявсех имеющихся пар вершин, а не только смежных).
^ Выпуклость полигона. У выпуклого полигона все углы 
 pi-1 pi pi+1 одного знака. Другими словами, при обходе выпуклого полигона по замкнутому контуру в произвольном направлении каждая вершина pi+1 расположена относительно ребра pi-1pi одинаково для всех значений i: слева при положительном направлении обхода и справа при отрицательном.
^ Самопересечение полигона. Полигон является самопересекающейся замкнутой ломаной линией, если у него существует хотя бы одна пара пересекающихся отрезков. Два отрезка пересекаются друг с другом, если концы одного находятся по разные стороны от прямой другого и наоборот (тестироваться должны все пары несмежных ребер полигона).

  1.  80 Тесты ориентации точки относительно полигона. Выпуклый тест.

 1. Выпуклый тест. Определяет положение точки относительно полигона (рис. 10): внешняя точка, внутренняя точка, граничная точка (внешнее подпространство полигона считается положительным, внутреннее – отрицательным, граница соответствует нулю).

 

  1.  81 Тесты ориентации точки относительно полигона. Габаритный тест.

Габаритный тест. Определяет гарантированную непринадлежность точки q произвольному полигону P путем сравнения ее координат с габаритами полигона – минимальными и максимальными координатами его вершин. Полностью задачу ориентации габаритный тест не решает, тем не менее, благодаря своей простоте, применяется во многих алгоритмах для быстрого обнаружения заведомо непересекающихся геометрических объектов (рис. 11).

  1.  82 Тесты ориентации точки относительно полигона. Угловой тест.

Угловой тест. Основан на вычислении и анализе алгебраической суммы углов i=(Vi, Vi+1) между смежными векторами Vi=pi-q, соединяющими точку q с вершинами pi, при обходе произвольного полигона P по замкнутому контуру в произвольном направлении. Т очка является внутренней, если сумма углов ∑i=2 π (рис. 12)

Точка является граничной (принадлежит границе полигона):
● если при расчете векторов получен нулевой вектор Vi=0, то тестируемая точка совпадает с вершиной pi;
● если при расчете углов i получен развернутый угол с модулем | i | = π, то тестируемая точка лежит на ребре pi pi+1.
Существуют две разновидности углового теста – радианный и октантный.

  1.  83 Тесты ориентации точки относительно полигона. Лучевой тест.

Лучевой тест ориентации точки q относительно полигона p заключается в выпускании из этой точки в произвольном направлении V луча p(t)=q+Vt ( t > 0) и подсчете числа его пересечений с ребрами p. Анализ пар дает следующие критерии ориентации точки относительно полигона: точка является внутренней, если число пар нечетно (ti>0, 0<i<1); точка является внешней, если число пар четно, в том числе равно нулю; точка лежит на границе p, если найдется хотя бы одна пара, для которой ti=0, 0i1.
Особенности лучевого теста (рис. 14):




● неопределенность числа пересечений при прохождении луча точно через вершину pi при i=1 или вершину pi+1 при i=0. Необходимо повторить тест заново с другим направлением луча V;
● требуется расчет параметров пересечения луча со всеми ребрами полигона.
Исследуются параметры пересечения луча с отрезками pi+(pi+1pi), 01.

  1.  84 Задача графического вывода фигур.

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

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

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

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

  1.  85 Простейший алгоритм закрашивания. 

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

  1.  Определить x0, y0.
  2.  Выполнить процедуру Закрасить(x0, y0).

Процедура Закрасить(x,y) описана в виде:

если цвет пиксела (x,y) не равен цвету границы, то

установить для пиксела (x,y) цвет заполнения;

закрасить(x+1, y);

закрасить(x-1, y);

закрасить(x, y+1);

закрасить(x, y-1).

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

  1.  86 Волновой алгоритм закрашивания.

Волновой алгоритм закрашивания был разработан Т.А. Блиновой и В.Н. Поревым и предназначался для расчета центра тяжести объектов по соответствующим изображениям – на основе волнового алгоритма поиска трассы на графе.

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

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

  1.  Алгоритм закрашивания линиями

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

  1.  Алгоритмы заполнения, использующие математическое описание контура. Заполнение прямоугольника и круга.

Математическим описанием контура может служить уравнение y=f(x) для окружности, эллипса или другой кривой. Для многоугольников (полигонов) контур задается множеством координат вершин (xi, yi). Возможны и другие формы описания контура. В любом случае алгоритмы данного класса не предусматривают обязательное предварительное создание пикселов контура растра - контур может совсем не выводиться в растр. Рассмотрим некоторые подобные алгоритмы заполнения.

Заполнение прямоугольника. Если прямоугольник задан координатами противоположных углов, например, левого верхнего (x1, y1) и правого нижнего (x2, y2), тогда алгоритм может заключаться в последовательном рисовании горизонтальных линий заданного цвета:

для y от y1 до y2 с шагом 1:

нарисовать горизонтальную линию с координатами (x1, y)-(x2, y)

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

Аналогично может быть построен и алгоритм заполнения эллипса.

  1.  Алгоритмы заполнения, использующие математическое описание контура. Заполнение полигона.

Математическим описанием контура может служить уравнение y=f(x) для окружности, эллипса или другой кривой. Для многоугольников (полигонов) контур задается множеством координат вершин (xi, yi). Возможны и другие формы описания контура. В любом случае алгоритмы данного класса не предусматривают обязательное предварительное создание пикселов контура растра - контур может совсем не выводиться в растр. Рассмотрим некоторые подобные алгоритмы заполнения.

Заполнение полигона. Контур полигона (в векторной форме) определяется вершинами, которые соединены отрезками прямых.

Один из наиболее популярных алгоритмов заполнения полигона заключается в закрашивании фигуры отрезками прямых горизонтальных линий. Алгоритм представляет собою цикл вдоль оси y, в ходе этого цикла выполняется поиск точек сечения линии контура с соответствующими горизонталями. Этот алгоритм получил название XY (Ж.Эгрон):

  1.  Найти min{yi} и max{yi} среди всех вершин Pi.
  2.  Выполнить цикл по y от y=min до y=max:
  3.  Найти точки пересечения всех отрезков контура с горизонталью y;
  4.  Координаты xj точек сечения записать в массив;
  5.  Отсортировать массив {xj} по возрастанию x;
  6.  Вывести горизонтальные отрезки с координатами

(x0, y) - (x1, y)

(x2, y) - (x3, y)

………………

(x2k, y) - (x2k+1, y)

Каждый отрезок выводится цветом заполнения.

В этом алгоритме использовано свойство топологии контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное число раз. Для выпуклых фигур существуют ровно две точки пересечения с любой прямой. Таким образом, на шаге 4 этого алгоритма в массив {xj} всегда должно записываться парное число течек сечения.

При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату y, совпадающую с yi вершины Pi, тогда надлежит анализировать то, как горизонталь проходит через вершину. Если горизонталь при этом пересекает контур (как, например, в вершинах P0  или P4), то в массив записывается одна точка сечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному минимуму или максимуму, как, например, в вершинах P1, P2, P3 или P5), тогда координата точки касания или не записывается, или записывается в массив два раза. Это условие четности числа количества точек пересечения, хранящихся в массиве {xj}.


 

А также другие работы, которые могут Вас заинтересовать

15003. Абайша сүйіп, Абайша күйіп жүрміз бе 135 KB
  АБАЙША СҮЙІП АБАЙША КҮЙІП ЖҮРМІЗ БЕ Атады таң батады күн толады ай. Ауысады күнде саба толағай. Бірі барда бірі болмай жоқты аңсап Неге пенде болды сонша қомағай Нәпсі сол ғой ныспы адам болғасын Тәркі өмір талқы тартыс додадай. Ақын ақын болмас еді а
15004. Азаттық жырының ақтаңгері (Дулат Бабатайұлы шығармашылығы) 50.5 KB
  Серікзат Дүйсенғазин Л.Н.Гумилев атындағы Еуразия ұлттық университетінің доценті филология ғылымдарының кандидаты АЗАТТЫҚ ЖЫРЫНЫҢ АҚТАҢГЕРІ Дулат Бабатайұлы шығармашылығындағы дәстүр мен жаңашылдық хақында Қазақтың ұлттық Ренессансының басы Аб...
15005. Айқап журналындағы оқу-тәрбие мәселелері 43 KB
  Айқап журналындағы оқутәрбие туралы ойларды зерделеу. XX ғасырдың бас кезінде яғни 1911 жылдың қаңтарынан бастап 1915 жылдың қыркүйек айына дейін Тройцкі қаласындағы Энергия баспахансында қазақ тілінде үзбей шығып тұрған Айқап журналы халқымыздың әлеуметтік с...
15006. Айналайын, Атажұртым 450 KB
  Қазақстан – ежелгі ел бірақ әлемнің қазіргі картасынан ол таяуда ғана яғни 1991 жылы орын алды. Біздің Отанымыз – егеменді тәуелсіз Қазақ мемлекеті. Жүз жиырмадан аса ұлт өкілдері тұратын осынау қасиетті мекенде асқақтаған Алатаулы өлкеде кеңшілігі керемет дархан даста...
15007. Ақиқаттан адасудың азабы 49 KB
  Ақиқаттан адасудың азабы Әнес САРАЙ Қазақстан Республикасы Мемлекеттік сыйлығының лауреаты. Шыңғыс Айтматовтың: €œАдам тұлға ретінде трагедиялық қобалжулар арқылы ашылады€ деп айтқаны бар. Шындығында өмір тану мен адам тану дегеніміз – осы екеуінің траг...
15008. Ақыт қажының Жиһаншаһ дастанындағы Шаһзада бейнесі 53.5 KB
  Таңғажайып Рымхан Е.А. Бөкетов атындағы Қарағанды мемлекеттік университетінің аспиранты АҚЫТ ҚАЖЫНЫҢ ЖИҺАНШАҺ ДАСТАНЫНДАҒЫ ШАҺЗАДА БЕЙНЕСІ Халық ақындарының шығармашылығындағы фольклорлық дәстүр мәселесін сөз еткенде ел аузында сақталып келген аңы...
15010. Ахмет Байтұрсынұлының Аққу, шортан, һәм шаян мысалы 69.54 KB
  Ахмет Байтұрсынұлы Аққу шортан һәм шаян мысалы. Ашық сабақ жоспары. Сабақтың тақырыбы: Ахмеn Байтұрсынұлы Аққу шортан Һәм шаян мысалы. Сабақтың мақсаты: а білімділік: Қазақ халқының бір тума ұлы Ахмет Байтұрсынұлының қазақ әдебиетін
15011. Алғашқы қазақ газеттерінің тарихы 39.5 KB
  Алғашқы шығарылған қазақ газеттерінің тарихы. Кез келген әдебиет бір күннің төңірегінде өрбитін немесе белгілі бір тарихи кезеңнің оқиғасын баяндайтын тар ұғымды дүние емес. Мәдениеті бай елдердің әдебиеті де қаз тұрып қалыптасқанша қоғамның дамуы секілді т