Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин

Функция Cross определяет, пересекает ли луч j-ое ребро многоугольника:

bool Cross(int j)

{

int first = j;

int second = j == n - 1 ? 0 : j + 1;

double y = (xh - points[first].x) * (points[second].y - points[first].y) / (points[second].x - points[first].x) + points[first].y;

double minimal = min(points[first].x, points[second].x);

double maximal = max(points[first].x, points[second].x);

return (points[first].x != points[second].x) && (yh >= y) && (xh > minimal) && (xh <= maximal);

}

Фрагмент основной программы:

...

int count = 0;

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

{

count += Cross(i);

}

...

Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.

Замечание: В данной реализации алгоритма луч направлен вниз.

Задача 2.

Достаточно ли видеопамяти объемом 256 Кбайт для работы монитора в режиме 640*480 и палитрой из 16 цветов?

16 цветов - 4 бита, т.к. 2^4 = 16
То есть объем одного пикселя - 4 бита.

Примечание.

Решение задач на кодирование графической информации.

Растровая графика.

Векторная графика.

Введение

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

Растровая графика.

Типы задач:

• Нахождение объема видеопамяти.

• Определение разрешающей способности экрана и установка графического режима.

• Кодировка цвета и изображения.

• Нахождение объема видеопамяти

Методические рекомендации:

В задачах такого типа используются понятия:

• объем видеопамяти,

• графический режим,

• глубина цвета,

• разрешающая способность экрана,

• палитра.

Во всех подобных задачах требуется найти ту или иную величину.

Видеопамять -это специальная оперативная память, в которой формируется графическое изображение. Иными словами для получения на экране монитора картинки её надо где-то хранить. Для этого и существует видеопамять. Чаще всего ее величина от 512 Кб до 4 Мб для самых лучших ПК при реализации 16,7 млн. цветов.

Объем видеопамяти рассчитывается по формуле: V=I*X*Y, где I – глубина цвета отдельной точки, X, Y –размеры экрана по горизонтали и по вертикали (произведение х на у – разрешающая способность экрана).

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

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

- разрешающая способность(количество точек, с помощью которых на экране воспроизводится изображение) - типичные в настоящее время уровни разрешения 800*600 точек или 1024*768 точек. Однако для мониторов с большой диагональю может использоваться разрешение 1152*864 точки.

- глубина цвета(количество бит, используемых для кодирования цвета точки), например, 8, 16, 24, 32 бита. Каждый цвет можно рассматривать как возможное состояние точки, Тогда количество цветов, отображаемых на экране монитора может быть вычислено по формуле K=2^I , где K– количество цветов, I– глубина цвета или битовая глубина.

Кроме перечисленных выше знаний учащийся должен иметь представление о палитре:

- палитра (количество цветов, которые используются для воспроизведения изображения), например 4 цвета, 16 цветов, 256 цветов, 256 оттенков серого цвета, 2¹⁶ цветов в режиме называемом High color или 2²⁴ , 2³² цветов в режиме True color.

Учащийся должен знать также связи между единицами измерения информации, уметь переводить из мелких единиц в более крупные, Кбайты и Мбайты, пользоваться обычным калькулятором и Wise Calculator.

Уровень «3»

1. Определить требуемый объем видеопамяти для различных графических режимов экрана монитора, если известна глубина цвета на одну точку.(2.76 [3])

Режим экрана	Глубина цвета (бит на точку)
640 на 480
800 на 600
1024 на 768
1280 на 1024

Решение:

• Всего точек на экране (разрешающая способность): 640 * 480 = 307200
2. Необходимый объем видеопамяти V= 4 бит * 307200 = 1228800 бит = 153600 байт = 150 Кбайт.
3. Аналогично рассчитывается необходимый объем видеопамяти для других графических режимов. При расчетах учащийся пользуется калькулятором для экономии времени.

Ответ:

Режим экрана	Глубина цвета (бит на точку)
640 на 480	150 Кб	300 Кб	600 Кб	900 Кб	1,2 Мб
800 на 600	234 Кб	469 Кб	938 Кб	1,4 Мб	1,8 Мб
1024 на 768	384 Кб	768 Кб	1,5 Мб	2,25 Мб	3 Мб
1280 на 1024	640 Кб	1,25 Мб	2,5 Мб	3,75 Мб	5 Мб

2. Черно-белое (без градаций серого) растровое графическое изображение имеет размер 10 ´10 точек. Какой объем памяти займет это изображение?( 2.68 [3])

Решение:

• Количество точек -100

• Так как всего 2 цвета черный и белый. то глубина цвета равна 1 ( 2¹ =2)

• Объем видеопамяти равен 100*1=100 бит

Аналогично решается задаа 2.69[3]

3. Для хранения растрового изображения размером 128 x 128 пикселей отвели 4 КБ памяти. Каково максимально возможное число цветов в палитре изображения. (ЕГЭ_2005, демо, уровень А). (См. также задачу 2.73 [3])

Решение:

• Определим количество точек изображения. 128*128=16384 точек или пикселей.

• Объем памяти на изображение 4 Кб выразим в битах, так как V=I*X*Y вычисляется в битах. 4 Кб=4*1024=4 096 байт = 4096*8 бит =32768 бит

• Найдем глубину цвета I =V/(X*Y)=32768:16384=2

• N=2^I , где N – число цветов в палитре. N=4

Ответ: 4

4. Сколько бит видеопамяти занимает информация об одном пикселе на ч/б экране (без полутонов)?([6],C. 143, пример 1)

Решение:

Если изображение Ч/Б без полутонов, то используется всего два цвета –черный и белый, т.е. К=2, 2ⁱ =2, I= 1 бит на пиксель.

Ответ: 1 пиксель

5. Какой объем видеопамяти необходим для хранения четырех страниц изображения, если битовая глубина равна 24, а разрешающая способность дисплея- 800 х 600 пикселей? ([6], №63)

Решение:

• Найдем объем видеопамяти для одной страницы: 800*600*24=11520000 бит =1440000 байт =1406,25 Кб ≈1, 37 Мб

• 1,37*4 =5,48 Мб ≈5.5 Мб для хранения 4 страниц.

Ответ: 5.5 Мб

Уровень «4»

6.Определить объем видеопамяти компьютера, который необходим для реализации графического режима монитора High Color с разрешающей способностью 1024 х 768 точек и палитрой цветов из 65536 цветов. (2.48 [3])

Методические рекомендации:

Если ученик помнит, что режим High Color – это 16 бит на точку, то объем памяти можно найти, определив число точек на экране и умножив на глубину цвета, т.е. 16. Иначе ученик может рассуждать так:

Решение:

1. По формуле K=2^I , где K – количество цветов, I – глубина цвета определим глубину цвета. 2^I =65536

Глубина цвета составляет: I = log₂65 536 = 16 бит (вычисляем с помощью программы Wise Calculator)

2..Количество точек изображения равно: 1024´768 = 786 432

3. Требуемый объем видеопамяти равен: 16 бит ´ 786 432 = 12 582 912 бит = 1572864 байт = 1536 Кб =1,5 Мб (»1,2 Мбайта. Ответ дан в практикуме Угринович). Приучаем учеников, переводя в другие единицы, делить на 1024, а не на 1000.

Ответ: 1,5 Мб

7. В процессе преобразования растрового графического изображения количество цветов уменьшилось с 65536 до 16. Во сколько раз уменьшится объем занимаемой им памяти? (2.70, [3])

Решение:

Чтобы закодировать 65536 различных цветов для каждой точки, необходимо 16 бит. Чтобы закодировать 16 цветов, необходимо всего 4 бита. Следовательно, объем занимаемой памяти уменьшился в 16:4=4 раза.

Ответ: в 4 раза

