Обсуждение:Линейный алгоритм Брезенхэма

Эта статья имеет рейтинг C-класса по шкале оценки контента Википедии . Она представляет интерес для следующих WikiProjects :

Робототехника средней важности Эта статья находится в рамках WikiProject Robotics , совместных усилий по улучшению освещения Robotics в Wikipedia. Если вы хотите принять участие, посетите страницу проекта, где вы можете присоединиться к обсуждению и увидеть список открытых задач.Робототехника Википедия: WikiProject Робототехника Шаблон: WikiProject Робототехника Робототехника Середина Данная статья имеет среднюю степень важности по шкале важности проекта . Информатика Средняя важность Эта статья находится в рамках WikiProject Computer science , совместных усилий по улучшению охвата статей, связанных с Computer science, в Wikipedia. Если вы хотите принять участие, посетите страницу проекта, где вы можете присоединиться к обсуждению и увидеть список открытых задач.Информатика Wikipedia:WikiProject Информатика Шаблон:WikiProject Информатика Информатика Середина Данная статья имеет среднюю степень важности по шкале важности проекта . Чем вы можете помочь WikiProject Computer science : Вот некоторые задачи, ожидающие внимания: Запросы статей  : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Computing: Software / CompSci Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Low This article has been rated as Low-importance on the project's importance scale. This article is supported by WikiProject Software (assessed as Mid-importance). This article is supported by WikiProject Computer science (assessed as Mid-importance). Things you can help WikiProject Computer science with: edit history watch purge Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

В этой статье мне не хватает двух вещей:

• применения этого алгоритма. Я понимаю, для чего можно использовать этот алгоритм, но я уверен, что не все это поймут.
• объяснение того, как это работает и/или комментарии в коде

Я сам не знаю алгоритма, поэтому оставлю это кому-нибудь другому. Jeronimo 14:36 ​​25 июля 2002 г. (PDT)

Я согласен и надеюсь, что будет сделано больше. Я прокомментирую свой код немного позже и посмотрю, что я могу сделать для небольшого раздела истории и раздела приложений немного позже сегодня. Я бы добавил, что было бы неплохо увидеть статьи для других линейных алгоритмов. Rlee0001 15:20 25 июля 2002 г. (PDT)

Если вам нужны комментарии, попробуйте [1]. (Отказ от ответственности, это мой собственный код.) Обратите внимание, что в статье использовалось уравнение наклона/пересечения для линии, и поэтому есть некоторые «запутанные» детали. В примере, на который я указываю, используются однородные координаты, поэтому в нем нет особых случаев. В конце также есть общий вариант, который напрямую рисует сглаженные линии. Это вариант, который выводит точки на экран. Он также включает изменение, рекомендованное Траном Тонгом, чтобы гарантировать точно такие же точки независимо от направления линии, которые раньше были необходимы для «стирания путем рисования черного в обратном порядке», использовавшегося в ранней графике как часть перетаскивания сегментов линии. Интересно, как такая история теряется для чего-то, что раньше использовалось часто. Плавающая точка была дорогой, целочисленная дешевле, поэтому стандартной процедурой раньше было преобразование точек в конечные целочисленные координаты calcomp и выполнение того, что делал мой пример. Я не думаю, что когда-либо видел производственную версию с использованием плавающей точки. Статья также могла бы указать на использование алгоритма в неграфических контекстах. И людям может быть интересен "перезапускаемый" вариант, который использовался для создания точно таких же точек при выводе графики полосами, как и при ее создании целиком. Аххх... история. Nahaj 23:33, 14 ноября 2005 (UTC) [ ответить ]

Поскольку алгоритм Брезенхэма в первую очередь применим к растровым устройствам, первоначальное его использование на плоттерах Calcomp (которые изначально могут рисовать прямые линии движениями пера) неясно. Рендеринг "пунктирных" линий, вероятно, является способом использования алгоритма на плоттерах, но я не уверен. Может ли кто-нибудь дать ответ? - Bevo 13:07, 25 июля 2004 (UTC)

Оказывается, ранние плоттеры Calcomp были по своей природе «инкрементальными», поэтому требовали алгоритма, подобного алгоритму Брезенхэма. См. http://www.pdp8.net/563/563.shtml Calcomp 563 Incremental Plotter Information - Bevo 20:52, 29 июля 2004 (UTC)

И они могли терять приращения при ряде условий. Отсюда "трюк" многих библиотек графиков того времени, рисующих часть регистрационного символа в каком-то углу в начале, а оставшуюся часть в конце графика. Если символ был правильным, у вас была некоторая уверенность, что график был построен нормально, в противном случае, если части были смещены или искажены, была какая-то ошибка. Nahaj 23:33, 14 ноября 2005 (UTC) [ ответить ]

Я думаю, что после умножения уравнений на deltax переменная deltaerr становится ненужной, так как она просто равна deltay. Замена deltaerr на deltay упростила бы код и приблизила бы его к другим реализациям, например, к той, что в FSHill: Computer Graphics Using OpenGL. Но в любом случае спасибо за эту статью, это пока лучшее и самое простое объяснение алгоритма, которое я видел.

X увеличивается вправо, как обычно, но Y увеличивается вниз, а не вверх. Я понимаю, что это зависит только от того, находится ли начало координат (0, 0) в верхнем левом или нижнем левом углу, но похоже, что этот выбор вызывает путаницу, отсюда и неверное "Эта первая версия обрабатывает только линии, которые восходят вправо", разве не должно быть нисхождение? Я бы предположил, что +X == вправо, +Y == вверх будет более привычно для неспециалистов, которые пришли из декартовых координат в математике в школе, без необходимости мысленно переворачивать по оси X. -- Ральф Кордерой 11:36, 3 декабря 2006 (UTC) [ ответить ]

