Skip to content
Advertisement

How to iterate through neighbours in 2D coordinates?

In a 2D plane, I want to check the neighbouring points until meeting a condition. For example, take a red pixel in this image (x,y). I want to iterate to find the white pixel closest to the selected red pixel.

This is an updated image provided by @Pranav Hosangadi

enter image description here

My original code is now irrelevant.

A possible solution is to create an array sorted by the distance (given on the image). Then, by looping through this array, check when the condition is met (e.g., the point is white). However, this array will be indefinite and an overkill.

// $x,$y is a given point
$array = array(
'0,0'=>0,
'-1,0'=>1,
'-1,-1'=>1.4
);

asort($array)

foreach($array as $a=>$b){
$c=explode(',',$a);
$x2=$c[0]; // x-axis distance from the given point
$y2=$c[1]; // y-axis distance from the given point
$x3=$x+$x2;
$y3=$y+$y2;
if( $x3,$y3 point is white) { break;}
}

$closest_distance=$b;

Therefore, we need to build the loop without predefined $array.

Advertisement

Answer

You could create a list of coordinate offsets ordered by their distance to the base point. Then your search function would be much simpler to write:

maxRows,maxCols = 16,16
offsets = (offset for dx in range(maxRows) for dy in range(maxCols)
                  for offset in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)])
offsets = sorted(offsets,key=lambda xy:xy[0]**2+xy[1]**2)[1:]


def closestPoint(pixels,row,col,value):
    for dx,dy in offsets:
        r,c = row+dy,col+dx
        if r not in range(len(pixels)): continue
        if c not in range(len(pixels[0])): continue
        if pixels[r][c] == value: return r,c
    return None,None

output:

bitmap = [    
[4, 2, 1, 2, 7, 3, 7, 2, 8, 7, 7, 8, 1, 7, 7, 6],
[6, 8, 3, 7, 1, 7, 8, 8, 8, 2, 4, 5, 8, 2, 5, 4],
[3, 2, 1, 6, 2, 7, 2, 2, 2, 2, 8, 2, 3, 5, 2, 7],
[8, 4, 4, 5, 2, 6, 7, 2, 6, 5, 6, 4, 5, 6, 7, 8],
[2, 6, 7, 2, 8, 6, 6, 8, 7, 6, 8, 6, 2, 8, 2, 8],
[6, 1, 7, 3, 7, 8, 8, 3, 0, 5, 6, 8, 4, 4, 5, 2],
[1, 5, 1, 7, 4, 5, 2, 2, 3, 7, 3, 3, 4, 2, 5, 4],
[1, 8, 5, 8, 1, 8, 2, 5, 4, 5, 4, 7, 2, 5, 7, 5],
[6, 6, 8, 6, 2, 6, 4, 1, 3, 4, 3, 6, 3, 6, 3, 7],
[6, 6, 5, 7, 3, 7, 3, 8, 1, 8, 2, 6, 3, 8, 2, 3],
[7, 5, 3, 1, 4, 3, 4, 3, 3, 5, 8, 5, 4, 4, 3, 3],
[2, 2, 1, 5, 1, 6, 6, 3, 8, 4, 1, 5, 2, 2, 1, 6],
[6, 2, 7, 1, 7, 4, 3, 5, 8, 6, 6, 3, 1, 2, 8, 5],
[1, 5, 1, 2, 2, 6, 3, 2, 3, 7, 4, 5, 6, 1, 8, 1],
[7, 6, 5, 2, 7, 2, 4, 8, 5, 1, 1, 4, 6, 1, 7, 7],
[2, 7, 3, 2, 1, 8, 6, 1, 6, 7, 4, 6, 7, 6, 2, 4]]

for p in range(1,9):
    print(p,closestPoint(bitmap,5,8,p))   

1 (8, 7)
2 (6, 7)
3 (6, 8)
4 (7, 8)
5 (5, 9)
6 (4, 9)
7 (4, 8)
8 (4, 7)

Note that, if you are going to check this for every position in the matrix, it will be more efficient to create a matrix of distances using a proximity refinement algorithm.

Going through offsets up to the maximum distance will skip 75% of the resulting positions. If you don’t know the maximum size in advance or if you want to avoid useless position skipping in the offset loop, you can keep a dictionary of size-positions that maps to valid positions from a given base:

posByDist = dict()
def getPositionsByDistance(height,width,r,c):
    positions = posByDist.get((height,width,r,c),[])
    if not positions:
        offsets = ((dr*dr+dc*dc,dr,dc) for dx in range(height) 
                                       for dy in range(width)
                    for dr,dc in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)]
                    if r+dr in range(height) and c+dc in range(width) )        
        positions = [(r+dr,c+dc) for _,dr,dc in sorted(offsets)]
        posByDist[height,width,r,c] = positions
    return positions

def closestPoint(pixels,row,col,value):
    h,w = len(pixels),len(pixels[0])
    return next(((r,c) for r,c in getPositionsByDistance(h,w,row,col)
                 if pixels[r][c] == value),(None,None))

This will only loop through valid positions and will dynamically create and reuse position maps as needed for those sizes and base positions that you actually encounter.

User contributions licensed under: CC BY-SA
4 People found this is helpful
Advertisement