2D Векторная Графика

Vertex

Vertex (вершина, угол, мн. ч. Vertices) = Точка = вершина угла – является базовым элементом Векторной Графики. В своей простейшей форме Vertex состоит из двух координат с двумя расстояниями от левого и верхнего краев окна.

Существует несколько вариантов:

1) 2D-Vertex с двумя координатами типа float: PointF {float x; float y;}

2) 2D-Vertex с 2-мя целочисленными координатами: Point {int x; int y;}

3) 3D-Vertex с 3-мя координатами float: Vector3 {float x; float y, float z;}

4) 3D-Vertexкак Vector3 плюс значения цвета, нормали, текстурные координаты и т.д. (см. Direct3D– VertexFormats)

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

Polygon

Polygon(Полигон) – важнейший тип данных Векторной Графики — это упорядоченный набор вершин p [0], p [1], p [i],..., p [n-1], где вершины p [i], связаны линиями DrawLine (p [i], p [i + 1]). Эти линии не должны пересекать друг друга.

Существует несколько вариантов:

а) открытый Полигон (англ.: polyline): начальная и конечная точки не являются одинаковыми. Открытые Полигоны имеют длину = length, но не имеют периметра и площади.

b) закрытый Полигон: начальная и конечная точки идентичны. Это приводит к тому, что закрытый n-угольник, кодируется через n + 1 Вертексов. Треугольник, например, имеет четыре вершины P0, P1, P2 и P3 == Р0! Закрытый Полигон обладает периметром (perimeter) и площадью (area).

Преобразование a) → b): открытый Полигон можно сделать закрытым, добавив копию Вертекса p[0] в конце массива Вертексов.

Если говорят о Полигоне без прилагательного открытый или закрытый, то имеется в виду закрытый полигон.

c) выпуклый Полигон: при любом расположении точек q0 и q1 внутри полигона, отрезок соединяющий эти точки полностью находится внутри Полигона.

d) вогнутый Полигон: при определенном расположении точек q0 и q1 внутри полигона, часть отрезка соединяющего эти точки может находится вне Полигона.

e) сложный Полигон: грани Полигона пересекаются. Такие Полигоны не могут быть полезными для Компьютерной Графики.

Примеры:

Полигоны программируются и хранятся в виде массивов.
Существует два основных типа 2D-Полигон-массивов:

a) Полигон как массив фиксированной длины:

constInt32 n = 100;
PointF[] p = newPointF[n];

Преимущество: быстрый и легкий доступ.

Недостаток: необходимо зарезервировать нужное пространство в памяти,
то есть вам нужно знать значение n.

b) Полигон как динамический массив:

ArrayList p = new ArrayList();
p.Add (p0);

Преимущество: в любое время можно добавить или удалить элемент массива.

Недостатки:

1) необходимость использования System.Collections;

2) доступ медленнее, чем с фиксированным массивом;

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

4) необходимость в явном приведении типов, т.е. для чтения из массива требуется указание типа: p0 = p (PointF) [i]; потому что ArrayList может содержать все возможные объекты в смешанном порядке.

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

using System.Collections; //подключение ArrayList
const Int32 n = 100; //длина массива
Random r = new Random(); //генератор случайных чисел
//для заполнения массива
Int32 i;
Pen mypen = new Pen( Color.Red, 1 );
Graphics g = this.CreateGraphics();

1) Пример: Point-массив фиксированной длины с Int-координатами
   Point[] p = new Point[n];
   for ( i=0; i < n; i++ ) //write into array
   { p[i].X = r.Next(100); p[i].Y = r.Next(100); }
   for ( i=0; i < n-1; i++ ) //read from array
     g.DrawLine( mypen, p[i], p[i+1] );

2) Пример: Point-массив динамический с переменной длиной и Int-координатами
   ArrayList p = new ArrayList();
   for ( i=0; i < n; i++ ) //write into array
     p.Add( new Point( r.Next(100), r.Next(100) ) );
   for ( i=0; i < p.Count-1; i++ ) //read from array
     g.DrawLine( mypen, (Point)p[i], (Point)p[i+1] );

3) Пример: PointF-массив с фиксированной длиной и Float-координатами
   PointF[] p = new PointF[n];
   for ( i=0; i < n; i++ ) //write into array)
   { p[i].X = 100f*(Single)r.NextDouble(); p[i].Y = 100f*(Single)r.NextDouble(); }
   for ( i=0; i < n-1; i++ ) //read from array
   { Int32 x0 = Convert.ToInt32( p[i  ].X );
     Int32 y0 = Convert.ToInt32( p[i  ].Y );
     Int32 x1 = Convert.ToInt32( p[i+1].X );
     Int32 y1 = Convert.ToInt32( p[i+1].Y );
     g.DrawLine( mypen, x0, y0, x1, y1 );
   }

