algorithm for undoing Bresenham lines

I have a blob of points on a grid that I want to create a sensible polygon outline for. The points will be selected by the user so I can’t expect them to be perfectly following Bresenham’s algorithm for lines with weird slopes. However, I am still struggling to even get something working for an obvious "nice" sloped side:

#
###
#####
#######
#####
###
#

What I want is to turn those points into an SVG polygon (or path, or polyline, etc). It is supposed to be a nice neat triangle as you might expect.

Here is the code I have tried so far:

import cmath

s = """
#
###
#####
#######
#####
###
#
"""
pts = [complex(c, r)
       for (r, rt) in enumerate(s.splitlines())
       for (c, ch) in enumerate(rt)
       if ch == "#"]


def centroid(pts: list[complex]) -> complex:
    return sum(pts) / len(pts)


def sort_counterclockwise(pts: list[complex],
                          center: complex | None = None) -> list[complex]:
    if center is None:
        center = centroid(pts)
    return sorted(pts, key=lambda p: cmath.phase(p - center))


def perimeter(pts: list[complex]) -> list[complex]:
    out = []
    for pt in pts:
        for d in (-1, 1, -1j, 1j, -1+1j, 1+1j, -1-1j, 1-1j):
            xp = pt + d
            if xp not in pts:
                out.append(pt)
                break
    return sort_counterclockwise(out, centroid(pts))


def example(all_points: list[complex], scale: float = 20) -> str:
    p = perimeter(all_points)
    p.append(p[0])
    vbx = max(map(lambda x: x.real, p)) + 1
    vby = max(map(lambda x: x.imag, p)) + 1
    return f"""<svg
    viewBox="-1 -1 {vbx} {vby}"
    width="{vbx * scale}"
    height="{vbx * scale}">
    <polyline
    fill="none"
    stroke="black"
    stroke-width="0.1"
    points="{" ".join(map(lambda x: f"{x.real},{x.imag}", p))}">
    </polyline></svg>"""


print(example(pts))

It results in a horrible jagged mess:

<svg
    viewBox="-1 -1 7.0 8.0"
    width="140.0"
    height="140.0">
    <polyline
    fill="none"
    stroke="black"
    stroke-width="0.1"
    points="0.0,3.0 0.0,2.0 0.0,1.0 1.0,2.0 2.0,2.0 2.0,3.0 3.0,3.0 4.0,3.0 4.0,4.0 5.0,4.0 6.0,4.0 4.0,5.0 3.0,5.0 2.0,5.0 2.0,6.0 1.0,6.0 0.0,7.0 0.0,6.0 0.0,5.0 0.0,4.0 0.0,3.0">
    </polyline></svg>

Any tips on making the algorithm respond better to making clearly-defined slopes and only produce a triangle for this?

>Solution :

A more appropriate methodology for solving this issue is instead of finding all edge points (any point with an empty neighbour) which is what you are doing. You can instead just find the left most and rightmost point of each row as these are the ones you wish to plot.

We can keep points (pts) defined the same way.

Then we can create an outline like this:

def get_outline_points(pts: List[complex]) -> List[complex]:

    by_y = defaultdict(list)
    for p in pts:
        by_y[p.imag].append(p.real)
    
    # Get leftmost points sorted from bottom to top
    left_side = [
        complex(min(row), y) 
        for y, row in sorted(by_y.items())
    ]
    
    # Get rightmost points sorted from top to bottom
    right_side = [
        complex(max(row), y) 
        for y, row in sorted(by_y.items(), reverse=True)
    ]
    
    # Combine left and right sides to form the outline
    outline = left_side + right_side
    
    return outline

Now you have an outline with straight/ smooth edges.

Finish rendering as svg similarly to how you already do but accounting for outline:

def create_svg(pts: list[complex], scale: float = 20) -> str:
    outline = get_outline_points(pts)
    
    # Close the polygon by adding first point again
    if outline and outline[0] != outline[-1]:
        outline.append(outline[0])
    
    vbx = max(p.real for p in outline) + 1
    vby = max(p.imag for p in outline) + 1
    
    points_str = " ".join(f"{p.real},{p.imag}" for p in outline)
    
    return f"""<svg
    viewBox="-1 -1 {vbx} {vby}"
    width="{vbx * scale}"
    height="{vby * scale}">
    <polygon
        fill="none"
        stroke="black"
        stroke-width="0.1"
        points="{points_str}"
    />
    </svg>"""

#
###
#####
#######
#####
###
#

  <svg
      viewBox="-1 -1 7.0 8.0"
      width="140"
      height="160">
      <polygon
          fill="none"
          stroke="black"
          stroke-width="0.1"
          points="0.0,1.0 0.0,1.0 0.0,2.0 0.0,3.0 0.0,4.0 0.0,5.0 0.0,6.0 0.0,7.0 0.0,7.0 6.0,4.0 0.0,1.0"
      />
  </svg>

#
###
#####
##########
#####
###
#

<svg
    viewBox="-1 -1 10.0 7.0"
    width="200.0"
    height="140.0">
    <polygon
        fill="none"
        stroke="black"
        stroke-width="0.1"
        points="0.0,0.0 0.0,1.0 0.0,2.0 0.0,3.0 0.0,4.0 0.0,5.0 0.0,6.0 2.0,5.0 4.0,4.0 9.0,3.0 4.0,2.0 2.0,1.0 0.0,0.0"
    />
    </svg>