PolytopeAlgebra

ECMAScript modules for exactly manipulating set algebra of polytopes on the basis of @kkitahara/linear-algebra.

Caution

Dimensions higher than 3 were not tested so much. Although there is no known problem, please be careful if you use this code for such high dimensions.

Installation

npm install @kkitahara/polytope-algebra @kkitahara/linear-algebra @kkitahara/real-algebra

Examples

Numerical set algebra (for 2-dimensional polytopes)

import { RealAlgebra } from '@kkitahara/real-algebra'
import { LinearAlgebra } from '@kkitahara/linear-algebra'
import { PolytopeAlgebra } from '@kkitahara/polytope-algebra'
// set a reasonable tolerance for equality
let r = new RealAlgebra(1e-8)
let l = new LinearAlgebra(r)
let dim = 2
let p2d = new PolytopeAlgebra(dim, l)

Generate a new hypercube of edge length 2 * d centred at the origin.

let d = 1
let p1 = p2d.hypercube(d)

// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

Calculate the volume of polytopes

let vol = p2d.volume(p1)
vol.toString() // '4'

Generate a new facet.

// A facet is characterised by its normal vector (nvec),
// distance from the origin (d),
// and the direction of the normal vector (faceOutside).
let nvec = [1, 0]
d = 1
let faceOutside = true
let f = p2d.facet(nvec, d, faceOutside)

// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\o\\\\\| f
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|

nvec = [1, 0]
d = 1
faceOutside = false
f = p2d.facet(nvec, d, faceOutside)

//             |\\\\\\\\\\\\
//             |\\\\\\\\\\\\
//             |\\\\\\\\\\\\
//       o   f |\\\\\\\\\\\\
//             |\\\\\\\\\\\\
//             |\\\\\\\\\\\\
//             |\\\\\\\\\\\\

// No need to normalise the normal vector,
// provided that `d` is the dot product of the normal vector and
// the position vector of a vertex on the facet.
f = p2d.facet([2, 0], 1, true)

// \\\\\\\\\|
// \\\\\\\\\|
// \\\\\\\\\|
// \\\\\\o\\| f
// \\\\\\\\\|
// \\\\\\\\\|
// \\\\\\\\\|

f = p2d.facet([2, 0], 2, true)

// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\o\\\\\| f
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|
// \\\\\\\\\\\\|

Add a facet to polytopes (in place)

p1 = p2d.hypercube(d)

// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

f = p2d.facet([2, -1], 1, true)

// \\\\\\\\\\\\/
// \\\\\\\\\\\/
// \\\\\\\\\\/
// \\\\\\o\\/ f
// \\\\\\\\/
// \\\\\\\/
// \\\\\\/

p1 = p2d.iaddFacet(p1, f)
p2d.volume(p1).toString() // '3'

// p1
// +-----------+
// |\\\\\\\\\\/
// |\\\\\\\\\/
// |\\\\\o\\/
// |\\\\\\\/
// |\\\\\\/
// +-----+

Copy (generate a new object)

let p2 = p2d.copy(p1)
p2d.volume(p2).toString() // '3'

// p2
// +-----------+
// |\\\\\\\\\\/
// |\\\\\\\\\/
// |\\\\\o\\/
// |\\\\\\\/
// |\\\\\\/
// +-----+

Rotation (new object is genrated, since v1.1.0)

let c4 = l.$(0, -1, 1, 0).setDim(2)
p2 = p2d.rotate(p1, c4)
p1 !== p2 // true
p2d.volume(p2).toString() // '3'

// p2
// +-__
// |\\\--_
// |\\\\\\--__
// |\\\\\o\\\\-+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

In-place rotation (new object is not genrated, since v1.1.0)

p2 = p2d.irotate(p2, c4)
p2d.volume(p2).toString() // '3'

// p2
//       +-----+
//      /\\\\\\|
//     /\\\\\\\|
//    /\\o\\\\\|
//   /\\\\\\\\\|
//  /\\\\\\\\\\|
// +-----------+

Translation (new object is generated)

p2 = p2d.translate(p1, [r.$(1, 2), 0])
p1 !== p2 // true
p2d.volume(p2).toString() // '3'

// p2
//    +-----------+
//    |\\\\\\\\\\/
//    |\\\\\\\\\/
//    |\\o\\\\\/
//    |\\\\\\\/
//    |\\\\\\/
//    +-----+