4) Пример: PointF-массив с переменной длиной и Float-координатами
   ArrayList p = new ArrayList();
   for ( i=0; i < n; i++ ) //write into array
     p.Add( new PointF( 100f*(Single)r.NextDouble(), 100f*(Single)r.NextDouble() ) );
   for ( i=0; i < p.Count-1; i++ ) //read from array
   { Int32 x0 = Convert.ToInt32( ((PointF)p[i  ]).X );
     Int32 y0 = Convert.ToInt32( ((PointF)p[i  ]).Y );
     Int32 x1 = Convert.ToInt32( ((PointF)p[i+1]).X );
     Int32 y1 = Convert.ToInt32( ((PointF)p[i+1]).Y );
     g.DrawLine( mypen, x0, y0, x1, y1 );
   }

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

Пример с минимальным интервалом в 10 пикселей:

Point p0 = new Point(), p1 = new Point();
protected override void OnMouseDown( MouseEventArgs e )
{
p0.X = e.X; //first vertex
p0.Y = e.Y; //first vertex
}

protected override void OnMouseMove( MouseEventArgs e )
{
if ( e.Button == MouseButtons.None ) return; //if no button pressed do nothin
p1.X = e.X; Int32 dx = p1.X - p0.X; //horizontal distance
p1.Y = e.Y; Int32 dy = p1.Y - p0.Y; //vertical distance
if ( Math.Sqrt( dx*dx + dy*dy ) < 10 ) return; //if distance < 10 do nothing
g.DrawLine( blackpen, p0, p1 );
p0 = p1;
}

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

if ( Math.Sqrt( dx*dx + dy*dy ) < 10 ) return;

на

if ( dx*dx + dy*dy < 100 ) return;.

Длина открытого Полигона (Polyline)

Дано: динамический массив Вертексов: ArrayList p = new ArrayList();заполненный объектами типа Point;

требуется найти Double length.

Для каждого отрезка используется теорема Пифагора: гипотенуза равна квадратному корню из суммы квадратов катетов в прямоугольном треугольнике. Сумма всех гипотенуз равна длине ломанной линии.

Double length = 0.0;

Pointp0 = (Point)p[0];

for (Int16 i=1; i < p.Count; p++)//цикл начинается не с 0, а с 1

{ Pointp1 = (Point)p[i];

Double dx = p1.X - p0.X; //горизонтальный катет

Double dy = p1.Y - p0.Y; //вертикальный катет

length += Math.Sqrt( dx*dx + dy*dy ); //гипотенуза

p0 = p1;

}

Периметр закрытого Полигона

Дано: динамический массив Вертексов:
ArrayList p = new ArrayList(), заполненный объектами типа Point;

требуется найти Double perimeter;

Для начала копируем первую точку Полигона в конец списка Вертексов, если это еще не сделано.

Double perimeter = 0.0;

Point p0 = (Point)p[0];

if ( p0 != (Point)p[p.Count-1] ) p.Add( p0 ); //закрываем Полигон

for (Int16 i=1; i < p.Count; p++)//цикл начинается не с 0, а с 1

{ Point p1 = (Point)p[i];

Double dx = p1.X - p0.X; //горизонтальный катет

Double dy = p1.Y - p0.Y; //вертикальный катет

perimeter += Math.Sqrt( dx*dx + dy*dy ); //гипотенуза

p0 = p1;

}

Площадь закрытого Полигона

Дано: динамический массив Вертексов:
ArrayList p = new ArrayList(), заполненный объектами типа Point;

требуется найти Double area;

Для начала копируем первую точку Полигона в конец списка Вертексов, если это еще не сделано.

Double area = 0.0;
Point p0 = (Point)p[0];
if ( p0 != (Point)p[p.Count-1] ) p.Add( p0 ); //закрываем Полигон
for ( Int16 i=1; i < p.Count; p++ ) //цикл начинается не с 0, а с 1
{ Point p1 = (Point)p[i];
Double dx = p1.X - p0.X; //ширина трапеции

  Double my = (p1.Y + p0.Y) / 2.0; //среднее значение y-координат
  area += dx * my; //площадь трапеции прибавляем к общей площади
  p0 = p1;
}

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

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

area = Math.Abs( area );

