跳到主要内容
Z

凸包(Convex Hull)可视化工具

基于 Andrew 单调链算法的动态凸包演示——在一片散点上展示压入(push)/弹出(pop)的构建过程,配合分步控制。直接在浏览器中运行。

免费 无需注册 客户端运行 注重隐私 Updated

/

伪代码

Press Run to animate the algorithm.

使用方法

  1. 1 点击 Run 为一组散点构建凸包。
  2. 2 观察单调链算法将各点压入(push),并在出现非左转时将其弹出(pop)。
  3. 3 使用 Shuffle 生成一组新的随机点,或逐步执行每一次操作。
  4. 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)的点。

功能特性

逐步动画演示

观看点被排序、转向被测试的过程中凸包逐步构建的样子。

复杂度

时间复杂度:O(n log n)(由排序主导)。空间复杂度:O(n)。

100% 隐私保护

完全在你的浏览器中运行——不会上传任何数据。

示例

Input

points incl. one interior point

Output

hull = outer points only; interior point excluded

常见使用场景

  1. 1

    计算几何

    了解许多几何算法所使用的基础凸包结构。

  2. 2

    碰撞检测与边界计算

    计算点云周围的紧密凸边界。

  3. 3

    学习方向判定

    理解用于构建凸包的左转/右转判定方法。

概要

Zerethon 的凸包可视化工具通过动画演示如何在浏览器中找到包围一组点的最小凸多边形,使用的是 O(n log n) 算法(例如 Graham 扫描法或 Andrew 单调链算法——其复杂度主要由初始排序决定)。内部点会被排除在凸包之外;所需空间为 O(n)。

分类
算法
价格
免费
隐私
基于浏览器
注册
无需

参考资料

隐私

除非另有说明，否则你的数据永远不会离开浏览器。凸包(Convex Hull)可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。

相关工具

冒泡排序可视化工具

带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。

打开工具

插入排序可视化工具

动画演示插入排序算法，支持单步执行、速度调节、自定义输入数据，并实时显示比较/写入次数与伪代码高亮。完全在浏览器本地运行。

打开工具

选择排序可视化工具

以动画方式演示选择排序（Selection Sort），提供逐步执行、速度调节、自定义输入数据、实时的比较/交换计数器以及伪代码展示。完全在浏览器本地运行。

打开工具

归并排序可视化工具

带动画演示的归并排序模拟器，支持单步执行、速度调节、自定义输入数据、实时比较/写入计数器以及伪代码高亮显示。完全在浏览器中运行。

打开工具

在 Zerethon Social 上创作、分享与成长

免费注册。赚取积分，收集成就，与全球创作者建立联系。

免费试用 Zerethon