91 lines
2.8 KiB
Markdown
91 lines
2.8 KiB
Markdown
# 凸包算法演示 (Convex Hull Demonstration)
|
||
|
||
这是一个交互式的凸包算法演示网页，支持同时比较 WebAssembly 和 JavaScript 实现的性能差异。
|
||
[git](https://git.kuraa.cc/kura/convex_hull)
|
||
|
||
## 功能特点
|
||
|
||
- 支持手动输入点集数据
|
||
- 提供随机点集生成功能（30/3000/10000/30000点）
|
||
- 可视化展示：
|
||
- 蓝色点表示输入的点集
|
||
- 红色线表示计算得出的凸包
|
||
- 双重实现对比：
|
||
- WebAssembly 实现
|
||
- 纯 JavaScript 实现（Graham Scan算法）
|
||
- 性能对比：
|
||
- 控制台输出两种实现的执行时间
|
||
- 支持大规模点集的性能测试
|
||
|
||
## 使用方法
|
||
|
||
1. 点集输入方式：
|
||
- 在文本框中手动输入点集，格式：`x1,y1;x2,y2;x3,y3;...`
|
||
- 使用随机生成按钮快速生成测试数据
|
||
|
||
2. 点击"计算凸包"按钮执行算法
|
||
- 自动进行 WebAssembly 和 JavaScript 两种实现的计算
|
||
- 在画布上显示结果
|
||
- 在控制台查看性能数据
|
||
|
||
## 技术实现
|
||
|
||
- 前端：原生 HTML + JavaScript
|
||
- 计算核心：
|
||
- WebAssembly 实现（通过 Emscripten 编译）
|
||
- JavaScript 实现（Graham Scan 算法）
|
||
- 可视化：Canvas 2D
|
||
|
||
## 在线演示
|
||
|
||
[在线测试地址](https://kuraa.cc/upload/convex_hull.html)
|
||
<iframe src="https://kuraa.cc/upload/convex_hull.html" width="80%" height="800" scrolling="auto"></iframe>
|
||
|
||
## 性能对比
|
||
|
||
- WebAssembly 版本通常在处理大规模数据时（如30000点）表现更优,实际不是！！！！！
|
||
- JavaScript 版本在小规模数据时（如30点）性能足够
|
||
|
||
## 本地运行
|
||
|
||
由于使用了 WebAssembly，需要通过 Web 服务器运行此项目。可以使用以下方式：
|
||
|
||
```bash
|
||
使用 Python 启动简单的 HTTP 服务器
|
||
python -m http.server
|
||
或使用 Node.js 的 http-server
|
||
npx http-server
|
||
```
|
||
|
||
|
||
## wasm 调用
|
||
```js
|
||
function callWasmConvexHull(points) {
|
||
//长度
|
||
var n = points.length;
|
||
var pointsPtr = Module._malloc(n * 8); //8字节一个点
|
||
|
||
for (let i = 0; i < n; i++) {
|
||
Module.setValue(pointsPtr + i * 8, points[i].x, 'i32');
|
||
Module.setValue(pointsPtr + i * 8 + 4, points[i].y, 'i32');
|
||
}
|
||
//多少点
|
||
var resultPtr = Module._malloc(n * 8);
|
||
var resultSizePtr = Module._malloc(4);
|
||
//调用wasm
|
||
Module._convexHull(pointsPtr, n, resultPtr, resultSizePtr);
|
||
var resultSize = Module.getValue(resultSizePtr, 'i32');
|
||
var resultPoints = [];
|
||
//读
|
||
for (let i = 0; i < resultSize; i++) {
|
||
var x = Module.getValue(resultPtr + i * 8, 'i32');
|
||
var y = Module.getValue(resultPtr + i * 8 + 4, 'i32');
|
||
resultPoints.push({ x: x, y: y });
|
||
}
|
||
// 释放
|
||
Module._free(pointsPtr);
|
||
Module._free(resultPtr);
|
||
Module._free(resultSizePtr);
|
||
return resultPoints
|
||
}
|
||
``` |