Описанный прямоугольник Полигон

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

Дано: динамический массив Вертексов:
ArrayList p = new ArrayList(), заполненный объектами типа Point;

требуется найти Rectangle box; //bounding box;

Для начала устанавливаем все четыре стены тюрьмы xmin, ymin, xmax, ymax на стартовую точку Полигона.

Int32 xmin, ymin, xmax, ymax;

xmin = xmax = ( (Point)p[0] ).X;
ymin = ymax = ( (Point)p[0] ).Y;

for ( int i=1; i < p.Count; i++ )
{
Point p0 = (Point)p[i]; //следующая вершина Полигона
if ( p0.X < xmin ) xmin = p0.X; //сдвигаем левую стену налево
if ( p0.X > xmax ) xmax = p0.X; //сдвигаем правую стену направо
if ( p0.Y < ymin ) ymin = p0.Y; //сдвигаем верхнюю стену наверх
if ( p0.Y > ymax ) ymax = p0.Y; //сдвигаем нижнюю стену вниз
}

box = new Rectangle( xmin, ymin, xmax-xmin, ymax-ymin );

Справка:
В классе Rectangle существуют свойства аналогичные X и Y под именами Left и Top.
Пример:
xmin = box.X = box.Left и
ymin = box.Y = box.Top.

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

Пример:
нам дан подвижный четырехугольник Rectangle box и массив стационарных четырехугольников Rectangle[] boxes = new Rectangle[n];.
Вопрос: задевает ли box какой-либо из массива boxes?

ручное решение:

for ( int i=0; i<n; i++ )

{ if ( box.X > boxes[i].X + boxes[i].Width ) continue; //box лежит правее

if ( box.Y > boxes[i].Y + boxes[i].Height ) continue; //box лежит ниже

if ( boxes[i].X > box.X + box.Width ) continue; //box лежит левее

if ( boxes[i].Y > box.Y + box.Height ) continue; //box лежит выше

Debug.WriteLine("box collides boxes[" + i.ToString() + "].\r\n" );

}

решение с использованием метода Rectangle.IntersectsWith:

for ( int i=0; i<n; i++ )
if ( box.IntersectsWith( boxes[i] ) )

Debug.WriteLine("box collides[" + i.ToString() + "].\r\n" );

Как правило, описанный прямоугольник также используется для определения указания курсором мыши на графический объект.
Пример: находится ли указатель мыши (с координатами e.X, e.Y) в пределах границ графического объекта i со описанным четырехугольником boxes[i]?

Решение с использованием метода Rectangle.Contains:

for ( int i=0; i<n; i++ )
if ( boxes[i].Contains( e.X, e.Y ) )
Debug.WriteLine("Мышиный курсор указывает на boxes[" + i.ToString() + "].\r\n" );

Центр Полигона

Для определения центра полигона лучше использовать координаты типа float (type PointF) вместо целочисленных координат (type Point), т.к. вычисление центра требует деление, которое редко дает нам целочисленный результат.

Существует четыре определения центра Полигона mp, которые в общем случае могут сильно отличаться своими значениями друг от друга:

1) Центр описанного прямоугольника:
PointF mp = new PointF( box.X + box.Width/2f, box.Y + box.Height/2f );
аналогично:
PointF mp = new PointF( xmin + (xmax-xmin)/2f, ymin + (ymax-ymin)/2f );
Недостаток: mp сильно зависит от формы Полигона и наличия "хвоста".

2) Центр тяжести = Center of gravity = centroid = geocenter = barycenter
Существует три общих определения "центра тяжести" Полигона p:
2a) Цент вершин , 2b) Центр периметра, 2c) Центр площади равномерной плотности.
При первом рассмотрении определения центра тяжести Полигона часто используется простейший треугольник. Так как в треугольнике все три определения дают одни и те же значения mp, часто возникает недоумение по поводу того факта, что три центра тяжести в несимметричных Полигонах часто находятся в разных точках.
Общий центр тяжести с треугольнике:
mp.X = ( p[0].X + p[1].X + p[2].X ) / 3f;
mp.Y = ( p[0].Y + p[1].Y + p[2].Y ) / 3f;

2a) Центр вершин - равномерное распределение "массы" Полигона p между его вершинами.
Вычисление: в открытом Полигоне суммируются отдельно значения координат x и y, полученные суммы делятся на число вершин;
в закрытом Полигоне игнорируется последняя точке, чтобы не посчитать одну вершину дважды.

Int32 count;

