535
Комментарий:
|
← Версия 20 от 2011-02-09 03:03:36 ⇥
4837
|
Удаления помечены так. | Добавления помечены так. |
Строка 5: | Строка 5: |
= Тема занятия: кратко = Какое-нибудь описание. |
= Комбинаторика. PyGame = |
Строка 10: | Строка 9: |
* Подтема 1 * {o} Подтема 2 |
* Наиболее эффективное вычисление количества ломаных на окружности. Использование предвычисленных значений функций. * {o} Введение в [[PyGame]] |
Строка 16: | Строка 15: |
1. {i} Первое 1. Второе |
1. Реализовать эффективный алгоритм для ломаных на окружности (здесь будет ссылка на математику с доски). 1. {i} Поставить себе [[PyGame]], освоиться в документации 1. На PyGame написать программу для рисования графика функции красиво. Либо рисовать ломаную, либо заполнять точки экрана с помощью fill. Последнее предпочтительнее, т.к. работает быстрее. 1. с помощью fill нарисовать отрезок на экране. 1. какой-нибудь 1. толщиной 2-3 пикселя 1. добавить anti-aliasing (сглаживание краев линии методом дорисовывания пикселей промежуточного цвета) [[attachment:lines-antialias.py]] 1. нарисовать график нелинейной функции === О проведении линий (по сути — прямоугольников) === [[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%B0|Растеризация отрезков на Википедии]]. В нашем случае эти алгоритмы не вполне пригодны. Общий метод: рассмотрим две параллельные прямые (границы «толстой» линии). Точки растра, целиком содержащиеся между прямых, закрасим чернилами. Точки растра, частично лежащие внутри области, закрасим цветом, смешанным из чернил и исходного цвета точки в пропорции, соответствующей ''площади'' перекрашиваемой части точки. |
Строка 19: | Строка 29: |
Если считать точки растра квадратными, придётся иметь дело с площадью 3-,4- и пятиугольников ([[attachment:lines-antialias.seg|исходник картинки в формате KSEG]]): {{attachment:lines-antialias.png}} Однако вычислять площадь полученного многоугольника довольно муторно, можно посчитать точки растра круглыми (это в чём-то правда) и вычислять площадь сегмента ([[attachment:lines-antialias2.seg|исходник картинки в формате KSEG]]): {{attachment:lines-antialias2.png}} Алгоритм перебора точек внутри области можно получить из [[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D1%83|алгоритма Ву]]. Для простоты вычисления заметим, что для этого алгоритма различаются 8 направлений, из которых 4 получаются из других 4 рисованием от конца к началу ([[attachment:lines8.seg|исходник картинки в формате KSEG]]): {{attachment:lines8.png}} Начало координат, в стиле PyGame, левый верхний угол. Для простоты начальная точка A помещена в начало координат. Имеем 4 различных параметра алгоритма (случаи `AB⁺`, где Y>0 аналогичны `B⁺A`): ||AB|| |X|>|Y| || X≥0, Y≥0 || ||AB'|| |X'|≤|Y'| || X'≥0, Y'≥0 || ||AB"|| |X"|≤|Y'| || X"<0, Y'≥0 || ||AB"'|| |X"'|>|Y| || X"'<0, Y≥0 || Вопросы «что рисовать в начале и в конце отрезка?» и «как рисовать линии толщиной < 2**0,5?» не рассматриваются |
Комбинаторика. PyGame
— тема по Linux
— необязательная тема
- Наиболее эффективное вычисление количества ломаных на окружности. Использование предвычисленных значений функций.
Введение в PyGame
Домашнее задание
— теоретическое задание
— новая тема
- Реализовать эффективный алгоритм для ломаных на окружности (здесь будет ссылка на математику с доски).
Поставить себе PyGame, освоиться в документации
На PyGame написать программу для рисования графика функции красиво. Либо рисовать ломаную, либо заполнять точки экрана с помощью fill. Последнее предпочтительнее, т.к. работает быстрее.
- с помощью fill нарисовать отрезок на экране.
- какой-нибудь
- толщиной 2-3 пикселя
- добавить anti-aliasing (сглаживание краев линии методом дорисовывания пикселей промежуточного цвета)
- нарисовать график нелинейной функции
- с помощью fill нарисовать отрезок на экране.
О проведении линий (по сути — прямоугольников)
Растеризация отрезков на Википедии. В нашем случае эти алгоритмы не вполне пригодны.
Общий метод: рассмотрим две параллельные прямые (границы «толстой» линии). Точки растра, целиком содержащиеся между прямых, закрасим чернилами. Точки растра, частично лежащие внутри области, закрасим цветом, смешанным из чернил и исходного цвета точки в пропорции, соответствующей площади перекрашиваемой части точки.
Если считать точки растра квадратными, придётся иметь дело с площадью 3-,4- и пятиугольников (исходник картинки в формате KSEG):
Однако вычислять площадь полученного многоугольника довольно муторно, можно посчитать точки растра круглыми (это в чём-то правда) и вычислять площадь сегмента (исходник картинки в формате KSEG):
Алгоритм перебора точек внутри области можно получить из алгоритма Ву. Для простоты вычисления заметим, что для этого алгоритма различаются 8 направлений, из которых 4 получаются из других 4 рисованием от конца к началу (исходник картинки в формате KSEG):
Начало координат, в стиле PyGame, левый верхний угол. Для простоты начальная точка A помещена в начало координат. Имеем 4 различных параметра алгоритма (случаи AB⁺, где Y>0 аналогичны B⁺A):
AB |
|X|>|Y| |
X≥0, Y≥0 |
AB' |
|X'|≤|Y'| |
X'≥0, Y'≥0 |
AB" |
|X"|≤|Y'| |
X"<0, Y'≥0 |
AB"' |
|X"'|>|Y| |
X"'<0, Y≥0 |
Вопросы «что рисовать в начале и в конце отрезка?» и «как рисовать линии толщиной < 2**0,5?» не рассматриваются