Announce: 3D connected components program

[Wm. Randolph Franklin]

This is to announce my latest program, CONNECT, which finds the
connected components in a 3-D rectangular volume of binary voxels
(the universe). For each component, CONNECT writes its volume,
surface area, and voxels (grouped into runs). CONNECT can do both
6-connectivity and 26-connectivity.

CONNECT is very space- and time-efficient. E.g., processing one
test volume of size 544x544x512, which has 151,519,232 voxels,
about 1/2 empty, to find the 534,723 6-connected components, takes
only 50 seconds of CPU and 45MB of virtual memory on a 233MHz
Pentium with Linux and g++.

The time for any particular case depends on the data complexity,
e.g., number of input runs and output components.   The worst
6-connectivity case would be to have alternating voxels full and
empty.

CONNECT could easily be extended to 4D volumes, if there was an
application.  It does 2D areas as a trivial subcase.  A
1x1024x1024 input is processed in under 1 second, with setup
overhead being most of that time.

I predict that CONNECT could process a 1024x1024x1024 universe in
10 CPU minutes, depending its complexity, tho the virtual memory
might page badly.  Does anyone have any real test data?

My confidence in CONNECT's correctness is based upon rotating the
large test case around the grand diagonal, rerunning CONNECT, and
sorting and comparing the output statistics of the components'
volumes and areas.  The results are identical.

I am the author of CONNECT.  You may use it for non-profit
research and education. You must make appropriate
acknowledgements.

For more info, including detailed usage and algorithm
descriptions, and a source tarball, go to

	      http://www.ecse.rpi.edu/Homepages/wrf/research/connect/

Comments are welcome.

------------------------
		      Wm. Randolph Franklin
                       Associate Professor
		     rfranklin at altavista.net
	      http://www.ecse.rpi.edu/Homepages/wrf/
		  +1 (518) 276-6077;  Fax: -6261
ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180 USA
			 (PGP key available)




-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.