HSI Halfspace Intersection: Calculate and draw convex polytopes from half-space equations

Examples

Basics

Hyperplanes and Halfspaces

In the euclidian space Rⁿ a hyperplane is a flat (n-1) dimensionl space. In R³ a hyperplane is a normal 2-dimensional plane, in R² a hyperplane is just a straight line.

Algebraically a hyperplane can be described with a linear expression of the form

a₁x₁ + a₂x₂ + ... + a_nx_n + d

with fixed coefficients a₁,a₂, ..., a_n, and d. A hyperplane partitions the euclidian space into 3 distinct and convex areas:

• H^- or H-: All points (x₁,x₂, ..., x_n) where the linear expression evaluates to a negative value. This is called the negative open half-space.
• H⁰ or H0: All points (x₁,x₂, ..., x_n) where the linear expression evaluates to 0.
• H⁺ or H+: All points (x₁,x₂, ..., x_n) where the linear expression evaluates to a positive value. This is called the positive open half-space.

The union of the point sets

• H^- and H⁰ is called the negative closed half-space.
• H⁺ and H⁰ is called the positive closed half-space. In this project a half-space is always a positive closed half-space.

Convex Polytopes

A convex polytope is the intersection of finitely many half-spaces in Rⁿ. In the sequel a polytope means always a convex polytope.

From a list of half-spaces the software in this repository calculates all faces of the polytope. In R³ this software also creates simple drawings.

Data Structure

All vertices, edges, sides and hyperplanes of a polytope are called faces. Set inclusion of the point sets of the faces defines a half-order relation on the faces. A half-order can be represented with a Hasse diagram or a face lattice diagram. This is a special form of a directed acyclic graph. In Haskell we can use Maps to implement directed acyclic graphs.

The next 2 images show all faces of a normal triangle on the left as a geometric object and on the right as a Hasse diagram:

Algorithms on Hasse Diagrams

Similar to trees, algorithms can traverse the nodes (aka faces) of a Hasse diagram in preorder or in postorder sequence. Different to trees, the algorithms can visit a node multiple times (Multiple visits) or only once (Single visit).

The following is necessary to specity an algorithm on a Hasse diagram:

• Traversal method (preorder or postorder)
• Visting frequency (Single or Multiple)
• The processing for each node / face.

The numbers in the nodes in the following images, represent the visiting sequence.

Postorder Visiting Sequence (or bottom up)

Preorder Visiting Sequence (or top down)

HSI Algorithm

The algorithm to calculate a polytope from a list of halfspaces starts with a huge cube and applies the HSI algorithm for each halfspace in the list.

To visualize the algorihm, we use a simple triangle. The dark blue line is the new half-space, the little arrow points towards H⁺.

The HSI algorithm is applied to the triangle and the dark blue halfspace The following sections contain a short description of the algorithm.

Data Elements stored for each face

Vertex Faces (Dim 0):

• The coordinates in Rⁿ for the vertex.
• A list of halfspaces where the the H⁰ hyperplanes intersect in this vertex.
• The position of this face relative to the halfspace.

Non Vertex Faces (Dim > 0)

• The dimension of the face
• A list of the halfspaces where the H⁰ hyperplanes intersect in this face
• The position of this face relative to the halfspace.

1. Calculate the Relative Position for each Face

The relative position of a vertex to a halfspace is either:

• "0" : if the vertex is part of H⁰
• "+" : if the vertex is part of H⁺
• "-" : if the vertex is part of H^-

Algorithm: Postorder, Single visit.

Processing per face: Calculate the relative position of the current face:

• Vertex face: Use the scalar product to calculate the relative position.
• Non Vertex face: The relative position is the OR-combination of all sub-faces. eg for an edge with vertices on both sides of H⁰ the relative position is "-+".

2. Remove Faces in H^-

Algorithm: Postorder, Single visit.

Processing per face: Remove every node with relative position "-" or "-0". Remove also all the references to the deleted nodes.

3. Intersection with H⁰

Algorithm: Postorder, Single visit.

Processing per face:

• Process only faces with relative positions "-+" or "-0+".
• Vertices never have relative positions "-+" or "-0+".
• For faces with dimension 1 (edges):
  • Create a new vertex-face.
  • Calculate the coordiantes of the new vertex.
• For faces with dimension n > 1:
  • Create a new face from the current face.
  • Set the dimension of the new face to n-1.
  • Add subfaces with dimension n-2 and relative position "0" as subfaces to the new face.
• Make the new face a subface of the current face.
• Add the halfspace to the list of the halfspaces in the new face.
• Set the relative position of the new face to "0"

In the following diagram we show the intersection of H⁰ with the orange edge with relative position "-+" marked with a star "*". It creates the new yellow vertex.

In the next diagram we show the intersection of the dark blue H⁰ with the triangle face (again marked with a star "*"). It creates the blue edge, and connects the 2 vertices with relative position "0" as sufaces of the newly created edge.

Higher Dimensions

Input Program

References

[1] Nef-W. (1978). Beiträge zur Theorie der Polyeder. Bern: Herbert Lang

[2] Welz-E, Gärtner-B. (2020). Theory of Combinatorial Algorithms, Chapter 9

[3] Article on Convex Polytopes on Wikipedia