| Domains | Work & Research | Community | Personal | Controls |
|---|---|---|---|---|
| jeneratiff.com | Professional | Sources | Publications | Private |
| dritsas.net | Academic | Articles | Resume | Login |
Voronoi Diagrams
Working with QHull
Qhull is an open source software for calculating convex hulls, delaunay triangulations, voronoi diagrams etc.
http://www.qhull.org/
Qhull works in the dos console. Here is an example that shows the parameters needed for producing the vertex table and face table used in the following Rhino script.
Next thing you may need is to create a custom point coordinate file and pass it to qhull. The format of input files is extremely simple: You need a text file, the first line of being 3 (as three dimensions). The next line should be the number of points listed below (5 in this example). Finally you need to list the point coordinates each vertex per line, each coordinate separated by a space character.
input.txt
3 5 1 0 0 0 1 0 0 0 1 2 4 6 7 3 1
The command line for passing the file to qvoronoi is “type input.txt | qvoronoi o Fv“. The “type” dos command just prints out the contents of a file. The pipe symbol “|” passes the information to qvoronoi. If you need to save the result of the command to a text file you may use this command instead “type input.txt | qvoronoi o Fv > output.txt“. Where input.txt is your point coordinate file and output.txt is something that looks like this:
output.txt
3 4 5 1 -10.101 -10.101 -10.101 2.989795918367347 2.989795918367347 2.091836734693878 2.5 2.5 2.5 4.785714285714286 -1.5 4.785714285714286 4 0 1 2 3 3 0 1 2 3 0 2 3 4 0 1 2 3 3 0 1 3 7 5 0 2 0 2 3 5 0 4 0 1 3 5 0 1 0 1 2 5 0 3 1 2 3 5 1 3 0 1 2 5 2 3 0 2 3 5 3 4 0 1 3
Don’t be afraid of this weird file format because the Rhino-script below will properly parse it and draw the voronoi diagram in Rhino. Just for the record: The first line “3” means three dimensions. The second reports that the voronoi diagram has four point and five regions. The next four lines are the points with the first point ←10.101, -10.101, -10.101> being an alias for points in the infinity. Next follow the five lines of the regions. Finally the last lines report the voronoi faces. The first line reports that there are seven faces. Each of the rest of the text denote a single face.
QHull to Rhino
0001 '' 0002 '' QVoronoi Import Dcript 0003 '' Copyright (C) 2006 Stylianos Dritsas 0004 '' 0005 '' License: 0006 '' http://creativecommons.org/licenses/by/2.5/ 0007 '' 0008 '' Acknowledgments: 0009 '' Andrew Kudless 0010 '' Thomas Tong 0011 '' 0012 0013 '' debug verbose flag 0014 DEBUG_MODE = true 0015 0016 '' import file! 0017 call import_qvoronoi( ) 0018 0019 '' 0020 '' qvoronoi import function 0021 '' 0022 function import_qvoronoi( ) 0023 0024 ''----------------------------------------------------------------------- 0025 '' begin file input 0026 ''----------------------------------------------------------------------- 0027 0028 '' request qvoronoi outputfile 0029 filename = rhino.openfilename( "Open", "QHull Files (*.*)|*.*||" ) 0030 if( isnull( filename ) ) then exit function 0031 0032 '' try opening the file 0033 set filesystem = createobject( "Scripting.FileSystemObject" ) 0034 if( not filesystem.fileexists( filename ) ) then exit function 0035 set textstream = filesystem.opentextfile( filename ) 0036 0037 ''----------------------------------------------------------------------- 0038 '' begin file reading 0039 ''----------------------------------------------------------------------- 0040 0041 '' skip first line (3 dimensions etc) 0042 call textstream.skipline( ) 0043 0044 '' read header info 0045 header = parse( textstream.readline( ) ) 0046 0047 '' decode header information 0048 vcount = header( 0 ) 0049 rcount = header( 1 ) 0050 0051 ''----------------------------------------------------------------------- 0052 '' read vertex table 0053 ''----------------------------------------------------------------------- 0054 0055 '' allocate vertices 0056 redim vertices( vcount - 1 ) 0057 0058 '' read vertices 0059 for index = lbound( vertices ) to ubound( vertices ) 0060 0061 vertices( index ) = parse( textstream.readline( ) ) 0062 0063 if( DEBUG_MODE ) then 0064 'call rhino.addtextdot( cstr( index ), vertices( index ) ) 0065 end if 0066 0067 next 0068 0069 ''----------------------------------------------------------------------- 0070 '' read regions table 0071 ''----------------------------------------------------------------------- 0072 0073 '' allocate regions 0074 redim regions( rcount - 1 ) 0075 0076 '' read regions 0077 for index = lbound( regions ) to ubound( regions ) 0078 0079 regions( index ) = butfirst( parse( textstream.readline( ) ) ) 0080 0081 if( DEBUG_MODE ) then 0082 'call plot( vertices, regions( index ) ) 0083 end if 0084 0085 next 0086 0087 ''----------------------------------------------------------------------- 0088 '' read facet table 0089 ''----------------------------------------------------------------------- 0090 0091 fcount = eval( textstream.readline( ) ) 0092 0093 redim faces( fcount - 1 ) 0094 redim polys( fcount - 1 ) 0095 0096 for index = lbound( faces ) to ubound( faces ) 0097 0098 '' parse face 0099 face = parse( textstream.readline( ) ) 0100 0101 '' skip size and first couple of indices 0102 faces( index ) = butfirst( butfirst( butfirst( face ) ) ) 0103 0104 if( DEBUG_MODE ) then 0105 polys( index ) = plot( vertices, faces( index ) ) 0106 end if 0107 0108 next 0109 0110 call rhino.addplanarsrf( polys ) 0111 call rhino.deleteobjects( polys ) 0112 0113 ''----------------------------------------------------------------------- 0114 '' clean up 0115 ''----------------------------------------------------------------------- 0116 0117 '' done! 0118 call textstream.close( ) 0119 0120 end function 0121 0122 '' 0123 '' plot index / vertex entry 0124 '' 0125 function plot( vertices, region ) 0126 0127 '' allocate polyline vertex buffer 0128 redim polyline( ubound( region ) + 1 ) 0129 0130 '' dereference pointers 0131 for index = lbound( region ) to ubound( region ) 0132 0133 pointer = abs( region( index ) ) 0134 0135 polyline( index ) = vertices( pointer ) 0136 0137 next 0138 0139 polyline( ubound( region ) + 1 ) = polyline( 0 ) 0140 0141 '' done! 0142 plot = rhino.addpolyline( polyline ) 0143 0144 end function 0145 0146 '' 0147 '' parse array of numbers 0148 '' 0149 function parse( text ) 0150 0151 '' tokenize the fields 0152 result = rhino.strtok( text ) 0153 0154 '' convert strings to numbers 0155 for index = lbound( result ) to ubound( result ) 0156 0157 result( index ) = eval( result( index ) ) 0158 0159 next 0160 0161 '' done! 0162 parse = result 0163 0164 end function 0165 0166 '' 0167 '' skip first element of array 0168 '' 0169 function butfirst( aggregate ) 0170 0171 '' number of elements in arr 0172 count = ubound( aggregate ) - lbound( aggregate ) + 1 0173 0174 '' resize to one less elements 0175 count = count - 1 0176 0177 '' allocate pure dynamic array 0178 result = array( 0 ) 0179 0180 '' allocate result buffer 0181 redim result( count - 1 ) 0182 0183 '' copy all but first 0184 for index = lbound( result ) to ubound( result ) 0185 0186 result( index ) = aggregate( index + 1 ) 0187 0188 next 0189 0190 '' done! 0191 butfirst = result 0192 0193 end function