1. Многоугольники. Свойства выпуклых многоугольников. Принадлежность точки многоугольнику.

Многоугольником (полигоном) обычно называется замкнутая ломаная линия, то есть линия, которая получается, если взять n любых точек A₁, A₂, ..., A_n и соединить прямолинейным отрезком каждую из них с последующей, а последнюю - с первой. Точки A₁, A₂, ..., A_n называются вершинами многоугольника, а отрезки A₁A₂, A₂A₃ ..., A_n-1A_n, A_nA₁-сторонами (ребрами). Многоугольник называется простым, если он не пересекает самого себя. Многоугольник называется плоским, если все его вершины лежат в одной плоскости. Простой плоский многоугольник охватывает односвязную область плоскости, которая считается его внутренней частью. Далее под многоугольником мы будем понимать простой плоский многоугольник вместе с его внутренней частью. То есть будем говорить, что точка принадлежит многоугольнику, если она принадлежит его границе или внутренней части.

Многоугольник называется выпуклым, если

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

или

2) отрезок, соединяющий его две любые его вершины целиком находится внутри многоугольника

или

3) многоугольник целиком расположен в одной полуплоскости относительно любого из его ребер

или

4) Любая прямая, не проходящая через вершину, пересекает ребра 0 или 2 раза.

или

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

или

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

Условия 1-6 эквивалентны.

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

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

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

2. Растровый и векторный способы представления изображений. Достоинства и недостатки.

В растровой графике изображение формируется из отдельных точек – пикселов (от picture element). Количество отображаемых пикселов на единицу длины называется разрешающей способностью или разрешением устройства. Часто измеряется в dpi – dots per inch – количество точек на дюйм. Очевидно, что разрешение устройства зависит от размеров его пиксела, и одно и то же изображение на устройствах с различным разрешением будет выглядеть по-разному.

Число битов, используемых компьютером для задания цвета одного пиксела называется глубиной цвета. Глубина цвета определяет в какое количество цветов (или градаций серого) можно раскрасить пиксел. 1 бит/пиксел - черно-белое изображение, 8 бит/пиксел – 256 цветов (градаций серого); 24 – более 16 миллионов цветов – это достаточно для представления всех различимых человеческим глазом цветов, поэтому этот режим называют естественными цветами (true color). Для задания дополнительных эффектов (например, прозрачности) пикселу могут быть сопоставлены дополнительные биты (-канал). Более подробно о работе с цветом в компьютерной графике будет рассказано позднее.

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

Преимущества растровой графики:

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

• Большинство устройств вывода являются растровыми, что облегчает вывод на них растровых изображений.

Недостатки растровой графики:

• Требуется большой объем памяти, независимо от содержания изображения (размер_изображения_в_битах = число_пикселов * глубина_цвета = разрешениеX * разрешениеY * размер_области_вывода_X * размер_области_вывода_Y * глубина_цвета). Отсюда необходимость компрессии/декомпрессии файлов с растровыми изображениями.

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

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

• Трудно выделить для обработки один из объектов изображения. Например, увеличить изображение человека на фотографии, не меняя фона – нетривиальная задача.

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

Преимущества векторной графики:

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

• На изображении легко выбрать один примитив или группу примитивов для последующего редактирования.

• Векторные изображения занимают сравнительно небольшой объем памяти (описание, например, дуги окружности на плоскости состоит из пяти чисел – центр, радиус, начальный и конечный угол). Благодаря компактности описаний, во многих популярных файловых форматах (например, DXF, IGES, HPGL, VRML) данные хранятся в неупакованном, текстовом виде, что делает возможным их просмотр и редактирование с помощью обычного текстового редактора.

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

Недостатки векторной графики:

• Изображения выглядят слишком искусственно, поскольку в природе мало дуг и прямых.

• При выводе на растровые устройства необходима растризация.

Векторная графика широко используется для построения схем, диаграмм, чертежей в системах автоматизированного проектирования и технологической подготовки производства (AutoCAD, Кредо, ...), CASE – системах (Rational Rose, ERWin, BPWin,...), системах подготовки презентаций (MS PowerPoint, Lotus Freelance,...), офисных графических системах назначения (CorelDraw, MS Visio и др.). Многие системы векторной графики позволяют включать в векторные изображения растровые фрагменты.

3. GDI+. Класс Graphics.

У класса Graphics большое число методов и свойств. Упомяну лишь о некоторых из них. Группа статических методов класса позволяет создать объект этого класса, задавая например описатель (handle) контекста устройства.

Для рисования наиболее важны три группы методов. К первой относится перегруженный метод DrawString, позволяющий выводить тексты в графическом режиме. Вторую группу составляют методы Draw - DrawEllipse, DrawLine, DrawArc и другие, позволяющие цветным пером (объектом класса Pen) рисовать геометрические фигуры: линии, различные кривые, прямоугольники, многоугольники, эллипсы и прочее. К третьей группе относятся методы Fill - FillEllipse, FillPie, FillRectangle и другие, позволяющие нарисовать и закрасить фигуру кистью. Кисти (объекты классов, производных от Brush), могут быть разные - сплошные, узорные, градиентные.

Графические операции лежат в основе пользовательских интерфейсов всех Windows-приложений. В среде Microsoft .NET Framework логическое представление поверхности графического вывода в физическом устройстве инкапсулировано в классе Graphics, принадлежащему пространству имен System.Drawing. Каждый экземпляр объекта класса Graphics представляет поверхность вывода устройства, обеспечивая необходимый уровень абстракции, который обособляет приложения, избавляя их от выполнения рутинных операций, связанных с непосредственным графическим выводом на аппаратные устройства. Это избавляет программиста от необходимости писать программный код низкого уровня для поддержки каждого устройства графического вывода.

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

Класс Graphics содержит несколько десятков свойств и методов.

Обычно вывод графики производится при обработке события Paint класса Form. В этом случае нет необходимости создавать объект Graphis. Он доступен как свойство Graphics аргумента e, относящегося к классу PaintEventArgs.

Событие Paint происходит, когда возникает необходимость перерисовки всего окно или некоторой его области. Такая необходимость возникает, например, при восстановлении пользователем размеров окна после сворачивания. Приложение может само инициировать это событие с помощью методов класса Form Redraw или Refresh.

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

1) мировое (world space) – пространство предметной области. В нем используются пользовательские единицы измерения и система координат;

2) Страничное (page space) представляет собой мировое пространство после выполнения преобразований поворота, сдвига и масштабирования, требуемых для получения нужного изображения сцены, описанной в мировых координатах.

3) Пространство устройства (device space) – абстракция поверхности физического устройства. При преобразовании изображения из пространства сцены в пространство устройства единицы измерения, используемые в страничном пространстве, должны быть преобразованы в единицы устройства.