Back to the PSciCo homepage

PLS: Piecewise-linear Systems


Polytope , boundary constraints , internal constraints , piecewise-linear system .


The PLS library contains the definition and the implementation of piecewise-linear systems. The library allows the programmer to build a piecewise-linear system, associate data with contained polytopes and query system with powerful library functions. PLSs are a very general way to represent

A polytope a finite region of n-dimensional space enclosed by a finite number of hyperplanes. In increasing dimensions, examples of polytopes are points (0d), line segments (1d), polygons (2d), polyhedrons (3d). A convex polytope is the convex hull of a set of vertices in n-dimensional space.

A PLS (piecewise-linear system) is a set of polytopes S with the following properties.

This definition is from page 7 of the paper
Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, and Han Wang, Control volume meshes using sphere packing: generation, refinement and coarsening. Proc. 5th Int. Meshing Roundtable, Sandia Nat. Lab., Oct 1996, pp. 47-61.
although in that paper the polytopes were defined to be convex. We do not impose this limitation.

Here is an example of a PLS with non-convex polytopes

It is taken from the paper
Jonathan Richard Shewchuk, Tetrahedral Mesh Generation by Delaunay Refinement. Proceedings of the Fourteenth Annual ACM Symposium on Computational Geometry (Minneapolis, Minnesota), pages 86-95, June 1998.
Note that in addition to the 3d object, each of the points, edges and faces is a polytope. Some of the polytopes are boundaries of higher-dimensional polytopes (such as the upper surface on the left) and some are internal constraints (such as the the lone edge embedded in the upper surface). A polytope can both be a boundary and an internal constraint (such as the other two joined edges embedded in the upper surface, which are internal constraints for the upper surface and boundary constrains for the two rectangles that penetrate the body).

Each polytope in a PLS is fully defined by a set of boundary and internal constraints , where each constraint corresponds to a polytope. In fact, the representation of a PLS is basically a DAG in which each node is a polytope and each edge represents a constraint. There are two types of edges corresponding to boundary and internal constraints. Edges always point from higher to lower dimensional polytopes. The leaves of the DAG (nodes with out-degree zero), are all zero-dimensional polytopes (i.e. points).

Using the library functions, the programmer can build a PLS by adding and removing polytopes and specifying the boundary and internal constraints. The library also allows the programmer to associate data with each polytope using the supplied PolytopeIdTable.

Relevant Files

The interface

  • PLS: The main definition.
  • ID: The definition of the identifiers.
  • The implementation

  • BuildPls: Builds a PLS from a geometry, vertex and ID.

  • Back to the PSciCo homepage.