From efc899c56858ccd5bd8681dff5501aa3c0df2cca Mon Sep 17 00:00:00 2001
From: Lukas Jiriste <ljiriste@student.42prague.com>
Date: Fri, 13 Sep 2024 12:20:36 +0200
Subject: [PATCH] Implement iteration optimization

Instead of checking every element of a
heightmap for eligibility to process,
only the elements neighbouring just
processed elements are checked.
This cuts the time to roughly a third.
---
 povodi.py | 40 +++++++++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 11 deletions(-)

diff --git a/povodi.py b/povodi.py
index 86477ef..08cb2af 100644
--- a/povodi.py
+++ b/povodi.py
@@ -5,8 +5,7 @@ def	is_noncalced_max(height_map, calced, multi_ind):
 	high_x = min(height_map.shape[0] - 1, multi_ind[0] + 1)
 	low_y = max(0, multi_ind[1] - 1)
 	high_y = min(height_map.shape[1] - 1, multi_ind[1] + 1)
-	masked_subarr = np.ma.masked_array(height_map[low_x:high_x + 1, low_y:high_y + 1],
-			mask=calced[low_x:high_x + 1, low_y:high_y + 1])
+	masked_subarr = np.ma.masked_array(height_map[low_x:high_x + 1, low_y:high_y + 1], mask=calced[low_x:high_x + 1, low_y:high_y + 1])
 	return (masked_subarr.max() == height_map[multi_ind])
 
 def	get_recipient(height_map, multi_ind):
@@ -26,19 +25,38 @@ def	get_recipient(height_map, multi_ind):
 	min_ind_small = np.unravel_index(sub_arr.argmin(), sub_arr.shape)
 	return ((min_ind_small[0] + multi_ind[0] - sub_x, min_ind_small[1] + multi_ind[1] - sub_y))
 
+def	append_eligible_neighbours(to_calc, height_map, calced, multi_ind):
+	high_x = min(height_map.shape[0] - 1, multi_ind[0] + 1)
+	low_x = max(0, multi_ind[0] - 1)
+	high_y = min(height_map.shape[1] - 1, multi_ind[1] + 1)
+	low_y = max(0, multi_ind[1] - 1)
+	for x in range(low_x, high_x + 1):
+		for y in range(low_y, high_y + 1):
+			if (is_noncalced_max(height_map, calced, (x, y))):
+				to_calc.append((x, y))
+	return
+
 def povodi(height_map):
 	height_map = np.array(height_map)
 	calced = height_map.astype('bool')
 	calced.fill(0)
 	result = height_map.astype("uint32")
 	result.fill(1)
-	while (not(calced.all())):
-		print(calced.sum() / calced.size)
-		it = np.nditer(height_map, flags=['multi_index'])
-		for el in it:
-			if (not(calced[it.multi_index]) and is_noncalced_max(height_map, calced, it.multi_index)):
-				calced[it.multi_index] = 1
-				recipient_ind = get_recipient(height_map, it.multi_index)
-				if (recipient_ind != it.multi_index):
-					result[recipient_ind] += result[it.multi_index]
+	to_calc = []
+	it = np.nditer(height_map, flags=['multi_index'])
+	for el in it:
+		if (is_noncalced_max(height_map, calced, it.multi_index)):
+			to_calc.append(it.multi_index)
+	i = 0
+	while (to_calc != []):
+		multi_ind = to_calc.pop()
+		if (calced[multi_ind]):
+			continue
+		print(i / height_map.size)
+		calced[multi_ind] = 1
+		recipient_ind = get_recipient(height_map, multi_ind)
+		if (recipient_ind != multi_ind):
+			result[recipient_ind] += result[multi_ind]
+		append_eligible_neighbours(to_calc, height_map, calced, multi_ind)
+		i += 1
 	return (result)
-- 
2.30.2