Положительный y = down, по-видимому, является доминирующим соглашением в вычислительной технике. Plugwash 11:25, 4 декабря 2006 (UTC) [ ответить ]

Просто представьте это как квадрант IV графика. Jamestheprogrammer 15:21, 10 марта 2007 (UTC) [ ответить ]

Plugwash прав, ось Y увеличивается вниз (в C++) -- Shreyasjoshis 05:28, 21 апреля 2007 (UTC) [ ответить ]

Этот стандарт, вероятно, возник из-за того, что стандартные ЭЛТ-мониторы отображают экран сверху вниз, и поэтому реализация графического режима с Y, поднимающимся к верхней части экрана, потребовала бы — в простейшем случае — поднять X влево и изменить порядок данных где-то перед тем, как они будут переданы через порт VGA. Решение с +X справа и +Y сверху потребовало бы более сложного метода, который меняет порядок строк, но не порядок пикселей.Upthorn 05:37, 14 мая 2007 (UTC) [ ответить ]

Вероятно, это также связано с тем, что текст пишется, начиная с верхнего левого угла страницы, и идет вниз по мере продвижения. Например, рассмотрим, как вы инициализируете массив памяти в C. Первое местоположение инициализируется первым, а следующие — поперек/вниз страницы. Если бы положительный Y не был направлен вниз, все было бы перевернуто. Кстати, вы можете легко переключаться между двумя форматами, просто выполняя "plot( x, (YRES-1)-y )" вместо "plot( x ,y )" 77.103.105.67 ( talk ) 11:54, 6 мая 2020 (UTC) [ ответить ]

На каком языке программирования написан код в этой статье? — Brim 07:59, 9 февраля 2005 (UTC)

Он написан на псевдокоде, который называется Wikicode . Есть ли какая-то часть, которая вам не ясна? Deco 18:23, 9 февраля 2005 (UTC)

Спасибо за объяснение. Примеры псевдокода понятны и просты для понимания. Я просто не был уверен, должны ли примеры на этой странице быть на каком-то определенном компьютерном языке или что-то в этом роде, так как я никогда раньше не сталкивался с Wikicode. Теперь я понимаю. Возможно, было бы яснее, если бы мы где-то в статье сказали: «Это пример Wikicode», но я посмотрел другие статьи, реализующие Wikicode, и прецедент, похоже, заключается в том, чтобы не делать подобных заявлений. — Brim 18:45, 9 февраля 2005 г. (UTC)

Шаблон {{wikicode}}, размещенный в каждой из этих статей, говорил именно это. Я удалил сообщение из шаблона из-за политического давления — возникло яростное противодействие концепции стандартного псевдокода. Если вы считаете это уместным, вы можете повторно добавить сообщение самостоятельно в Шаблон: Wikicode. Deco 07:36, 10 февраля 2005 (UTC)

в статье об алгоритме рисования линий утверждается, что это позволяет избежать арифметики с плавающей точкой, однако код здесь явно этого не делает. Пожалуйста, поясните. Plugwash 21:44, 20 марта 2006 (UTC) [ ответить ]

Ага, только что заметил последний раздел «оптимизация», думаю, я немного проясню ситуацию, чтобы другие не пропустили ее. Plugwash 22:19, 20 марта 2006 (UTC) [ ответить ]

Хм... Я вижу, что это может сбивать с толку. Первая версия приведена только в педагогических целях, поскольку она лучше иллюстрирует алгоритм. Надеюсь, вы не против, что я немного сдвинул ваше пояснение, так как считаю, что введение должно, вероятно, просто дать общий обзор. Хенрик 13:57, 21 марта 2006 (UTC) [ ответить ]

Если это имело значение, я преобразовал окончательный оптимизированный псевдокод в процедуру C++. Я считаю, что сделал верную построчную реализацию. Итог: это не сработало. Некоторые октанты плоскости работали нормально. Другие создавали только линии под углом 45 градусов. Вернулся и проверил и перепроверил свою реализацию. Она делала все, что говорил псевдокод, и в том же порядке (насколько я мог судить).

Зашел на другой сайт и преобразовал их версию псевдокода в реализацию C++. Работает отлично. Возможно, стоит еще раз проверить псевдокод этой Wiki, чтобы убедиться, что он действительно правильный.

Следует отметить, что предоставленный алгоритм работает только тогда, когда (x1, y1) указывает верхнюю левую точку линии, а (x2, y2) — нижнюю правую. Реализация ниже должна быть портом псевдокода 1:1 (на C++). PrisonerOfPain 23:32, 20 сентября 2006 (UTC) [ ответить ]

Код C, который сейчас в статье, у меня тоже не работает, с той же проблемой, которую вы описали. Почему код ниже говорит, что он неверный? Он тоже не работает? Dood77 (обсуждение) 18:12, 29 ноября 2007 (UTC) [ ответить ]

Я на самом деле не тестировал код, но я почти уверен, что основная ошибка исходит от ABS и SWAP; попробуйте использовать функции вместо макросов или хотя бы поставьте скобки, например

1. определить ABS(x) ((x) < 0?-(x):(x))

-ElNinyo, 28 апреля 2008 г. — Предыдущий неподписанный комментарий добавлен 87.126.153.152 (обсуждение) 11:43, 28 апреля 2008 г. (UTC) [ ответить ]