8. Достаточно ли видеопамяти объемом 256 Кбайт для работы монитора в режиме 640 ´ 480 и палитрой из 16 цветов? (2.77 [3])

Решение:

• Узнаем объем видеопамяти, которая потребуется для работы монитора в режиме 640х480 и палитрой в 16 цветов. V=I*X*Y=640*480*4 (2⁴ =16, глубина цвета равна 4),

V= 1228800 бит = 153600 байт =150 Кб.

• 150 < 256, значит памяти достаточно.

Ответ: достаточно

9. Укажите минимальный объем памяти (в килобайтах), достаточный для хранения любого растрового изображения размером 256 х 256 пикселей, если известно, что в изображении используется палитра из 2¹⁶ цветов. Саму палитру хранить не нужно.

• 128

• 512

• 1024

• 2048

(ЕГЭ_2005, уровень А)

Решение:

Найдем минимальный объем памяти, необходимый для хранения одного пикселя. В изображении используется палитра из 2¹⁶ цветов, следовательно, одному пикселю может быть сопоставлен любой из 2¹⁶ возможных номеров цвета в палитре. Поэтому, минимальный объем памяти, для одного пикселя будет равен log₂ 2¹⁶ =16 битам. Минимальный объем памяти, достаточный для хранения всего изображения будет равен 16*256*256 =2⁴ * 2⁸ * 2⁸ =2²⁰ бит=2²⁰ : 2³ =2¹⁷ байт = 2¹⁷ : 2¹⁰ =2⁷ Кбайт =128 Кбайт, что соответствует пункту под номером 1.

Ответ: 1

10. Используются графические режимы с глубинами цвета 8, 16. 24, 32 бита. Вычислить объем видеопамяти, необходимые для реализации данных глубин цвета при различных разрешающих способностях экрана.

