2D logical array, find closest element with value false

E

Edward Jensen

Hi.

I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false. By
closest I mean in terms of a metric where each step to the left, right, up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently? And by the way... Does this metric have a name?

Thanks in advance!
 
K

Keith Thompson

Edward Jensen said:
I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false. By
closest I mean in terms of a metric where each step to the left, right, up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently? And by the way... Does this metric have a name?

That sounds like more of a general programming question than a C
question, but ...

I doubt that there's any algorithm more efficient than the obvious
one: do a spiral search. First check the 8 elements adjacent to the
starting point, then check the 12 elements at a distance of 2, and so
on. Don't go beyond the boundaries of the array.

If there are better answers, you're more likely to find them in
comp.programming.
 
F

Fred

Hi.

I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false. By
closest I mean in terms of a metric where each step to the left, right, up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently? And by the way... Does this metric have a name?

Thanks in advance!

Do you need:
A) the closest element that is false, or
B) the distance to the closest element that is false?

For (A) therre may be multiple solutions. For example,
there are 3, 5, or 8 elements a distance 1 from a cell,
any or all of of which can be false.
There are 5, 6, 7, 11, or 16 elements a distance 2
from a cell.

B) has either zero or one solution.
 
F

Flash Gordon

Edward said:
Hi.

I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false. By
closest I mean in terms of a metric where each step to the left, right, up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently?

The most efficient method will depend how far away the false is likely
to be, (available) cache size compared to how far you are likely to need
to travel, speed of cache-fills, speed of bit-twidling operations (by
using one bit per value you can minimise memory access and potentially
do clever stuff with bit-twiddling to find the 0 (if there is one) in a
word etc. However, changing the encoding of your array might impact on
the performance of other parts of your program.
And by the way... Does this metric have a name?

Distance? ;-)
 
J

jameskuyper

Edward said:
Hi.

I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false. By
closest I mean in terms of a metric where each step to the left, right, up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently? And by the way... Does this metric have a name?

I first heard of this metric under the name "the maximum metric",
because it can be written as d = max(|delta x|, }delta y|). However,
a wikipedia search for "maximum metric" redirected me to "Chebyshev
distance", also know as the "L-inifinity" metric.
 
K

Keith Thompson

Keith Thompson said:
That sounds like more of a general programming question than a C
question, but ...

I doubt that there's any algorithm more efficient than the obvious
one: do a spiral search. First check the 8 elements adjacent to the
starting point, then check the 12 elements at a distance of 2, and so
on. Don't go beyond the boundaries of the array.

Correction, there are (at most) 16 elements at a distaince of 2.
 
B

BartC

Edward Jensen said:
Hi.

I have a rather large 2D array with boolean values. If I look at a certain
element and it's true, I need to find the closest element with is false.
By
closest I mean in terms of a metric where each step to the left, right,
up,
down, left-up-diagonal, right-up-diagonal, left-down-diagonal and
right-down-digonal has a length of one. Any ideas on how to do this
efficiently? And by the way... Does this metric have a name?

What sort of size are we talking about, and how efficient do you need it?
Ie. how often does this search have to be done, and how sparse are these
false elements?

How many bits are you using to store each element? Probably one char per
element is simplest but the data looks like a 2-level image which is
normally stored using one bit per element.

This would make things more fiddly but could reduce memory accesses if you
can look at 32 or 64-bits at a time (and 64-bits can encode an 8x8 block of
elements; any block that is not 0xFFFFFFFFFFFFFFFF has a false element in
there somewhere).

Do the contents of the array change frequently? If not, perhaps the array
can be subdivided into a grid of MxN blocks and a map can be created to
store the status (whether it contains a false element) of each block, to
quickly check whether a region has a false in it. However if false values
occur frequently then this might not help.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top