## 11 Geometry## 11.1 OverviewThe geometry package provides classes useful for many physical simulations in Euclidean spaces, like vectors and rotations in 3D, as well as on the sphere. It also provides a general implementation of Binary Space Partitioning Trees (BSP trees). All supported type of spaces (Euclidean 3D, Euclidean 2D, Euclidean 1D, 2-Sphere and 1-Sphere) provide dedicated classes that represent complex regions of the space as shown in the following table:
All these regions share common features. Regions can be defined from several non-connected parts. As an example, one PolygonsSet instance in Euclidean 2D (i.e. the plane) can represent a region composed of several separated polygons separate from each other. They also support regions containing holes. As an example a SphericalPolygonsSet on the 2-Sphere can represent a land mass on the Earth with an interior sea, where points on this sea would not be considered to belong to the land mass. Of course more complex models can also be represented and it is possible to define for example one region composed of several continents, with interior sea containing separate islands, some of which having lakes, which may have smaller island ... In the infinite Euclidean spaces, regions can have infinite parts. for example in 1D (i.e. along a line), one can define an interval starting at abscissa 3 and extending up to infinity. This is also possible in 2D and 3D. For all spaces, regions without any boundaries are also possible so one can define the whole space or the empty region. The classical set operations are available in all cases: union, intersection, symmetric difference (exclusive or), difference, complement. There are also region predicates (point inside/outside/on boundary, emptiness, other region contained). Some geometric properties like size, or boundary size can be computed, as well as barycenters on the Euclidean space. Another important feature available for all these regions is the projection of a point to the closest region boundary (if there is a boundary). The projection provides both the projected point and the signed distance between the point and its projection, with the convention distance to boundary is considered negative if the point is inside the region, positive if the point is outside the region and of course 0 if the point is already on the boundary. This feature can be used for example as the value of a function in a root solver to determine when a moving point crosses the region boundary. ## 11.2 Euclidean spacesVector1D, Vector2D and Vector3D provide simple vector types. One important feature is that instances of these classes are guaranteed to be immutable, this greatly simplifies modeling 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. Vector1DFormat, Vector2DFormat and Vector3DFormat are specialized classes for formatting output or parsing input with text representation of 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 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 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
Since a rotation is basically a vectorial operator, several
rotations can be composed together and the composite operation
u, r(u) = r)
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 _{1}(r_{2}(u))r to
_{1}r and the result we get is _{2}r =
r. For this purpose, the class
provides the methods: _{1} o r_{2}applyTo(Rotation) and
applyInverseTo(Rotation).
## 11.3 n-SphereThe Apache Commons Math library provides a few classes dealing with geometry on the 1-sphere (i.e. the one dimensional circle corresponding to the boundary of a two-dimensional disc) and the 2-sphere (i.e. the two dimensional sphere surface corresponding to the boundary of a three-dimensional ball). The main classes in this package correspond to the region explained above, i.e. ArcsSet and SphericalPolygonsSet. ## 11.4 Binary Space PartitioningBSP 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. This is how the regions explained above in the Euclidean and Sphere spaces are implemented. The partitioning package provides the engine to do the computation, but not the dimension-specific implementations. The various interfaces in this package (hyperplane, sub-hyperplane, embedding, and even region) are therefore not considered to be reusable public interface, they are private interface. They may change and users are not expected to rely directly on them. What users can rely on is the BSP tree class itself, and the space-specific implementations of the interfaces (i.e. Plane in 3D as the implementation of hyperplane, or S2Point on the 2-Sphere as the implementation of Point). Another example of BST tree use would be to represent Voronoi tesselations, the attribute of each cell holding the defining point of the cell. This is not available yet. 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. ## 11.5 Regions
The regions in all Euclidean and spherical spaces are based on BSP-tree using a
The recommended way to build regions is to start from basic shapes built from their boundary representation
and to use the set operations to combine these basic shapes into more complex shapes. The basic shapes
that can be constructed from boundary representations must have a closed boundary and be in one part
without holes. Regions in several non-connected parts or with holes must be built by building the parts
beforehand and combining them. All regions (
Another way to build regions is to create directly the underlying BSP-tree. All regions ( PolygonsSet empty = new PolygonsSet(new BSPTree<Euclidean2D>(false), tolerance); In the Euclidean 3D case, the PolyhedronsSet class has another specific constructor to build regions from vertices and facets. The signature of this constructor is: PolyhedronsSet(List<Vector3D> vertices, List<int[]> facets, double tolerance); The vertices list contains all the vertices of the polyhedrons, the facets list defines the facets, as an indirection in the vertices list. Each facet is a short integer array and each element in a facet array is the index of one vertex in the list. So in our cube example, the vertices list would contain 8 points corresponding to the cube vertices, the facets list would contain 6 facets (the sides of the cube) and each facet would contain 4 integers corresponding to the indices of the 4 vertices defining one side. Of course, each vertex would be referenced once in three different facets.
Beware that despite some basic consistency checks are performed in the constructor, not everything
is checked, so it remains under caller responsibility to ensure the vertices and facets are consistent
and properly define a polyhedrons set. One particular trick is that when defining a facet, the vertices
If one wants to further look at how it works, there is a test parser for PLY file formats in the unit tests section of the library and some basic ply files for a simple geometric shape (the N pentomino) in the test resources. This parser uses the constructor defined above as the PLY file format uses vertices and facets to represent 3D shapes. |