CSC 413/513 - Algorithms

3D Blob Program

You are to write and submit a program named "blob3d.c" that will use the disjoint set union/find operations with path compression and the weighted union heuristic to find "blobs" in 3D images. Your 3D image will be formed by running the simulation software in ~seyfarth/particles/particle_system.cpp. This software simulates motion of randomly placed particles in a cube. There are A particles (1) and B particles (2) which have opposite charges. The A's should clump together over time as should the B's. Your program will compute some simple statistics on the image.

       blob [dim] [frames] [particles]

Your program should accept the dimension of the cube from the command line defaulting to 20. It also should accept a number of frames (steps in the simulation) which should default to 100. Finally it should accept a number of particles (A+B) which should default to 1000. Then your program should execute the simulation similar to the execution of ~seyfarth/particles/mk_movie.cpp to prepare the 3D array to analyze.

Your program should use the disjoint set union/find algorithms to determine the contiguous blobs of 1's in the image. It also should determine the contiguous blobs of 2's. A pair of pixels are judged to be contiguous if they have equal coordinates in 2 dimensions and differ by 1 (mod dim) in the third. This means each pixel has 6 nearest neighbors.

Your program should report the number of blobs, the average number of pixels per blob, and the number of pixels in the largest blob for both 1's and 2's. The report should be printed on stdout.