anvaka/isect
GitHub: anvaka/isect
一个JavaScript线段交叉点检测库，提供扫描线、暴力、空间索引三种算法以适应不同数据密度和性能需求。
Stars: 279 | Forks: 18
# isect - 交叉点检测库 [](https://github.com/anvaka/isect/actions/workflows/tests.yaml)
该库允许您在给定的线段集合中找出所有交叉点。
[](https://anvaka.github.io/isect/)
[在线试用演示](https://anvaka.github.io/isect/)
# 算法
该库实现了三种算法
## Bentley-Ottmann 扫描线算法
该算法的性能为 `O(n*log(n) + k*log(n))`，其中 `n` 是线段数量，`k` 是交叉点数量。
当您拥有大量线段且交叉点不多时（更具体地说是 `k = o(n^2/log(n))`），首选此方法。
该算法遵循 Mark de Berg、Otfried Cheong、Marc van Kreveld 和 Mark Overmars 合著的《Computation Geometry, Algorithms and Applications》一书。它确实支持退化情况，但请阅读限制部分以了解更多信息。
[](https://anvaka.github.io/isect/?isAsync=true&p0=12&p1=40&generator=complete&algorithm=sweep&stepsPerFrame=1)
## 暴力算法
这是一个“朴素”的实现，即把每条线段与所有其他线段进行比较，因此性能为 O(n*n)。
尽管它很朴素，但在只有几千条线段却有数百万个交叉点的情况下，它比 Bentley-Ottmann 算法快得多。这种场景在力导向图绘制中很常见，即“毛球”由几千条线组成。
[](https://anvaka.github.io/isect/?isAsync=true&p0=12&p1=40&generator=complete&algorithm=brute&stepsPerFrame=1)
## "Bush" 算法
该算法由 [@mourner](https://twitter.com/mourner/status/1049325199617921024) 和 [@dy](https://github.com/anvaka/isect/issues/1) 建议。
它使用 [mourner/flatbush](https://github.com/mourner/flatbush) 作为线段的空间索引，然后遍历每条线段，检查重叠的包围盒。
直观地看，该算法的最坏情况性能与暴力算法相当。当每条线段都与其他所有线段重叠时，我们应该预期会有 `O(n^2)` 次操作。然而，在实践中，该算法 beats 了 `Bentley-Ottman` 和 `Brute force` 方法。
它的美在于其简单性。它能很好地适应稀疏和密集的线段分布。
您也可以在下面找到性能测试套件，以便您自行决定。我绝对会将此算法作为我的默认选择。
## 性能
基准测试代码[在此处可用](https://github.com/anvaka/isect/blob/master/perf/index.js)。每秒操作数越高越好！
### K12 图
[](https://anvaka.github.io/isect/?isAsync=false&p0=12&p1=40&generator=complete&algorithm=brute&stepsPerFrame=1)
* Sweep: Circular lines 12x40 x 1,069 ops/sec ±1.98% (91 runs sampled)
* **Brute: Circular lines 12x40 x 7,463 ops/sec ±3.01% (76 runs sampled)**
* Bush: Circular lines 12x40 x 5,678 ops/sec ±2.20% (80 runs sampled)
该图只有 `66` 条唯一线段和 `313` 个唯一交叉点。暴力算法比扫描线快 7 倍，紧随其后的是
### 100 条随机线
[](https://anvaka.github.io/isect/?isAsync=false&p0=100&p1=40&generator=random&algorithm=brute&stepsPerFrame=1)
在此演示中，100 条线是在边长为 42px 的方框内随机采样的。
* Sweep: 100 Random lines lines in 42px box x 277 ops/sec ±1.20% (87 runs sampled)
* **Brute: 100 Random lines lines in 42px box x 3,606 ops/sec ±3.61% (74 runs sampled)**
* Bush: 100 Random lines in 42px box x 3,314 ops/sec ±2.66% (83 runs sampled)
再一次，暴力算法胜出。暴力算法与 Bush 之间的差距缩小了。扫描线排在最后。
### 稀疏交叉点
[](https://anvaka.github.io/isect/?isAsync=false&p0=50&p1=40&generator=sparse&algorithm=sweep&stepsPerFrame=1)
* Sweep: 2,500 sparse lines x 156 ops/sec ±0.97% (80 runs sampled)
* Brute: 2,500 sparse lines x 13.62 ops/sec ±0.91% (38 runs sampled)
* **Bush: 2,500 sparse lines x 592 ops/sec ±1.05% (93 runs sampled)**
现在 Bush 算法以巨大优势胜出。Bentley-Ottman 位居第二，暴力算法排在最后。
### 平行倾斜线
[](https://anvaka.github.io/isect/?isAsync=false&p0=1000&p1=40&generator=parallelSlanted&algorithm=sweep&stepsPerFrame=1)
* **Sweep: 1000 slanted, not intersect x 622 ops/sec ±1.23% (91 runs sampled)**
* Brute: 1000 slanted, not intersect x 230 ops/sec ±2.37% (87 runs sampled)
* Bush: 1000 slanted, not intersect x 243 ops/sec ±1.07% (87 runs sampled)
在这个例子中，线太多，且它们都不相交。此外，大多数矩形包围盒确实相交，这给 `bush` 算法增加了更多工作。
# 用法
从 npm 安装该模块：
```
npm i isect
```
或从 CDN 下载：
```
```
如果您从 CDN 下载，该库将在 `isect` 全局名称下可用。
## 基本用法
以下代码检测数组中线段之间的所有交叉点：
```
var isect = require('isect');
// Prepare the library to detect all intersection
var detectIntersections = isect.bush([{
from: {x: 0, y: 0},
to: {x: 10, y: 10}
}, {
from: {x: 0, y: 10},
to: {x: 10, y: 0}
}]);
// Detect them all, operation is synchronous.
var intersections = detectIntersections.run();
console.log(intersections);
// Prints:
//
// [ { point: { x: 5, y: 5 }, segments: [ [Object], [Object] ] } ]
//
// array of segments contain both segments.
```
## 暴力算法与扫描线算法
您也可以使用不同的算法运行上述示例。只需将 `.bush()` 更改为 `.sweep()`（以运行 Bentley-Ottman）或 `.brute()`（以尝试暴力算法）：
```
var isect = require('isect');
// Prepare the library to detect all intersection
var bruteForce = isect.brute([{
from: {x: 0, y: 0},
to: {x: 10, y: 10}
}, {
from: {x: 0, y: 10},
to: {x: 10, y: 0}
}]);
var intersections = bruteForce.run();
console.log(intersections);
// do the same with sweep line:
var sweepLine = isect.sweep([{
from: {x: 0, y: 0},
to: {x: 10, y: 10}
}, {
from: {x: 0, y: 10},
to: {x: 10, y: 0}
}]);
var intersections = sweepLine.run();
console.log(intersections);
```
所有算法都有相同的 API。在下面的每个示例中，您可以将 `.bush()` 替换为 `.sweeep()` 或 `.brute()` —— 只需注意那些指出 API 差异的说明。
## 提前停止
如果您不关心所有交叉点，但想知道是否至少有一个交叉点，您可以传递一个 `onFound()` 回调并请求库在找到交叉点后立即停止：
```
var intersections = isect.bush([/* array of segments */], {
onFound(point, segments) {
// `point` is {x, y} of the intersection,
// `segments` are intersecting segments.
// If you return true from this method, no further processing will be done:
return true; // yes, stop right now!
}
});
```
## 异步工作流
如果您想让浏览器有时间处理用户输入，将算法分成块可能是理想的（这样 UI 线程就不会被淹没）。您可以通过调用算法实例的 `.step()` 方法来做到这一点：
```
var detector = isect.bush([/* array of segments */]);
// instead of detector.run(), we do:
var isDone = detector.step()
// isDone will be set to true, once the algorithm is completed.
```
这正是我如何进行算法逐步动画演示的方式：
[](https://anvaka.github.io/isect/?isAsync=true&p0=12&p1=40&generator=complete&algorithm=sweep&stepsPerFrame=1)
[点击这里](https://anvaka.github.io/isect/?isAsync=true&p0=12&p1=40&generator=complete&algorithm=sweep&stepsPerFrame=1)查看其实际效果。
## 限制
扫描线算法易受浮点舍入误差的影响。有可能构造一个包含近乎水平线的示例，导致其失败。
虽然扫描线实现检测 `point-segment`（点-线段）重叠，但我没有实现 `point-point`（点-点）重叠。即，输入数组中不与任何线段重叠的相同点不会被报告。
# 其他
* 演示的源代码[在此处可用](https://github.com/anvaka/isect/tree/master/demo/interactive)。
* 扫描线算法需要一个二叉搜索树。为此我使用了 [w8r/splay-tree](https://github.com/w8r/splay-tree)。非常喜欢这个库！
我也尝试过 AVL 树，但发现其性能比伸展树差。
* 如果您需要更高精度的扫描线，请考虑移植此库以使用 [decimal.js](https://github.com/MikeMcl/decimal.js-light)。
* 我非常希望在 JavaScript 中实现更快的交叉算法。
如果您知道任何算法 - 请分享。特别是这篇论文 [An optimal algorithm for finding segments intersections](http://club.pdmi.ras.ru/moodle/file.php/15/Materials/p211-balaban.pdf) 看起来非常有前途！
它们的运行时间是 `O(n * log(n) + k)`，应该比 Bentley-Ottmann 更快。
# 许可证
MIT
# 感谢！
希望您喜欢这个库。如果您有任何反馈，请随时 ping 我 (anvaka@gmail.com 或 https://twitter.com/anvaka)。
标签：Bentley-Ottmann算法, Flatbush, JavaScript库, MITM代理, Webhook, 二维几何, 力导向图, 图形学, 扫描线算法, 数学库, 数据可视化, 暴力算法, 碰撞检测, 空间索引, 算法库, 线段相交检测, 自定义脚本, 计算几何