Dada la coordenada de dos puntos A(x1, y1) y B(x2, y2). La tarea de encontrar todos los puntos intermedios necesarios para dibujar la línea AB en la pantalla de la computadora de píxeles. Tenga en cuenta que cada píxel tiene coordenadas enteras.
Ejemplos:
Input : A(0,0), B(4,4) Output : (0,0), (1,1), (2,2), (3,3), (4,4) Input : A(0,0), B(4,2) Output : (0,0), (1,0), (2,1), (3,1), (4,2)
A continuación se presentan algunas suposiciones para mantener el algoritmo simple.
- Dibujamos una línea de izquierda a derecha.
- x1 < x2 y y1 < y2
- La pendiente de la línea está entre 0 y 1. Dibujamos una línea de abajo a la izquierda a arriba a la derecha.
Entendamos el proceso considerando primero la forma ingenua.
// A naive way of drawing line
void naiveDrawLine(x1, x2, y1, y2)
{
m = (y2 - y1)/(x2 - x1)
for (x = x1; x <= x2; x++)
{
// Assuming that the round function finds
// closest integer to a given float.
y = round(mx + c);
print(x, y);
}
}
El algoritmo anterior funciona, pero es lento. La idea del algoritmo de Bresenham es evitar la multiplicación y suma de punto flotante para calcular mx + c, y luego calcular el valor redondo de (mx + c) en cada paso. En el algoritmo de Bresenham, nos movemos a lo largo del eje x en intervalos unitarios.
- Siempre aumentamos x en 1, y elegimos sobre el próximo y, si necesitamos ir a y+1 o permanecer en y. En otras palabras, desde cualquier posición (X k , Y k ) debemos elegir entre (X k + 1, Y k ) y (X k + 1, Y k + 1).
- Nos gustaría elegir el valor de y (entre Y k + 1 e Y k ) correspondiente a un punto más cercano a la línea original.
Necesitamos un parámetro de decisión para decidir si elegir Y k + 1 o Y k como el siguiente punto. La idea es realizar un seguimiento del error de pendiente desde el incremento anterior hasta y. Si el error de pendiente se vuelve mayor a 0.5, sabemos que la línea se ha movido hacia arriba un píxel y que debemos incrementar nuestra coordenada y y reajustar el error para representar la distancia desde la parte superior del nuevo píxel, lo cual se hace restando uno de error
// Modifying the naive way to use a parameter
// to decide next y.
void withDecisionParameter(x1, x2, y1, y2)
{
m = (y2 - y1)/(x2 - x1)
slope_error = [Some Initial Value]
for (x = x1, y = y1; x = 0.5)
{
y++;
slope_error -= 1.0;
}
}
Cómo evitar la aritmética de punto flotante
El algoritmo anterior todavía incluye aritmética de punto flotante. Para evitar la aritmética de coma flotante, considere el valor por debajo del valor m.
m = (y2 – y1)/(x2 – x1)
Multiplicamos ambos lados por (x2 – x1)
También cambiamos pendiente_error a pendiente_error * (x2 – x1). Para evitar la comparación con 0,5, lo cambiamos aún más a pendiente_error * (x2 – x1) * 2.
Además, generalmente se prefiere comparar con 0 que con 1.
// Modifying the above algorithm to avoid floating
// point arithmetic and use comparison with 0.
void bresenham(x1, x2, y1, y2)
{
m_new = 2 * (y2 - y1)
slope_error_new = [Some Initial Value]
for (x = x1, y = y1; x = 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
El valor inicial de pendiente_error_nuevo es 2*(y2 – y1) – (x2 – x1). Consulte esto como prueba de este valor
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program for Bresenham’s Line Generation
// Assumptions :
// 1) Line is drawn from left to right.
// 2) x1 < x2 and y1 < y2
// 3) Slope of the line is between 0 and 1.
// We draw a line from lower left to upper
// right.
#include<bits/stdc++.h>
using namespace std;
// function for line generation
void bresenham(int x1, int y1, int x2, int y2)
{
int m_new = 2 * (y2 - y1);
int slope_error_new = m_new - (x2 - x1);
for (int x = x1, y = y1; x <= x2; x++)
{
cout << "(" << x << "," << y << ")\n";
// Add slope to increment angle formed
slope_error_new += m_new;
// Slope error reached limit, time to
// increment y and update slope error.
if (slope_error_new >= 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
}
// driver function
int main()
{
int x1 = 3, y1 = 2, x2 = 15, y2 = 5;
bresenham(x1, y1, x2, y2);
return 0;
}
Java
// Java program for Bresenhams Line Generation
// Assumptions :
// 1) Line is drawn from left to right.
// 2) x1 < x2 and y1 < y2
// 3) Slope of the line is between 0 and 1.
// We draw a line from lower left to upper
// right.
class GFG
{
// function for line generation
static void bresenham(int x1, int y1, int x2,
int y2)
{
int m_new = 2 * (y2 - y1);
int slope_error_new = m_new - (x2 - x1);
for (int x = x1, y = y1; x <= x2; x++)
{
System.out.print("(" +x + "," + y + ")\n");
// Add slope to increment angle formed
slope_error_new += m_new;
// Slope error reached limit, time to
// increment y and update slope error.
if (slope_error_new >= 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
}
// Driver code
public static void main (String[] args)
{
int x1 = 3, y1 = 2, x2 = 15, y2 = 5;
bresenham(x1, y1, x2, y2);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python 3 program for Bresenham’s Line Generation
# Assumptions :
# 1) Line is drawn from left to right.
# 2) x1 < x2 and y1 < y2
# 3) Slope of the line is between 0 and 1.
# We draw a line from lower left to upper
# right.
# function for line generation
def bresenham(x1,y1,x2, y2):
m_new = 2 * (y2 - y1)
slope_error_new = m_new - (x2 - x1)
y=y1
for x in range(x1,x2+1):
print("(",x ,",",y ,")\n")
# Add slope to increment angle formed
slope_error_new =slope_error_new + m_new
# Slope error reached limit, time to
# increment y and update slope error.
if (slope_error_new >= 0):
y=y+1
slope_error_new =slope_error_new - 2 * (x2 - x1)
# driver function
if __name__=='__main__':
x1 = 3
y1 = 2
x2 = 15
y2 = 5
bresenham(x1, y1, x2, y2)
#This code is contributed by ash264
C#
// C# program for Bresenhams Line Generation
// Assumptions :
// 1) Line is drawn from left to right.
// 2) x1 < x2 and y1< y2
// 3) Slope of the line is between 0 and 1.
// We draw a line from lower left to upper
// right.
using System;
class GFG {
// function for line generation
static void bresenham(int x1, int y1, int x2,
int y2)
{
int m_new = 2 * (y2 - y1);
int slope_error_new = m_new - (x2 - x1);
for (int x = x1, y = y1; x <= x2; x++)
{
Console.Write("(" + x + "," + y + ")\n");
// Add slope to increment angle formed
slope_error_new += m_new;
// Slope error reached limit, time to
// increment y and update slope error.
if (slope_error_new >= 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
}
// Driver code
public static void Main ()
{
int x1 = 3, y1 = 2, x2 = 15, y2 = 5;
bresenham(x1, y1, x2, y2);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program for Bresenham’s
// Line Generation Assumptions :
// 1) Line is drawn from
// left to right.
// 2) x1 < x2 and y1 < y2
// 3) Slope of the line is
// between 0 and 1.
// We draw a line from lower
// left to upper right.
// function for line generation
function bresenham($x1, $y1, $x2, $y2)
{
$m_new = 2 * ($y2 - $y1);
$slope_error_new = $m_new - ($x2 - $x1);
for ($x = $x1, $y = $y1; $x <= $x2; $x++)
{
echo "(" ,$x , "," , $y, ")\n";
// Add slope to increment
// angle formed
$slope_error_new += $m_new;
// Slope error reached limit,
// time to increment y and
// update slope error.
if ($slope_error_new >= 0)
{
$y++;
$slope_error_new -= 2 * ($x2 - $x1);
}
}
}
// Driver Code
$x1 = 3; $y1 = 2; $x2 = 15; $y2 = 5;
bresenham($x1, $y1, $x2, $y2);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// javascript program for Bresenhams Line Generation
// Assumptions :
// 1) Line is drawn from left to right.
// 2) x1 < x2 and y1 < y2
// 3) Slope of the line is between 0 and 1.
// We draw a line from lower left to upper
// right.
// function for line generation
function bresenham(x1 , y1 , x2,y2)
{
var m_new = 2 * (y2 - y1);
var slope_error_new = m_new - (x2 - x1);
for (x = x1, y = y1; x <= x2; x++)
{
document.write("(" +x + "," + y + ")<br>");
// Add slope to increment angle formed
slope_error_new += m_new;
// Slope error reached limit, time to
// increment y and update slope error.
if (slope_error_new >= 0)
{
y++;
slope_error_new -= 2 * (x2 - x1);
}
}
}
// Driver code
var x1 = 3, y1 = 2, x2 = 15, y2 = 5;
bresenham(x1, y1, x2, y2);
// This code is contributed by Amit Katiyar
</script>
Producción :
(3,2) (4,3) (5,3) (6,3) (7,3) (8,4) (9,4) (10,4) (11,4) (12,5) (13,5) (14,5) (15,5)
Complejidad de tiempo: O(x2 – x1)
Espacio auxiliar: O(1)
La explicación anterior es para proporcionar una idea aproximada detrás del algoritmo. Para obtener una explicación detallada y una prueba, los lectores pueden consultar las referencias a continuación.
El programa anterior solo funciona si la pendiente de la línea es menor que 1. Aquí hay una implementación del programa para cualquier tipo de pendiente.
C++
#include <iostream>
//#include <graphics.h>
//Uncomment the graphics library functions if you are using it
using namespace std;
void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide)
{
//pk is initial decision making parameter
//Note:x1&y1,x2&y2, dx&dy values are interchanged
//and passed in plotPixel function so
//it can handle both cases when m>1 & m<1
int pk = 2 * dy - dx;
for (int i = 0; i <= dx; i++)
{
cout << x1 << "," << y1 << endl;
//checking either to decrement or increment the value
//if we have to plot from (0,100) to (100,0)
x1 < x2 ? x1++ : x1--;
if (pk < 0)
{
//decision value will decide to plot
//either x1 or y1 in x's position
if (decide == 0)
{
// putpixel(x1, y1, RED);
pk = pk + 2 * dy;
}
else
{
//(y1,x1) is passed in xt
// putpixel(y1, x1, YELLOW);
pk = pk + 2 * dy;
}
}
else
{
y1 < y2 ? y1++ : y1--;
if (decide == 0)
{
//putpixel(x1, y1, RED);
}
else
{
// putpixel(y1, x1, YELLOW);
}
pk = pk + 2 * dy - 2 * dx;
}
}
}
int main()
{
// int gd = DETECT, gm;
// initgraph(&gd, &gm, "xxx");
int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy, pk;
//cin cout
dx = abs(x2 - x1);
dy = abs(y2 - y1);
//If slope is less than one
if (dx > dy)
{
//passing argument as 0 to plot(x,y)
plotPixel(x1, y1, x2, y2, dx, dy, 0);
}
//if slope is greater than or equal to 1
else
{
//passing argument as 1 to plot (y,x)
plotPixel(y1, x1, y2, x2, dy, dx, 1);
}
// getch();
}
Java
// Java program for Bresenhams Line Generation
import java.io.*;
import java.lang.Math;
class GFG
{
public static void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide)
{
//pk is initial decision making parameter
//Note:x1&y1,x2&y2, dx&dy values are interchanged
//and passed in plotPixel function so
//it can handle both cases when m>1 & m<1
int pk = 2 * dy - dx;
for (int i = 0; i <= dx; i++)
{
System.out.println(x1+","+y1+"\n");
//checking either to decrement or increment the value
//if we have to plot from (0,100) to (100,0)
if(x1 < x2)
x1++;
else
x1--;
if (pk < 0)
{
//decision value will decide to plot
//either x1 or y1 in x's position
if (decide == 0)
{
pk = pk + 2 * dy;
}
else
pk = pk + 2 * dy;
}
else
{
if(y1 < y2)
y1++;
else
y1--;
pk = pk + 2 * dy - 2 * dx;
}
}
}
// Driver code
public static void main (String[] args)
{
int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy, pk;
dx = Math.abs(x2 - x1);
dy = Math.abs(y2 - y1);
//If slope is less than one
if (dx > dy)
{
//passing argument as 0 to plot(x,y)
plotPixel(x1, y1, x2, y2, dx, dy, 0);
}
//if slope is greater than or equal to 1
else
{
//passing argument as 1 to plot (y,x)
plotPixel(y1, x1, y2, x2, dy, dx, 1);
}
}
}
// This code is contributed by kothavvsaakash
C#
// C# program for Bresenhams Line Generation
using System;
class GFG
{
static public void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide)
{
//pk is initial decision making parameter
//Note:x1&y1,x2&y2, dx&dy values are interchanged
//and passed in plotPixel function so
//it can handle both cases when m>1 & m<1
int pk = 2 * dy - dx;
for (int i = 0; i <= dx; i++)
{
Console.Write(x1+","+y1+"\n");
//checking either to decrement or increment the value
//if we have to plot from (0,100) to (100,0)
if(x1 < x2)
x1++;
else
x1--;
if (pk < 0)
{
//decision value will decide to plot
//either x1 or y1 in x's position
if (decide == 0)
{
pk = pk + 2 * dy;
}
else
pk = pk + 2 * dy;
}
else
{
if(y1 < y2)
y1++;
else
y1--;
pk = pk + 2 * dy - 2 * dx;
}
}
}
// Driver code
static public void Main ()
{
int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy;
dx = Math.Abs(x2 - x1);
dy = Math.Abs(y2 - y1);
//If slope is less than one
if (dx > dy)
{
//passing argument as 0 to plot(x,y)
plotPixel(x1, y1, x2, y2, dx, dy, 0);
}
//if slope is greater than or equal to 1
else
{
//passing argument as 1 to plot (y,x)
plotPixel(y1, x1, y2, x2, dy, dx, 1);
}
}
}
// This code is contributed by kothavvsaakash
100,110 101,110 102,111 103,111 104,112 105,112 106,112 107,113 108,113 109,114 110,114 111,114 112,115 113,115 114,116 115,116 116,116 117,117 118,117 119,118 120,118 121,118 122,119 123,119 124,120 125,120
Artículos relacionados:
Referencia:
https://csustan.csustan.edu/~tom/Lecture-Notes/Graphics/Bresenham-Line/Bresenham-Line.pdf
https://en.wikipedia.org/wiki/Bresenham’s_line_algorithm
http://graphics .idav.ucdavis.edu/education/GraphicsNotes/Bresenhams-Algorithm.pdf
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA