Optimizing Floodfill algorithm implementation as much as possible
up vote
5
down vote
favorite
Actually my implementation is not working very well for big areas (I don't know why) I already created a question on Stackoverflow. But I figured out how to do it to work with an O(n) implementation (you can see what I mean here (see the fiddle I attached)).
But for some reason as I said it is not working very well on big areas.
/// <summary>
/// Floods the fill.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target.</param>
/// <param name="replacement">The replacement.</param>
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement)
where T : IEquatable<T>
{
int i;
source.FloodFill(x, y, width, height, target, replacement, out i);
}
/// <summary>
/// Floods the array following Flood Fill algorithm
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target to replace.</param>
/// <param name="replacement">The replacement.</param>
/// <param name="i">The i.</param>
// This was generic
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, out int i)
where T : IEquatable<T>
{
i = 0;
HashSet<int> queue = new HashSet<int>();
queue.Add(P(x, y, width, height));
while (queue.Count > 0)
{
int _i = queue.First(),
_x = _i % width,
_y = _i / width;
queue.Remove(_i);
if (source[_i].Equals(target))
source[_i] = replacement;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
{
queue.Add(targetIndex);
if (Monitor.IsEntered(i))
++i;
else
Interlocked.Increment(ref i);
}
}
if (i > 100000)
break;
}
}
My main concerns are the following:
- I don't know if there is a better way to debug how many iterations has the algorithm done (and if I'm getting them correctly).
- I don't like to use
Monitor.IsEntered
(I'm not sure if this is needed). - I would like to speed-up it, but I don't know how (I think this is slow) (you can compare it with ms-paint to see differences, I know it's written on C++, but... I would like to get a significant perfomance).
- Also, I don't know if there is a better way to do it (to avoid unnecesary memory consumption).
c# performance algorithm
New contributor
add a comment |
up vote
5
down vote
favorite
Actually my implementation is not working very well for big areas (I don't know why) I already created a question on Stackoverflow. But I figured out how to do it to work with an O(n) implementation (you can see what I mean here (see the fiddle I attached)).
But for some reason as I said it is not working very well on big areas.
/// <summary>
/// Floods the fill.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target.</param>
/// <param name="replacement">The replacement.</param>
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement)
where T : IEquatable<T>
{
int i;
source.FloodFill(x, y, width, height, target, replacement, out i);
}
/// <summary>
/// Floods the array following Flood Fill algorithm
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target to replace.</param>
/// <param name="replacement">The replacement.</param>
/// <param name="i">The i.</param>
// This was generic
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, out int i)
where T : IEquatable<T>
{
i = 0;
HashSet<int> queue = new HashSet<int>();
queue.Add(P(x, y, width, height));
while (queue.Count > 0)
{
int _i = queue.First(),
_x = _i % width,
_y = _i / width;
queue.Remove(_i);
if (source[_i].Equals(target))
source[_i] = replacement;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
{
queue.Add(targetIndex);
if (Monitor.IsEntered(i))
++i;
else
Interlocked.Increment(ref i);
}
}
if (i > 100000)
break;
}
}
My main concerns are the following:
- I don't know if there is a better way to debug how many iterations has the algorithm done (and if I'm getting them correctly).
- I don't like to use
Monitor.IsEntered
(I'm not sure if this is needed). - I would like to speed-up it, but I don't know how (I think this is slow) (you can compare it with ms-paint to see differences, I know it's written on C++, but... I would like to get a significant perfomance).
- Also, I don't know if there is a better way to do it (to avoid unnecesary memory consumption).
c# performance algorithm
New contributor
2
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
Are you readingi
from a different thread for some reason? (e.g. to show a progress bar?)
– VisualMelon
2 days ago
1
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday
add a comment |
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Actually my implementation is not working very well for big areas (I don't know why) I already created a question on Stackoverflow. But I figured out how to do it to work with an O(n) implementation (you can see what I mean here (see the fiddle I attached)).
But for some reason as I said it is not working very well on big areas.
/// <summary>
/// Floods the fill.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target.</param>
/// <param name="replacement">The replacement.</param>
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement)
where T : IEquatable<T>
{
int i;
source.FloodFill(x, y, width, height, target, replacement, out i);
}
/// <summary>
/// Floods the array following Flood Fill algorithm
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target to replace.</param>
/// <param name="replacement">The replacement.</param>
/// <param name="i">The i.</param>
// This was generic
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, out int i)
where T : IEquatable<T>
{
i = 0;
HashSet<int> queue = new HashSet<int>();
queue.Add(P(x, y, width, height));
while (queue.Count > 0)
{
int _i = queue.First(),
_x = _i % width,
_y = _i / width;
queue.Remove(_i);
if (source[_i].Equals(target))
source[_i] = replacement;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
{
queue.Add(targetIndex);
if (Monitor.IsEntered(i))
++i;
else
Interlocked.Increment(ref i);
}
}
if (i > 100000)
break;
}
}
My main concerns are the following:
- I don't know if there is a better way to debug how many iterations has the algorithm done (and if I'm getting them correctly).
- I don't like to use
Monitor.IsEntered
(I'm not sure if this is needed). - I would like to speed-up it, but I don't know how (I think this is slow) (you can compare it with ms-paint to see differences, I know it's written on C++, but... I would like to get a significant perfomance).
- Also, I don't know if there is a better way to do it (to avoid unnecesary memory consumption).
c# performance algorithm
New contributor
Actually my implementation is not working very well for big areas (I don't know why) I already created a question on Stackoverflow. But I figured out how to do it to work with an O(n) implementation (you can see what I mean here (see the fiddle I attached)).
But for some reason as I said it is not working very well on big areas.
/// <summary>
/// Floods the fill.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target.</param>
/// <param name="replacement">The replacement.</param>
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement)
where T : IEquatable<T>
{
int i;
source.FloodFill(x, y, width, height, target, replacement, out i);
}
/// <summary>
/// Floods the array following Flood Fill algorithm
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source.</param>
/// <param name="x">The x.</param>
/// <param name="y">The y.</param>
/// <param name="width">The width.</param>
/// <param name="height">The height.</param>
/// <param name="target">The target to replace.</param>
/// <param name="replacement">The replacement.</param>
/// <param name="i">The i.</param>
// This was generic
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, out int i)
where T : IEquatable<T>
{
i = 0;
HashSet<int> queue = new HashSet<int>();
queue.Add(P(x, y, width, height));
while (queue.Count > 0)
{
int _i = queue.First(),
_x = _i % width,
_y = _i / width;
queue.Remove(_i);
if (source[_i].Equals(target))
source[_i] = replacement;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
{
queue.Add(targetIndex);
if (Monitor.IsEntered(i))
++i;
else
Interlocked.Increment(ref i);
}
}
if (i > 100000)
break;
}
}
My main concerns are the following:
- I don't know if there is a better way to debug how many iterations has the algorithm done (and if I'm getting them correctly).
- I don't like to use
Monitor.IsEntered
(I'm not sure if this is needed). - I would like to speed-up it, but I don't know how (I think this is slow) (you can compare it with ms-paint to see differences, I know it's written on C++, but... I would like to get a significant perfomance).
- Also, I don't know if there is a better way to do it (to avoid unnecesary memory consumption).
c# performance algorithm
c# performance algorithm
New contributor
New contributor
New contributor
asked 2 days ago
z3nth10n
1264
1264
New contributor
New contributor
2
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
Are you readingi
from a different thread for some reason? (e.g. to show a progress bar?)
– VisualMelon
2 days ago
1
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday
add a comment |
2
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
Are you readingi
from a different thread for some reason? (e.g. to show a progress bar?)
– VisualMelon
2 days ago
1
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday
2
2
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
Are you reading
i
from a different thread for some reason? (e.g. to show a progress bar?)– VisualMelon
2 days ago
Are you reading
i
from a different thread for some reason? (e.g. to show a progress bar?)– VisualMelon
2 days ago
1
1
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday
add a comment |
2 Answers
2
active
oldest
votes
up vote
6
down vote
Monitor.IsEntered
This call basically makes no sense. Monitor.IsEntered
is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i
: it is a counter. It isn't even a meaningful target for Monitor.IsEntered
because it isn't an object.
There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment
). This may noticeably improve performance, since Monitor.IsEntered
is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).
If, for some reason, you are reading i
from a different thread while the flood-fill is running, then you might want to use Interlocked
methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i
before this has finished then keep track of it as a 'normal' variable, and then set it as out
at the end (if it is needed at all). out
parameters can be abused, and may interfere with the compilers ability to perform optimisations.
100000
What is this?
if (i > 100000)
break;
This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target
will be 'replaced' (what does that mean?).
Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException
, or return a bool
indicating that it did not complete, or something else.
HashSet
/Stack
You should probably be using a Stack
. HashSet.Contain
is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement)
is always false
, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)
Excepting the first pixel, if you set source[targetIndex] = replacement
when you queue it then you don't need to check if it is already in the HashSet
: you only need to check that source[targetIndex].Equals(target)
, which you have to do anyway. The probably with your non-HashSet
code wasn't the Stack
, it was how you were using it.
With a stack, the code will look mostly the same, only you'll be Pop
ing from the stack (instead of using First()
and Remove(T)
. It should be much faster, because it doesn't lean on HashSet
, which while being 'kind of O(1)
' isn't going to outperform a single array lookup which probably needs to be done anyway.
Indexing
I'm guessing Pn
is static, and looks something like this:
static int Pn(int x, int y, int width => x + y * width;
IEquatable<T>
It's good that you are using this.
Naming
Most of the names are cryptic. This is not ideal. It isn't clear why you use P
rather than Pn
. i
and _i
are completely unrelated (and both poor names). target
and targetIndex
are mostly unrelated.
Code
Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
where T : IEquatable<T>
{
// code can't handle this, so throw
if (target.Equals(replacement))
{
throw new ArgumentException("Target and Replacement cannot equate");
}
// do start manually, and exit quickly if appropriate
int start = P(x, y, width, height);
if (!source[start].Equals(target))
{
explored = 0;
return;
}
// stack is not a great name, but I'm in a hurry right now...
Stack<int> stack = new Stack<int>();
stack.Push(start);
int count = 1;
while (queue.Count > 0)
{
int _i = stack.Pop(),
_x = _i % width,
_y = _i / width;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
// if pixel matched target, reset it and queue
if (source[targetIndex].Equals(target))
{
source[targetIndex] = replacement;
stack.Push(targetIndex);
count++;
}
}
if (i > cutoff)
throw new Exception("FloodFill passed cutoff");
}
// report the number of cells explored
explored = count;
}
Not worth a full answer, but I thought I'd add on that_tx
and_ty
are (besides being cryptically named) not needed. You can instead just ensure thattargetIndex
is non-negative and less thanwidth*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.
– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
IftargetIndex
is non-negative, thentargetIndex%width
will also be non-negative, and so willtargetIndex/width
(providedwidth
is non-negative).targetIndex%width
will never be greater than or equal towidth
. And the only waytargetIndex/width
can be greater than or equal toheight
is iftargetIndex
is greater than or equal towidth*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.
– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing anIndexOutOfRange
; rather, it's to stop it going fromx=0, y=1
tox=width-1, y=0
(wrapping around) when you subtract1
from the index. You are definitely right that_ty
is redundant.
– VisualMelon
yesterday
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
add a comment |
up vote
3
down vote
All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.
VisualMelon has commented some details so I won't go further into that.
When determine the area for a floodfill all you need are:
1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)
2) The width of each row (count of columns)
3) The starting point inside the area to flood
4) The target value
5) The replacement value
So the signature of the method could be something like this:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
The height (number of rows) is redundant and can easily be calculated.
You should maybe make a check of the dimension:
if (source.Length % width != 0) throw new Exception("source has wrong size");
Finding the neighbors is as simple as:
North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;
A solution could then be as follow:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
if (source == null || source.Length == 0 || target.Equals(replacement))
return;
int length = source.Length;
Queue<int> queue = new Queue<int>();
int current = startY * width + startX;
if (!source[current].Equals(target))
return;
// If no target value was found the return
if (current >= length) return;
// A target value was found at index current so enqueue that
queue.Enqueue(current);
// Local function that enqueue an index if it is within
// the boundaries of the source and the value equals the target value.
void Enqueue(int index)
{
if (index >= 0 && index < length && source[index].Equals(target))
{
source[index] = replacement;
queue.Enqueue(index);
}
}
while (queue.Count > 0)
{
current = queue.Dequeue();
// North
int neighbor = current - width;
Enqueue(neighbor);
// South
neighbor = current + width;
Enqueue(neighbor);
// East: The current index as a column index must be lesser
// than the width - 1 or else going east will
// roundtrip to the next row
if (current % width < width - 1)
{
neighbor = current + 1;
Enqueue(neighbor);
// North-East and South-East are easily found in the same way as North and South
// NE
Enqueue(neighbor - width);
// SE
Enqueue(neighbor + width);
}
// West: This is analogue to East: current as a column index must be greater than 0
// or else going west will roundtrip to the previous row.
if (current % width > 0)
{
neighbor = current - 1;
Enqueue(neighbor);
// Completely analogue to NE an SE
// NW
Enqueue(neighbor - width);
// SW
Enqueue(neighbor + width);
}
}
}
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).
– VisualMelon
yesterday
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
Monitor.IsEntered
This call basically makes no sense. Monitor.IsEntered
is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i
: it is a counter. It isn't even a meaningful target for Monitor.IsEntered
because it isn't an object.
There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment
). This may noticeably improve performance, since Monitor.IsEntered
is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).
If, for some reason, you are reading i
from a different thread while the flood-fill is running, then you might want to use Interlocked
methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i
before this has finished then keep track of it as a 'normal' variable, and then set it as out
at the end (if it is needed at all). out
parameters can be abused, and may interfere with the compilers ability to perform optimisations.
100000
What is this?
if (i > 100000)
break;
This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target
will be 'replaced' (what does that mean?).
Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException
, or return a bool
indicating that it did not complete, or something else.
HashSet
/Stack
You should probably be using a Stack
. HashSet.Contain
is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement)
is always false
, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)
Excepting the first pixel, if you set source[targetIndex] = replacement
when you queue it then you don't need to check if it is already in the HashSet
: you only need to check that source[targetIndex].Equals(target)
, which you have to do anyway. The probably with your non-HashSet
code wasn't the Stack
, it was how you were using it.
With a stack, the code will look mostly the same, only you'll be Pop
ing from the stack (instead of using First()
and Remove(T)
. It should be much faster, because it doesn't lean on HashSet
, which while being 'kind of O(1)
' isn't going to outperform a single array lookup which probably needs to be done anyway.
Indexing
I'm guessing Pn
is static, and looks something like this:
static int Pn(int x, int y, int width => x + y * width;
IEquatable<T>
It's good that you are using this.
Naming
Most of the names are cryptic. This is not ideal. It isn't clear why you use P
rather than Pn
. i
and _i
are completely unrelated (and both poor names). target
and targetIndex
are mostly unrelated.
Code
Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
where T : IEquatable<T>
{
// code can't handle this, so throw
if (target.Equals(replacement))
{
throw new ArgumentException("Target and Replacement cannot equate");
}
// do start manually, and exit quickly if appropriate
int start = P(x, y, width, height);
if (!source[start].Equals(target))
{
explored = 0;
return;
}
// stack is not a great name, but I'm in a hurry right now...
Stack<int> stack = new Stack<int>();
stack.Push(start);
int count = 1;
while (queue.Count > 0)
{
int _i = stack.Pop(),
_x = _i % width,
_y = _i / width;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
// if pixel matched target, reset it and queue
if (source[targetIndex].Equals(target))
{
source[targetIndex] = replacement;
stack.Push(targetIndex);
count++;
}
}
if (i > cutoff)
throw new Exception("FloodFill passed cutoff");
}
// report the number of cells explored
explored = count;
}
Not worth a full answer, but I thought I'd add on that_tx
and_ty
are (besides being cryptically named) not needed. You can instead just ensure thattargetIndex
is non-negative and less thanwidth*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.
– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
IftargetIndex
is non-negative, thentargetIndex%width
will also be non-negative, and so willtargetIndex/width
(providedwidth
is non-negative).targetIndex%width
will never be greater than or equal towidth
. And the only waytargetIndex/width
can be greater than or equal toheight
is iftargetIndex
is greater than or equal towidth*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.
– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing anIndexOutOfRange
; rather, it's to stop it going fromx=0, y=1
tox=width-1, y=0
(wrapping around) when you subtract1
from the index. You are definitely right that_ty
is redundant.
– VisualMelon
yesterday
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
add a comment |
up vote
6
down vote
Monitor.IsEntered
This call basically makes no sense. Monitor.IsEntered
is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i
: it is a counter. It isn't even a meaningful target for Monitor.IsEntered
because it isn't an object.
There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment
). This may noticeably improve performance, since Monitor.IsEntered
is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).
If, for some reason, you are reading i
from a different thread while the flood-fill is running, then you might want to use Interlocked
methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i
before this has finished then keep track of it as a 'normal' variable, and then set it as out
at the end (if it is needed at all). out
parameters can be abused, and may interfere with the compilers ability to perform optimisations.
100000
What is this?
if (i > 100000)
break;
This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target
will be 'replaced' (what does that mean?).
Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException
, or return a bool
indicating that it did not complete, or something else.
HashSet
/Stack
You should probably be using a Stack
. HashSet.Contain
is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement)
is always false
, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)
Excepting the first pixel, if you set source[targetIndex] = replacement
when you queue it then you don't need to check if it is already in the HashSet
: you only need to check that source[targetIndex].Equals(target)
, which you have to do anyway. The probably with your non-HashSet
code wasn't the Stack
, it was how you were using it.
With a stack, the code will look mostly the same, only you'll be Pop
ing from the stack (instead of using First()
and Remove(T)
. It should be much faster, because it doesn't lean on HashSet
, which while being 'kind of O(1)
' isn't going to outperform a single array lookup which probably needs to be done anyway.
Indexing
I'm guessing Pn
is static, and looks something like this:
static int Pn(int x, int y, int width => x + y * width;
IEquatable<T>
It's good that you are using this.
Naming
Most of the names are cryptic. This is not ideal. It isn't clear why you use P
rather than Pn
. i
and _i
are completely unrelated (and both poor names). target
and targetIndex
are mostly unrelated.
Code
Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
where T : IEquatable<T>
{
// code can't handle this, so throw
if (target.Equals(replacement))
{
throw new ArgumentException("Target and Replacement cannot equate");
}
// do start manually, and exit quickly if appropriate
int start = P(x, y, width, height);
if (!source[start].Equals(target))
{
explored = 0;
return;
}
// stack is not a great name, but I'm in a hurry right now...
Stack<int> stack = new Stack<int>();
stack.Push(start);
int count = 1;
while (queue.Count > 0)
{
int _i = stack.Pop(),
_x = _i % width,
_y = _i / width;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
// if pixel matched target, reset it and queue
if (source[targetIndex].Equals(target))
{
source[targetIndex] = replacement;
stack.Push(targetIndex);
count++;
}
}
if (i > cutoff)
throw new Exception("FloodFill passed cutoff");
}
// report the number of cells explored
explored = count;
}
Not worth a full answer, but I thought I'd add on that_tx
and_ty
are (besides being cryptically named) not needed. You can instead just ensure thattargetIndex
is non-negative and less thanwidth*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.
– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
IftargetIndex
is non-negative, thentargetIndex%width
will also be non-negative, and so willtargetIndex/width
(providedwidth
is non-negative).targetIndex%width
will never be greater than or equal towidth
. And the only waytargetIndex/width
can be greater than or equal toheight
is iftargetIndex
is greater than or equal towidth*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.
– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing anIndexOutOfRange
; rather, it's to stop it going fromx=0, y=1
tox=width-1, y=0
(wrapping around) when you subtract1
from the index. You are definitely right that_ty
is redundant.
– VisualMelon
yesterday
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
add a comment |
up vote
6
down vote
up vote
6
down vote
Monitor.IsEntered
This call basically makes no sense. Monitor.IsEntered
is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i
: it is a counter. It isn't even a meaningful target for Monitor.IsEntered
because it isn't an object.
There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment
). This may noticeably improve performance, since Monitor.IsEntered
is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).
If, for some reason, you are reading i
from a different thread while the flood-fill is running, then you might want to use Interlocked
methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i
before this has finished then keep track of it as a 'normal' variable, and then set it as out
at the end (if it is needed at all). out
parameters can be abused, and may interfere with the compilers ability to perform optimisations.
100000
What is this?
if (i > 100000)
break;
This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target
will be 'replaced' (what does that mean?).
Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException
, or return a bool
indicating that it did not complete, or something else.
HashSet
/Stack
You should probably be using a Stack
. HashSet.Contain
is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement)
is always false
, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)
Excepting the first pixel, if you set source[targetIndex] = replacement
when you queue it then you don't need to check if it is already in the HashSet
: you only need to check that source[targetIndex].Equals(target)
, which you have to do anyway. The probably with your non-HashSet
code wasn't the Stack
, it was how you were using it.
With a stack, the code will look mostly the same, only you'll be Pop
ing from the stack (instead of using First()
and Remove(T)
. It should be much faster, because it doesn't lean on HashSet
, which while being 'kind of O(1)
' isn't going to outperform a single array lookup which probably needs to be done anyway.
Indexing
I'm guessing Pn
is static, and looks something like this:
static int Pn(int x, int y, int width => x + y * width;
IEquatable<T>
It's good that you are using this.
Naming
Most of the names are cryptic. This is not ideal. It isn't clear why you use P
rather than Pn
. i
and _i
are completely unrelated (and both poor names). target
and targetIndex
are mostly unrelated.
Code
Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
where T : IEquatable<T>
{
// code can't handle this, so throw
if (target.Equals(replacement))
{
throw new ArgumentException("Target and Replacement cannot equate");
}
// do start manually, and exit quickly if appropriate
int start = P(x, y, width, height);
if (!source[start].Equals(target))
{
explored = 0;
return;
}
// stack is not a great name, but I'm in a hurry right now...
Stack<int> stack = new Stack<int>();
stack.Push(start);
int count = 1;
while (queue.Count > 0)
{
int _i = stack.Pop(),
_x = _i % width,
_y = _i / width;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
// if pixel matched target, reset it and queue
if (source[targetIndex].Equals(target))
{
source[targetIndex] = replacement;
stack.Push(targetIndex);
count++;
}
}
if (i > cutoff)
throw new Exception("FloodFill passed cutoff");
}
// report the number of cells explored
explored = count;
}
Monitor.IsEntered
This call basically makes no sense. Monitor.IsEntered
is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i
: it is a counter. It isn't even a meaningful target for Monitor.IsEntered
because it isn't an object.
There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment
). This may noticeably improve performance, since Monitor.IsEntered
is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).
If, for some reason, you are reading i
from a different thread while the flood-fill is running, then you might want to use Interlocked
methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i
before this has finished then keep track of it as a 'normal' variable, and then set it as out
at the end (if it is needed at all). out
parameters can be abused, and may interfere with the compilers ability to perform optimisations.
100000
What is this?
if (i > 100000)
break;
This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target
will be 'replaced' (what does that mean?).
Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException
, or return a bool
indicating that it did not complete, or something else.
HashSet
/Stack
You should probably be using a Stack
. HashSet.Contain
is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement)
is always false
, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)
Excepting the first pixel, if you set source[targetIndex] = replacement
when you queue it then you don't need to check if it is already in the HashSet
: you only need to check that source[targetIndex].Equals(target)
, which you have to do anyway. The probably with your non-HashSet
code wasn't the Stack
, it was how you were using it.
With a stack, the code will look mostly the same, only you'll be Pop
ing from the stack (instead of using First()
and Remove(T)
. It should be much faster, because it doesn't lean on HashSet
, which while being 'kind of O(1)
' isn't going to outperform a single array lookup which probably needs to be done anyway.
Indexing
I'm guessing Pn
is static, and looks something like this:
static int Pn(int x, int y, int width => x + y * width;
IEquatable<T>
It's good that you are using this.
Naming
Most of the names are cryptic. This is not ideal. It isn't clear why you use P
rather than Pn
. i
and _i
are completely unrelated (and both poor names). target
and targetIndex
are mostly unrelated.
Code
Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.
public static void FloodFill<T>(this T source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
where T : IEquatable<T>
{
// code can't handle this, so throw
if (target.Equals(replacement))
{
throw new ArgumentException("Target and Replacement cannot equate");
}
// do start manually, and exit quickly if appropriate
int start = P(x, y, width, height);
if (!source[start].Equals(target))
{
explored = 0;
return;
}
// stack is not a great name, but I'm in a hurry right now...
Stack<int> stack = new Stack<int>();
stack.Push(start);
int count = 1;
while (queue.Count > 0)
{
int _i = stack.Pop(),
_x = _i % width,
_y = _i / width;
for (int offsetX = -1; offsetX < 2; offsetX++)
for (int offsetY = -1; offsetY < 2; offsetY++)
{
// do not check origin or diagonal neighbours
if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
continue;
int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
int _tx = targetIndex % width,
_ty = targetIndex / width;
// skip out of bounds point
if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
continue;
// if pixel matched target, reset it and queue
if (source[targetIndex].Equals(target))
{
source[targetIndex] = replacement;
stack.Push(targetIndex);
count++;
}
}
if (i > cutoff)
throw new Exception("FloodFill passed cutoff");
}
// report the number of cells explored
explored = count;
}
edited 2 days ago
answered 2 days ago
VisualMelon
3,019918
3,019918
Not worth a full answer, but I thought I'd add on that_tx
and_ty
are (besides being cryptically named) not needed. You can instead just ensure thattargetIndex
is non-negative and less thanwidth*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.
– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
IftargetIndex
is non-negative, thentargetIndex%width
will also be non-negative, and so willtargetIndex/width
(providedwidth
is non-negative).targetIndex%width
will never be greater than or equal towidth
. And the only waytargetIndex/width
can be greater than or equal toheight
is iftargetIndex
is greater than or equal towidth*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.
– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing anIndexOutOfRange
; rather, it's to stop it going fromx=0, y=1
tox=width-1, y=0
(wrapping around) when you subtract1
from the index. You are definitely right that_ty
is redundant.
– VisualMelon
yesterday
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
add a comment |
Not worth a full answer, but I thought I'd add on that_tx
and_ty
are (besides being cryptically named) not needed. You can instead just ensure thattargetIndex
is non-negative and less thanwidth*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.
– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
IftargetIndex
is non-negative, thentargetIndex%width
will also be non-negative, and so willtargetIndex/width
(providedwidth
is non-negative).targetIndex%width
will never be greater than or equal towidth
. And the only waytargetIndex/width
can be greater than or equal toheight
is iftargetIndex
is greater than or equal towidth*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.
– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing anIndexOutOfRange
; rather, it's to stop it going fromx=0, y=1
tox=width-1, y=0
(wrapping around) when you subtract1
from the index. You are definitely right that_ty
is redundant.
– VisualMelon
yesterday
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
Not worth a full answer, but I thought I'd add on that
_tx
and _ty
are (besides being cryptically named) not needed. You can instead just ensure that targetIndex
is non-negative and less than width*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.– benj2240
yesterday
Not worth a full answer, but I thought I'd add on that
_tx
and _ty
are (besides being cryptically named) not needed. You can instead just ensure that targetIndex
is non-negative and less than width*height
. You could even precalculate the maximum target index outside of the loop, since it will not change.– benj2240
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
@benj2240 they are necessary: it's checking bounds for a 2D grid (i.e. disallow wrap-around).
– VisualMelon
yesterday
If
targetIndex
is non-negative, then targetIndex%width
will also be non-negative, and so will targetIndex/width
(provided width
is non-negative). targetIndex%width
will never be greater than or equal to width
. And the only way targetIndex/width
can be greater than or equal to height
is if targetIndex
is greater than or equal to width*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.– benj2240
yesterday
If
targetIndex
is non-negative, then targetIndex%width
will also be non-negative, and so will targetIndex/width
(provided width
is non-negative). targetIndex%width
will never be greater than or equal to width
. And the only way targetIndex/width
can be greater than or equal to height
is if targetIndex
is greater than or equal to width*height
. This isn't super wasteful code, mind you. But doing the algebra at design time is more efficient than doing it at run time.– benj2240
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing an
IndexOutOfRange
; rather, it's to stop it going from x=0, y=1
to x=width-1, y=0
(wrapping around) when you subtract 1
from the index. You are definitely right that _ty
is redundant.– VisualMelon
yesterday
@benj2240 maybe I'm missing something, but the idea isn't to stop it throwing an
IndexOutOfRange
; rather, it's to stop it going from x=0, y=1
to x=width-1, y=0
(wrapping around) when you subtract 1
from the index. You are definitely right that _ty
is redundant.– VisualMelon
yesterday
1
1
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
@benj2240 err... only now that I look at the OP code again, it is clearly broken, and fails to perform this task (please do write an answer to that effect)
– VisualMelon
yesterday
add a comment |
up vote
3
down vote
All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.
VisualMelon has commented some details so I won't go further into that.
When determine the area for a floodfill all you need are:
1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)
2) The width of each row (count of columns)
3) The starting point inside the area to flood
4) The target value
5) The replacement value
So the signature of the method could be something like this:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
The height (number of rows) is redundant and can easily be calculated.
You should maybe make a check of the dimension:
if (source.Length % width != 0) throw new Exception("source has wrong size");
Finding the neighbors is as simple as:
North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;
A solution could then be as follow:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
if (source == null || source.Length == 0 || target.Equals(replacement))
return;
int length = source.Length;
Queue<int> queue = new Queue<int>();
int current = startY * width + startX;
if (!source[current].Equals(target))
return;
// If no target value was found the return
if (current >= length) return;
// A target value was found at index current so enqueue that
queue.Enqueue(current);
// Local function that enqueue an index if it is within
// the boundaries of the source and the value equals the target value.
void Enqueue(int index)
{
if (index >= 0 && index < length && source[index].Equals(target))
{
source[index] = replacement;
queue.Enqueue(index);
}
}
while (queue.Count > 0)
{
current = queue.Dequeue();
// North
int neighbor = current - width;
Enqueue(neighbor);
// South
neighbor = current + width;
Enqueue(neighbor);
// East: The current index as a column index must be lesser
// than the width - 1 or else going east will
// roundtrip to the next row
if (current % width < width - 1)
{
neighbor = current + 1;
Enqueue(neighbor);
// North-East and South-East are easily found in the same way as North and South
// NE
Enqueue(neighbor - width);
// SE
Enqueue(neighbor + width);
}
// West: This is analogue to East: current as a column index must be greater than 0
// or else going west will roundtrip to the previous row.
if (current % width > 0)
{
neighbor = current - 1;
Enqueue(neighbor);
// Completely analogue to NE an SE
// NW
Enqueue(neighbor - width);
// SW
Enqueue(neighbor + width);
}
}
}
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).
– VisualMelon
yesterday
add a comment |
up vote
3
down vote
All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.
VisualMelon has commented some details so I won't go further into that.
When determine the area for a floodfill all you need are:
1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)
2) The width of each row (count of columns)
3) The starting point inside the area to flood
4) The target value
5) The replacement value
So the signature of the method could be something like this:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
The height (number of rows) is redundant and can easily be calculated.
You should maybe make a check of the dimension:
if (source.Length % width != 0) throw new Exception("source has wrong size");
Finding the neighbors is as simple as:
North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;
A solution could then be as follow:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
if (source == null || source.Length == 0 || target.Equals(replacement))
return;
int length = source.Length;
Queue<int> queue = new Queue<int>();
int current = startY * width + startX;
if (!source[current].Equals(target))
return;
// If no target value was found the return
if (current >= length) return;
// A target value was found at index current so enqueue that
queue.Enqueue(current);
// Local function that enqueue an index if it is within
// the boundaries of the source and the value equals the target value.
void Enqueue(int index)
{
if (index >= 0 && index < length && source[index].Equals(target))
{
source[index] = replacement;
queue.Enqueue(index);
}
}
while (queue.Count > 0)
{
current = queue.Dequeue();
// North
int neighbor = current - width;
Enqueue(neighbor);
// South
neighbor = current + width;
Enqueue(neighbor);
// East: The current index as a column index must be lesser
// than the width - 1 or else going east will
// roundtrip to the next row
if (current % width < width - 1)
{
neighbor = current + 1;
Enqueue(neighbor);
// North-East and South-East are easily found in the same way as North and South
// NE
Enqueue(neighbor - width);
// SE
Enqueue(neighbor + width);
}
// West: This is analogue to East: current as a column index must be greater than 0
// or else going west will roundtrip to the previous row.
if (current % width > 0)
{
neighbor = current - 1;
Enqueue(neighbor);
// Completely analogue to NE an SE
// NW
Enqueue(neighbor - width);
// SW
Enqueue(neighbor + width);
}
}
}
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).
– VisualMelon
yesterday
add a comment |
up vote
3
down vote
up vote
3
down vote
All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.
VisualMelon has commented some details so I won't go further into that.
When determine the area for a floodfill all you need are:
1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)
2) The width of each row (count of columns)
3) The starting point inside the area to flood
4) The target value
5) The replacement value
So the signature of the method could be something like this:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
The height (number of rows) is redundant and can easily be calculated.
You should maybe make a check of the dimension:
if (source.Length % width != 0) throw new Exception("source has wrong size");
Finding the neighbors is as simple as:
North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;
A solution could then be as follow:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
if (source == null || source.Length == 0 || target.Equals(replacement))
return;
int length = source.Length;
Queue<int> queue = new Queue<int>();
int current = startY * width + startX;
if (!source[current].Equals(target))
return;
// If no target value was found the return
if (current >= length) return;
// A target value was found at index current so enqueue that
queue.Enqueue(current);
// Local function that enqueue an index if it is within
// the boundaries of the source and the value equals the target value.
void Enqueue(int index)
{
if (index >= 0 && index < length && source[index].Equals(target))
{
source[index] = replacement;
queue.Enqueue(index);
}
}
while (queue.Count > 0)
{
current = queue.Dequeue();
// North
int neighbor = current - width;
Enqueue(neighbor);
// South
neighbor = current + width;
Enqueue(neighbor);
// East: The current index as a column index must be lesser
// than the width - 1 or else going east will
// roundtrip to the next row
if (current % width < width - 1)
{
neighbor = current + 1;
Enqueue(neighbor);
// North-East and South-East are easily found in the same way as North and South
// NE
Enqueue(neighbor - width);
// SE
Enqueue(neighbor + width);
}
// West: This is analogue to East: current as a column index must be greater than 0
// or else going west will roundtrip to the previous row.
if (current % width > 0)
{
neighbor = current - 1;
Enqueue(neighbor);
// Completely analogue to NE an SE
// NW
Enqueue(neighbor - width);
// SW
Enqueue(neighbor + width);
}
}
}
All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.
VisualMelon has commented some details so I won't go further into that.
When determine the area for a floodfill all you need are:
1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)
2) The width of each row (count of columns)
3) The starting point inside the area to flood
4) The target value
5) The replacement value
So the signature of the method could be something like this:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
The height (number of rows) is redundant and can easily be calculated.
You should maybe make a check of the dimension:
if (source.Length % width != 0) throw new Exception("source has wrong size");
Finding the neighbors is as simple as:
North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;
A solution could then be as follow:
public static void FloodFill<T>(this T source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
if (source == null || source.Length == 0 || target.Equals(replacement))
return;
int length = source.Length;
Queue<int> queue = new Queue<int>();
int current = startY * width + startX;
if (!source[current].Equals(target))
return;
// If no target value was found the return
if (current >= length) return;
// A target value was found at index current so enqueue that
queue.Enqueue(current);
// Local function that enqueue an index if it is within
// the boundaries of the source and the value equals the target value.
void Enqueue(int index)
{
if (index >= 0 && index < length && source[index].Equals(target))
{
source[index] = replacement;
queue.Enqueue(index);
}
}
while (queue.Count > 0)
{
current = queue.Dequeue();
// North
int neighbor = current - width;
Enqueue(neighbor);
// South
neighbor = current + width;
Enqueue(neighbor);
// East: The current index as a column index must be lesser
// than the width - 1 or else going east will
// roundtrip to the next row
if (current % width < width - 1)
{
neighbor = current + 1;
Enqueue(neighbor);
// North-East and South-East are easily found in the same way as North and South
// NE
Enqueue(neighbor - width);
// SE
Enqueue(neighbor + width);
}
// West: This is analogue to East: current as a column index must be greater than 0
// or else going west will roundtrip to the previous row.
if (current % width > 0)
{
neighbor = current - 1;
Enqueue(neighbor);
// Completely analogue to NE an SE
// NW
Enqueue(neighbor - width);
// SW
Enqueue(neighbor + width);
}
}
}
edited yesterday
answered yesterday
Henrik Hansen
5,9481722
5,9481722
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).
– VisualMelon
yesterday
add a comment |
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).
– VisualMelon
yesterday
1
1
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).
Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).– VisualMelon
yesterday
The flood-fill does need to start from somewhere; I think this ought still to be a parameter (rather than a linear scan: there could be multiple starts which need different replacements). Also, perhaps you added them intentionally, but the OP explicitly wants 4-way connectivity (excludes NE/SE/etc.).
Enqueue
as a local function is a grear idea (I didn't mention it because it could well be slower than even the inefficient loop in the OP, but I'm glad someone else has said it).– VisualMelon
yesterday
add a comment |
z3nth10n is a new contributor. Be nice, and check out our Code of Conduct.
z3nth10n is a new contributor. Be nice, and check out our Code of Conduct.
z3nth10n is a new contributor. Be nice, and check out our Code of Conduct.
z3nth10n is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207678%2foptimizing-floodfill-algorithm-implementation-as-much-as-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
What is P in queue.Add(P(x, y, width, height)), and Pn later?
– Errorsatz
2 days ago
Are you reading
i
from a different thread for some reason? (e.g. to show a progress bar?)– VisualMelon
2 days ago
1
Could you take the description from your SO question and add it here? It's offtopic there so I think it won't stay there forever and when this happens noone will be able to decipher this one ;-)
– t3chb0t
yesterday