# slab-decomposition

> Slab decomposition data structure for 2D vertical ray queries

Latest version **1.0.3** (published 2021-07-15) · MIT license · 0 weekly downloads

## Install

```sh
npm install slab-decomposition
pnpm add slab-decomposition
yarn add slab-decomposition
bun add slab-decomposition
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.3 |
| Published | 2021-07-15 |
| First published | 2014-03-01 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 3 |
| Unpacked size | 21.5 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 6 |
| Author | Mikola Lysenko |
| Maintainers | mikolalysenko |
| Keywords | slab, decomposition, ray, query, line, segment, 2d |

## Links

- npm: https://www.npmjs.com/package/slab-decomposition
- Repository: https://github.com/mikolalysenko/slab-decomposition
- Issues: https://github.com/mikolalysenko/slab-decomposition/issues
- npm.io page: https://npm.io/package/slab-decomposition

## Dependencies (3)

- [robust-orientation](https://npm.io/package/robust-orientation.md) ^1.1.3
- [binary-search-bounds](https://npm.io/package/binary-search-bounds.md) ^2.0.0
- [functional-red-black-tree](https://npm.io/package/functional-red-black-tree.md) ^1.0.0

## Alternatives

- [gamedig](https://npm.io/package/gamedig.md) — 29.3K weekly downloads
- [join-monster](https://npm.io/package/join-monster.md) — 12.8K weekly downloads
- [masked](https://npm.io/package/masked.md) — 5.5K weekly downloads
- [@comunica/actor-query-process-explain-logical](https://npm.io/package/@comunica/actor-query-process-explain-logical.md) — 4.7K weekly downloads
- [@veracity/vui](https://npm.io/package/@veracity/vui.md) — 4.6K weekly downloads

## Recent versions

- 1.0.3 (latest) — 2021-07-15
- 1.0.2 — 2014-09-19
- 1.0.1 — 2014-03-30
- 1.0.0 — 2014-03-30
- 0.0.0 — 2014-03-01

## README

slab-decomposition
==================
Given a collection of line segments, constructs a slab decomposition for the purpose of point location queries. This implementation uses a functional red-black tree to store the slabs, requires O(n log(n)) space and answers vertical ray queries in O(log(n)) time.

# Example

```javascript
var makeSlab = require("slab-decomposition")
var slabs = makeSlab([
  [[0, 0], [10, 10]],
  [[10,10], [20, 0]],
  [[5, 5], [20, 0]]
])

for(var i=-10; i<10; ++i) {
  console.log(slabs.castUp([i, -1]))
}
```

# Install

```
npm install slab-decomposition
```

# API

## Constructor

### `var slabs = require("slab-decomposition")(segments)`
Constructs a slab decomposition from the segments

* `segments` is a collection of line segments which only overlap at their end points

**Returns** A slab decomposition data structure

## Methods

### `slabs.castUp(point)`
Casts a vertical ray from `point` going upward along `[0,1]`.  Returns the index of the first segment hit.

* `point` is the base point of the ray

**Returns** The index of the first segment hit by point, otherwise -1 if no segment intersects the ray.

# Credits
(c) 2014 Mikola Lysenko. MIT License

---
_Source: https://npm.io/package/slab-decomposition · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._