Различия между версиями 1 и 14 (по 13 версиям)
Версия 1 от 2011-02-02 17:53:24
Размер: 535
Редактор: PavelSutyrin
Комментарий:
Версия 14 от 2011-02-05 17:13:15
Размер: 4843
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 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 (сглаживание краев линии методом дорисовывания пикселей промежуточного цвета)
   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: Строка 28:
Если считать точки растра квадратными, придётся иметь дело с площадью 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

  • {o} — тема по Linux

  • <!> ­— необязательная тема

  • Наиболее эффективное вычисление количества ломаных на окружности. Использование предвычисленных значений функций.
  • {o} Введение в PyGame

Домашнее задание

  • {i} — теоретическое задание

  • {*} — новая тема

  1. Реализовать эффективный алгоритм для ломаных на окружности (здесь будет ссылка на математику с доски).
  2. {i} Поставить себе PyGame, освоиться в документации

  3. На PyGame написать программу для рисования графика функции красиво. Либо рисовать ломаную, либо заполнять точки экрана с помощью fill. Последнее предпочтительнее, т.к. работает быстрее.

    1. с помощью fill нарисовать отрезок на экране.
      1. какой-нибудь
      2. толщиной 2-3 пикселя
      3. добавить anti-aliasing (сглаживание краев линии методом дорисовывания пикселей промежуточного цвета)
    2. нарисовать график нелинейной функции

О проведении линий (по сути — прямоугольников)

Растеризация отрезков на Википедии. В нашем случае эти алгоритмы не вполне пригодны.

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

Если считать точки растра квадратными, придётся иметь дело с площадью 3-,4- и пятиугольников (исходник картинки в формате KSEG):

lines-antialias.png

Однако вычислять площадь полученного многоугольника довольно муторно, можно посчитать точки растра круглыми (это в чём-то правда) и вычислять площадь сегмента (исходник картинки в формате KSEG):

lines-antialias2.png

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

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?» не рассматриваются


CategoryClass CategoryVmsh

LecturesVMSH/2011-02-02 (последним исправлял пользователь FrBrGeorge 2011-02-09 03:03:36)