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

Вход на сайт

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

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

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

Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...
Пример, к которому вы оставили комментарий строит именно то самое изображение на языке с#, которое вам необходимо. Отличается только цветовая палитра.

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

Рейтинг@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, внутри которого происходит просчёт принадлежности точек окружности