traverse pixels along known path

traverse_pixels.py

import numpy as np
from typing import NamedTuple
import matplotlib.pyplot as plt


class Point(NamedTuple):
    """
    a point in 2D with x, y coords
    """

    x: float
    y: float

class Pixel(NamedTuple):
    """
    a pixel integer x, y coords
    """

    x: int
    y: int  
        
def traverse_pixels(entry_pos, exit_pos):
    """
    Ray equation describes a point t along its trajectory:
    
    point(t) = u + tv
    
    where u is the entry position and v is the direction of the ray.
    
    We can start the traverse towards the pixel that is closest
    _in units of t_ from starting point. This is done by adding a pixel
    size in that direction also in units of t. Repeat until reaching
    the exit pixel.
    
    Voxels have unit size, ie units are in pixel size
    such that stepX and stepY are -1 or 1
    
    From the entry and exit positions one can determine v
    ie v = norm(exit_pos - entry_position)
    
    :param entry_pos: incidence position, in pixel units or u above
    :param exit_pos: exit position, in pixel units
    :return: list of pixels
    """
    dx = abs(exit_pos.x - entry_pos.x)
    dy = abs(exit_pos.y - entry_pos.y)
    
    start_pixel = Pixel(int(entry_pos.x), int(entry_pos.y))
    end_pixel = Pixel(int(exit_pos.x), int(exit_pos.y))    
    
    x, y = start_pixel.x, start_pixel.y
    
    n = 0
  
    norm = np.sqrt(dx*dx + dy*dy)
    
    # set the travelling direction quadrant based on dx, dy signs
    if dx == 0:
        stepX = 0
        
        tDeltaX = np.inf
        tDeltaY = dy
        
        tmaxX = np.inf
        
    elif dy == 0:
        stepY = 0
        
        tDeltaX = dx
        tDeltaY = np.inf
        
        tmaxY = np.inf
        
    else:    
        # deltas are just the inverse component of t
        tDeltaX = norm/dx
        tDeltaY = norm/dy
        
    if exit_pos.x < entry_pos.x:
        stepX = -1
        tmaxX = abs((entry_pos.x - np.floor(entry_pos.x)) * tDeltaX)
        n += x - end_pixel.x
        
    elif exit_pos.x > entry_pos.x:
        stepX = 1
        tmaxX = abs((np.ceil(entry_pos.x) - entry_pos.x) * tDeltaX)
        n += end_pixel.x - x
        
    if exit_pos.y < entry_pos.y:
        stepY = -1
        tmaxY = abs((entry_pos.y - np.floor(entry_pos.y)) * tDeltaY)
        n += y - end_pixel.y
        
    elif exit_pos.y > entry_pos.y:
        stepY = 1
        tmaxY = abs((np.ceil(entry_pos.y) - entry_pos.y) * tDeltaY)
        n += end_pixel.y - y

    # list of pixels travelled
    line = [Pixel(x, y)]

    for _ in range(n):
        if tmaxX < tmaxY:
            tmaxX += tDeltaX
            x += stepX
        elif tmaxX > tmaxY:
            tmaxY += tDeltaY
            y += stepY
        else:
            x += stepX
            y += stepY
        
        line.append(Pixel(x,y))
        
    return line    
  
if __name__ == '__main__':
    start = Point(np.random.uniform(0,7), np.random.uniform(0,7))
    end = Point(np.random.uniform(0,7), np.random.uniform(0,7))
    pixels = traverse_pixels(start, end)
    
    # plot the results
    data = np.zeros((8,8))
    x = [pixel.x for pixel in pixels]
    y = [pixel.y for pixel in pixels]
    data[x, y] = 1
    
    fig, ax = plt.subplots()
    ax.imshow((data.T), extent=(0, 8, 8, 0), origin='upper')
    # draw gridlines
    ax.grid(which='major', axis='both', linestyle='-', color='w', linewidth=2)

    plt.plot([start.x, end.x], [start.y, end.y], marker = 'o')
    plt.show()