wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Connected area generating algorithm
        
(Message started by: BNC on Mar 1^st, 2008, 8:10am)

Title: Connected area generating algorithm
Post by BNC on Mar 1^st, 2008, 8:10am

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?

Title: Re: Connected area generating algorithm
Post by Icarus on Mar 1^st, 2008, 8:30am

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.

Title: Re: Connected area generating algorithm
Post by BNC on Mar 2^nd, 2008, 7:12am

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...

Title: Re: Connected area generating algorithm
Post by Icarus on Mar 2^nd, 2008, 12:15pm

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.

Title: Re: Connected area generating algorithm
Post by rmsgrey on Mar 2^nd, 2008, 1:28pm

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...

Title: Re: Connected area generating algorithm
Post by BNC on Mar 2^nd, 2008, 2:22pm

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...

Title: Re: Connected area generating algorithm
Post by Icarus on Mar 2^nd, 2008, 2:45pm

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.

Title: Re: Connected area generating algorithm
Post by towr on Mar 3^rd, 2008, 1:11am

Do you want an area without holes in it, or doesn't that matter?

Title: Re: Connected area generating algorithm
Post by BNC on Mar 3^rd, 2008, 1:40am

on 03/03/08 at 01:11:32, 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.