{"id":3333,"date":"2024-12-23T17:53:49","date_gmt":"2024-12-23T17:53:49","guid":{"rendered":"https:\/\/www.byteblueprints.com\/?p=3333"},"modified":"2025-05-05T14:25:07","modified_gmt":"2025-05-05T14:25:07","slug":"how-computers-draw-lines-part-3-implement-breshenham-algorithm-python","status":"publish","type":"post","link":"https:\/\/www.byteblueprints.com\/?p=3333","title":{"rendered":"How Computers Draw Lines Part 3 (Implement Breshenham Algorithm Python)"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Overview<\/h3>\n\n\n\n<p>Bresenham\u2019s Line Algorithm is an efficient method for drawing lines between two points on a pixel grid. This implementation handles horizontal, vertical, diagonal, and sloped lines with any given start and end points.<\/p>\n\n\n\n<p>Source code: <a href=\"https:\/\/github.com\/byteblueprints\/bresenham-algorithms\" rel=\"noreferrer noopener\" target=\"_blank\">https:\/\/github.com\/byteblueprints\/bresenham-algorithms<\/a><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Description:<\/h3>\n\n\n\n<p><code>get_bresenhams_line(x0, y0, x1, y1)<\/code> generates a list of pixel coordinates that lie on a straight line between two points <code>(x0, y0)<\/code> and <code>(x1, y1)<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Parameters:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>x0 (int)<\/code>: The x-coordinate of the starting point.<\/li>\n\n\n\n<li><code>y0 (int)<\/code>: The y-coordinate of the starting point.<\/li>\n\n\n\n<li><code>x1 (int)<\/code>: The x-coordinate of the ending point.<\/li>\n\n\n\n<li><code>y1 (int)<\/code>: The y-coordinate of the ending point.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Returns:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>list of tuple<\/code>: A list of pixel coordinates that lie on the line connecting <code>(x0, y0)<\/code> and <code>(x1, y1)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">How it&nbsp;works:<\/h3>\n\n\n\n<p>The algorithm determines the slope of the line between the start and end points and uses different strategies for different types of lines:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Horizontal or Vertical Lines: If either the horizontal or vertical distance (<code>dx<\/code> or <code>dy<\/code>) is 0, it uses simple iteration along one axis.<\/li>\n\n\n\n<li>Diagonal Lines: For lines with a slope of 1 (45-degree diagonal), the algorithm handles both x and y increments simultaneously.<\/li>\n\n\n\n<li>Other Slopes: For lines with slopes greater or less than 1, the algorithm adjusts based on the slope to minimize pixel calculations.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Python Implementation:<\/h2>\n\n\n\n<pre class=\"wp-block-preformatted\">def get_bresenhams_line(x0, y0, x1, y1) -&gt; list:<br>    \"\"\"<br>    Generates a list of pixel coordinates that form a line between two points (x0, y0) and (x1, y1) using Bresenham's line algorithm.<br><br>    Args:<br>        x0 (int): The x-coordinate of the starting point.<br>        y0 (int): The y-coordinate of the starting point.<br>        x1 (int): The x-coordinate of the ending point.<br>        y1 (int): The y-coordinate of the ending point.<br><br>    Returns:<br>        list of tuple: A list of pixel coordinates that lie on the line connecting (x0, y0) and (x1, y1).<br><br>    The function calculates the line using different cases based on the slope (m) and handles cases where the line is horizontal, vertical, or diagonal.<br>    It uses Bresenham's algorithm to ensure efficient pixel plotting for all types of lines.<br>    \"\"\"<br>    dx = abs(x1 - x0)<br>    dy = abs(y1 - y0)<br><br>    # If the starting and ending points are the same, return the single point.<br>    if dx == 0 and dy == 0:<br>        return [(x0, y0)]<br><br>    step_x = 1 if x0 &lt; x1 else -1<br>    step_y = 1 if y0 &lt; y1 else -1<br><br>    current_x = x0<br>    current_y = y0<br><br>    d = 2 * dy - dx<br><br>    pixels_to_be_colored = [(x0, y0)]<br><br>    # Handle horizontal or vertical lines (when either dx or dy is 0)<br>    if dy == 0 or dx == 0:<br>        while True:<br>            if y0 != y1:<br>                current_y = current_y + step_y<br>            else:<br>                current_x = current_x + step_x<br>            pixels_to_be_colored.append((current_x, current_y))<br>            if current_x &gt;= x1 and current_y &gt;= y1:<br>                break<br>    else:<br>        m = dy \/ dx<br><br>        # Handle lines with slope equal to 1 (45 degree diagonal)<br>        if m == 1:<br>            while True:<br>                current_y = current_y + step_y<br>                current_x = current_x + step_x<br>                pixels_to_be_colored.append((current_x, current_y))<br>                if current_x &gt;= x1 and current_y &gt;= y1:<br>                    break<br>        # Handle lines with slope less than 1<br>        elif m &lt; 1:<br>            while True:<br>                current_x = current_x + 1<br>                if d &gt;= 0:<br>                    current_y = current_y + step_y<br>                    d = d - 2 * dx<br>                d = 2 * dy + d<br>                pixels_to_be_colored.append((current_x, current_y))<br>                if current_x &gt;= x1 and current_y &gt;= y1:<br>                    break<br>        # Handle lines with slope greater than 1<br>        elif m &gt; 1:<br>            while True:<br>                current_y = current_y + 1<br>                if d &lt;= 0:<br>                    current_x = current_x + step_x<br>                    d = 2 * dy + d<br>                d = d - 2 * dx<br>                pixels_to_be_colored.append((current_x, current_y))<br>                if current_x &gt;= x1 and current_y &gt;= y1:<br>                    break<br>    return pixels_to_be_colored<\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">References<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Bresenham%27s_line_algorithm\" target=\"_blank\" rel=\"noreferrer noopener\">Bresenham\u2019s line algorithm\u200a\u2014\u200aWikipedia<\/a><\/li>\n<\/ul>\n\n\n\n<p>Next :- <a href=\"https:\/\/www.byteblueprints.com\/?p=3335\">Xiaolin Wu\u2019s line algorithm in\u00a0python<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Overview Bresenham\u2019s Line Algorithm is an efficient method for drawing lines between two points on a pixel grid. This implementation handles horizontal, vertical, diagonal, and sloped lines with any given start and end points. Source code: https:\/\/github.com\/byteblueprints\/bresenham-algorithms Description: get_bresenhams_line(x0, y0, x1, y1) generates a list of pixel coordinates that lie on a straight line between [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":3382,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14,15],"tags":[],"class_list":["post-3333","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-bresenham"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3333"}],"version-history":[{"count":4,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3333\/revisions"}],"predecessor-version":[{"id":3740,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3333\/revisions\/3740"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/media\/3382"}],"wp:attachment":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}