Código de string para línea 2D

El código de string es una técnica de compresión sin pérdidas que se utiliza para representar un objeto en imágenes. Las coordenadas de cualquier límite continuo de un objeto se pueden representar como una string de números donde cada número representa una dirección particular en la que está presente el siguiente punto en la línea conectada. Se toma un punto como referencia/punto de partida y al trazar los puntos generados a partir de la string, se puede volver a dibujar la figura original.

Este artículo describe cómo generar un código de string de 8 vecindarios de una línea recta 2D. En una cuadrícula rectangular, un punto puede tener como máximo 8 puntos circundantes, como se muestra a continuación. El siguiente punto de la línea tiene que ser uno de estos 8 puntos circundantes. A cada dirección se le asigna un código. Usando este código, podemos averiguar cuál de los puntos circundantes debe trazarse a continuación.

Los códigos de string podrían generarse utilizando declaraciones condicionales para cada dirección, pero se vuelve muy tedioso describir sistemas que tienen una gran cantidad de direcciones (las cuadrículas 3-D pueden tener hasta 26 direcciones). En su lugar, usamos una función hash. La diferencia en las coordenadas X( ) e Y( ) de dos puntos sucesivos se calcula y se procesa para generar la clave para el código de string entre los dos puntos.

Lista de códigos de string: 

Función hash: 

Tabla de picadillo:- 
 

1	0	5	0
1	1	8	1
0	1	7	2
-1	1	6	3
-1	0	3	4
-1	-1	0	5
0	-1	1	6
1	-1	2	7

La función no genera el valor 4, por lo que se almacena allí un valor ficticio.

Ejemplos: 
 

Input : (2, -3), (-4, 2)
Output : Chain code for the straight line from (2, -3) to (-4, 2) is 333433

Input : (-7, -4), (9, 3)
Output : Chain code for the straight line from (-7, -4) to (9, 3) is 0101010100101010

# Python3 code for generating 8-neighbourhood chain
# code for a 2-D line
 
codeList = [5, 6, 7, 4, -1, 0, 3, 2, 1]
 
# This function generates the chaincode
# for transition between two neighbour points
def getChainCode(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    hashKey = 3 * dy + dx + 4
    return codeList[hashKey]
 
'''This function generates the list of
chaincodes for given list of points'''
def generateChainCode(ListOfPoints):
    chainCode = []
    for i in range(len(ListOfPoints) - 1):
        a = ListOfPoints[i]
        b = ListOfPoints[i + 1]
        chainCode.append(getChainCode(a[0], a[1], b[0], b[1]))
    return chainCode
 
 
'''This function generates the list of points for
a straight line using Bresenham's Algorithm'''
def Bresenham2D(x1, y1, x2, y2):
    ListOfPoints = []
    ListOfPoints.append([x1, y1])
    xdif = x2 - x1
    ydif = y2 - y1
    dx = abs(xdif)
    dy = abs(ydif)
    if(xdif > 0):
        xs = 1
    else:
        xs = -1
    if (ydif > 0):
        ys = 1
    else:
        ys = -1
    if (dx > dy):
 
        # Driving axis is the X-axis
        p = 2 * dy - dx
        while (x1 != x2):
            x1 += xs
            if (p >= 0):
                y1 += ys
                p -= 2 * dx
            p += 2 * dy
            ListOfPoints.append([x1, y1])
    else:
 
        # Driving axis is the Y-axis
        p = 2 * dx-dy
        while(y1 != y2):
            y1 += ys
            if (p >= 0):
                x1 += xs
                p -= 2 * dy
            p += 2 * dx
            ListOfPoints.append([x1, y1])
    return ListOfPoints
 
def DriverFunction():
    (x1, y1) = (-9, -3)
    (x2, y2) = (10, 1)
    ListOfPoints = Bresenham2D(x1, y1, x2, y2)
    chainCode = generateChainCode(ListOfPoints)
    chainCodeString = "".join(str(e) for e in chainCode)
    print ('Chain code for the straight line from', (x1, y1),
            'to', (x2, y2), 'is', chainCodeString)
 
DriverFunction()

// JavaScript code for generating 8-neighbourhood chain
// code for a 2-D line
 
let codeList = [5, 6, 7, 4, -1, 0, 3, 2, 1];
 
// This function generates the chaincode
// for transition between two neighbour points
function getChainCode(x1, y1, x2, y2){
    let dx = x2 - x1;
    let dy = y2 - y1;
    let hashKey = 3 * dy + dx + 4;
    return codeList[hashKey];  
}
 
 
// This function generates the list of
// chaincodes for given list of points
function generateChainCode(ListOfPoints){
    let chainCode = [];
    for(let i = 0; i < ListOfPoints.length-1; i++){
        let a = ListOfPoints[i];
        let b = ListOfPoints[i + 1];
        chainCode.push(getChainCode(a[0], a[1], b[0], b[1]));
             
    }
    return chainCode;   
}
 
// This function generates the list of points for
// a straight line using Bresenham's Algorithm
function Bresenham2D(x1, y1, x2, y2){
    let ListOfPoints = [];
    ListOfPoints.push([x1, y1]);
    let xdif = x2 - x1;
    let ydif = y2 - y1;
    let dx = Math.abs(xdif);
    let dy = Math.abs(ydif);
    if(xdif > 0){
        xs = 1;
    }      
    else{
        xs = -1;
    }
         
    if (ydif > 0){
        ys = 1;
    }
    else{
        ys = -1;
    }
         
    if (dx > dy){
        // Driving axis is the X-axis
        let p = 2 * dy - dx;
        while (x1 != x2){
            x1 += xs
            if (p >= 0){
                y1 += ys;
                p -= 2 * dx;        
            }
            p += 2 * dy;
            ListOfPoints.push([x1, y1]);        
        }
        
    }
    else{
        // Driving axis is the Y-axis
        let p = 2 * dx-dy;
        while(y1 != y2){
             y1 += ys;
            if (p >= 0){
                x1 += xs;
                p -= 2 * dy;             
            }
            p += 2 * dx;
            ListOfPoints.push([x1, y1]);       
        }
    }
     
    return ListOfPoints  
}
 
 
function DriverFunction(){
    let x1 = -9;
    let y1 = -3;
    let x2 = 10;
    let y2 = 1;
    let ListOfPoints = Bresenham2D(x1, y1, x2, y2);
    let chainCode = generateChainCode(ListOfPoints);
     
    let chainCodeString = "";
    for(let i = 0; i < chainCode.length; i++){
            chainCodeString += chainCode[i].toString();   
    }
 
    console.log("Chain code for the straight line from (", x1,",", y1,")","to","(", x2,",", y2,")", "is", chainCodeString);
}
 
DriverFunction();
// The code is contributed by Nidhi goel

Chain code for the straight line from (-9, -3) to (10, 1) is 0010000100010000100