Алгоритм построения окружности методом средней точки (3 видео)

Содержание

Алгоритм генерации круга
Алгоритм Брезенхема
Алгоритм
Алгоритм окружности средней точки для заполненных окружностей
5 ответов
обновление
Алгоритм рисования средней точки круга
📹 Видео

Видео:Всё про углы в окружности. Геометрия | МатематикаСкачать

Алгоритм генерации круга

Рисование круга на экране немного сложнее, чем рисование линии. Существует два популярных алгоритма для генерации круга — алгоритм Брезенхема и алгоритм средней точки круга . Эти алгоритмы основаны на идее определения последующих точек, необходимых для рисования круга. Давайте обсудим алгоритмы подробно —

Уравнение окружности: X 2 + Y 2 = r 2 , где r — радиус.

Видео:Построение окружности по трём точкам.Скачать

Алгоритм Брезенхема

Мы не можем отобразить непрерывную дугу на растровом дисплее. Вместо этого мы должны выбрать ближайшее положение пикселя, чтобы завершить дугу.

На следующем рисунке вы можете видеть, что мы поместили пиксель в положение (X, Y) и теперь должны решить, куда поместить следующий пиксель — в N (X + 1, Y) или в S (X + 1, Y-1).

Это может быть решено параметром решения d .

Если d
Если d> 0, то S (X + 1, Y-1) должен быть выбран в качестве следующего пикселя.

Алгоритм

Шаг 1 — Получить координаты центра окружности и радиуса и сохранить их в x, y и R соответственно. Установите P = 0 и Q = R.

Шаг 2 — Установите параметр решения D = 3 — 2R.

Шаг 3 — Повторите шаг 8, пока P ≤ Q.

Видео:Лекция 2 | Компьютерная графика | Виталий Галинский | ЛекториумСкачать

Алгоритм окружности средней точки для заполненных окружностей

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

этот ответ обеспечивает модификацию алгоритма, который дает заполненный круг, но некоторые пиксели посещаются несколько раз: быстрый алгоритм для рисования закрашенного круга?

Q: как я могу растеризировать круг без рисования пиксели несколько раз? Обратите внимание, что RAM очень ограничен!

обновление:

нижние пиксели отображаются слишком много раз. Я что-то упускаю?

обновление #2: это решение работает:

Видео:Геометрия 7 класс (Урок№16 - Окружность. Задачи на построение.)Скачать

5 ответов

ответ на другой вопрос-это прекрасно. Однако, поскольку это создает путаницу, я собираюсь объяснить это немного.

алгоритм, который вы видите в Википедии в основном находит x и y 1/8 окружности (углы от 0 до pi/4 ), а затем рисует 8 точек, которые являются его зеркалами. Например:

то, что предлагает другое решение, которое имеет смысл, если вы внимательно посмотрите на эту картину, — это вместо рисования 8 точек нарисовать 4 горизонтальные линии:

теперь, если вы вычисляете (x,y) для углов в [0, pi/4] и нарисуйте эти 4 линии для каждой вычисленной точки, вы нарисуете много горизонтальных линий, заполняющих круг без какой-либо линии, перекрывающей другую.

обновление

причина, по которой вы получите перекрывающиеся линии в нижней части круга заключается в том, что (x,y) координаты округлены, поэтому в этих местах (x,y) движение горизонтально сами себя.

если вы посмотрите на это Википедия изображение:

вы заметите, что в верхней части круга некоторые пиксели выровнены по горизонтали. Горизонтальные линии, исходящие из этих точек, перекрываются.

если вы не хотите этого, решение довольно легкое. Вы должны сохранить предыдущий x вы нарисовали (так как верхняя и нижняя части являются зеркалами оригинала (x,y) , вы должны сохраняйте предыдущий x, который представляет y этих линий) и рисуйте только горизонтальные линии, если это значение изменяется. Если нет, значит, вы на той же линии.

