by Ted Ashton, Jason Cantarella, Harrison Chapman, and Tom Eddy.
plCurve is a library for efficiently handling polygonal space curves. It allows curves to be open or closed, and to contain multiple components. In addition, curves (or sections of curves) may be constrained to lie at particular points, on particular lines, or in particular planes. To support operations on plCurves, the library provides a fully functional linear algebra package for vectors in 3-space, including vector arithmetic, dot and cross products, and higher-level operations such as taking linear combinations of vectors. The library also supports splining plCurves and reading and writing them to disk. The file format used by plCurve is the Geomview VECT format, which is a simple human-readable format for space polygons.
plCurve is written in syntax-checked ANSI C, and is valgrind-clean for memory bugs. The package is built using the GNU Autotools and installs in the standard way. The argtable2 library is required for the demonstration programs included with plCurve.
plCurve is currently supported and actively developed. The current roadmap for development is to switch the main interface to Python, and then to build new functionality into the library in Python, so the interface will shift to Python in the next version. We will be adding more topological invariants (via SnapPy) after the shift.
The main data types in the plCurve library are the
plCurve types. The
plc_vector is a struct containing one field: an array
c of 3
doubles giving the components of the vector in R^3. These vectors can be added, subtracted, and so forth with the functions described in
The plCurve data type is much more complicated, but is essentially a wrapper for an array of pointers to individual components. Most programmers will need to know:
Users should always allocate
plCurve *, rather than
plCurve variables. Library functions which create plCurves also allocate memory for the main data structure and the library function to destroy plCurves,
plc_free, expects to deallocate the pointer to
plCurve which it is passed.
C is of type
plCurve *, then
C->ncis the number of components in the curve.
C->cp[i].nvis the number of vertices in the ith component of C.
C->cp[i].vt[j]is the jth vertex of component i.
C->cp[i].openis true if the polygon is open, false if the polygon is closed.
There is a limited form of wraparound addressing in plCurves. If
C->cp[i].nv = N and the component is closed,
C->cp[i].vt[-1] is equal to the last vertex of the curve and
C->cp[i].vt[N] is equal to the first vertex. If the component is open, then
C->cp[i].vt[-1] = C->cp[i].vt and
C->cp[i].vt[N] = C->cp[i].vt[N-1]. These provisions make for much cleaner and nicer code, and extensive experience with geometric programming for polygons tells us that these conventions are usually what you want to happen. However, in order to implement this functionality, programmers should only modify in-range vertex addresses and they must call
plc_fixwrap anytime they directly modify the vertices of a
plCurve in order to make sure that wraparound addresses work properly on subsequent reads of the same
Python module ‘
If Python dependencies are met and bindings not disabled on compile, a Python module
libpl is built. At this time, most functionality of
pd_code_t is supported. Headers are included to call some Python-implemented procedures from C. An introduction to, and links to the documentation for, the Python wrappings can be found here.
Overview of Functionality
- Basic vector operations in R^3. Vector addition, dot, cross, distances. Circumcircle of three points, intersection of three planes, inradius of tetrahedron, angles and dihedral angles.
- plCurve data type for space polygons. Supports being constrained to point, line or plane, multiple components, open and closed polygons. Read/write, copy operations. Convert between polygon and spline. Scale, rotation, translate, project to plane. Renumber components and change orientation. Fold along diagonal.
- Geometric measurements of polygons. Counts of vertices and edges. Turning angles, curvature, total curvature and total torsion. Arclength and subarc lengths. Diameter, center of mass, radius of gyration, chordlengths.
- Symmetries of polygons. Define rotational or reflectional symmetries of polyline. Group operations on symmetries. Symmetrize polygon over a group to correct numerical errors.
- Topological measurements of polygons. Compute HOMFLY. Identify knot type from HOMFLY if possible.
- Random polygons. Generate random closed and open length-2 polygons using Stiefel manifold algorithm of Cantarella, Deguchi, Shonkwiler. Generate Markov chains of equilateral polygons and polygons with a fixed failure-to-close (one long edge) using the Toric Symplectic algorithm of Cantarella and Shonkwiler. Generate equilateral closed polygons using the Action-Angle direct sampling algorithm of Cantarella, Duplantier, Shonkwiler, and Uehara.
- Planar diagrams of polygons. Includes a complete implementation of a type for describing knot and link diagrams, capable of handling arbitrarily large diagrams, converting space polygons to diagrams, performing basic consistency checks on diagrams, and producing drawings of diagrams. Development roadmap includes automated simplification of diagrams and links to the Mathematica package KnotTheory and SnapPy for computing invariants.
The latest plCurve can be obtained from the subversion repository. Point releases tend to lag behind the subversion build, but are included below for convenience. Note that you’ll need the GNU Autotools in order to build from subversion.
- This version exposes more of the functionality of the C interface in the python interface, including plc_classify (plc_classify_knot in python) and plc_homfly (plc_knot_homfly in python). In addition, fixes a rare bug where the library would segfault when attempting to classify a polygon which could not be converted stably to a pd_code.
- This version includes a new tool, /tools/randomknot.c which generates random equilateral polygons with a given knot type (by rejection sampling the moment polytope sampler of Cantarella, Duplantier, Shonkwiler, Uehara).
- This version includes a new tool, /tools/diagram_to_img.py which uses the Spherogram library to produce drawings from pdcodes.
- This version expands on the planar diagram code functionality with new functions for topological operations on pdcodes, random pdcodes, and drawings of pdcodes. In addition, it updates the random polygon library to use the Action-Angle direct sampling algorithm of Cantarella, Duplantier, Shonkwiler, and Uehara. The update to 7.6.3 is a bugfix release correcting a number of small bugs and adding some options to processpdstor to help users more easily recreate the data in our paper on random diagrams.
- This version incorporates planar diagram (pd) codes for knot and link projections, including robust code for converting space curves to projections. This version also incorporates the Toric Symplectic Markov Chain Monte Carlo (TSMCMC) algorithm for integrating over spaces of fixed edgelength polygons (with error bounds), using the method of Cantarella and Shonkwiler.
- This version includes a lot of new functionality for random polygons, including code for random loop closures and open and closed random polygons with fixed total length.
- This version has a completely rewritten build system and also includes new functionality for generating random polygons using the probability measures on polygon spaces defined in my paper with Clay Shonkwiler and Tetsuo Deguchi.
- This version contains some nearest-neighbor code and a facility for handling curves with symmetries.
- This version includes a version of the Ewing/Millett HOMFLY code which can be used to compute HOMFLY polynomials for knots, and some functionality to classify VECTS by topological type using this polynomial. At the moment, this interface is fairly basic, but it will be improved in subsequent versions.