Author |
Topic: Connected area generating algorithm (Read 536 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Connected area generating algorithm
« on: Mar 1st, 2008, 8:10am » |
 Quote  Modify
|
I am working on an algorithm that requires working on a connected random area. The area is composed of rectangular pixels located in a given matrix.
For example, the matrix may be 10X10 pixels, and the area to find will be 25 connected pixel, in an arbitrary shape. Later, I will larger numbers (say, 100 pixels in a 50X50 matrix).
The first chalange is creating this random area (that the algorithm I'm working on will accept as an input). I thought of the following algorithm for this problem:
Select a random first pixel
N=1
LOOP UNTIL N=AREA_SIZE
mark_neighbors_in_matrix
select a neighbor randomly
N=N+1
CLOSE LOOP
The problem I see, this algorithm may take quite a while to run, especially in larger matices. The neighbor finding procedure itslef will probably have to scan the whole matrix, and do for each area cell.
Any ideas for a more efficient algorithm?
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Connected area generating algorithm
« Reply #1 on: Mar 1st, 2008, 8:30am » |
Quote Modify
|
I don't see why the neighbor-finder would need to scan the entire matrix. It only needs to scan the 4 or 8 neighbors of each point (less for edge pixels, of course). There is a problem of what to do when every neighboring pixel is already in the area, but then you can just choose a direction and head that way until you reach an edge.
However, if you follow your procedure, your random area is going to look like a crooked loopy string.
Another approach is to keep track of two groups: boundary and interior points. In each iteration you choose a boundary point, then choose a neighbor not already included. Then you examine the neighbors of the new point, and if any of them has become an interior point. This should produce sets with a fractal look.
You can make your sets more blob-like by increasing the likely-hood of a boundary point being chosen by the number of its neighbors that have already been chosen.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Connected area generating algorithm
« Reply #2 on: Mar 2nd, 2008, 7:12am » |
Quote Modify
|
Why do you say it will be a "crooked loopy string" (CLS) shape? I agree it would be shapeless -- but that's OK. CLS, on the other hand, will be a trivial case for the algorithm I thinking of.
I like your idea about the increased likelyhood of many-neighbors boundry points. It may even be as simple as searching all boundry points, and adding all neighbors. A neighbor of many boundry points will appear multiple times, thus will have increased probability! Nice...
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Connected area generating algorithm
« Reply #3 on: Mar 2nd, 2008, 12:15pm » |
Quote Modify
|
Because by adding the next pixel to the last, you are moving in linear fashion. The shape of your resultant area should reflect this to some extent.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Connected area generating algorithm
« Reply #4 on: Mar 2nd, 2008, 1:28pm » |
Quote Modify
|
My instinct would be to read the original post's neighbours as neighbours of the existing area rather than of the last point selected - I've no idea whether that was the intended meaning, but it does produce an algorithm that neatly avoids the potential problem of the last cell having no previously unselected neighbours...
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Connected area generating algorithm
« Reply #5 on: Mar 2nd, 2008, 2:22pm » |
Quote Modify
|
Yes, indeed, that was my intent. It could, though, produce "spaghetti-like" area... and I think Icarus's idea of increasing the likelihood of selecting a cell according to the number of area neighbors it has would overcome this.
I'm open to more clever suggestions...
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Connected area generating algorithm
« Reply #6 on: Mar 2nd, 2008, 2:45pm » |
Quote Modify
|
I see I was mis-interpreting the algorithm entirely. Rather than searching the entire matrix for each n to determine the boundaries, I would just keep track of all boundary points in a hash. Each time you add a point, you go through the neighbors of the added point and determine: if the neighbor was a boundary point, is it still? The best way to track this may be to keep a count of how many of its own neighbors are chosen. When the count reaches 4 or 8, depending on your definition of "neighbor", it becomes an interior point, so remove it from your hash.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Connected area generating algorithm
« Reply #7 on: Mar 3rd, 2008, 1:11am » |
Quote Modify
|
Do you want an area without holes in it, or doesn't that matter?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Connected area generating algorithm
« Reply #8 on: Mar 3rd, 2008, 1:40am » |
Quote Modify
|
on Mar 3rd, 2008, 1:11am, towr wrote:| Do you want an area without holes in it, or doesn't that matter? |
|
I will need both. The algorithm is a variant of the set covering problem, applied to covering of a "geographical" area with "cells" of different shapes. Holes in that case may represent unpopulated regions.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print