In-place translation (new object is not generated)

p1 = p2d.itranslate(p1, [r.$(1, 2), 0])
p2d.volume(p1).toString() // '3'

// p1
//    +-----------+
//    |\\\\\\\\\\/
//    |\\\\\\\\\/
//    |\\o\\\\\/
//    |\\\\\\\/
//    |\\\\\\/
//    +-----+

Scaling (new object is generated)

p2 = p2d.scale(p1, 2)
p1 !== p2 // true
p2d.volume(p2).toString() // '12'

// p2
// +-----------------------+
// |\\\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\/
// |\\\\\o\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\/
// |\\\\\\\\\\\\/
// +-----------+

In-place scaling (new object is not generated)

p1 = p2d.iscale(p1, r.$(1, 3))
p2d.volume(p1).toString() // '1 / 3'

//      p1
//      +---+
//      |o\/
//      +-+

Multiplication (intersection, new object is generated)

p1 = p2d.hypercube(1)
p2 = p2d.itranslate(p2d.hypercube(1), [1, 1])
let p3 = p2d.mul(p1, p2)
p3 !== p1 // true
p3 !== p2 // true
p2d.volume(p3).toString() // '1'

//
//
//
// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

//       p2
//       +-----------+
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       o-----------+
//
//
//

//
//
//
//       p3
//       +-----+
//       |\\\\\|
//       |\\\\\|
//       o-----+
//
//
//

Subtraction (set difference, new object is generated)

p1 = p2d.hypercube(1)
p2 = p2d.itranslate(p2d.hypercube(1), [1, 1])
p3 = p2d.sub(p1, p2)
p3 !== p1 // true
p3 !== p2 // true
p2d.volume(p3).toString() // '3'

//
//
//
// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

//       p2
//       +-----------+
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       o-----------+
//
//
//

//
//
//
// p3
// +-----+
// |\\\\\|
// |\\\\\|
// |\\\\\o-----+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

Addition (union, new object is generated)

p1 = p2d.hypercube(1)
p2 = p2d.itranslate(p2d.hypercube(1), [1, 1])
p3 = p2d.add(p1, p2)
p3 !== p1 // true
p3 !== p2 // true
p2d.volume(p3).toString() // '7'

//
//
//
// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

//       p2
//       +-----------+
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       |\\\\\\\\\\\|
//       o-----------+
//
//
//

//
//       +-----------+
//       |\\\\\\\\\\\|
// p3    |\\\\\\\\\\\|
// +-----+\\\\\\\\\\\|
// |\\\\\\\\\\\\\\\\\|
// |\\\\\\\\\\\\\\\\\|
// |\\\\\o\\\\\+-----+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+

JSON (stringify and parse)

let str = JSON.stringify(p3)
let p4 = JSON.parse(str, p2d.reviver)
let p5 = p2d.mul(p3, p4)
p2d.volume(p4).toString() // '7'
p2d.volume(p5).toString() // '7'

Exact set algebra for polytopes

You can work with an exact algebra if you use

import { ExactRealAlgebra as RealAlgebra } from '@kkitahara/real-algebra'
import { LinearAlgebra } from '@kkitahara/linear-algebra'
import { PolytopeAlgebra } from '@kkitahara/polytope-algebra'
let r = new RealAlgebra()
let l = new LinearAlgebra(r)
let dim = 3
let p3d = new PolytopeAlgebra(dim, l)

insted of RealAlgebra. See the documents of @kkitahara/real-algebra for more details about the exact algebra. :warning: The exact algebra can take a long time, and, in some cases, it can consume huge amount of memory.

Another implementation

Another implementation of the algebra is available:

...
...
import { AnotherPolytopeAlgebra } from '@kkitahara/polytope-algebra'
...
...
let p3d = new AnotherPolytopeAlgebra(3, l)

It internally uses the intersection operation for union and difference operations (these are much more time-consuming than intersection operation). So, in some cases, it may be more efficient than the original PolytopeAlgebra.

ESDoc documents

For more examples, see ESDoc documents:

cd node_modules/@kkitahara/polytope-algebra
npm install --only=dev
npm run doc

and open doc/index.html in your browser.

LICENSE

© 2019 Koichi Kitahara
Apache 2.0