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 can be installed with autotools, using the usual
but the preferred method of installation is to use Homebrew. You’ll need to use our Tap to get the formula, so the commands are:
brew tap designbynumbers/cantarellalab
brew install libplcurve
This will allow you to get updated versions of the library as they become available without any further work on your part.
plCurve is currently supported and actively developed.
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
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 GitHub repository. Point releases tend to lag behind the GitHub version, but are included below for convenience. Note that you’ll need the GNU Autotools in order to build by cloning the Git repo directly.
- This release makes several changes. The major one is that the PD_VERBOSE integer variable has been changed to a preprocessor #define symbol. This allows user programs to compile without including the “int PD_VERBOSE;” line which was previously required. This version also updates plc_random_equilateral_closed_polygon() to use the faster progressive action-angle method of Cantarella, Schumacher, and Shonkwiler and includes an (exponentially slow) rejection sampler for generating self-avoiding polygons.
- This release makes a number of housekeeping changes in order to facilitate the transition to a public repository on GitHub, as well as squashing a number of bugs introduced in the 9.0 release. The major change is that the utility program plcrwalk has been improved and replaced by randompolygon. The randompolygon program will now have the main role going forward. We also eliminated some old utility programs which were rarely used and difficult to support.
- This release fixes some build problems; previously, the utility programs released with the library would try to link with the library before it was built. This was hard to see on systems with previous plcurve installations because the programs would silently link with the previously installed version of the library. The build order is now fixed and tested with Mac OS Monterey (12.4).
- The Python library interface is now disabled by default. The reason for this is that the existing interface uses distutils, which is now deprecated in current Python installations. Until we can remove these dependencies, you may need to downdate your Python environment to < 3.9 in order to compile the interface.
- The symbol PD_VERBOSE (which was previously defined in the library) now needs to be defined in user programs. Addint PD_VERBOSE = 0;This solves some duplicate symbol problems with clang on the Apple M1 platforms.
- The “or” fields in pd_face_t, pd_dihedral_t, and pd_orientation_t were changed to “orient” in order to be compatible with C++, which uses “or” as a reserved word. This is (retroactively) part of the C90 standard, and the library now includes the iso646.h header to ensure that non-compliant code will cause a compiler error. There were also internal library functions which used “or” as a variable name; these have now been changed. This is (in principle) a change that may break some user code, though users should not be directly accessing these internal data types in most cases. See C Alternative Tokens for more information.
- This is largely a bug-squashing release. It fixes some rare errors exposed by smarter compiler warnings, which could cause a segfault when plCurve was exiting due to another error. This version also fixes some compilation errors in the python interface which prevented compilation with recent versions of Cython. The new version has been tested with Cython 0.29.24 on Big Sur (Mac OS) and compiles and checks cleanly.
- 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.