Cone Algorithm

--- Generic surface particle identification algorithm

Yanting Wang


The cone algorithm is a fast algorithm that can accurately identify which particles are on the surface of a condense-phase cluster in three dimensions. While a general computational geometry algorithm, it is especially useful for computational surface science and computational nano science.

A sample cluster performed with the cone algorithm is shown below. The green spheres are the particles identified as on the surface, and yellow ones are inside.

Downloading source code

The source code for the cone algorithm is free for academic or personal usage. By downloading the following source code, you agree that:
  1. the source code will only be used for academic or personal purpose, not commercial purpose.
  2. the author is not responsible for any consequences caused by the usage of this code.
  3. if the usage of this code leads to publishable research results, you will cite the original publication describing this algorithm: Yanting Wang, S. Teitel, and Christoph Dellago, Melting of Icosahedral Gold Nanoclusters from Molecular Dynamics Simulations J. Chem. Phys. 122 214722-214738, 2005.

Basic idea

For a given three-dimensional cluster composed of a set of particles, how can we tell which particles (e.g. atoms) are on the surface? It seems easy to tell by human eyes. Visual criterion can be interpreted as: A particle is on the surface if it is not all surrounded by other particles. How can we decide if a concave particle is on the surface or not? We may say: if it is not so deep in the cave, it can be treated as a surface particle.

In order to tell computer how to pick up surface particles according to their positions, one quantified expression equivalent to the above criteria is:

For a given particle, its associated cone region is defined as the region inside a cone of a certain side length and angle, whose vertex resides on the particle. A hollow cone is a cone region with no other particles inside it. A particle is identified as on the surface if at least one associated hollow cone exists.

There are two adjustable parameters for the cone: angle and side length. The accuracy (or satisfactory) of the results depends on these two parameters. This algorithm is immediately applicable to the situations when there are multiple molecules in one configuration and/or there are holes inside molecules.



Although C++ is used, the programming is more structural than object-oriented. The program can be used with pipe to cascade standard input and output.
Details of programming and usage is documented in the README file included in the package. The source code has sufficient comments and should be easy to read.

Multi-layer identification

Calling the cone algorithm repeatedly can identify different sub surface layers. layers.C is a sample program for doing this. The multi-layer analysis of an icosahedral gold cluster with 2624 atoms are shown in the daily work for gold facets. The image below is an intersection shown of a multi-layer icosahedral gold cluster. (The atoms are identical gold atoms. They are colored differently according to the layers they belong to.)

Back to Yanting Wang's Homepage

You are the visitor since July 18, 2008.