учитывая тот факт, что вы сначала столкнетесь с самыми внутренними точками, вы должны нарисовать линии для предыдущей точки только новой точки имеет разные x (конечно, последняя строка всегда рисуется). Кроме того, вы можете начать рисовать с угла PI / 4 до 0 вместо 0 до PI / 4 и что вы будете сначала сталкиваются внешние точки, поэтому вы рисуете линии каждый раз, когда вы видите новый x .

Мне нужно было это сделать, вот код, который я придумал для этого. Визуальное изображение здесь показывает пиксели, нарисованные там, где число-это порядок, в котором пиксели пересекаются, а зеленые числа представляют пиксели, нарисованные с использованием отражения завершения столбца с использованием симметрии, как показано в коде.

Я придумал алгоритм, который рисует круг уже заполнен.
Он повторяет пиксели, на которых будет нарисован круг, и ничего больше.
Отсюда все о скорости функции draw-pixel.

что касается алгоритма, вот код:

надеюсь, что это помогает . некоторые новые пользователи . жалко некро-постинг.

Я хотел прокомментировать ваше обновление #2: это решение работает: (но я думаю, что мне нужно больше репутации в первую очередь. ) что в решении есть небольшая ошибка, совпадающая при рисовании небольших кругов. Если вы установите радиус в 1, вы получите

чтобы исправить это все, что вам нужно сделать, это изменить условную проверку в plot4points с

Я проверил это на маленьких и больших кругах, чтобы убедиться, что каждый пиксель по-прежнему назначается только один раз. Кажется, работает отлично. Меня думает х != 0 не требуется. Сохраните немного производительности.

Видео:1 2 4 сопряжение окружностейСкачать

Алгоритм рисования средней точки круга

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

Мы используем вышеупомянутый алгоритм, чтобы вычислить все точки периметра круга в первом октанте, а затем распечатать их вместе с их зеркальными точками в других октантах. Это будет работать только потому, что круг симметричен относительно своего центра.

Алгоритм очень похож на алгоритм генерации линий средней точки . Здесь только граничное условие отличается.

Для любого данного пикселя (x, y) следующий пиксель, который должен быть нанесен на график, имеет вид (x, y + 1) или (x-1, y + 1) . Это можно решить, выполнив следующие действия.

Найти среднюю точку p из двух возможных пикселей, т. Е. (X-0.5, y + 1)
Если p лежит внутри или по периметру круга, мы строим пиксель (x, y + 1), в противном случае, если он находится снаружи, мы строим пиксель (x-1, y + 1).

Граничное условие: находится ли средняя точка внутри или снаружи круга, можно определить по формуле:

Given a circle centered at (0,0) and radius r and a point p(x,y)
F(p) = x 2 + y 2 – r 2

if F(p) 0, the point is outside the circle

В нашей программе мы обозначаем F (p) через P. Значение P рассчитывается в средней точке двух конкурирующих пикселей, т.е. (x-0.5, y + 1). Каждый пиксель описывается нижним индексом k.

Первая точка, которая будет нанесена на график, — это (r, 0) на оси x. Начальное значение P рассчитывается следующим образом:

P1 = (r – 0.5) 2 + (0+1) 2 – r 2
= 1.25 – r
= 1 -r (When rounded off)

Примеры:

// C программа для реализации
// Алгоритм рисования средней точки круга
#include

// Реализация алгоритма рисования средней точки круга

void midPointCircleDraw( int x_centre, int y_centre, int r)

// Печать начальной точки на осях

printf ( «(%d, %d) » , x + x_centre, y + y_centre);

// когда радиус равен нулю только один

// точка будет напечатана

printf ( «(%d, %d) » , x + x_centre, -y + y_centre);

printf ( «(%d, %d) » , y + x_centre, x + y_centre);

printf ( «(%d, %d)n» , -y + x_centre, x + y_centre);

// Инициализация значения P

// Средняя точка находится внутри или по периметру

// Средняя точка находится за пределами периметра

P = P + 2*y — 2*x + 1;

// Все точки периметра уже напечатаны

// Печать сгенерированной точки и ее отражения

// в других октантах после перевода

printf ( «(%d, %d) » , x + x_centre, y + y_centre);

printf ( «(%d, %d) » , -x + x_centre, y + y_centre);

printf ( «(%d, %d) » , x + x_centre, -y + y_centre);

printf ( «(%d, %d)n» , -x + x_centre, -y + y_centre);

// Если сгенерированная точка находится на линии x = y, то

// точки периметра уже напечатаны

printf ( «(%d, %d) » , y + x_centre, x + y_centre);

printf ( «(%d, %d) » , -y + x_centre, x + y_centre);

printf ( «(%d, %d) » , y + x_centre, -x + y_centre);

printf ( «(%d, %d)n» , -y + x_centre, -x + y_centre);

// Чтобы нарисовать круг радиуса 3 с центром в (0, 0)

midPointCircleDraw(0, 0, 3);

// C ++ программа для реализации
// Алгоритм рисования средней точки круга
#include

using namespace std;

// Реализация алгоритма рисования средней точки круга

void midPointCircleDraw( int x_centre, int y_centre, int r)

// Печать начальной точки на осях

// когда радиус равен нулю только один

// точка будет напечатана

// Инициализация значения P

// Средняя точка находится внутри или по периметру

// Средняя точка находится за пределами периметра

P = P + 2*y — 2*x + 1;

// Все точки периметра уже напечатаны

// Печать сгенерированной точки и ее отражения

// в других октантах после перевода

// Если сгенерированная точка находится на линии x = y, то

// точки периметра уже напечатаны

// Чтобы нарисовать круг радиуса 3 с центром в (0, 0)

midPointCircleDraw(0, 0, 3);

// Java-программа для реализации
// Алгоритм рисования средней точки круга

// Реализация круга средней точки

static void midPointCircleDraw( int x_centre,

int y_centre, int r)

// Печать начальной точки

// по осям после перевода

