box-intersect

Any dimensional box intersection

Last updated 2 years ago by
mikolalysenko .

MIT ·
Repository ·
Bugs ·
Original npm ·
Tarball ·
package.json
$ cnpm install box-intersect

SYNC missed versions from
official npm registry.

This modules finds all intersection in a set of n boxes in d-dimensions, or between a pair of sets with n and m boxes respectively. The time taken is O((n+m) log^d(n+m)) and the algorithm uses a temporary scratch memory of size O(n+m). This memory is pooled so that after the first execution no additional memory is allocated. Some possible applications of this library include:

- Collision detection
- Polygon clipping
- Batched box stabbing queries
- Mesh boolean operations (CSG)

The algorithm in this package is based on the one described in the following paper:

A detailed experimental analysis of the performance of this module as well as comparisons with other libraries for box intersection can be found in the following repository:

For more information on this problem, please see the following series of blog posts:

Here is how to detect all pairs of overlapping boxes in a single set of boxes:

```
var boxIntersect = require('box-intersect')
//Boxes are listed as flattened 2*d length arrays
var boxes = [
[1, 1, 2, 2], //Interpretation: [minX, minY, maxX, maxY]
[0, -1, 3, 2],
[2, 1, 4, 5],
[0.5, 3, 1, 10]
]
//Default behavior reports list of intersections
console.log('overlaps:', boxIntersect(boxes))
//Note: Boxes are closed
//Can also use a visitor to report all crossings
var result = boxIntersect(boxes, function(i,j) {
console.log('overlap:', boxes[i], boxes[j])
//Can early out by returning any value
if(i === 2 || j === 2) {
return 2
}
})
console.log('early out result:', result)
```

```
overlap: [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ]
overlap: [ 1, 1, 2, 2 ] [ 0, -1, 3, 2 ]
overlap: [ 1, 1, 2, 2 ] [ 2, 1, 4, 5 ]
early out result: 2
```

You can also detect all intersections between two different sets of boxes:

```
var boxIntersect = require('box-intersect')
//Again, boxes are given as flattened lists of coordinates
var red = [
[0, 0, 0, 8, 1, 1], //Format: [minX, minY, minZ, maxX, maxY, maxZ]
[0, 0, 0, 1, 8, 1],
[0, 0, 0, 1, 1, 8]
]
var blue = [
[5, 0, 0, 6, 10, 10],
[0, 5, 0, 10, 6, 10],
[0, 0, 5, 10, 10, 10]
]
//Report all crossings
console.log('crossings=', boxIntersect(red, blue))
//Again can use a visitor:
boxIntersect(red, blue, function(r, b) {
console.log('overlap:', red[r], blue[b])
})
```

```
crossings= [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ] ]
overlap: [ 0, 0, 0, 8, 1, 1 ] [ 5, 0, 0, 6, 10, 10 ]
overlap: [ 0, 0, 0, 1, 8, 1 ] [ 0, 5, 0, 10, 6, 10 ]
overlap: [ 0, 0, 0, 1, 1, 8 ] [ 0, 0, 5, 10, 10, 10 ]
```

Using npm, just run the following command:

```
npm install box-intersect
```

This module works in any reasonable CommonJS environment, such as browsersify, iojs or node.js.

```
var boxIntersect = require('box-intersect')
```

`boxIntersect(boxes[, otherBoxes, visit])`

Finds all pairs intersections in a set of boxes. There are two basic modes of operation for this function:

`complete`

which detects all pairs of intersections within a single set of boxes`bipartite`

which detects pairs of intersections between two different sets of boxes

The parameters to the function are as follows:

`boxes`

is a list of boxes. Boxes are represented as length 2*d arrays where the first d-components are the lower bound of the box and then the next d components are the upper bound.`otherBoxes`

is an optional list of boxes which`boxes`

is tested against. If not specified, then the algorithm will report self intersections in`boxes`

`visit(i,j)`

is a callback which is called once for each overlapping pair of boxes. If`visit`

returns any value not equal to`undefined`

, then the search is terminated immediately and this value is returned. If`visit`

is not specified, then a list of intersecting pairs is returned.

**Returns** If `visit`

was specified, then the last returned value of `visit`

. Otherwise an array of pairs of intersecting boxes.

**Note** The boxes are treated as cartesian products of *closed* intervals. For example, the boxes `[1,1,2,2]`

and `[0,0,1,1]`

will be reported as intersecting by this module.

(c) 2014 Mikola Lysenko. MIT License

- 1.0.2 ... latest (2 years ago)

Maintainers (1)

Downloads

Today
2

This Week
147

This Month
1,668

Last Day
78

Last Week
556

Last Month
1,537

Dependencies (2)

- bit-twiddle ^1.0.2
- typedarray-pool ^1.1.0

Dev Dependencies (6)

- array-shuffle ^1.0.0
- dup ^1.0.0
- guarded-array ^1.0.0
- iota-array ^1.0.0
- tape ^3.4.0
- uniq ^1.0.1

Dependents (19)

Copyright 2014 - 2017 © taobao.org |