11 Geometry

11.1 Overview

The geometry package provides classes useful for many physical simulations in Euclidean spaces, like vectors and rotations in 3D, as well as a general implentation of Binary Space Partitioning Trees (BSP trees).

11.2 Euclidean spaces

Interval and IntervalsSet represent one dimensional regions. All classical set operations are available for intervals sets: union, intersection, symmetric difference (exclusive or), difference, complement, as well as region predicates (point inside/outside/on boundary, emptiness, other region contained). It is also possible to compute geometrical properties like size, barycenter or boundary size. Intervals sets can be built by constructive geometry (union, intersection ...) or from a boundary representation.

PolygonsSet represent two dimensional regions. All classical set operations are available for polygons sets: union, intersection, symmetric difference (exclusive or), difference, complement, as well as region predicates (point inside/outside/on boundary, emptiness, other region contained). It is also possible to compute geometrical properties like size, barycenter or boundary size and to extract the vertices. Polygons sets can be built by constructive geometry (union, intersection ...) or from a boundary representation.

PolyhedronsSet represent three dimensional regions. All classical set operations are available for polyhedrons sets: union, intersection, symmetric difference (exclusive or), difference, complement, as well as region predicates (point inside/outside/on boundary, emptiness, other region contained). It is also possible to compute geometrical properties like size, barycenter or boundary size and to extract the vertices. Polyhedrons sets can be built by constructive geometry (union, intersection ...) or from a boundary representation.

Vector3D provides a simple vector type. One important feature is that instances of this class are guaranteed to be immutable, this greatly simplifies modelling dynamical systems with changing states: once a vector has been computed, a reference to it is known to preserve its state as long as the reference itself is preserved.

Numerous constructors are available to create vectors. In addition to the straightforward cartesian coordinates constructor, a constructor using azimuthal coordinates can build normalized vectors and linear constructors from one, two, three or four base vectors are also available. Constants have been defined for the most commons vectors (plus and minus canonical axes, null vector, and special vectors with infinite or NaN coordinates).

The generic vectorial space operations are available including dot product, normalization, orthogonal vector finding and angular separation computation which have a specific meaning in 3D. The 3D geometry specific cross product is of course also implemented.

Vector3DFormat is a specialized format for formatting output or parsing input with text representation of 3D vectors.

Rotation represents 3D rotations. Rotation instances are also immutable objects, as Vector3D instances.

Rotations can be represented by several different mathematical entities (matrices, axe and angle, Cardan or Euler angles, quaternions). This class presents a higher level abstraction, more user-oriented and hiding implementation details. Well, for the curious, we use quaternions for the internal representation. The user can build a rotation from any of these representations, and any of these representations can be retrieved from a Rotation instance (see the various constructors and getters). In addition, a rotation can also be built implicitely from a set of vectors and their image.

This implies that this class can be used to convert from one representation to another one. For example, converting a rotation matrix into a set of Cardan angles can be done using the following single line of code:

double[] angles = new Rotation(matrix, 1.0e-10).getAngles(RotationOrder.XYZ);

Focus is oriented on what a rotation does rather than on its underlying representation. Once it has been built, and regardless of its internal representation, a rotation is an operator which basically transforms three dimensional vectors into other three dimensional vectors. Depending on the application, the meaning of these vectors may vary as well as the semantics of the rotation.

For example in a spacecraft attitude simulation tool, users will often consider the vectors are fixed (say the Earth direction for example) and the rotation transforms the coordinates coordinates of this vector in inertial frame into the coordinates of the same vector in satellite frame. In this case, the rotation implicitly defines the relation between the two frames (we have fixed vectors and moving frame). Another example could be a telescope control application, where the rotation would transform the sighting direction at rest into the desired observing direction when the telescope is pointed towards an object of interest. In this case the rotation transforms the direction at rest in a topocentric frame into the sighting direction in the same topocentric frame (we have moving vectors in fixed frame). In many case, both approaches will be combined, in our telescope example, we will probably also need to transform the observing direction in the topocentric frame into the observing direction in inertial frame taking into account the observatory location and the Earth rotation.

These examples show that a rotation means what the user wants it to mean, so this class does not push the user towards one specific definition and hence does not provide methods like projectVectorIntoDestinationFrame or computeTransformedDirection. It provides simpler and more generic methods: applyTo(Vector3D) and applyInverseTo(Vector3D).

Since a rotation is basically a vectorial operator, several rotations can be composed together and the composite operation r = r1 o r2 (which means that for each vector u, r(u) = r1(r2(u))) is also a rotation. Hence we can consider that in addition to vectors, a rotation can be applied to other rotations as well (or to itself). With our previous notations, we would say we can apply r1 to r2 and the result we get is r = r1 o r2. For this purpose, the class provides the methods: applyTo(Rotation) and applyInverseTo(Rotation).

11.3 Binary Space Partitioning

BSP trees are an efficient way to represent space partitions and to associate attributes with each cell. Each node in a BSP tree represents a convex region which is partitioned in two convex sub-regions at each side of a cut hyperplane. The root tree contains the complete space.

The main use of such partitions is to use a boolean attribute to define an inside/outside property, hence representing arbitrary polytopes (line segments in 1D, polygons in 2D and polyhedrons in 3D) and to operate on them.

Another example would be to represent Voronoi tesselations, the attribute of each cell holding the defining point of the cell.

The application-defined attributes are shared among copied instances and propagated to split parts. These attributes are not used by the BSP-tree algorithms themselves, so the application can use them for any purpose. Since the tree visiting method holds internal and leaf nodes differently, it is possible to use different classes for internal nodes attributes and leaf nodes attributes. This should be used with care, though, because if the tree is modified in any way after attributes have been set, some internal nodes may become leaf nodes and some leaf nodes may become internal nodes.