【文件属性】：
文件名称：isect:线段相交检测库
文件大小：250KB
文件格式：ZIP
更新时间：2021-05-06 04:20:15
brute-force computational-geometry segments sweep-line bentley-ottmann
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撰写的“计算几何，算法和应用”一书。 它确实支持退化的案例，尽管阅读限制以了解更多信息。
蛮力算法
这是“天真”的实现，其中将每个段与所有其他段进行比较，因此具有O（n * n）性能。
尽管它很幼稚，但是在有数千条线和数百万个交点的情况下，它的运行速度比Bentley-Ottmann算法快得多。 这种情况在基于力的图形绘制中很常见，其中“
【文件预览】：
isect-master
----.travis.yml(36B)
----sweep.js(8KB)
----rollup.config.js(863B)
----index.js(117B)
----package.json(991B)
----perf()
--------index.js(4KB)
--------generators.js(4KB)
--------perf-chart.js(1KB)
----.eslintrc.json(123B)
----test()
--------findIntersections.js(9KB)
----brute.js(2KB)
----LICENSE(1KB)
----package-lock.json(157KB)
----src()
--------sweepStatus.js(11KB)
--------createEventQueue.js(523B)
--------geom.js(2KB)
--------SweepEvent.js(259B)
--------intersectSegments.js(796B)
----.npmignore(13B)
----index.d.ts(296B)
----rollup.config-min.js(681B)
----.gitignore(290B)
----demo()
--------interactive()
----bush.js(3KB)
----README.md(9KB)
----build()
--------isect.min.js(17KB)
--------isect.js(57KB)
--------isect.min.js.map(85KB)
--------isect.module.js(53KB)
--------isect.js.map(108KB)