Liang-Barsky 线段裁剪算法库

一个高性能的 Liang-Barsky 线段裁剪算法实现，专为需要大量图形裁剪计算的场景设计。

功能特点

• 🚀 高性能实现：采用多种优化技术，包括减少内存分配、内联计算、提前退出和减少属性访问
• 📦 多种数据类型支持：支持 number[]、Float32Array 和 Float64Array 类型
• 🔄 内存复用：支持结果数组复用，进一步减少内存分配开销
• 📚 批量处理：提供批量线段裁剪功能，减少重复计算开销
• ⚡ 可选验证：支持跳过输入验证以提升性能敏感场景的执行效率

安装

npm install liang-barsky-clipping

使用方法

基本使用

import { liangBarskyClipping } from 'liang-barsky-clipping';

// 定义线段 [x1, y1, x2, y2]
const segment = [50, 50, 450, 450];

// 定义裁剪窗口 [left, right, bottom, top]
const window = [100, 400, 100, 400];

// 执行裁剪
const result = liangBarskyClipping(segment, window);

if (result) {
  console.log('裁剪后的线段:', result); // [100, 100, 400, 400]
} else {
  console.log('线段完全不可见');
}

使用 TypedArray 提升性能

const segment = new Float32Array([50, 50, 450, 450]);
const window = new Float32Array([100, 400, 100, 400]);
const result = liangBarskyClipping(segment, window);

内存复用

// 预分配结果数组以复用内存
const resultBuffer = new Float32Array(4);
const result = liangBarskyClipping(segment, window, resultBuffer);

跳过验证提升性能

// 在性能敏感场景跳过输入验证
const result = liangBarskyClipping(segment, window, undefined, true);

批量处理

import { batchLiangBarskyClipping } from 'liang-barsky-clipping';

const segments = [
  [50, 50, 450, 450],
  [0, 0, 500, 500],
  [200, 200, 300, 300]
];

const window = [100, 400, 100, 400];
const results = batchLiangBarskyClipping(segments, window);

API 参考

liangBarskyClipping(segment, window, result?, skipValidation?)

执行单条线段的 Liang-Barsky 裁剪

参数:

• segment: 线段坐标数组 [x1, y1, x2, y2]
• window: 裁剪窗口 [left, right, bottom, top]
• result (可选): 用于存储结果的数组，可复用内存
• skipValidation (可选): 是否跳过输入验证，默认 false

返回值:

• 裁剪后的线段数组，如果完全不可见则返回 null

batchLiangBarskyClipping(segments, window)

批量处理多条线段裁剪

参数:

• segments: 线段数组的数组
• window: 裁剪窗口

返回值:

• 裁剪结果数组，每个元素为裁剪后的线段或 null

性能优化

1. 使用 TypedArray: 使用 Float32Array 或 Float64Array 替代普通数组
2. 内存复用: 通过 result 参数复用内存
3. 跳过验证: 在确保输入正确的前提下使用 skipValidation=true
4. 批量处理: 处理多条线段时使用批量接口

算法原理

Liang-Barsky 算法是一种参数化的线段裁剪算法，通过计算线段与裁剪窗口边界的交点参数值来确定可见部分。相比 Cohen-Sutherland 算法，Liang-Barsky 算法只需要进行一次线段与窗口的比较，因此效率更高。

该实现通过以下优化进一步提升性能：

• 减少内存分配
• 内联计算
• 提前退出条件判断
• 减少属性访问次数

许可证

MIT