if ( (Point)p[0] != (Point)p[p.Count-1] ) count = p.Count; else count = p.Count-1;
for ( i=0; i < count; i++
{ Point p0 = (Point)p[i];
mp.X += p0.X;
mp.Y += p0.Y;
}
mp.X /= count;
mp.Y /= count;
Недостаток: значение mp зависит от неравномерной плотности расположения вершин Полигона.

2b) Центр периметра
Чтобы найти центр тяжести периметра закрытого Полигона нужно заменить каждую его сторону точкой с массой эквивалентной длине этой стороны и расположенной в центре этой стороны.

Point p0 = (Point)p[0], p1;
PointF mp = new PointF( 0f, 0f );
float length, perimeter = 0f;
for ( i=1; i < p.Count; i++ )
{ p1 = (Point)p[i];
int dx = p[i].X - p[i-1].X;
int dy = p[i].Y - p[i-1].Y;
length = (float)Math.Sqrt( dx*dx + dy*dy );
mp.X += length * ( p0.X + dx/2f );
mp.Y += length * ( p0.Y + dy/2f );
perimeter += length;
p0 = p1;
}
mp.X /= perimeter;
mp.Y /= perimeter;
Недостаток: значение mp зависит от присутствия узких "ущелий".

2c) Центр площади равномерной плотности

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

2D Polygon Scroll

Дано:
1) размер массива Вертексов: const Int32 n = 100;
2) PointF palt = new PointF[n];
3) PointF pneu = new PointF[n]; //Результат

Нужно получить:
2D-Scroll = 2D-Translate = 2D-Сдвиг на дельту, определенную типом Single - dx, dy.

for ( i=0; i < palt.Count; i++ )
{
pneu[i].X = palt[i].X + dx;
pneu[i].Y = palt[i].Y + dy;
}

Можно сэкономить память и сделать сдвиг Полигона без создания его копии:

for ( i=0; i < p.Count; i++)
{
palt[i].X += dx;
palt[i].Y += dy;
}

2D Polygon Zoom

Нужно получить: 2D-Zoom = 2D-Scaling = 2D-Масштабирование на размер Single zoomx, zoomy.
Полигоны palt и pneu должны обязательно использовать тип данных float для хранения координат (PointF).

for ( i=0; i < palt.Count; i++ )
{
pneu[i].X = palt[i].X * zoomx;
pneu[i].Y = palt[i].Y * zoomy;
}

Можно проще:
for ( i=0; i < p.Count; i++ )
{
palt[i].X *= zoomx;
palt[i].Y *= zoomy;
}

zoomx < 1.0f = уменьшение со сдвигом налево
zoomy < 1.0f = уменьшение со сдвигом вверх
zoomx > 1.0f = увеличение со сдвигом вправо
zoomy > 1.0f = увеличение со сдвигом вниз

Пример:

Часто сдвиги при масштабировании нежелательны. Хочется масштабировать Полигон прямо на месте.
Для этого используется центр полигона mp:
1) Сдвигаем Полигон так, что mp сдвигается в начало координат.
2) Производим масштабирование
3) Производим обратный сдвиг

for ( i=0; i < palt.Count; i++ )

{ pneu[i].X = (palt[i].X - mp.X) * zoomx + mp.X;
pneu[i].Y = (palt[i].Y - mp.Y) * zoomy + mp.Y;
}

Или без создания копии Полигона:

for ( i=0; i < p.Count; i
{ palt[i].X -= mp.X;
  palt[i].Y -= mp.Y;
  palt[i].X *= zoomx;
  palt[i].Y *= zoomy;
  palt[i].X += mp.X;
  palt[i].Y += mp.Y;
}

2D Polygon Rotation

Нужно получить: 2D-Rotation = 2D-Поворот по часовой стрелке на угол Single alpha или Double alpha.
Ось вращения при 2D-Повороте - это невидимая ось Z, которая "протыкает" клиентское окно в левом верхнем углу.
Полигоны palt и pneu должны содержать координаты в переменных с плавающей запятой (PointF).

Double arcus = alpha * 2.0 * Math.PI / 360.0; //alpha в радианах
Single cosinus = (Single)Math.Cos( arcus );   //cosinus(alpha) float
Single sinus   = (Single)Math.Sin( arcus );   //  sinus(alpha) float
for ( i=0; i < palt.Count; i++ )
{ pneu[i].X = palt[i].X * cosinus - palt[i].Y * sinus;
  pneu[i].Y = palt[i].X * sinus + palt[i].Y * cosinus;
}

Можно проделать это и с одним Полигоном, однако со вспомогательной переменной, так как оригинальное значение palt[i].X используется дважды:

for ( i=0; i < p.Count; i++)
{ Single help = palt[i].X * cosinus - palt[i].Y * sinus;
palt[i].Y = palt[i].X * sinus + palt[i].Y * cosinus;
palt[i].X = help;
}

Если необходимо повернуть Полигон против часовой стрелки, то нужно поменять знаки перед значениями синусов:

for ( i=0; i < palt.Count; i++ )
{ pneu[i].X = palt[i].X * cosinus + palt[i].Y * sinus;
pneu[i].Y = -palt[i].X * sinus + palt[i].Y * cosinus;
}

Осторожно: так же, как при масштабировании, при поворотах также происходят смещения Полигона относительно начала координат, что почти всегда нежелательно.

Пример поворота на 90 градусов - Полигон уезжает из зоны видимости за пределы положительных координат:

Если мы хотим повернуть Полигон на месте, нужно поступить также, как при масштабировании:
1) Сдвигаем Полигон так, чтобы mp оказалась в начале координат
2) делаем поворот вокруг нулевой точки
3) Возвращаем центр Полигона в первоначальное положение

