# chamfer2D.py : image class, weighted mask and DT transforms in 2D
#
# CC-BY Edouard.Thiel@univ-amu.fr - 10/07/2022

import math


#----------------------------- I M A G E   2 D --------------------------------

class Image2D :

    """
    Stores an m*n image with m rows and n columns.
    Pixels are accessed by mat[i][j] where 0 <= i < m and 0 <= j < n.
    """

    def __init__ (self, m, n) :
        self.mat = [ [0]*n for i in range (m) ]
        self.m = m
        self.n = n

    def copy (self, img) :    
        if self.m != img.m or self.n != img.n : 
            raise ValueError ("Images sizes are different")
        for i in range (self.m) :
            for j in range (self.n) :
                self.mat[i][j] = img.mat[i][j]

    def duplicate (self) :
        tmp = Image2D (self.m, self.n)
        tmp.copy (self)
        return tmp

    def is_equal (self, img) :
        if self.m != img.m or self.n != img.n : 
            raise ValueError ("Images sizes are different")
        for i in range (self.m) :
            for j in range (self.n) :
                if self.mat[i][j] != img.mat[i][j] :
                    return False
        return True

    def show_values (self) :
        for i in range (self.m) :
            for j in range (self.n) :
                print (f"{self.mat[i][j]:3d}", end=" ")
            print()

    def show_diffs (self, img) :
        if self.m != img.m or self.n != img.n : 
            raise ValueError ("Images sizes are different")
        for i in range (self.m) :
            for j in range (self.n) :
                print (f"{self.mat[i][j]:3d}", 
                    end="*" if self.mat[i][j] != img.mat[i][j] else " ")
            print()

    def init_center (self) :
        for i in range (self.m) :
            for j in range (self.n) :
                self.mat[i][j] = 1
        self.mat[self.m//2][self.n//2] = 0

    def is_inside (self, i, j) :
        return 0 <= i < self.m and 0 <= j < self.n


#-------------------------------- H A L F   M A S K ---------------------------

class HalfMask :

    """
    Stores a half weighted mask M^h.
    """

    def __init__ (self) :
        self.reset()

    def reset (self) :
        self.weightings = []

    def add_weighting_gsym (self, i, j, w) :
        """
        Add a weighting in the first octant plus its grid symmetries.
        """
        if not (0 <= i <= j and 0 < j) :
            raise ValueError ("Bad coordinates, 1st octant expected")
        self.weightings.append ((i, j, w))
        # Add grid symmetries
        if i != j :
            self.weightings.append ((j, i, w))
        if i > 0 or (i == 0 and -j > 0) :
            self.weightings.append ((i, -j, w))
        if i != j and i != 0 :
            self.weightings.append ((j, -i, w))

    def full_mask_weightings (self) :
        return self.weightings + [ (-i,-j,w) for i,j,w in self.weightings]

    def show_values (self) :
        for p in self.weightings :
            print (p)


#------------------------- S E Q U E N T I A L   D T --------------------------

def compute_one_DT_scan (img, half_mask, scan_num, show=False) :

    forward = scan_num % 2 == 1
    if forward :
        i_start = 0 ; i_end = img.m                     # 0 to m-1
        j_start = 0 ; j_end = img.n ; step = 1          # 0 to n-1
    else :
        i_start = img.m-1 ; i_end = -1                  # m-1 to 0
        j_start = img.n-1 ; j_end = -1 ; step = -1      # n-1 to 0

    changed = False
    for i in range (i_start, i_end, step) :
        for j in range (j_start, j_end, step) :
            if img.mat[i][j] == 0 : 
                continue
            min_w = -1 if scan_num == 1 else img.mat[i][j]  # -1 : undefined
            for p_i, p_j, p_w in half_mask.weightings :
                q_i = i - p_i*step ; q_j = j - p_j*step
                if not img.is_inside (q_i, q_j) : 
                    continue
                if img.mat[q_i][q_j] == -1 : 
                    continue
                q_w = img.mat[q_i][q_j] + p_w
                if min_w == -1 or q_w < min_w : 
                    min_w = q_w
            if img.mat[i][j] != min_w : 
                    changed = True
            img.mat[i][j] = min_w                           # can be -1

    if show :
        print ("DT_scan", scan_num, "forward" if forward else "backward",
            " changed:", changed)
        img.show_values()
    return changed


def compute_sequential_DT_in_two_scans (img, half_mask, show=False) :

    compute_one_DT_scan (img, half_mask, 1, show)
    compute_one_DT_scan (img, half_mask, 2, show)


def compute_sequential_DT_multi_scans (img, half_mask, show=False) :

    scan_num = 1
    while True :
        if compute_one_DT_scan (img, half_mask, scan_num, show) : 
            scan_num += 1
        else : break
    return scan_num


#-------------------------- P A R A L L E L   D T -----------------------------

def init_DT_parallel (img) :

    for i in range (img.m) :
        for j in range (img.n) :
            if img.mat[i][j] != 0 :
                img.mat[i][j] = -1


def compute_DT_parallel_one_pass (img, half_mask) :

    changed = False
    cur = img.duplicate()
    full_mask_weightings = half_mask.full_mask_weightings()

    for i in range (cur.m) :
        for j in range (cur.n) :
            if cur.mat[i][j] == 0 :
                continue
            min_v = -1
            for p_i, p_j, p_w in full_mask_weightings :
                q_i = i + p_i
                q_j = j + p_j
                if not cur.is_inside (q_i, q_j) :
                    continue
                if cur.mat[q_i][q_j] == -1 :
                    continue
                q_v = cur.mat[q_i][q_j] + p_w
                if min_v == -1 or q_v < min_v :
                    min_v = q_v
            if cur.mat[i][j] != min_v and min_v != -1 :
                img.mat[i][j] = min_v
                changed = True
    return changed


def compute_DT_parallel (img, half_mask, show=False) :

    init_DT_parallel (img)
    if show :
        print ("DT_parallel_init")
        img.show_values()

    num_passes = 0
    while True :
        num_passes += 1
        changed = compute_DT_parallel_one_pass (img, half_mask)
        if show :
            print ("pass", num_passes)
            img.show_values()
        if not changed :
            break
    return num_passes


#----------------------------- H O M O G E N E I T Y --------------------------

def check_homogeneity_from_center (img, trace=False) :
    """
    Simple homogeneity test for DT image initialized with init_center().
    Might be a wrong norm test if the image is too small.
    """

    is_homog = True
    cm = img.m//2
    cn = img.n//2

    for i in range (img.m) :
        for j in range (img.n) :
            if img.mat[i][j] <= 0 :
                continue
            di = i-cm
            dj = j-cn
            g = math.gcd (di, dj)
            if g == 1 :
                continue
            gi = cm + di//g
            gj = cn + dj//g
            if img.mat[i][j] != img.mat[gi][gj]*g :
                if trace :
                    is_homog = False
                    print ("non homogeneous:", i, j, img.mat[i][j], ":",
                        gi, gj, img.mat[gi][gj], ": g =", g)
                else :
                    return False

    return is_homog


#-------------------------- V I S I B L E   P O I N T S -----------------------

def show_visible_point_names () :

    print ("""
                                    +---+
  8                                 |   |
                                +---+---+
  7                             |   | w |
                            +---+---+---+
  6                         |   | s |   |
                        +---+---+---+---+
  5                     |   | m | r | v |
                    +---+---+---+---+---+
  4                 |   | k |   | q |   |
                +---+---+---+---+---+---+
  3             |   | g | j |   | p | u |
            +---+---+---+---+---+---+---+
  2         |   | e |   | i |   | o |   |
        +---+---+---+---+---+---+---+---+
  1     | b | c | d | f | h | l | n | t |
    +---+---+---+---+---+---+---+---+---+
  0 |   | a |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
      0   1   2   3   4   5   6   7   8
    """)


def get_visible_coords_by_name (name) :
    """
    Returns coords i,j of a visible point from its name, else raise ValueError.

    Example:
        i, j = get_visible_coords_by_name ("a")
    """

    if name == "a" : return 0, 1
    if name == "b" : return 1, 1
    if name == "c" : return 1, 2
    if name == "d" : return 1, 3
    if name == "e" : return 2, 3
    if name == "f" : return 1, 4
    if name == "g" : return 3, 4
    if name == "h" : return 1, 5
    if name == "i" : return 2, 5
    if name == "j" : return 3, 5
    if name == "k" : return 4, 5
    if name == "l" : return 1, 6
    if name == "m" : return 5, 6
    if name == "n" : return 1, 7
    if name == "o" : return 2, 7
    if name == "p" : return 3, 7
    if name == "q" : return 4, 7
    if name == "r" : return 5, 7
    if name == "s" : return 6, 7
    if name == "t" : return 1, 8
    if name == "u" : return 3, 8
    if name == "v" : return 5, 8
    if name == "w" : return 7, 8

    raise ValueError ("unknown visible point name, 'a'..'w' expected")


def get_visible_coords_from_names (names) :
    """
    Returns the list of coordinates tuples for the visible point names.

    Example:
        v_coords = get_visible_coords_from_names ("abc")
    returns
        [ (0,1), (1,1), (1,2) ]
    """

    return [ get_visible_coords_by_name (name) for name in names ]


#-------------------------- M I S C E L L A N E O U S -------------------------

def multi_loop (n, a, b) :
    """
    Iterator simulating n nested loops:
        for v in multi_loop (n, a, b) :
    is equivalent to
        for v[0] in range (a, b) :
          for v[1] in range (a, b) :
            ...
              for v[n-1] in range (a, b) :

    Example:
        for v in multi_loop (3, 0, 2) :
            print(v)
    """

    v = [0]*n
    k = 0 ; v[k] = a
    while k >= 0 :
        if v[k] < b :
            if k < n-1 :
                k += 1 ; v[k] = a
            else :
                yield v
                v[k] += 1
            continue
        k -= 1
        if k >= 0 : v[k] += 1


#------------------------------------------------------------------------------