Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(
У Вас число превысит максимальное число int. Можно использовать в Вашем случае uint, но лучше все переписать на double.
Добавление к программе строки glutReshapeFunc(changeSize); приводит к тому, что треугольник перестаёт совсем отрисовываться.
Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

С помощью данного алгоритма можно заполнить (зарисовать) любую окружность.

Теоретическое обоснование метода заключаются в использовании свойства квадрата и теоремы Пито: " в выпуклый четырёхугольник ABCD можно вписать окружность тогда и только тогда, когда суммы его противоположных сторон равны ".

Действительно, любой квадрат является выпуклым четырёхугольником:

  1. Cостоит из четырех точек и четырех последовательно соединяющих их отрезков;
  2. Никакие три из данных точек не лежат на одной прямой;
  3. Соединяющие эти три данных точки отрезки не пересекаются.

Из данного обоснования можно вывести идею,что если любую окружность можно вписать в квадрат, то перебирая все точки, принадлежащие этому квадрату, можно найти все точки,принадлежащие данной окружности или лежащие в ней, если известны координаты центра вписанной окружности и её радиус. Закрасив все такие точки, мы нарисуем и саму окружность, и круг,который этой окружностью ограничен.

Представление алгоритма на языке псевдокода :

  • 1.Получить X и Y координаты окружности, радиус окружности R, цвет заполнения color;
  • 2.Присвоить переменной cX значение левого края (X-R) описанного квадрата ABCD и начать цикл до правого края (X+R) (BD) с шагом в 1 единицу измерения (пиксель)
    • 2.1Присвоить переменной cY значение верхнего края (Y+R) и начать цикл от до нижнего края (Y-R) (CD) с таким же шагом
      • 2.1.1.Если значения cX и cY удовлетворяют неравенству (X-cX)2+(Y-cY)2≤Radius2 и в точке с координатами (cX,cY) не стоит точка цвета color, то поставить точку цвета color с координатами (cX, cY)
    • 2.2.Закончить цикл по переменной cY
  • 3.Закончить цикл по переменной cX

Данный алгоритм имеет сложность O(N2) и выгодно отличается от обобщенного рекурсивного алгоритма заполнения многоугольников потребляемой памятью, имея примерно такое же время работы применимо к окружности. Также, данный алгоритм гарантированно не переполняет стек вызовов, что позволяет закрашивать ему окружность любого радиуса. Недостатками являются сравнительно малая скорость заполнения и сложность O(N2).

Рис 1. Пример работы алгоритма. Синий квадрат показывает границы квадрата ABCD, внутри которого происходит просчёт принадлежности точек окружности