# 凸包算法演示 (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
    }
```