<SPAN class="keyword token">import</SPAN> heapq
<SPAN class="keyword token">import</SPAN> numpy <SPAN class="keyword token">as</SPAN> np
<SPAN class="keyword token">from</SPAN> scipy <SPAN class="keyword token">import</SPAN> ndimage
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">flood_fill</SPAN><SPAN class="punctuation token">(</SPAN>test_array<SPAN class="punctuation token">,</SPAN> four_way<SPAN class="operator token">=</SPAN><SPAN class="token boolean">False</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">""</SPAN><SPAN class="string token">""</SPAN><SPAN class="string token">""</SPAN>
input_array <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>copy<SPAN class="punctuation token">(</SPAN>test_array<SPAN class="punctuation token">)</SPAN>
input_rows<SPAN class="punctuation token">,</SPAN> input_cols <SPAN class="operator token">=</SPAN> input_array<SPAN class="punctuation token">.</SPAN>shape
<SPAN class="comment token"># Set h_max to a value larger than the array maximum to ensure</SPAN>
<SPAN class="comment token"># that the while loop will terminate</SPAN>
h_max <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>max<SPAN class="punctuation token">(</SPAN>input_array<SPAN class="operator token">*</SPAN><SPAN class="number token">2.0</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="comment token"># Build mask of cells with data not on the edge of the image</SPAN>
<SPAN class="comment token"># Use 3x3 square structuring element</SPAN>
inside_mask <SPAN class="operator token">=</SPAN> ndimage<SPAN class="punctuation token">.</SPAN>binary_erosion<SPAN class="punctuation token">(</SPAN>
np<SPAN class="punctuation token">.</SPAN>isfinite<SPAN class="punctuation token">(</SPAN>input_array<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
structure<SPAN class="operator token">=</SPAN>ndimage<SPAN class="punctuation token">.</SPAN>generate_binary_structure<SPAN class="punctuation token">(</SPAN><SPAN class="number token">2</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">2</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">.</SPAN>astype<SPAN class="punctuation token">(</SPAN>np<SPAN class="punctuation token">.</SPAN>int<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="comment token"># Initialize output array as max value test_array except edges</SPAN>
output_array <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>copy<SPAN class="punctuation token">(</SPAN>input_array<SPAN class="punctuation token">)</SPAN>
output_array<SPAN class="punctuation token">[</SPAN>inside_mask<SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> h_max
<SPAN class="comment token"># Build priority queue and place edge pixels into priority queue</SPAN>
<SPAN class="comment token"># Last value is flag to indicate if cell is an edge cell</SPAN>
put <SPAN class="operator token">=</SPAN> heapq<SPAN class="punctuation token">.</SPAN>heappush
get <SPAN class="operator token">=</SPAN> heapq<SPAN class="punctuation token">.</SPAN>heappop
fill_heap <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">[</SPAN>
<SPAN class="punctuation token">(</SPAN>output_array<SPAN class="punctuation token">[</SPAN>t_row<SPAN class="punctuation token">,</SPAN> t_col<SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> int<SPAN class="punctuation token">(</SPAN>t_row<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> int<SPAN class="punctuation token">(</SPAN>t_col<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="token boolean">True</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">for</SPAN> t_row<SPAN class="punctuation token">,</SPAN> t_col <SPAN class="keyword token">in</SPAN> np<SPAN class="punctuation token">.</SPAN>transpose<SPAN class="punctuation token">(</SPAN>np<SPAN class="punctuation token">.</SPAN>where<SPAN class="punctuation token">(</SPAN>edge_mask<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">]</SPAN>
heapq<SPAN class="punctuation token">.</SPAN>heapify<SPAN class="punctuation token">(</SPAN>fill_heap<SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">neighbors</SPAN><SPAN class="punctuation token">(</SPAN>row<SPAN class="punctuation token">,</SPAN> col<SPAN class="punctuation token">,</SPAN> four_way<SPAN class="operator token">=</SPAN><SPAN class="token boolean">False</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""Return indices of adjacent cells"""</SPAN>
<SPAN class="keyword token">if</SPAN> four_way<SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">return</SPAN> <SPAN class="punctuation token">[</SPAN>
<SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row<SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
<SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row<SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">]</SPAN>
<SPAN class="keyword token">else</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">return</SPAN> <SPAN class="punctuation token">[</SPAN>
<SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
<SPAN class="punctuation token">(</SPAN>row<SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
<SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">+</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
<SPAN class="punctuation token">(</SPAN>row<SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN>row <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> col <SPAN class="operator token">-</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">]</SPAN>
<SPAN class="comment token"># Iterate until priority queue is empty</SPAN>
<SPAN class="keyword token">while</SPAN> <SPAN class="token boolean">True</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">try</SPAN><SPAN class="punctuation token">:</SPAN>
h_crt<SPAN class="punctuation token">,</SPAN> t_row<SPAN class="punctuation token">,</SPAN> t_col<SPAN class="punctuation token">,</SPAN> edge_flag <SPAN class="operator token">=</SPAN> get<SPAN class="punctuation token">(</SPAN>fill_heap<SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">except</SPAN> IndexError<SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">break</SPAN>
<SPAN class="keyword token">for</SPAN> n_row<SPAN class="punctuation token">,</SPAN> n_col <SPAN class="keyword token">in</SPAN> neighbors<SPAN class="punctuation token">(</SPAN>t_row<SPAN class="punctuation token">,</SPAN> t_col<SPAN class="punctuation token">,</SPAN> four_way<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="comment token"># Skip cell if outside array edges</SPAN>
<SPAN class="keyword token">if</SPAN> edge_flag<SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">try</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">if</SPAN> <SPAN class="operator token">not</SPAN> inside_mask<SPAN class="punctuation token">[</SPAN>n_row<SPAN class="punctuation token">,</SPAN> n_col<SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">continue</SPAN>
<SPAN class="keyword token">except</SPAN> IndexError<SPAN class="punctuation token">:</SPAN>
<SPAN class="line-numbers-rows"><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN></SPAN>