System.out.print( «(» + (x + x_centre)

// когда радиус равен нулю только один

// точка будет напечатана

System.out.print( «(» + (x + x_centre)

System.out.print( «(» + (y + x_centre)

System.out.println( «(» + (-y + x_centre)

// Инициализация значения P

// Средняя точка находится внутри или по периметру

// Средняя точка находится за пределами периметра

P = P + 2 * y — 2 * x + 1 ;

// Все точки периметра уже

// Печать сгенерированной точки и ее

// отражение в других октантах после

System.out.print( «(» + (x + x_centre)

System.out.print( «(» + (-x + x_centre)

System.out.print( «(» + (x + x_centre) +

System.out.println( «(» + (-x + x_centre)

// Если сгенерированная точка находится на

// линия x = y, то точки периметра

// уже были напечатаны

System.out.print( «(» + (y + x_centre)

System.out.print( «(» + (-y + x_centre)

System.out.print( «(» + (y + x_centre)

System.out.println( «(» + (-y + x_centre)

public static void main(String[] args) <

// Нарисовать круг радиуса

// 3 с центром в (0, 0)

midPointCircleDraw( 0 , 0 , 3 );

// Этот код предоставлен Anant Agarwal.

# Python3 программа для реализации
# Mid-PoCircle Алгоритм рисования

# Реализация Mid-PoCircle Drawing
# Алгоритм

# Печать начального оттиска

# осей после перевода

print ( «(» , x + x_centre, «, » ,

# Когда радиус равен нулю только один

# может быть напечатан

print ( «(» , x + x_centre, «, » ,

print ( «(» , y + x_centre, «, » ,

print ( «(» , — y + x_centre, «, » ,

x + y_centre, «)» , sep = «»)

# Инициализация значения P

# Mid-Pois внутри или на

# Полуза вне периметра

P = P + 2 * y — 2 * x + 1

# Все точки периметра имеют

# Печать сгенерированного и его отражения

# в других октантах после перевода

print ( «(» , x + x_centre, «, » , y + y_centre,

print ( «(» , — x + x_centre, «, » , y + y_centre,

print ( «(» , x + x_centre, «, » , — y + y_centre,

print ( «(» , — x + x_centre, «, » , — y + y_centre,

# Если сгенерированные помехи на линии x = y, то

# точки периметра уже напечатаны

print ( «(» , y + x_centre, «, » , x + y_centre,

print ( «(» , — y + x_centre, «, » , x + y_centre,

print ( «(» , y + x_centre, «, » , — x + y_centre,

print ( «(» , — y + x_centre, «, » , — x + y_centre,

if __name__ = = ‘__main__’ :

# Чтобы нарисовать круг радиуса 3

# с центром в (0, 0)

midPointCircleDraw( 0 , 0 , 3 )

# Этот код предоставлен
# SHUBHAMSINGH10

// C # программа для реализации Mid-Point
// Алгоритм рисования круга

// Реализация круга средней точки

static void midPointCircleDraw( int x_centre,

int y_centre, int r)

// Печать начальной точки на

// оси после перевода

Console.Write( «(» + (x + x_centre)

// когда радиус равен нулю только один

// точка будет напечатана

Console.Write( «(» + (x + x_centre)

Console.Write( «(» + (y + x_centre)

Console.WriteLine( «(» + (-y + x_centre)

// Инициализация значения P

// Средняя точка находится внутри или по периметру

// Средняя точка находится за пределами периметра

P = P + 2 * y — 2 * x + 1;

// Все точки периметра уже

// Печать сгенерированной точки и ее

// отражение в других октантах после

Console.Write( «(» + (x + x_centre)

Console.Write( «(» + (-x + x_centre)

Console.Write( «(» + (x + x_centre) +

Console.WriteLine( «(» + (-x + x_centre)

// Если сгенерированная точка находится на

// линия x = y, то точки периметра

// уже были напечатаны

Console.Write( «(» + (y + x_centre)

Console.Write( «(» + (-y + x_centre)

Console.Write( «(» + (y + x_centre)

Console.WriteLine( «(» + (-y + x_centre)

public static void Main()

// Нарисовать круг радиуса

// 3 с центром в (0, 0)

midPointCircleDraw(0, 0, 3);

// Этот код предоставлен нитин митталь.

// PHP программа для реализации
// Алгоритм рисования средней точки круга

// Реализация средней точки
// Алгоритм рисования круга

function midPointCircleDraw( $x_centre ,

echo «(» , $x + $x_centre , «,» , $y + $y_centre , «)» ;

// когда радиус равен нулю только один

// точка будет напечатана

echo «(» , $x + $x_centre , «,» , — $y + $y_centre , «)» ;

echo «(» , $y + $x_centre , «,» , $x + $y_centre , «)» ;

echo «(» ,- $y + $x_centre , «,» , $x + $y_centre , «)» , «n» ;

// Инициализация значения P

// Средняя точка находится внутри

// или по периметру

// Середина находится снаружи

// Все точки периметра

// уже были напечатаны

// точка и ее отражение

// в других октантах

echo «(» , $x + $x_centre , «,» , $y + $y_centre , «)» ;

echo «(» ,- $x + $x_centre , «,» , $y + $y_centre , «)» ;

echo «(» , $x + $x_centre , «,» , — $y + $y_centre , «)» ;

echo «(» ,- $x + $x_centre , «,» , — $y + $y_centre , «)» , «n» ;

// Если сгенерированная точка

// на линии x = y тогда

// точки периметра имеют

echo «(» , $y + $x_centre , «,» , $x + $y_centre , «)» ;

echo «(» ,- $y + $x_centre , «,» , $x + $y_centre , «)» ;

echo «(» , $y + $x_centre , «,» , — $x + $y_centre , «)» ;

echo «(» ,- $y + $x_centre , «,» , — $x + $y_centre , «)» , «n» ;

// Нарисовать круг радиуса

// 3 с центром в (0, 0)

midPointCircleDraw(0, 0, 3);

// Этот код предоставлен нитин митталь.
?>

Список литературы: алгоритм средней точки круга
Ссылки на изображения: Октаны круга , Растеризованный круг , другие изображения были созданы для этой статьи geek

Спасибо Тухина Сингх за улучшение этой статьи.
Эта статья предоставлена Набанит Рой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.