Я думаю, вам следует прочитать сообщение об ошибке SWAP, отправленное в gcc по адресу [2] — Предыдущий неподписанный комментарий добавлен пользователем 193.147.222.244 ( обсуждение ) 18:00, 10 февраля 2009 (UTC) [ ответ ]

// ПРИМЕЧАНИЕ: ДАННАЯ РЕАЛИЗАЦИЯ НЕВЕРНА!#define ABS(x) (x < 0 ? -x : x)#define SWAP(x, y) (x ^= y ^= x ^= y)void LineDrawer_Bresenham::Draw(int x1, int y1, int x2, int y2, int color){bool крутой = ABS(y2 - y1) > ABS(x2 - x1);если(крутой){ПЕРЕСТАНОВКА(x1, y1);ПЕРЕСТАНОВКА(x2, y2);}если(x1 > x2){ПЕРЕСТАНОВКА(x1, x2);ПЕРЕСТАНОВКА(y1, y2);}int dx = x2 - x1;int dy = ABS(y2 - y1);ошибка int = 0;int ystep;целое у = у1;если (y1 < y2){ystep = 1;}еще{ystep = -1;}для (int x = x1; x < x2; x++) {если(крутой){буфер[y + x * SCRWIDTH] = цвет;}еще{	буфер[x + y * SCRWIDTH] = цвет;}ошибка += dy;если(2 * ошибка >= dx){y += ystep;ошибка -= dx;}}}

-- анонимно

Реализация макроса "SWAP" в приведенном выше коде неверна, как объясняется в алгоритме обмена XOR и [3]. Некоторые хорошие компиляторы C скомпилируют эту реализацию во что-то, что не даст ожидаемых результатов.

Реализация макроса "ABS" в приведенном выше коде неверна, как объясняется в Wikibooks: C Programming/Preprocessor#.23define. Хороший компилятор C всегда скомпилирует эту реализацию во что-то, что возвращает "-3" при задании "1-2", а это не то, что нам нужно.

Существует много способов правильно реализовать "SWAP" и "ABS". Например, в C++,

#define SWAP(x, y) std::swap(x,y)#определить ABS(x) std::abs(x)

или, в C,

#определить ABS( x ) ( ((x) < 0) ? -(x) : (x) )#define SWAP(x, y) { int temp = x; x = y; y = temp; } /* предположим, что x и y — это int */

или, если вы настаиваете на том, чтобы быть «умным»,

#определить ABS( x ) ( ((x) < 0) ? -(x) : (x) )#define SWAP(x, y) { x ^= y; y ^= x; x ^= y; } /* предположим, что x и y не ссылаются на одну и ту же ячейку памяти */

Как только эти ошибки будут исправлены, перевод «оптимизированного» псевдокода, представленного в статье, на язык C в пропорции 1:1, по-моему, даст правильные результаты.

Решено

-- 68.0.124.33 ( обсуждение ) 19:06, 23 ноября 2010 (UTC) [ ответ ]

Я чувствовал себя настолько свободным, что добавил эту главу как прямой перевод с немецкой версии, куда я также внес эту и некоторые другие части. Поскольку мой родной язык не английский, кто-то может захотеть пройтись по формулировкам этой новой главы и перевести их на настоящий английский... Кроме того, первоначальное описание алгоритма и иллюстрация сильно отличаются в немецкой версии, возможно, мы сможем объединить все это и извлечь лучшее из обоих. de:PeterFrankfurt, 4 февраля 2007 г. — Предыдущий неподписанный комментарий был добавлен 84.177.118.110 (обсуждение) 15:08, 4 февраля 2007 г. (UTC). [ ответить ]

Я думаю, что в конце кода на языке C должно быть следующее, а не то, что там есть:

если (у>=х){ setPixel(x0 + x, y0 + y); setPixel(x0 - x, y0 + y); setPixel(x0 + x, y0 - y); setPixel(x0 - x, y0 - y); если (у>х){ setPixel(x0 + y, y0 + x); setPixel(x0 - y, y0 + x); setPixel(x0 + y, y0 - x); setPixel(x0 - y, y0 - x); } }

Это предотвращает двойную прорисовку пикселей. Я не уверен, что это вызывает какие-либо проблемы, поэтому я и добавил это здесь.

Ну, это проблема только для (максимум) 4 пикселей во всем круге (в 50 % случаев 0 пикселей), я лично могу жить с этой избыточностью. --PeterFrankfurt 17:19, 10 марта 2007 (UTC) [ ответить ]

Большая часть этой статьи НЕ об алгоритме Брезенхэма, а о различных других алгоритмах DDA, которые являются его вариациями или обобщениями. Я бы рекомендовал переименовать эту статью в DDA или Цифровые дифференциальные анализаторы, и прояснить, какие алгоритмы на самом деле являются алгоритмами Брезенхэма (в основном только первая часть), а какие, например, обобщение средней точки, принадлежат более поздним ученым-компьютерщикам.

Например, «Другой подход» — это алгоритм DDA средней точки, разработанный Питтевеем: Питтевей, MLV, «Алгоритм рисования эллипсов или гипербол с помощью цифрового плоттера», Computer J., 10(3) ноября 1967 г., стр. 282-289.

Ван Эйкен (Ван Эйкен, младший, "Эффективный алгоритм рисования эллипса", CG&A, 4(9), сентябрь 1984 г., стр. 24-35) показал, что алгоритм средней точки дает тот же результат, что и алгоритм Брезенхэма. Swestrup 17:59, 28 февраля 2007 г. (UTC) [ ответить ]

