Region Sets From Boundaries

Question

I have an elevation map represented by a 2D array of floats.

There are regions of this map whose edges I have contained in a single vector which contains a list of the edge cells (identified by their x and y coordinates).

The edge cells are not aware of which region they are associated with, nor are edge cells which are contiguous within the vector necessarily adjacent to each other in the map.

I would like to be able to uniquely identify each region based on this information (the list of edge cells for the whole map, which again, may not be adjacent).

I have thought about trying to start at one edge cell and traverse the edge, but then the enclosed space may contain regions which should be excluded (a lake around an island which itself contains a lake). I've considered using some kind of bucket fill, but this would disrupt the valuable elevation data and I don't want to create a second array to store the information.

Any thoughts on an efficient way to go about it?

Answer 1

Richard,

This is a classical connected components labeling problem, isn't it ?

There are indeed several solutions when you are allowed to store a 'state' map, i.e. an auxiliary image where pixels can be assigned discrete values. Among these methods, you can indeed paint the edge pixels, then flood fill the enclosed regions. In this case, a single bit per pixel is enough.

If you don't want to afford extra storage for this bit, you can probably "steal" it from the floating point values. For instance if all elevations are positive, you can embezzle the sign bit for this purpose (and reset it afterwards); easily done in C by mapping a bitfield over the float.