{"id":3335,"date":"2024-12-23T17:54:47","date_gmt":"2024-12-23T17:54:47","guid":{"rendered":"https:\/\/www.byteblueprints.com\/?p=3335"},"modified":"2025-05-05T14:26:04","modified_gmt":"2025-05-05T14:26:04","slug":"xiaolin-wus-line-algorithm-in-python","status":"publish","type":"post","link":"https:\/\/www.byteblueprints.com\/?p=3335","title":{"rendered":"Xiaolin Wu\u2019s line algorithm in\u00a0python"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Xiaolin Wu\u2019s Line Algorithm<\/h3>\n\n\n\n<p>This is an implementation of Xiaolin Wu\u2019s Line Algorithm in Python. The algorithm is used to calculate a list of pixel coordinates with intensity values to form an anti-aliased line between two points on a 2D grid. It is widely used in computer graphics for rendering smooth lines on raster displays.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Overview<\/h3>\n\n\n\n<p>Xiaolin Wu\u2019s Line Algorithm is an efficient method for drawing anti-aliased lines between two points on a pixel grid. Unlike traditional line-drawing algorithms like Bresenham\u2019s, this algorithm assigns intensity values to pixels based on their proximity to the ideal line, resulting in smoother and visually appealing lines<\/p>\n\n\n\n<p>Source code:&nbsp;<a href=\"https:\/\/github.com\/byteblueprints\/bresenham-algorithms\" target=\"_blank\" rel=\"noreferrer noopener\">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>xiaolin_wu_line(x0, y0, x1, y1)<\/code> generates a list of pixel coordinates along with their intensity values that form a smooth 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 (float)<\/code>: The x-coordinate of the starting point.<\/li>\n\n\n\n<li><code>y0 (float)<\/code>: The y-coordinate of the starting point.<\/li>\n\n\n\n<li><code>x1 (float)<\/code>: The x-coordinate of the ending point.<\/li>\n\n\n\n<li><code>y1 (float)<\/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 tuples, where each tuple contains:<\/li>\n\n\n\n<li><code>x (int)<\/code>: The x-coordinate of the pixel.<\/li>\n\n\n\n<li><code>y (int)<\/code>: The y-coordinate of the pixel.<\/li>\n\n\n\n<li><code>i (float)<\/code>: The intensity value of the pixel (ranges from 0 to 1).<\/li>\n\n\n\n<li><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">How it&nbsp;works:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Anti-Aliasing<\/strong>: The algorithm calculates fractional intensities for pixels near the line to minimize the jagged appearance.<\/li>\n\n\n\n<li><strong>Steep Lines<\/strong>: For lines with a steep slope, the roles of x and y are swapped to ensure proper handling.<\/li>\n\n\n\n<li><strong>Endpoints<\/strong>: The algorithm handles endpoints separately for precision.<\/li>\n\n\n\n<li><strong>Line Traversal<\/strong>: Pixels along the line are calculated using incremental updates based on the line\u2019s slope.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Python Implementation:<\/h2>\n\n\n\n<pre class=\"wp-block-preformatted\">import math<br><br>def xiaolin_wu_line(x0, y0, x1, y1):<br>    \"\"\"<br>    Generates a list of pixel coordinates and their intensity values that form a smooth line between two points (x0, y0) and (x1, y1)<br>    using Xiaolin Wu's line algorithm.<br><br>    Args:<br>        x0 (float): The x-coordinate of the starting point.<br>        y0 (float): The y-coordinate of the starting point.<br>        x1 (float): The x-coordinate of the ending point.<br>        y1 (float): The y-coordinate of the ending point.<br><br>    Returns:<br>        list of tuple: A list of tuples, each containing the coordinates (x, y) and intensity (i) of a pixel.<br>    \"\"\"<br>    def plot(x, y, c):<br>        \"\"\"Helper function to return a pixel with its intensity.\"\"\"<br>        return (int(x), int(y), c)<br><br>    def ipart(x):<br>        \"\"\"Returns the integer part of x.\"\"\"<br>        return math.floor(x)<br><br>    def round(x):<br>        \"\"\"Rounds x to the nearest integer.\"\"\"<br>        return ipart(x + 0.5)<br><br>    def fpart(x):<br>        \"\"\"Returns the fractional part of x.\"\"\"<br>        return x - math.floor(x)<br><br>    def rfpart(x):<br>        \"\"\"Returns 1 minus the fractional part of x.\"\"\"<br>        return 1 - fpart(x)<br><br>    pixels = []<br><br>    steep = abs(y1 - y0) &gt; abs(x1 - x0)<br><br>    if steep:<br>        x0, y0 = y0, x0<br>        x1, y1 = y1, x1<br><br>    if x0 &gt; x1:<br>        x0, x1 = x1, x0<br>        y0, y1 = y1, y0<br><br>    dx = x1 - x0<br>    dy = y1 - y0<br>    gradient = dy \/ dx if dx != 0 else 1<br><br>    # Handle the first endpoint<br>    xend = round(x0)<br>    yend = y0 + gradient * (xend - x0)<br>    xgap = rfpart(x0 + 0.5)<br>    xpxl1 = xend  # This will be used as the first pixel<br>    ypxl1 = ipart(yend)<br><br>    if steep:<br>        pixels.append(plot(ypxl1, xpxl1, rfpart(yend) * xgap))<br>        pixels.append(plot(ypxl1 + 1, xpxl1, fpart(yend) * xgap))<br>    else:<br>        pixels.append(plot(xpxl1, ypxl1, rfpart(yend) * xgap))<br>        pixels.append(plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap))<br><br>    intery = yend + gradient  # First y-intersection for the main loop<br><br>    # Handle the second endpoint<br>    xend = round(x1)<br>    yend = y1 + gradient * (xend - x1)<br>    xgap = fpart(x1 + 0.5)<br>    xpxl2 = xend  # This will be used as the last pixel<br>    ypxl2 = ipart(yend)<br><br>    if steep:<br>        pixels.append(plot(ypxl2, xpxl2, rfpart(yend) * xgap))<br>        pixels.append(plot(ypxl2 + 1, xpxl2, fpart(yend) * xgap))<br>    else:<br>        pixels.append(plot(xpxl2, ypxl2, rfpart(yend) * xgap))<br>        pixels.append(plot(xpxl2, ypxl2 + 1, fpart(yend) * xgap))<br><br>    # Main loop<br>    for x in range(xpxl1 + 1, xpxl2):<br>        if steep:<br>            pixels.append(plot(ipart(intery), x, rfpart(intery)))<br>            pixels.append(plot(ipart(intery) + 1, x, fpart(intery)))<br>        else:<br>            pixels.append(plot(x, ipart(intery), rfpart(intery)))<br>            pixels.append(plot(x, ipart(intery) + 1, fpart(intery)))<br>        intery += gradient<br><br>    return pixels<\/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\/Xiaolin_Wu%27s_line_algorithm\" target=\"_blank\" rel=\"noreferrer noopener\">Xiaolin Wu\u2019s Line Algorithm\u200a\u2014\u200aWikipedia<\/a><\/li>\n<\/ul>\n\n\n\n<p>Next :- <a href=\"https:\/\/www.byteblueprints.com\/?p=3337\">String Representation of Portraits<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Xiaolin Wu\u2019s Line Algorithm This is an implementation of Xiaolin Wu\u2019s Line Algorithm in Python. The algorithm is used to calculate a list of pixel coordinates with intensity values to form an anti-aliased line between two points on a 2D grid. It is widely used in computer graphics for rendering smooth lines on raster displays. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":3383,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14,17],"tags":[],"class_list":["post-3335","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-xiaolin_wus"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3335","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=3335"}],"version-history":[{"count":5,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3335\/revisions"}],"predecessor-version":[{"id":3741,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/posts\/3335\/revisions\/3741"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=\/wp\/v2\/media\/3383"}],"wp:attachment":[{"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.byteblueprints.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}