基于Graham扫描算法的MATLAB凸包计算工具

资 源 简 介

本项目实现了高效的二维点集凸包计算，采用Graham扫描算法替代内置函数，支持随机/自定义点集输入，并提供完整的算法可视化流程与凸包顶点输出。

详 情 说 明

基于Graham扫描算法的二维点集最小凸包计算系统

项目介绍

本项目实现了一个基于Graham扫描算法的二维平面点集凸包计算系统。该系统能够高效地计算给定点集的最小凸包，并提供完整的算法流程可视化，帮助用户深入理解Graham扫描算法的执行过程。系统采用自研算法替代MATLAB内置函数，具有更好的透明度和教学价值。

功能特性

• 核心算法实现：完整实现Graham扫描算法，包括极角排序、向量叉积判断和栈数据结构管理
• 多模式输入支持：支持随机点集生成、手动输入和文件导入三种数据输入方式
• 可视化展示：提供原始散点图、凸包边界连线图和算法执行过程动态演示
• 性能分析：输出计算时间、顶点数量统计等性能指标
• 详细日志：生成算法执行过程的详细步骤说明

使用方法

基本操作流程

1. 准备输入数据：

- 随机生成：指定点数和坐标范围自动生成测试点集 - 手动输入：通过矩阵格式 [x1 y1; x2 y2; ...; xn yn] 输入坐标 - 文件导入：从文本文件或MAT文件加载点集数据

1. 执行凸包计算：

- 运行主程序，系统自动完成点集预处理、极角排序和凸包构建 - 实时显示算法执行状态和进度信息

1. 查看结果：

- 获取凸包顶点序列（顺时针排列的坐标矩阵） - 查看可视化图形结果和性能统计报告 - 分析算法执行日志了解详细计算过程

示例代码

% 随机生成50个点在[0,100]范围内的点集 points = rand(50, 2) * 100;

% 执行凸包计算 convex_hull = main(points);

系统要求

• 软件环境：MATLAB R2018b或更高版本
• 必要工具箱：基础MATLAB环境即可运行，无需额外工具箱
• 硬件要求：普通PC配置即可满足计算需求

文件说明

主程序文件实现了系统的核心功能，包括点集数据的接收与验证、Graham扫描算法的完整执行流程、可视化图形的生成与展示、性能指标的统计与分析。该文件整合了算法实现的所有关键模块，负责协调各功能组件的协同工作，确保从数据输入到结果输出的完整处理链路。同时，它还提供了用户交互界面和结果导出功能，使整个系统能够以统一的方式运行和展示。