Converting a Diagonal Line to Orthogonal Segments

Question

I am generating lines which can be vertical, horizontal, or diagonal (given by endpoints), and want to adapt these to a 2D grid-like environment, such that the entire line is broken up into smaller 1-unit-length lines, and each section is only either vertical or horizontal, not diagonal.

My current approach is to divide each line into 1-unit pieces, grab the endpoints, and treat those as my new lines. I use a set to prevent duplicates.

newEdges = Set([])
# discretize edges into 1-unit edges
for edge in cleanEdges:
    distance = edge[0].distance_to_point(edge[1])

    if distance <= d:
        newEdges.add(edge)
    else:
        numNewPoints = int(ceil(distance / d))  # number of new points to add
        # break up into smaller pieces and add to path
        prevPoint = edge[0]
        for i in xrange(numNewPoints):
            # get x, y coords of new points
            newX = int(round(edge[0].x + (i * d) / distance * (edge[1].x - edge[0].x)))
            newY = int(round(edge[0].y + (i * d) / distance * (edge[1].y - edge[0].y)))
            newPoint = (newX, newY)

            if prevPoint != newPoint:
                newEdge = (prevPoint, newPoint)
                newEdges.add(newEdge)
                prevPoint = newPoint

        if prevPoint != edge[1]:
            newEdge = (prevPoint, edge[1])
            newEdges.add(newEdge)

However this is not only clunky, but occasionally yields diagonal segments.

What would be a good way to both discretize all the lines and convert the diagonal lines into horizontal/vertical segments?

Answer 1

You seem to be looking for some form of a Bresenham algorithm. One ready available implementation is in scikit-image as skimage.draw.line_aa.

Answer 2

So the actual term for what I was looking for is a 4-Connected Line. It becomes very easy to search for once you know that term. There is a great solution by 6502 here: Algorithm for drawing a 4-connected line.