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
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.