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.

kninnug/TriVis