Хорошо, я изменил это и попытался приписать эти части более правильно. Но я думаю, что нам следует оставить это вместе под названием Bresenham, потому что это то, что будут искать заинтересованные люди. --PeterFrankfurt 14:03, 2 марта 2007 (UTC) [ ответить ]

Я думаю, что исходная точка зрения все еще остается в силе. Название статьи — « Алгоритм Брезенхэма для линий». Я не вижу проблемы во включении другого контента по работе Питтевея и Ван Эйкена в какую-то другую, более общую статью о рисовании линий и окружностей (или, учитывая уровень технических подробностей, возможно, в их собственные статьи). Эти статьи, безусловно, можно было бы связать отсюда. Но я не думаю, что этот материал должен быть в этой статье. «Заинтересованные люди» все равно смогут найти другие алгоритмы через вики-ссылки в статье, в то время как эта статья снова обретет некоторую направленность. — Аллан Макиннес ( обсуждение ) 06:36, 18 мая 2007 (UTC) [ ответить ]

Понимание вычисления параметра решения, который используют алгоритмы средней точки окружности и эллипса, очень важно для полного понимания алгоритма и для полноты. - Видрат 16:23, 29 апреля 2007 (UTC) [ ответить ]

Реализовав вариант круга на ассемблере AVR, используя пример BASIC в качестве отправной точки, я обнаружил две интересные вещи (обе подтверждены запуском кода примера в BBC Basic для Windows):

Во-первых, вычисление Y^2 и X^2 совершенно излишне; хорошо, это показывает, как вычисленные значения соотносятся с теоремой Пифагора, но это пустая трата процессорного времени, если люди понимают это как пример из реальной жизни.

Во-вторых, при портировании в среду без плавающей точки я вычислил Y-end, умножив r на root-2 * 65536, а затем отбросив два младших байта результата. Достаточно справедливо, но конечная точка октанта — это точка, в которой увеличение y и уменьшение x становятся равными. yend не нужно вычислять, а проверка цикла while-wend может быть y<=x. Это позволяет избежать любых вычислений с плавающей точкой вообще, более того, это позволяет избежать вычисления избыточного значения вообще.

Я не вижу никаких проблем, есть ли какие-либо комментарии? (Кроме моей неправильной орфографии, которая уже исправлена)

Вы совершенно правы, вычисления Y^2 и X^2 не нужны, а yend можно заменить проверкой y<=x. Посмотрим, какие оптимизации будут дальше. Хороший момент. --PeterFrankfurt 00:08, 9 мая 2007 (UTC) [ ответить ]

Я добавил кое-что, касающееся вычисления квадрата числа по сумме нечетных чисел N, считая от 1. См. square_number . Я нашел упоминание об этой технике на folklore.org. Сайт Macintosh stories. Там упоминалось, что эта идея лежит в основе реализации круговой процедуры. Я считаю, что за ней стоял Bill_Atkinson .

Я пытался реализовать это сам. Пришел с каким-то кодом. Затем попытался найти способ сохранить порог . Я пришел только к вычислению y так же, как и x. По сумме нечетных рядов. Должно быть, можно сделать это еще лучше, сказал я себе.${\displaystyle r*r-y*y}$

Просмотр того, что было на этой странице, дал мне больше понимания. Что это относится к Брезенхэму.

void raster_circle(целое число x0, целое число y0, целое число радиуса) { ошибка int = 1 - радиус; int nextodd_x = 0; int nextodd_y = -2 * радиус - 1; целое число х = 0; int y = радиус; нарисуйте начальный квадрат пикселей в то время как ( х < у ) {

Я понял, что в цикле y речь идет о получении нечетных чисел из этой серии с дальнего конца.

 /* подготовить следующий нечетный с дальнего конца и уменьшить на него */ если ( ошибка >= 0 ) { у--; следующий_четный_y += 2; f += nextodd_y; } х++;

Я также понял, что в цикле x речь идет о получении просто следующего нечетного числа.

 /* увеличить на следующий od от */ следующийнечетный_x += 2; f += nextodd_x;  нарисуйте правильные восемь пикселей }}

Я завершаю это, давая свое псевдоотношение. Это может быть составлено для .${\displaystyle x(ydelta)=y(xdelta)}$${\displaystyle x(nextodd_{y})=y(nextodd_{x})}$

В статье предполагается перевернутая система координат, линия идет слегка вниз, и говорится: "(то есть линия имеет наклон больше -1 и меньше 0.)". Эти три утверждения не могут быть все верными.

• Если первые два верны, то наклон должен быть в диапазоне <0, 1>
• Если первый и последний символы верны, линия должна немного подняться вверх.
• Если последние два утверждения верны, то система координат не должна быть перевернутой.

Примите решение и исправьте это. Ура, Shinobu 15:56, 19 мая 2007 (UTC) [ ответить ]

По состоянию на 12 апреля 2017 года наклон по-прежнему считается отрицательным, когда y1 > y0 (и x1>x0). Это произошло в 3-м абзаце раздела «Метод». Ошибочная строка была: «...(линия имеет отрицательный наклон, абсолютное значение которого меньше 1)». Я исправляю ее. Для авторов, которые не могут понять тот факт, что увеличение y по мере увеличения x всегда означает, что наклон ПОЛОЖИТЕЛЬНЫЙ (в этой системе координат это означает, что при увеличении x вправо → y увеличивается вниз ↓ ), пожалуйста, воздержитесь от редактирования. Спасибо 98.21.215.86 (обсуждение) 19:22, 12 апреля 2017 (UTC) [ ответить ]

