npm package: @kkitahara/polytope-algebra
Description: ECMAScript modules for exactly manipulating set algebra of polytopes on the basis of @kkitahara/linear-algebra.
Author: Koichi Kitahara
Latest version: 1.2.8

[![JavaScript Style Guide](https://img.shields.io/badge/code_style-standard-brightgreen.svg)](https://standardjs.com)
[![license](https://img.shields.io/npm/l/@kkitahara/polytope-algebra.svg)](https://www.apache.org/licenses/LICENSE-2.0)
[![version](https://img.shields.io/npm/v/@kkitahara/polytope-algebra/latest.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)
[![bundle size](https://img.shields.io/bundlephobia/min/@kkitahara/polytope-algebra.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)
[![downloads per week](https://img.shields.io/npm/dw/@kkitahara/polytope-algebra.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)
[![downloads per month](https://img.shields.io/npm/dm/@kkitahara/polytope-algebra.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)
[![downloads per year](https://img.shields.io/npm/dy/@kkitahara/polytope-algebra.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)
[![downloads total](https://img.shields.io/npm/dt/@kkitahara/polytope-algebra.svg)](https://www.npmjs.com/package/@kkitahara/polytope-algebra)

# PolytopeAlgebra

ECMAScript modules for exactly manipulating
set algebra of polytopes on the basis of
[@kkitahara/linear-algebra](https://www.npmjs.com/package/@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)
```javascript
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.
```javascript
let d = 1
let p1 = p2d.hypercube(d)

// p1
// +-----------+
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// |\\\\\o\\\\\|
// |\\\\\\\\\\\|
// |\\\\\\\\\\\|
// +-----------+
```
Calculate the volume of polytopes
```javascript
let vol = p2d.volume(p1)
vol.toString() // '4'
```
Generate a new facet.
```javascript
// 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)
```javascript
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)
```javascript
let p2 = p2d.copy(p1)
p2d.volume(p2).toString() // '3'

// p2
// +-----------+
// |\\\\\\\\\\/
// |\\\\\\\\\/
// |\\\\\o\\/
// |\\\\\\\/
// |\\\\\\/
// +-----+
```
Rotation (new object is genrated, since v1.1.0)
```javascript
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)
```javascript
p2 = p2d.irotate(p2, c4)
p2d.volume(p2).toString() // '3'

// p2
//       +-----+
//      /\\\\\\|
//     /\\\\\\\|
//    /\\o\\\\\|
//   /\\\\\\\\\|
//  /\\\\\\\\\\|
// +-----------+
```
Translation (new object is generated)
```javascript
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)
```javascript
p1 = p2d.itranslate(p1, [r.$(1, 2), 0])
p2d.volume(p1).toString() // '3'

// p1
//    +-----------+
//    |\\\\\\\\\\/
//    |\\\\\\\\\/
//    |\\o\\\\\/
//    |\\\\\\\/
//    |\\\\\\/
//    +-----+
```
Scaling (new object is generated)
```javascript
p2 = p2d.scale(p1, 2)
p1 !== p2 // true
p2d.volume(p2).toString() // '12'

// p2
// +-----------------------+
// |\\\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\\\/
// |\\\\\o\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\\/
// |\\\\\\\\\\\\\/
// |\\\\\\\\\\\\/
// +-----------+
```
In-place scaling (new object is not generated)
```javascript
p1 = p2d.iscale(p1, r.$(1, 3))
p2d.volume(p1).toString() // '1 / 3'

//      p1
//      +---+
//      |o\/
//      +-+
```
Multiplication (intersection, new object is generated)
```javascript
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)
```javascript
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)
```javascript
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)
```javascript
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
```javascript
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:
```javascript
...
...
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
&copy; 2019 Koichi Kitahara  
[Apache 2.0](LICENSE)