VMD-L Mailing List

From: Andrew Dalke (dalke_at_bioreason.com)
Date: Mon Sep 28 1998 - 17:31:10 CDT

Hello,

  I was searching the web and came across a program that computes
the convex hull of a set of points. This by Ken Clarkson at Bell
Labs, is called "hull" and is at
    http://cm.bell-labs.com/netlib/voronoi/hull.html .

A convex hull is the smallex convex shape that contains the set
of points you give it. Mostly for fun, I wrote a little interface
to it for VMD; you give it a selection and it draws the triangulated
hull. I don't think it is important for molecular systems, but
since "hull" also computes the Delauny triangulation and the
alpha shape, I figured some here might be interested in that aspect
of it.

  To use the VMD script, first compile hull and change the line
> set hull "/usr/people/dalke/ftps/hull/hull"
to where ever you installed it. To see the convex hull of, for
example, residue 38:

  draw_hull [atomselect top "resid 38"]

                                                Andrew
                                                dalke_at_bioreason.com

# This is a -*-tcl-*- script for VMD.

# interface to the "hull" code found at
# http://cm.bell-labs.com/netlib/voronoi/hull.html
# Change this line to reflect your installation location!
set hull "/usr/people/dalke/ftps/hull/hull"

# Given a selection, compute the verticies
proc hull {sel} {
    global hull

    # Make a temporary directory
    set dirname [unique_file convex_hull]
    file mkdir $dirname

    # Save the atom coordinates
    set atoms [$sel get {x y z}]
    set outfile [open "$dirname/input_coordinates.dat" w]
    foreach atom $atoms {
        puts $outfile $atom
    }
    close $outfile

    # Run the executable (note: there's no error checking in
    # any of this procedure)
    catch {
        # need to scale by 100 since hull rounds to integers
        # (A precision of 0.01 Angstroms is good enough for atoms.)
        exec $hull -m 100 < "$dirname/input_coordinates.dat" > \
            "$dirname/output_verticies.dat"
    }

    # Read the list of triangles into "triangles"
    set triangles {}
    set infile [open "$dirname/output_verticies.dat" r]
    gets $infile line
    while {[gets $infile line] >= 0} {
        lassign $line v1 v2 v3
        # ignores the "-1" when doing Delaunay triangulation
        if {$v1 < 0 || $v2 < 0 || $v3 < 0} {
            continue
        }
        # Save the coordinates of the triangle
        lappend triangles [list [lindex $atoms $v1] [lindex $atoms $v2] \
                               [lindex $atoms $v3]]
    }
    # Remove the temp files/directory
    file delete "$dirname/input_coordinates.dat"
    file delete "$dirname/output_verticies.dat"
    file delete $dirname

    # return the triangle verticies
    return $triangles
}

# Given a selection, draw the hull
proc draw_hull {sel} {
    set tri [hull $sel]
    draw color trans_blue
    foreach t $tri {
        lassign $t v1 v2 v3
        draw triangle $v1 $v2 $v3
    }
}