凸包(Convex Hull)可视化工具
基于 Andrew 单调链算法的动态凸包演示——在一片散点上展示压入(push)/弹出(pop)的构建过程,配合分步控制。直接在浏览器中运行。
伪代码
Press Run to animate the algorithm.
Time · Space
使用方法
- 1 点击 Run 为一组散点构建凸包。
- 2 观察单调链算法将各点压入(push),并在出现非左转时将其弹出(pop)。
- 3 使用 Shuffle 生成一组新的随机点,或逐步执行每一次操作。
- 4 绿色轮廓线即为最终得到的凸包。
为什么使用此工具
- 直观看到 Andrew 单调链算法如何分别构建下凸包和上凸包。
- 理解为什么会造成右转的点最终会被从链中剔除。
- 观察整个构建过程的时间复杂度为 O(n log n)——主要开销来自排序步骤。
- 完全在浏览器本地运行,无需注册,也无需上传任何文件。
常见问题
什么是凸包?
凸包是能够包含一组点的最小凸多边形——可以想象用一根橡皮筋绷紧包住所有的点,然后让它收缩到贴合边界的状态。
这个工具使用的是什么算法?
Andrew 单调链算法:先对所有点进行排序,然后通过将各点压入(push)来分别构建下凸包和上凸包,并弹出(pop)任何会形成非左转(即右转,顺时针方向)的点。
凸包算法的时间复杂度是多少?
为 O(n log n),主要由最初的排序步骤决定;链的实际构建过程本身是线性复杂度。Graham 扫描算法和 QuickHull 算法也具有相同的平均复杂度上界。
凸包有哪些用途?
常用于碰撞检测(collision detection)、形状分析、路径规划(pathfinding)、地理信息系统(GIS),以及作为许多几何算法的预处理步骤。
什么是 凸包(Convex Hull)可视化工具？
凸包可视化工具演示了如何找出包围一组点的最小凸多边形。它采用 Andrew 单调链算法:先对所有点排序,再分别构建下凸包(lower hull)和上凸包(upper hull),并弹出(pop)任何会形成非左转(non-left turn)的点。
凸包(Convex Hull)可视化工具 是 Zerethon Tools 提供的免费 算法 工具。基于 Andrew 单调链算法的动态凸包演示——在一片散点上展示压入(push)/弹出(pop)的构建过程,配合分步控制。直接在浏览器中运行。. 完全在浏览器中运行 — 无需注册，无需上传。
- 分类
- 算法
- 价格
- 免费
- 隐私
- 基于浏览器
- 注册
- 无需
隐私
除非另有说明，否则你的数据永远不会离开浏览器。凸包(Convex Hull)可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。
相关工具
冒泡排序可视化工具
带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。
打开工具插入排序可视化工具
动画演示插入排序算法，支持单步执行、速度调节、自定义输入数据，并实时显示比较/写入次数与伪代码高亮。完全在浏览器本地运行。
打开工具选择排序可视化工具
以动画方式演示选择排序（Selection Sort），提供逐步执行、速度调节、自定义输入数据、实时的比较/交换计数器以及伪代码展示。完全在浏览器本地运行。
打开工具归并排序可视化工具
带动画演示的归并排序模拟器，支持单步执行、速度调节、自定义输入数据、实时比较/写入计数器以及伪代码高亮显示。完全在浏览器中运行。
打开工具在 Zerethon Social 上创作、分享与成长
免费注册。赚取积分，收集成就，与全球创作者建立联系。