Я хотел бы отметить, что эти алгоритмы рисования линий, опубликованные PrisonerOfPain, и алгоритм линий Брезенхэма, обсуждаемый в статье, даже не будут работать для некоторых линий, идущих прямо вниз. Вот пример: линия начинается в [1,1] и заканчивается в [3, 25], линия идет прямо вниз (в растровой системе координат), как вы увидите, вы выполните цикл только 2 раза, рисуя только два пикселя. Должен быть еще один цикл для рисования всех пикселей оси Y, или вы можете захотеть вычислить отношение dx/dy и учесть его при цикле от x1 до x2. Я сейчас в середине экзамена, поэтому я расскажу о своем алгоритме рисования линий немного позже.

Фомас 02:03, 24 мая 2007 (UTC) [ ответить ]

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

Решено

-- 68.0.124.33 ( обсуждение ) 19:06, 23 ноября 2010 (UTC) [ ответ ]

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

Функция drawLine(x1, y1, x2, y2) int dX = Abs(x2 - x1) int dY = Abs(y2 - y1) int x = x1 int y = y1 Если (x1 > x2) Тогда offsetX = -1 Иначе offsetX = 1 Если (y1 > y2) Тогда offsetY = -1 Иначе offsetY = 1 УстановитьПиксель(x,y) Если (dX > dY) Тогда ошибка  int = dX / 2 Пока (x != x2) ошибка = ошибка - dY Если (ошибка < 0) y = y + смещениеY ошибка = ошибка + dX Конец Если x = x + смещениеX УстановитьПиксель(x,y) Wend  Else  int ошибка = dY / 2 Пока (y != y2) ошибка = ошибка - dX Если (ошибка < 0) x = x + смещениеX ошибка = ошибка + dY Конец Если y = y + смещениеY УстановитьПиксель(x,y) Венд  Конец ЕСЛИ  Конец Если Конец Функция

Фомас 00:00, 26 мая 2007 (UTC) [ ответить ]

Похоже, это действительно работает, проверено путем преобразования в ассемблер x86. 83.21.28.61 (обсуждение) 11:16, 10 марта 2008 (UTC) [ ответить ]

У меня тоже работает.. преобразовано в C. Спасибо! -- JeffryJohnston ( обсуждение ) 22:42, 4 мая 2008 (UTC) [ ответить ]

Вышеприведенное НЕ работает! Это даже синтаксически некорректно, так как есть дополнительный END IF перед END FUNCTION. Также есть дополнительный раздел в Java ниже для случая, когда dX = dY, который отсутствует в вышеприведенном. Когда вы документируете алгоритмы, вам нужно убедиться, что документация верна, иначе она бессмысленна. Это лучшая причина использовать настоящий язык, а не псевдокод. Настоящие языки имеют реализации, так что написанное на них можно протестировать. Лучшие из них имеют формальные семантические определения и могут быть обоснованы математически. Псевдокоды, как правило, не имеют ни того, ни другого. —Предыдущий комментарий без знака , добавленный 86.138.15.151 (обсуждение) 22:31, 28 марта 2010 (UTC) [ ответить ]

Это версия Java, для тех, кому интересно...

public void drawLine(int x1, int y1, int x2, int y2){ Point2D.Double[] пикселей = new Point2D.Double[Math.abs(x1 - x2) + Math.abs(y1 - y2)]; int dX = Math.abs(x2 - x1); int dY = Math.abs(y2 - y1); целое число х = х1; целое у = у1; int offsetY; int offsetX; счетчик целых чисел = 0;   если (x1 > x2) смещениеX = -1;иначе если (x2 > x1) смещение X = 1;иначе смещениеX = 0; если (y1 > y2) смещение Y = -1;иначе если (y2 > y1) смещение Y = 1;иначе смещениеY = 0;пиксели[счетчик] = new Point2D.Double(x, y); если (dX > dY){ ошибка int = dX / 2; пока (х != х2){ счетчик ++; ошибка = ошибка - dY; если (ошибка < 0){ y = y + смещениеY; ошибка = ошибка + dX; } x = x + смещениеX; пиксели[счетчик] = new Point2D.Double(x, y); } } иначе если (dY > dX){ ошибка int = dY / 2; пока (y != y2){ счетчик ++; ошибка = ошибка - dX; если (ошибка < 0){ x = x + смещениеX; ошибка = ошибка + dY; } y = y + смещениеY; пиксели[счетчик] = new Point2D.Double(x, y); } } иначе если (dX == dY){ пока(х != х2){ х++; у++; пиксели[счетчик] = new Point2D.Double(x, y); } }}

Обратите внимание, что пределы массива ни в коем случае не являются точными; однако они достаточно велики, чтобы вместить строку. 192.84.113.70 ( обсуждение ) 17:34, 14 июля 2008 (UTC)Я,Я сам и я [ ответить ]

Это обсуждение имеет особое значение? Я бы предпочел удалить... semanticprecision 15:53, 6 июля 2007 (UTC) [ ответить ]

Эта статья теперь в беспорядке - у нас есть два альтернативных описания одного и того же алгоритма, лучшим подходом было бы вместо этого изменить исходный контент, чтобы включить новую информацию. Так что теперь у нас есть то, что по сути является ответвлением контента на той же странице. Я испытываю искушение переместить второе описание в песочницу, чтобы мы могли переместить полезные части обратно в статью по частям. Если никто не возражает, я, скорее всего, сделаю это через день или два. henrik • talk 11:28, 9 августа 2007 (UTC) [ ответить ]

