TriVis

Compute visibility polygons by Triangular Expansion.

Example

// Points to be triangulated
const points = [[53,98],[5,201],[194,288],[280,195],[392,148],[413,43],[278,5],[169,71],[146,171]],
	// Edges to be constrained
	edges = [[5, 8]],
	// Triangulate
	del = Delaunator.from(points),
	// Constrain the triangulation
	con = new Constrainautor(del);
con.constrainAll(edges);

// Query point
const qx = 162, qy = 262,
	// Obstruction callback: use constrained edges as obstructions
	obstructs = (edg) => con.isConstrained(edg),
	// Left & right end-points of the initial viewing cone (optional)
	ilx = 45, ily = 144, irx = 280, iry = 145,
	// Compute visibility polygon
	poly = triangularExpansion(del, qx, qy, obstructs, ilx, ily, irx, iry);

for(const [lx, ly, rx, ry] of poly){
	drawTriangle(lx, ly, qx, qy, rx, ry);
}

Install

Install from NPM:

npm install @kninnug/trivis

Use in Node.js:

const triangularExpansion = require('@kninnug/trivis');

or as an ECMAScript/ES6 module:

import triangularExpansion from '@kninnug/trivis';

or in the browser:

<script src="node_modules/@kninnug/trivis/lib/TriVis.js"></script>

or minified:

<script src="node_modules/@kninnug/trivis/lib/TriVis.min.js"></script>

The TriVis library does not depend on Delaunator itself, but the input is expected to be in the format that Delaunator outputs. The ES module variant (TriVis.mjs) depends on robust-predicates and containing-triangle, but the CommonJS, browser, and minified versions (lib/TriVis.cjs, lib/TriVis.js, and TriVis.min.js) come with these dependencies compiled in, and can be used standalone. The (source) TypeScript version is in TriVis.ts.

Usage

poly = triangularExpansion(del, qx, qy, obstructs, ilx = NaN, ily = NaN, irx = NaN, iry = NaN)

Parameters:

• del: The triangulation in the format that Delaunator outputs.
• qx, qy: The coordinates of the query point.
• obstructs: A callback that receives an edge id of the triangulation and must indicate whether it obstructs the view. Edges on the hull of the triangulation are always considered to be obstructing.
• ilx, ily, irx, iry: If given, i.e. not NaN, the coordinates of the left and right points restricting the viewing cone. The angles between these points and the query point should not be greater than 180°. If these arguments are not given, the visibility polygon is computed in all directions.

Return value:

An array of 4-element arrays, [lx, ly, rx, ry] with the coordinates of the left- and right-hand side end-points of the segments that make up the visibility polygon. Each triplet (lx, ly) (qx, qy) (rx, ry) forms a counter-clockwise triangle that is entirely visible from the query point. The segments are also ordered counter-clockwise around (qx, qy).

Changes

2.0.0

• Convert to TypeScript.
• Move built files to lib/.

1.0.1

• Update dependencies.
• Move test files to separate repository.

1.0.0

• Initial version.

Attributions

• The Triangular Expansion algorithm is adapted from Efficient Computation of Visibility Polygons, March 18, 2014, Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang, Alexander Kröller.
• Uses Vladimir Agafonkin's robust-predicates port of Jonathan Shewchuk's Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry.
• Ray-segment intersection computation adapted from Nicky Case's Sight & Light tutorial.
• The example image and initial idea for this library were inspired by Amit Patel's article on 2D visibility.