2D Grid Fitting: detecting holes in a 2d grid

Question

I have a list of 2d coordinates (by row) mapped to a grid. However there could be some missing nodes in there. I'm trying to detect and compute an estimated position for the missing nodes.

In the example below, the last nodes in the 2nd, 3rd and 4th rows are missing. See red arrows.

I'm looking for a numpy-friendly solution, if possible. I looked at other potential ways and RectBivariateSpline (scipy.interpolate) but they won't work since my grid may be tilted.

nodes = [[(194, 146), (311, 146), (427, 146), (545, 146), (662, 146), (780, 146), (904, 146), (1014, 146), (1130, 146), (1248, 146), (1365, 146), (1483, 146), (1602, 146), (1719, 146), (1842, 146)],
             [(159, 196), (278, 196), (401, 196), (524, 196), (643, 197), (766, 197), (887, 196), (1011, 196), (1135, 196), (1258, 196), (1381, 197), (1503, 196), (1624, 196), (1750, 196)], 
             [(117, 251), (242, 251), (370, 251), (496, 251), (627, 251), (752, 251), (880, 251), (1010, 251), (1137, 251), (1266, 251), (1395, 251), (1522, 251), (1653, 252), (1780, 251)], 
             [(73, 311), (203, 311), (336, 311), (473, 311), (604, 311), (735, 312), (872, 312), (1006, 312), (1141, 312), (1277, 312), (1412, 312), (1549, 312), (1681, 312), (1824, 312)], 
             [(163, 377), (299, 378), (442, 378), (580, 378), (719, 378), (864, 378), (1005, 378), (1147, 378), (1289, 378), (1433, 379), (1571, 378), (1716, 379), (1856, 379), (1998, 378)], 
             [(110, 451), (260, 451), (408, 451), (554, 451), (702, 452), (853, 452), (1001, 452), (1151, 452), (1301, 452), (1453, 452), (1600, 452), (1751, 452), (1899, 453), (2052, 453)], 
             [(59, 532), (212, 534), (372, 533), (529, 533), (684, 534), (843, 534), (998, 534), (1158, 534), (1314, 535), (1474, 535), (1631, 535), (1793, 535), (1949, 535)], 
             [(163, 624), (329, 624), (496, 625), (663, 625), (830, 626), (996, 626), (1163, 627), (1334, 627), (1496, 627), (1667, 627), (1834, 627), (2002, 627)], 
             [(115, 728), (284, 728), (459, 729), (639, 729), (814, 730), (992, 730), (1174, 731), (1347, 730), (1528, 731), (1707, 731), (1883, 731)], 
             [(40, 846), (233, 846), (422, 846), (611, 848), (799, 848), (992, 848), (1183, 849), (1369, 849), (1559, 849), (1752, 850), (1942, 851)], 
             [(172, 982), (372, 982), (580, 982), (782, 984), (983, 984), (1186, 984), (1394, 985), (1598, 986), (1803, 987), (2013, 989)], 
             [(98, 1141), (323, 1140), (540, 1141), (759, 1141), (978, 1142), (1203, 1142), (1419, 1144), (1641, 1144), (1865, 1147)]]

Answer 1

I ended up doing it "the iterative way". Here's the pseudo-code:

• identify the most vertical line
• find the upper node closest to that line. centerline_x is the starting search criteria
• list all nodes that are vertically aligned with centerline_x
• move to the left. line_offset -= 1
• compute the mean horizontal distance for each line and search within that offset
• stop when no node fills the criteria, repeat for the right hand-side.
• if less than 3 points are found, discard the vertical line

Here's the code:

def bin_vertical_grid_nodes(grid_nodes, image_width, centerline_x):
    # return the list of vertical nodes     
    vertically_aligned_nodes = list()
    
    # go from center to the left hand-side 
    vnodes_left = find_vlines_from_offset(grid_nodes, image_width, centerline_x, 0, -1)  # -1 is "go to the left"

    # go from center+1 to the right hand-side 
    vnodes_right = self.find_vlines_from_offset(grid_nodes, image_width, centerline_x, 1, +1)  # +1 is "go to the right"

    # store the nodes from left to right
    vertically_aligned_nodes = [vline for vline in reversed(vnodes_left)]
    vertically_aligned_nodes.extend(vnodes_right)
    return vertically_aligned_nodes


def find_vlines_from_offset(grid_nodes, image_width, centerline_x, offset_x_start, direction):
    # bin all the vertical lines from a given offset from the center vertical line
    vertically_aligned_nodes = list()
    
    # select the upper node that is the closest to the centerline_x
    upper_nodes_x = numpy.asarray(grid_nodes[0])[:, 0]
    closest_point_idx = (numpy.abs(upper_nodes_x - centerline_x)).argmin()
    centerline_x = upper_nodes_x[closest_point_idx]

    line_offset_x = offset_x_start

    while True:
        lines_pos = list()  # list of nodes aligned with found_x
    
        # go through each horizontal line and find the node that is the closest to found_x
        for row in grid_nodes:
            closest_pt = self.get_closest_node_from(row, centerline_x, line_offset_x, image_width)
            if closest_pt is not None:  
                lines_pos.append(closest_pt)  # keep point that belongs to this vertical line    

        # nothing else to add
        if len(lines_pos) == 0:
            break

        # store the nodes and shift to the adjacent vertical line
        if len(lines_pos) >= 3:
            vertically_aligned_nodes.append(lines_pos)
        line_offset_x += direction  # go left or right

    return vertically_aligned_nodes

    
def get_closest_node_from(list_horiz_nodes, centerline_x, line_offset_x, image_width, leeway=0.5):
    # return the node that is closest to posx, given the leeway
    row = numpy.asarray(list_horiz_nodes)
    row_x = row[:, 0]  # x coordinates of row
    
    # compute the mean distance between each nodes in this line
    nodes_distance = numpy.ediff1d(row_x)  # compute pair-wise distance between nodes
    median_spacing = int(round(numpy.median(nodes_distance)))  # get the median distance
    posx = centerline_x + (line_offset_x * median_spacing)  
    if posx < 0 or posx >= image_width:
        return None

    # get the point closest from posx
    closest_point_idx = (numpy.abs(row_x - posx)).argmin()
    distance_from_pt = abs(row[closest_point_idx][0] - posx)
    if distance_from_pt > median_spacing * leeway:      
        return None  # this point was too far

    return list_horiz_nodes[closest_point_idx]

Here are some results: