public class LasserreVolume
extends java.lang.Object
Each nD half-space is represented by an inequality of the form a1*x1 + a2*x2 + ... + an*xn <= b. For example, in 2D, each half-space is defined by coefficients a1, a2 and b, and at least three such half-spaces are required to define a bounded polygon. This class computes the area of such a polygon or, more generally, the volume of an nD polytope, using Lasserre's recursive algorithm.
This implementation currently assumes that the half-planes for any redundant half-spaces are not parallel. This assumption is and (the computed volume) is valid if each specified half-plane represents part of the boundary of a strictly convex polytope. In particular, this assumption is valid for any Voronoi polytope.
See Lasserre J.B., 1983, An analytical expression and an algorithm for the volume of a convex polyhedron in R^n: Journal of Optimization Theory and Applications, 39, 363--377.
Constructor and Description |
---|
LasserreVolume(int n)
Constructs an initially unbounded (infinite) volume in n dimensions.
|
Modifier and Type | Method and Description |
---|---|
void |
addHalfSpace(double[] a,
double b)
Adds an nD half-space a1*x1 + a2*x2 + … + an*xn <= b.
|
void |
addHalfSpace(double a1,
double b)
Adds a 1D half-space a1*x1 <= b to bound this volume.
|
void |
addHalfSpace(double a1,
double a2,
double b)
Adds a 2D half-space a1*x1 + a2*x2 <= b to bound this volume.
|
void |
addHalfSpace(double a1,
double a2,
double a3,
double b)
Adds a 3D half-space a1*x1 + a2*x2 + a3*x3 <= b to bound this volume.
|
void |
clear()
Removes all half-spaces for this volume, making it infinite.
|
double |
getVolume()
Gets this volume.
|
public LasserreVolume(int n)
n
- the number of dimensions.public void addHalfSpace(double a1, double b)
a1
- the coefficient a1.b
- the right-hand-side.public void addHalfSpace(double a1, double a2, double b)
a1
- the coefficient a1.a2
- the coefficient a2.b
- the right-hand-side.public void addHalfSpace(double a1, double a2, double a3, double b)
a1
- the coefficient a1.a2
- the coefficient a2.a3
- the coefficient a3.b
- the right-hand-side.public void addHalfSpace(double[] a, double b)
a
- array {a1,a2,...,an} of coefficients.b
- the right-hand-side.public void clear()
public double getVolume()