I have a need for a special collection which doesn't seem to fit perfectly in any of the existing ones. I'm wondering if I have overlooked something in the documentation, or if someone has a good idea on how to code what I'm trying to do. Here's the situation:

Suppose we have a boolean array of about 500x500, representing a black and white image. In a loop, we will pick a point at random, then draw a shape around that point and fill it in. We will continue to do this until the image is almost completely filled with shapes, but we don't want the shapes to overlap. So, when we make subsequent random picks, we throw them out if they happen to be in the area where the image is already filled.

When the image is very nearly filled, then finding an unfilled point by a random method will become difficult, and we will be rejecting most of our picks.

I would like to find a way to put an additional structure on the image which I can use to guarantee that my random picks will only be drawn from the unfilled pixels. Although there are a number of ways to do this, most of them that I can imagine do require some amount of searching and sorting that puts the performance below an acceptable level.

Here's one idea. Define a coordinate class that is Comparable, sorting by a random key assigned at instantiation, and build up a TreeSet. Then to make a pick, take the first element in the tree and remove it. The problem with this method is that if I want to remove a subset all at once, then its going to take a lot of searching. In particular, although removing all the points in one of the filled shapes would be fast with an array, since the shapes are usually connected and gathered together in a usually small area, with the TreeSet it would take log(n) because we have no idea where the points are in the tree set.

I'm not really following the point of your last paragraph. You talk about the problems with this method, but I didn't catch what the benefits would have been. What's the point of the TreeSet here? Can't really comment more on that idea without better understanding.

What sorts of shapes are you drawing around these points, anyway? Circles or squares might lead to some simplified algorithms. Are they more complex than that? Do they have different sizes? Random orientations? Do you also choose the shapes randomly, or are there certain shapes that have to be there?

One possibility that occurs to me is that it might be worthwhile to build an int[][] where the value at any point is the distance from that point to the nearest already-placed shape. Call this value the free distance at that point, and the int[][] is a map of free space. For simplicity it may be best to measure free space using taxicab distance here, abs(x + y), rather than pythagorean distance, sqrt(x^2 + y^2). Every time you place a new shape, you update the free space map using the distances from your newly-placed shape. The first time you place a shape, you need to update the entire map with new distances. But with each subsequent shape it gets easier, as you only need to update the areas of the map that are closest to your new shape. You can start at the new shape and work your way outward. Whenever you find an already-exiting free space value which is <= the distance from your new shape, you can stop updating in that particular direction, because some other shape is closer. The more shapes you get, the quicker the free space updates will become.

So what's the use of this free space map? It's to speed up the process of finding new sites for shapes. To place a given shape, determine the minimum free space required for that shape. This is like the minimum radius of that shape, except "radius" may be calculated with taxicab distance. It may also be useful to find the maximum required free space for the shape. Then, pick a point at random. Look up the free space at that point. If it's less than the minimum required, abandon this point and try a new one. If it's greater than the maximum required, place the shape immediately, update the free space map, and move on to place a new shape. If the free space is between the min and max, then you probably have to perform a more complex analysis to determine if the shape can fit at this point - this will depend on the details of the shape and its surroundings. If it fits, place it; if not, go back and pick a new random point. You'll still have some wasted time here trying things that turn out to not fit, but it should be much less wasted time than you would have had without the free space map.

At some point, as the map becomes more and more crowded, change strategies. For each new shape to place, scan the map and make a list of all the points on the map with free space >= the minimum required free space for the current shape. Once the list is complete, pick one point at random, and see if you can get a fit. Keep picking from the list until you find a fit. If you go through the entire list, then a fit is impossible for that shape. Move on to another shape. Once you've tried all the shapes, you're done.

A variation on this may be to presort your possible shapes by size. Then you pick a point, and find the biggest shape that can fit at that point. And keep repeating until the smallest shape you have is larger than the smallest free space on the map.

There's still a lot of complexity to work through here, and there may well be a more elegant solution out there somewhere. But that's my best idea so far. Hope it helps...

"I'm not back." - Bill Harding, Twister

Christopher Arthur
Ranch Hand

Joined: Mar 09, 2004
Posts: 149

posted

0

Hi,

The free space idea is interesting, I'm going to think about that a little bit. I hadn't thought of trying to describe the negative space.

The shapes are determined by flow streams in a vector field, so it is hard to know a priori how they will look, except that mostly they are long thin strips that may twist about in all kinds of ways. All we know about the vector field is that it is zero-divergence everywhere.

At the moment I've opted for an easy solution, which is keep picking points stupidly at random, but counting the number of picks that fail to hit free space. When the percent of failure reaches a set level, then just quit and say that's good enough.

As it turns out, though, the rest of the routine has turned out to be much faster than I had imagined it would, so I have some clock cycles to experiment.

Oh, as for the TreeSet, the idea was to use it to contain a list of all the pixels in a shuffled order. I would then make random picks by pulling from the top of the tree and removing that element. When I put a shape around that point, I would have to remove all of its pixels from the TreeSet, too, so that the next pick would guarantee to miss any shapes. [ September 16, 2006: Message edited by: Christopher Arthur ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

[Christopher]: The shapes are determined by flow streams in a vector field, so it is hard to know a priori how they will look, except that mostly they are long thin strips that may twist about in all kinds of ways. All we know about the vector field is that it is zero-divergence everywhere.

Interesting. From that description I'm thinking that my free space map idea may not be much use - it was conceived with more compact objects in mind. For long twisty things, I think the difference between minimum and maximum "diameter" will usually be large enough that you'll have to do more careful checking anyway. Ah well.

So now I'm curious what sort of application has you randomly placing a bunch of zero-divergence vector fields. Or are the shapes actually "containers" for the fields, e.g. pipes or waveguides of some sort? Even so, I'm having a hard time imagining why they'd be placed randomly somewhere.

As for the TreeSet idea, hm. What's the point of randomly shuffling them and then putting them in a sorted set? Anyway I would think that for each new position/shape you need to try, you still need to check all those points individually to see if they're available or not. I'm not seeing why a TreeSet would make that any easier than just checking elements in your original bitmap/boolean array. Though to be fair, it sounds like you may not need this after all, so feel free to skip these questions if you want. I'm more interested in finding out what your application is for, at this point.

You create a second bit map that matches the first, only this array (matix if you like) has bits 0 for not mapped and 1 for mapped - the random number runs down the number of 0 bits of this array to find the next mapped object - now take this one step further, start at the beginning, come up with a random number of items, fill those in, generate a second group.

Another way to handle this would be to create a neural net front end, to find the next open area.