for ( i=0; i < palt.Count; i++ )
{ Single x = palt[i].X - mp.X;
  Single y = palt[i].Y - mp.Y;
  pneu[i].X = x * cosinus - y * sinus + mp.X;
  pneu[i].Y = x * sinus + y * cosinus + mp.Y;
}

Концентрические лучи (Splash)

= Излучение, при котором все точки начала отрезка совпадают, а его концы равномерно распределены на границе одного круга (окружности).

Дано:

1) один центр: Point mid = new Point();
2) один радиус: Double radius = 100;
3) число лучей звезды: Int16 const nn = 120;
4) цвет и толщина лучей: Pen mypen = new Pen( Color.Red, 5 );
5) фигура, которой должен заканчиваться каждый луч - обрезан, закруглен, заострен и так далее:
mypen.EndCap = System.Drawing.Drawing2D.LineCap.DiamondAnchor;
Если нам известен угол arcus одного луча (в радианах), то можно определить его конечную точку x,y с помощью так называемого уравнения окружности в параметрической форме:
x = mid.X + radius * Math.Cos( arcus ); y = mid.Y + radius * Math.Sin( arcus );

Угол между двумя соседними лучами равен 360.0 / nn, тот же угол в радианах: Double arcus_1 = 2.0 * Math.PI / nn;

Нам понадобится зарезервировать память для nn конечных точек:Point[] stern = new Point[nn];и заполнить данный массив через следующий цикл:for ( Int16 i=0; i < nn; i++ ) { Double arcus_i = arcus_1 * i; Double x = radius * Math.Cos( arcus_i ); Double y = radius * Math.Sin( arcus_i ); stern[i].X = mid.X + ConvertToInt32( x ); stern[i].Y = mid.Y + ConvertToInt32( y ); g.DrawLine( mypen, mid.X, mid.Y, stern[i].X, stern[i].Y ); }

Программирование кривых в параметрической форме

В Компьютерной Графике все виды 2D-линий (прямая, парабола, эллипс, сплайн и т.д.) записываются в форме двух уравнений с параметром t.

Пример 1: Прямая между двумя вершинами x₀,y₀ и x₁,y₁ в параметрической форме:
x = x₀ + t * ( x₁ - x₀ );
y = y₀ + t * ( y₁ - y₀ );
где t принимает значение от 0.0 до 1.0.

Если нужно рассчитать положение 100 точек между x₀,y₀ и x₁,y₁ , то достаточно простой программы:
float[] x = new Single[100]; float[] y = new Single[100]; for ( int i=0; i < 100; i++ ) { float t = i * 0.01f; x[i] = x0 + t * ( x1 - x0 ); y[i] = y0 + t * ( y1 - y0 ); }

Пример 2: Окружность с радиусом r и центром xm,ym в параметрической форме:
x = xm + r * cosinus( 2 * Pi * t );
y = ym + r * sinus( 2 * Pi * t );
где t принимает значение от 0.0 до 1.0.

Если нужно рассчитать положение 100 точек окружности, то достаточно простой программы:
float[] x = new Single[100]; float[] y = new Single[100]; for ( int i=0; i < 100; i++ ) { double arcus = 2.0 * Math.PI * i * 0.01; x[i] = xm + r * (Single)Math.Cos( arcus ); y[i] = ym + r * (Single)Math.Sin( arcus ); }

Удачи!