Версия алгоритма на языке C неверна. Она не может рисовать линии, где dy > dx. Это происходит из-за того простого факта, что она не включает переменную "steep", которая используется в коде выше. 91.89.169.47 (обсуждение) 23:51, 10 января 2008 (UTC) [ ответить ]

Алгоритм круга средней точки использовался для указания на раздел «Вариант круга» в этой статье. Раздел был удален, но теперь я перенес его в новую статью. Не уверен, является ли это наиболее используемым названием для этого алгоритма, поэтому, пожалуйста, внесите соответствующие изменения, если вы знаете лучше. Lakeworks ( обсуждение ) 20:56, 12 января 2008 (UTC) [ ответ ]

Для получения дополнительной информации по этой теме щелкните ссылку ниже http://signalspot.com/2008/01/14/a-novel-and-accurate-method-for-circular-object-identification-combined-approach-of-hough-transform-eigen-values-and/#more-264 —Предыдущий неподписанный комментарий добавлен 117.198.96.60 (обсуждение) 19:58, 13 января 2008 (UTC) [ ответить ]

Я просто немного пересматривал модуль Graphics, который я делаю, и наткнулся на это, и насколько я знаю из лекций и т. д., это НЕ алгоритм Брезенхэма, это DDA. Алгоритм Брезенхэма отличается очень тонко, он включает больше предварительных вычислений и не разделяется при вычислении параметра решения, поэтому быстрее и лучше. Плюс разные вычисления для параметра решения в зависимости от значения <0 или >0. Очень неправильно называть статью чем-то, что она не описывает. —Предыдущий неподписанный комментарий добавлен Leshiy uk (обсуждение • вклад ) 21:38, 11 мая 2008 (UTC) [ ответить ]

это правда, это не алгоритм Брессенхэма, а алгоритм "средней линии"

93.184.73.10 ( обсуждение ) 01:15, 24 мая 2014 (UTC) [ ответить ]

Могу ли я использовать исходный код реализации C, указанный на странице моего лицензионного программного обеспечения MIT/X11? 149.156.160.140 (обсуждение) 08:04, 22 января 2009 (UTC) [ ответить ]

Реализация C99/C++ не рисует полную горизонтальную линию. При вводе (0,0), (2,0) она рисует только пиксели (0,0) и (1,0), а (2,0) остается пустым.

Должна ли эта строка:

для (int x = x0; x != x1; x += xstep) {

быть изменен на этот?

для (int x = x0; x <= x1; x += xstep) {

-- 155.210.155.136 (обсуждение) 08:35, 17 июля 2009 (UTC) [ ответить ]

Я удалил код реализации из статьи. Он нам не нужен; псевдокода достаточно. Как видно из обсуждений выше, код реализации подвержен ошибкам, и что еще хуже, это оригинальное исследование . Соответствующее обсуждение есть в [4]. Консенсус был в том, что нам на самом деле не нужен код реализации, псевдокода достаточно. Offliner ( talk ) 16:01, 9 августа 2009 (UTC) [ reply ]

Я думаю, что следующий алгоритм неверен. Я не совсем уверен, поэтому лучше оставлю его в покое.

 function line(x0, x1, y0, y1) int deltax := x1 - x0 int deltay := y1 - y0 real error := 0 real deltaerr := deltay / deltax // Предположим, что deltax != 0 (линия не вертикальная), // обратите внимание, что это деление необходимо выполнить таким образом, чтобы сохранить дробную часть int y := y0 для x от x0 до x1 график(x,y) ошибка := ошибка + deltaerr  если abs(ошибка) ≥ 0,5 тогда у := у + 1 ошибка := ошибка - 1.0

Меня беспокоит эта строка.

 если abs(ошибка) ≥ 0,5 тогда

«abs» здесь совершенно неверен, потому что если deltaerr равен точно 0,5, условие всегда будет выполняться, уменьшая ошибку на 0,5 с каждым оборотом.

И да, это мое оригинальное исследование :) Miko3k ( обсуждение ) 23:16, 12 августа 2009 (UTC) [ ответить ]

Я согласен с вашим главным выводом — «abs()» в первом примере псевдокода статьи следует убрать, поскольку он не нужен для конкретного октанта, для обработки которого предназначен первый пример.

Однако я не вижу, в чем проблема в случае, когда deltaerr равен ровно 0,5.

В случае, когда deltaerr равен ровно 0,5, он увеличивает y каждый раз, когда увеличивает x — разве это не то, что нам нужно?

непосредственно перед первым прохождением цикла: ошибка = 0.

В первый раз цикла: мы устанавливаем ошибку на +0,5, затем оператор «if» оказывается истинным (с абсциссой или без нее), и ошибка в итоге принимает значение -0,5.

непосредственно перед вторым прохождением цикла: ошибка = -0,5.

Во время второго прохода по циклу: мы устанавливаем ошибку на 0, затем оператор «if» не выполняется — с абсциссой или без нее ноль не больше 0,5 — поэтому значение ошибки остается равным 0.

непосредственно перед третьим прохождением цикла: ошибка = 0.

В третий раз цикла: повторяем то же самое, что и в первый раз.

Мне кажется, что текущий псевдокод (с abs или без) работает везде в первом октанте, т.е. для любого возможного значения наклона deltaerr от 0 до 1,0. -- 68.0.124.33 ( обсуждение ) 05:25, 24 ноября 2010 (UTC) [ ответ ]

Я думаю, что следующий код Octave отображает псевдокод, приведенный здесь

функция [indx indy]=bresenham ( x,y ) % векторы x, y в координатах экрана x = круглый ( x ); y = круглый ( y );    % находится ли линия выше диагонали крутой = abs ( y ( 2 ) - y ( 1 )) > abs ( x ( 2 ) - x ( 1 )); если крутой % отразить вдоль диагонали y_new = x ; x = y ; y = y_new ; очистить y_new ; конец                     обратный = x ( 1 ) > x ( 2 ); если обратный % обратный наклон x = x ([ 2 1 ]); y = y ([ 2 1 ]); конец           deltax = x ( 2 ) - x ( 1 ); deltay = abs ( y ( 2 ) - y ( 1 ));        если deltax ~= 0 deltaerr = deltay / deltax ; иначе % вернуть вертикальный список индексов disp ( 'вертикальная линия' ) end       если y ( 1 ) < y ( 2 ) % положительный наклон ystep = 1 ; иначе ystep = - 1 ; конец            % инициализация indy = нули ( deltax + 1 , 1 ); indx = indy ;  j = 0 ; err = пол ( дельтаксис / 2 );      для i = 0 : deltax , если крутой indx ( i + 1 )= j + y ( 1 ); indy ( i + 1 )= i + x ( 1 ); иначе indx ( i + 1 )= i + x ( 1 ); indy ( i + 1 )= j + y ( 1 ); конец err = err - deltay ; если err < 0 j = j + ystep ; err = err + deltax ; конец конец                                

Вот тестовый скрипт

% Скриптовая фигура ( 1 , 'Позиция' ,[ 0 200 0 200 ]);   экранx = 20 ; экранy = 20 ;x = linspace ( 0 , 1 , 100 ) * 10 + 3 ; y = 2 * x - 3 ; y2 = - 1,5 * x + 22 ; y3 = .6342 * x + 3 ;               [ indx , indy ] = брезенхам ( x ([ 1 конец ]), y ([ 1 конец ])); [ indx2 , indy2 ] = брезенхам ( x ([ 1 конец ]), y2 ([ 1 конец ])); [ indx3 , indy3 ] = брезенхам ( x ([ 1 конец ]) + 5 , y3 ([ 1 конец ]));            h = plot ( indx , indy , 'bo' , ... indx2 , indy2 , 'ro' , ... indx3 , indy3 , 'go' ); set ( h , 'markersize' , 12 );удержание графика ( x , y , '-b' , x , y2 , ' -r' , x + 5 , y3 , '-g' ) удержание выключено  set ( gca , 'xtick' ,( 1 : screenx ) - 0.5 , 'ytick' ,( 1 : screeny ) - 0.5 , 'yticklabel' ,[], 'xticklabel' ,[]); сеткаось([1 экранx 1 экранy]) ось равна    

Результат показан на рисунке справа.

Я думаю, вы можете видеть, что решение было принято неверно для двух строк. Это, вероятно, не алгоритм Брезенхэма. Kakila 17:22(CEST) Воскресенье, 6 июня 2010 г. — Предыдущий недатированный комментарий добавлен 15:31, 6 июня 2010 г. (UTC). [ ответить ]

Хорошо сделано. Может кто-нибудь посмотреть, если меняется

err = floor(дельтаксис / 2);

к

err = round(дельтаксис / 2);

исправить этот глюк? Что нам нужно сделать, чтобы исправить псевдокод в статье? -- 68.0.124.33 ( talk ) 19:06, 23 ноября 2010 (UTC) [ ответить ]

В разделе «Оптимизация» основной статьи я просто не могу понять, какого черта все дробные числа умножаются на «дельтакс». Разрешено ли нам выполнять такое умножение везде, где это нужно? И почему ошибка установлена ​​в «дельтакс/2», она также может быть дробным числом, если выражена таким образом. — Предыдущий комментарий без знака добавлен Jaybhanderi ( talk • contribs ) 17:24, 9 июня 2010 (UTC) [ ответить ]

Мы делаем это, потому что на оборудовании, которое использовал г-н Брезенхэм, а также на другом оборудовании, которое используется и сегодня[5], операция «деления» с плавающей точкой настолько медленная, что она заставляет наше оборудование работать заметно медленнее. Деление с плавающей точкой на таком медленном оборудовании занимает в сотни раз больше циклов, чем умножение и деление целых чисел.

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

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

Я не знаю, почему «оптимизированный» алгоритм в текущей версии статьи подразумевает, что «ошибка» может быть дробным числом, когда в нем говорится

ошибка int := deltax / 2

Будет ли лучше изменить это на

ошибка int := round( deltax / 2 )

или

ошибка int := floor( deltax / 2 )

? -- 68.0.124.33 ( обсуждение ) 20:19, 23 ноября 2010 (UTC) [ ответ ]

Я не понимаю, как умножение на deltax приводит к делению с плавающей точкой внутри основного цикла. Единственное деление, которое я смог придумать, это то, что в неравенстве будет написано:

ошибка > дельтакс/2

Но deltax/2 останется постоянным на протяжении всего цикла, так что его можно будет легко вычислить до входа в цикл. Я что-то упустил? — Предыдущий комментарий без знака , добавленный 87.161.171.40 (обсуждение) 21:48, 9 февраля 2013 (UTC) [ ответить ]

Другая реализация, которую я видел, была ОЧЕНЬ медленной, поэтому вот та, которую я написал, по сути, просто преобразовав псевдокод под заголовком «Оптимизация»:

public static final void lineAlgorithm(int x0, int y0, int x1, int y1) { // Bresenham's line algorithmboolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);if (steep) {int tmp = x0;x0 = y0;y0 = tmp;tmp = x1;x1 = y1;y1 = tmp;}if (x0 > x1) {int tmp = x0;x0 = x1;x1 = tmp;tmp = y0;y0 = y1;y1 = tmp;}int deltax = x1 - x0;int deltay = Math.abs(y1 - y0);int error = deltax / 2;int ystep = -1;int y = y0;if (y0 < y1)ystep = 1;for (int x = x0; x <= x1; x++) {error -= deltay;if (error < 0) {y += ystep;error += deltax;} } }

И это только мне кажется или версия алгоритма «Упрощение» намного медленнее изначально оптимизированной? 24.193.99.41 (обсуждение) 19:33, 8 августа 2011 (UTC) [ ответить ]

-- может быть, потому что «упрощенный» алгоритм имеет 3 оператора «if» во внутреннем цикле, а «оптимизированный» алгоритм имеет только 2? .. на самом деле, вычеркните это: я не учел цикл «for», который технически также является «if»

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

Кроме того, «упрощение» первого алгоритма до такого, который не выполняет никаких обменов, впечатляет, и я был бы очень признателен за некоторые педагогические шаги для его вывода. Я думаю, что в этом также может быть некоторая общая педагогическая ценность. Кроме того, как это соотносится с другими с точки зрения производительности? Я также не уверен, что упрощение — правильное слово. — Предыдущий неподписанный комментарий, добавленный Arketyp (обсуждение • вклад ) 13:52, 14 марта 2012 (UTC) [ ответить ]

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

В разделе «Оптимизация» указано: «Это приводит к разделению внутри основного цикла, однако...». Что? О каком «разделении» вы говорите? Где вы там видите «разделение»? Нет абсолютно никакого разумного объяснения, почему мы перешли от подсчета ошибок от нуля и выше к подсчету от дельтакса и ниже. Почему, в самом деле?

Раздел «Вывод» начинается с переосмысления канонического уравнения прямой в 2D. И он делает это с нуля. Почему??? Почему бы просто не использовать Ax+By+C=0 как общеизвестный базовый факт?

Следующий раздел «Алгоритм» неполон. Он никуда не ведет. Следующий раздел «Алгоритм с целочисленной арифметикой» совершенно бессвязен. Он представляет две формулы для второй точки, но не дает объяснения того, что делают там эти уравнения. Он говорит о «разнице D», но не объясняет, что это за «разница D» для второй точки. Что такое D для второй точки? Что делают там эти две формулы?

50.242.89.251 (обсуждение) 20:28, 26 апреля 2014 (UTC) [ ответить ]

Я удалил раздел оптимизации. Он был основан на неточной и/или сильно устаревшей информации. Больше не верно, что числа с плавающей точкой медленные, так было много лет; на многих современных ЦП и ГП они быстрее. И ошибки FP не являются проблемой. С помощью только float (не говоря уже о double) вам нужно было бы рисовать изображения шириной в миллионы, если не миллиарды пикселей, чтобы типичные ошибки FP были заметны. Наконец, наличие нескольких исходных образцов является излишним; по той же причине я удалил следующий раздел, который был просто еще одной оптимизацией на его основе.-- JohnBlackburne ^words _deeds 02:09, 21 сентября 2014 (UTC) [ ответить ]

Следующий блок повторяется до и в конце цикла:

если D > 0 у = у+1 Д = Д - (2*дх)

Но на самом деле его последнее выполнение бесполезно, поэтому мы могли бы вместо этого поместить его только в начало цикла, тем самым упростив код:

plotLine(x0,y0, x1,y1) дх=х1-х0 dy=y1-y0 D = 2*dy - dx участок(x0,y0) у=у0 для x от x0+1 до x1 если D > 0 у = у+1 Д = Д - (2*дх) график(x,y) Д = Д + (2*ди)

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

2. По моему мнению, анимированное изображение, представляющее собой снимок экрана с чьей-то уникальной реализацией линейного алгоритма Брезенхэма, бесполезно.

3. Метод обобщения алгоритма на все 8 октантов можно упростить и представить более наглядно.

72.229.111.192 (обсуждение) 20:30, 24 мая 2017 (UTC) [ ответить ]

Что касается пункта 1: он все еще неверен. Здесь есть несколько основных заблуждений. У пикселя нет центра, и у него определенно нет углов. За словами «центр пикселя» даже есть ссылка на основную статью о пикселях. Видимо, человек, который это сделал, не читал статью о пикселях. Честно говоря, об этом не говорится прямо. Если вы хотите просветить себя (и, возможно, улучшить эту статью), я рекомендую прочитать статью «Пиксель — это не маленький квадрат» Элви Рэя Смита от 1995 года. Короче говоря, пиксель — это точка выборки . У нее есть положение, но нет протяженности. 2001:16B8:4870:FD00:DD8E:E505:61A7:D939 (обсуждение) 14:41, 20 октября 2019 (UTC) [ ответить ]

-- См. также: https://en.wikipedia.org/wiki/%3F:#Lua функция  bline ( x0 ,  y0 ,  x1 ,  y1 )  локальный  dx ,  sx  =  math.abs ( x1  -  x0 )  , x0  <  x1  и  1  или  -1 локальный dy , sy = math.abs ( y1 - y0 ) , y0 < y1 и 1 или -1 локальная err , e2 = ( dx > dy и dx  или - dy ) / 2                        while  true  do  setPixel ( x0 , y0 );  if  x0  ==  x1  and  y0  ==  y1  then  break  end  e2  =  err  if  e2  >  - dx  then  err  -=  dy ;  x0  +=  sx  end  if  e2  <  dy  then  err  +=  dx ;  y0  +=  sy  end  end end