Примечание:задача сводится в конечном итоге к решению задачи №1 (уровень «3», но ученику самому необходимо вспомнить стандартные режимы экрана.

11. Сколько секунд потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами? (ЕГЭ_2005, уровень В)

Решение:

• Определим объем изображения в битах:

3 байт = 3*8 = 24 бит,

V=I*X*Y=640*480*24 бит =7372800 бит

• Найдем число секунд на передачу изображения: 7372800 : 28800=256 секунд

Ответ: 256.

12. Сколько секунд потребуется модему, передающему сообщения со скоростью 14400 бит/сек, чтобы передать цветное растровое изображение размером 800 х 600 пикселей, при условии, что в палитре 16 миллионов цветов? (ЕГЭ_2005, уровень В)

Решение:

Для кодирования 16 млн. цветов требуется 3 байта или 24 бита (Графический режим True Color). Общее количество пикселей в изображении 800 х 600 =480000. Так как на 1 пиксель приходится 3 байта, то на 480000 пикселей приходится 480000*3=1 440 000 байт или 11520000 бит. 11520000 : 14400 = 800 секунд.

Ответ: 800 секунд.

13. Современный монитор позволяет получать на экране 16777216 различных цветов. Сколько бит памяти занимает 1 пиксель? ([6], с.143, пример 2)

Решение:

Один пиксель кодируется комбинацией двух знаков «0» и «1». Надо узнать длину кода пикселя.

2^х =16777216, log₂ 16777216 =24 бит

Ответ: 24.

14. Каков минимальный объем памяти ( в байтах), достаточный для хранения черно-белого растрового изображения размером 32 х 32 пикселя, если известно, что в изображении используется не более 16 градаций серого цвета.(ЕГЭ_2005, уровень А)

Решение:

• Глубина цвета равна 4, т.к. 16 градаций цвета используется.

• 32*32*4=4096 бит памяти для хранения черно-белого изображения

• 4096 : 8 = 512 байт.

Ответ: 512 байт

Уровень «5»

15. Монитор работает с 16 цветной палитрой в режиме 640*400 пикселей. Для кодирования изображения требуется 1250 Кбайт. Сколько страниц видеопамяти оно занимает? (Задание 2,Тест I-6)

Решение:

1. Т.к. страница –раздел видеопамяти, вмещающий информацию об одном образе экрана одной «картинки» на экране, т.е. в видеопамяти могут размещаться одновременно несколько страниц, то, чтобы узнать число страниц надо поделить объем видеопамяти для всего изображения на объем памяти на 1 страницу. К-число страниц, К=V_изобр/V_{1 стр}

V_изобр =1250 Кб по условию

• Для этого вычислим объем видеопамяти для одной страницы изображения с 16 цветовой палитрой и разрешающей способностью 640*400.

V_{1 стр} = 640*400*4 , где 4- глубина цвета (2⁴ =16)

V_{1 стр} = 1024000 бит = 128000 байт =125 Кб

3. К=1250 : 125 =10 страниц

Ответ: 10 страниц

16. Страница видеопамяти составляет 16000 байтов. Дисплей работает в режиме 320*400 пикселей. Сколько цветов в палитре? (Задание 3,Тест I-6)

Решение:

1. V=I*X*Y – объем одной страницы, V=16000 байт = 128000 бит по условию. Найдем глубину цвета I.

I=V/(X*Y).

I= 128000 / (320*400)=1.

2. Определим теперь, сколько цветов в палитре. K=2^I ,гдеK – количество цветов, I – глубина цвета. K=2

Ответ: 2 цвета.

17. Сканируется цветное изображение размером 10´10 см. Разрешающая способность сканера 600 dpi и глубина цвета 32 бита. Какой информационный объем будет иметь полученный графический файл. (2.44, [3], аналогично решается задача 2.81 [3])

Решение:

1. Разрешающая способность сканера 600 dpi (dot per inch — точек на дюйм) означает, что на отрезке длиной 1 дюйм сканер способен различить 600 точек. Переведем разрешающую способность сканера из точек на дюйм в точки на сантиметр:

600 dpi : 2,54 » 236 точек/см (1 дюйм = 2.54 см.)

2. Следовательно, размер изображения в точках составит 2360´2360 точек. (умножили на 10 см.)

3. Общее количество точек изображения равно:

2360´2360 = 5 569 600

4. Информационный объем файла равен:

32 бит ´ 5569600 = 178 227 200 бит » 21 Мбайт

Ответ: 21 Мбайт

18. Объем видеопамяти равен 256 Кб. Количество используемых цветов -16. Вычислите варианты разрешающей способности дисплея. При условии, что число страниц изображения может быть равно 1, 2 или 4. ([1], №64, стр. 146)

Решение:

• Если число страниц равно 1, то формулу V=I*X*Y можно выразить как

256 *1024*8 бит = X*Y*4 бит, (так как используется 16 цветов, то глубина цвета равна 4 бит.)

т.е. 512*1024 = X*Y; 524288 = X*Y.

Соотношение между высотой и шириной экрана для стандартных режимов не различаются между собой и равны 0,75. Значит, чтобы найти X и Y, надо решить систему уравнений:

Выразим Х=524288/ Y, подставим во второе уравнение, получим Y² =524288*3/4=393216. Найдем Y≈630; X=524288/630≈830

Вариантом разрешающей способности может быть 630 х 830.

2. Если число страниц равно 2, то одна страница объемом 256:2=128 Кбайт, т.е

128*1024*8 бит = X*Y*4 бит, т.е. 256*1024 = X*Y; 262144 = X*Y.

Решаем систему уравнений:

Х=262144/ Y; Y² =262144*3/4=196608; Y=440, Х=600

Вариантом разрешающей способности может быть 600 х 440.

4. Если число страниц равно 4, то 256:4 =64; 64*1024*2=X*Y; 131072=X*Y; решаем систему

X=131072/Y; Y² =131072*3/4=98304; Y≈310, X≈420