convex_hull/readme.md

凸包算法演示 (Convex Hull Demonstration)

这是一个交互式的凸包算法演示网页，支持同时比较 WebAssembly 和 JavaScript 实现的性能差异。 git

功能特点

• 支持手动输入点集数据
• 提供随机点集生成功能（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

在线演示

在线测试地址

性能对比

• WebAssembly 版本通常在处理大规模数据时（如30000点）表现更优,实际不是！！！！！
• JavaScript 版本在小规模数据时（如30点）性能足够

本地运行

由于使用了 WebAssembly，需要通过 Web 服务器运行此项目。可以使用以下方式：

使用 Python 启动简单的 HTTP 服务器
python -m http.server
或使用 Node.js 的 http-server
npx http-server

wasm 调用

  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
    }