Differences between revisions 15 and 16
Revision 15 as of 2011-02-05 14:15:24
Size: 4869
Editor: FrBrGeorge
Comment:
Revision 16 as of 2011-02-05 14:18:24
Size: 4851
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 43: Line 43:
||AB̈́´̈́´|| |Ẍ́´̈́´|≤|Ÿ́´| || Ẍ́´̈́´<0, Ÿ́´≥0 ||
||AB̈́´̈́´̈́´|| |Ẍ́´̈́´̈́´|>|Y| || Ẍ́´̈́´̈́´<0, Y≥0 ||
||AB̈́´´|| |Ẍ́´´|≤|Ÿ́´| || Ẍ́´´<0, Ÿ́´≥0 ||
||AB̈́´´´|| |Ẍ́´´´|>|Y| || Ẍ́´´´<0, Y≥0 ||

Комбинаторика. 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̈́´

|Ẍ́´|≤|Ÿ́´|

Ẍ́´≥0, Ÿ́´≥0

AB̈́´´

|Ẍ́´´|≤|Ÿ́´|

Ẍ́´´<0, Ÿ́´≥0

AB̈́´´´

|Ẍ́´´´|>|Y|

Ẍ́´´´<0, Y≥0

Вопросы «что рисовать в начале и в конце отрезка?» и «как рисовать линии толщиной < 2**0,5?» не рассматриваются


CategoryClass CategoryVmsh

LecturesVMSH/2011-02-02 (last edited 2011-02-09 00:03:36 by FrBrGeorge)