liang-barsky

Liang-Barsky line clipping algorithm

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
liang-barsky
33111.0.53 years ago7 years agoMinified + gzip package size for liang-barsky in KB

Readme

Liang-Barsky line-clipping algorithm npm
Preview
Fast, destructive implemetation of Liang-Barsky line clipping algorithm. It clips a 2D segment by a rectangle.
This is an adaptation of the C++ code that impressed me by its simplicity.

API

Destructive
var a = [-10, -10], b = [10, 10];
clip(a, b, [-5, -5, 5, 5]); // returns 1 - "clipped"
console.log(a);             // [-5, -5]
console.log(b);             // [5, 5]

Non-destructive
var a  = [-10, -10], b  = [10, 10];
var an = a.slice(),  bn = b.slice();
clip(a, b, [-5, -5, 5, 5], an, bn); // returns 1 - "clipped"
console.log(an);              // [-5, -5]
console.log(bn);              // [5, 5]
console.log(a);               // [-10, -10]
console.log(b);               // [10, 10]

Return value is 1 if the line was clipped, and 0 if it lies completely outside of the provided bounding box.

Install

npm install -S liang-barsky

import clip from 'liang-barsky';
// or
var clip = require('liang-barsky');

Or just drop-in the file
<script src="path/to/liang-barsky.umd.js"></script>
<script>
  liangBarsky([0, 0], [10, 10], [0, 0, 5, 5]);
</script>

Performance

I ran a check against the Cohen-Sutherland algorithm implemented by @mourner for clipping just one segment. Though test include memory allocation, they are fair for the task at hand, since you can use the results in an equal manner after the invocation of the clipper.
npm run benchmark

liang-barsky x 136,671,492 ops/sec ±0.36% (90 runs sampled)
mapbox/lineclip x 9,030,039 ops/sec ±0.84% (86 runs sampled)
- Fastest is liang-barsky

Future plan

Implement a sub-routine for polylines. Loop through pairs, tracking in-out transitions.

License

MIT