>

>
1x
go to beginning previous frame pause play next frame go to end

A polygon is a plane figure that is bounded by a closed circuit composed of a finite sequence of straight line segments.


This visualization features a few computational geometry algorithms that can be carried out on simple (non-crossing) polygons with 3 or more non-collinear points, such as determining their perimeters and areas, determining concavity or convexity, determining whether a point is inside or outside, and to cut them with a simple line.


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

多边形的顶点可以按顺时针(CW)或逆时针(CCW)顺序排列。在这个可视化中,我们更喜欢使用CCW顺序(尽管以CW顺序绘制多边形也是可以接受的)。在底层,我们还将第一个顶点设置为最后一个顶点以简化实现。


请注意,我们限制绘制的多边形为简单多边形,即,没有边交叉。


多边形的顶点/角数存储在变量n中。由于多边形是一个封闭的电路,多边形的边数/边数也是n


Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

所有可用的操作都如常在左侧菜单中列出。


前两个是用于给出简单输入多边形的,接下来的五个是你可以在当前绘制的多边形上运行的计算几何算法。


Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

在这个可视化中,你可以绘制任何简单多边形(至少3个点),没有任何共线的点(实际上,我们可以修改我们的实现以允许共线的点,只是这会复杂化一些操作)。最小的这样的多边形是一个三角形。


你绘制的多边形可以是的(连接多边形内任意两点的线将保持在多边形内)或的。


如果你没有关闭循环(从最后一个顶点回到顶点0绘制一条边),我们将自动为你完成这个操作。


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

我们提供了一些示例多边形作为起点。


加载此可视化页面后,我们将随机选择示例多边形。

🕑

多边形的周长就是连续线段(多边形边)的长度(欧几里得距离)之和。


这个程序适用于凸多边形和凹多边形,运行时间为 O(n)。


那么我们现在就来计算当前绘制的多边形的 Perimeter

🕑

当多边形的顶点以环形方式(顺时针或逆时针)给出时,我们可以使用鞋带公式来计算其面积。


这个鞋带公式返回的面积,是由边缘端点定义的向量的交叉积的一半。


这个公式非常通用,因为它适用于凸多边形和凹多边形。它可以在O(n)中计算。


那么我们现在就来计算当前绘制的多边形的 Area

🕑

如果我们在多边形内部的任意两个不同点之间画一条线,并且线始终保持在多边形内部,那么这个多边形就被称为多边形。否则,多边形被称为


有一种更简单的方法可以检查给定的多边形(假设没有三个共线的点)是否为凸的,而不需要使用上述的直接定义。我们可以检查多边形的所有三个连续顶点是否形成同一种类型的转弯(全部为CCWs或全部为CWs)。这个检查显然是O(n)。


言归正传,让我们检查当前绘制的多边形 IsConvex

🕑

有几种算法可以检查一个点(pt1)是否在多边形内。我们认为最稳健的算法是绕数算法,它计算多边形的每条边/侧与pt1为原点所成的角度之和。由于只有n个这样的角度,所以这个检查也以O(n)运行。


输入的简单多边形可以像当前显示的 "MAZE" 测试用例那样复杂。尝试 InsidePolygonOutsidePolygon 测试用例。


探索模式中,您将被要求提供被测试点(pt1)作为此操作的额外输入。

🕑

我们可以用由两点 (pt1, pt2) 定义的直线切割一个凸多边形。切割的结果是两个较小但也是凸的多边形。此算法当前返回切割线 (pt1, pt2) '左侧'的较小多边形。


请注意,尽管可能,但切割凹多边形更复杂,因为它可能会产生超过两个(可能是退化的)多边形。我们在这个可视化中允许这样的操作,但在实际实现中必须格外小心。


尝试 Left Side 查看此例程的默认版本,以及 Right Side 我们交换 pt1 和 pt2 以获取切割的另一侧。


在探索模式中,您将被要求提供两个点来定义切割线 (pt1 和 pt2) 作为此操作的额外输入(为避免退化情况,这两个点应放置在不同的位置)。


此例程也以 O(n) 运行。

🕑

VisuAlgo中还有一个计算几何可视化:凸包


您现在可以使用这些算法在多边形程序中解决一些编程练习:UVa 11265 - Sultan的问题Kattis - robotprotection


您可以使用/修改我们的多边形算法实现代码:
polygon.cpp | py | java | ml


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Visualisation Scale

Edit Polygon

示例多边形

周长(P)

面积(P)

isConvex(P)

inPolygon(pt, P)

cutPolygon(ln,P)

>

1.0x (Default)

0.5x (Minimal Details)

Convex

Concave

Mountain

Maze

Star

Goalkeeper

Fish

关于 团队 使用条款
隐私政策

关于

VisuAlgo最初由副教授Steven Halim于2011年构思,旨在通过提供自学、互动式学习平台,帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年,VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

虽然VisuAlgo主要面向新加坡国立大学(NUS)的学生,包括各种数据结构和算法课程(例如CS1010/等价课程,CS2040/等价课程(包括IT5003),CS3230,CS3233和CS4234),但它也是全球好奇心的宝贵资源,促进在线学习。

最初,VisuAlgo并不适用于智能手机等小触摸屏,因为复杂的算法可视化需要大量的像素空间和点击拖动交互。为了获得最佳用户体验,建议使用最低分辨率为1366x768的屏幕。然而,自2022年4月以来,VisuAlgo的移动(精简)版本已经推出,使得在智能手机屏幕上使用VisuAlgo的部分功能成为可能。

VisuAlgo仍然在不断发展中,正在开发更复杂的可视化。目前,该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器,其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成,并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统,它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重,计算机科学教师可以显著提高学生对这些基本概念的掌握程度,因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言:英语、中文和印尼语。此外,我们还用各种语言撰写了关于VisuAlgo的公开笔记,包括印尼语、韩语、越南语和泰语:

id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1
CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1
Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2
CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

本科生研究人员 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

最后一年项目/ UROP学生 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han, Tan Chee Heng
Aug 2024-Apr 2025: Edbert Geraldy Cangdinata, Huang Xing Chen, Nicholas Patrick

List of translators who have contributed ≥ 100 translations can be found at statistics page.

致谢
NUS教学与学习发展中心(CDTL)授予拨款以启动这个项目。在2023/24学年,Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

使用条款

VisuAlgo慷慨地向全球计算机科学界提供免费服务。如果您喜欢VisuAlgo,我们恳请您向其他计算机科学学生和教师宣传它的存在。您可以通过社交媒体平台(如Facebook、YouTube、Instagram、TikTok、Twitter等)、课程网页、博客评论、电子邮件等方式分享VisuAlgo。

数据结构与算法(DSA)的学生和教师可以直接在课堂上使用本网站。如果您从本网站截取屏幕截图或视频,可以在其他地方使用,但请引用本网站的URL(https://visualgo.net)和/或下面的出版物列表作为参考。但请不要下载VisuAlgo的客户端文件并将其托管在您的网站上,因为这构成了抄袭行为。目前,我们不允许他人分叉此项目或创建VisuAlgo的变体。个人使用离线副本的客户端VisuAlgo是可以接受的。

请注意,VisuAlgo的在线测验组件具有重要的服务器端元素,保存服务器端脚本和数据库并不容易。目前,普通公众只能通过“培训模式”访问在线测验系统。“测试模式”提供了一个更受控制的环境,用于在新加坡国立大学的真实考试中使用随机生成的问题和自动验证。


出版物列表

这项工作曾在2012年国际大学生程序设计竞赛(波兰,华沙)的CLI研讨会上和2012年国际信息学奥林匹克竞赛(意大利,锡尔米奥内-蒙蒂基亚里)的IOI会议上展示过。您可以点击此链接阅读我们2012年关于该系统的论文(当时还没有称为VisuAlgo),以及此链接阅读2015年的简短更新(将VisuAlgo与之前的项目关联起来)。


错误报告或新功能请求

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误,或者您想要请求新功能,请联系Steven Halim副教授。他的联系方式是将他的名字连接起来,然后加上gmail dot com。

隐私政策

版本 1.2 (更新于2023年8月18日星期五)。

自2023年8月18日(星期五)起,我们不再使用 Google Analytics。因此,我们现在使用的所有 cookies 仅用于此网站的运营。即使是首次访问的用户,烦人的 cookie 同意弹窗现在也已关闭。

自2023年6月7日(星期五)起,由于 Optiver 的慷慨捐赠,全世界的任何人都可以自行创建一个 VisuAlgo 账户,以存储一些自定义设置(例如,布局模式,默认语言,播放速度等)。

此外,对于 NUS 学生,通过使用 VisuAlgo 账户(一个 NUS 官方电子邮件地址,课堂名册中的学生姓名,以及在服务器端加密的密码 - 不存储其他个人数据),您同意您的课程讲师跟踪您的电子讲义阅读和在线测验培训进度,这是顺利进行课程所必需的。您的 VisuAlgo 账户也将用于参加 NUS 官方的 VisuAlgo 在线测验,因此,将您的账户凭据传递给他人代您进行在线测验构成学术违规。课程结束后,您的用户账户将被清除,除非您选择保留您的账户(OPT-IN)。访问完整的 VisuAlgo 数据库(包含加密密码)的权限仅限于 Halim 教授本人。

对于全球其他已经给 Steven 写过信的 CS 讲师,需要一个 VisuAlgo 账户(您的(非 NUS)电子邮件地址,您可以使用任何显示名称,以及加密密码)来区分您的在线凭据与世界其他地方。您的账户将具有 CS 讲师特定的功能,即能够查看隐藏的幻灯片,这些幻灯片包含了在隐藏幻灯片之前的幻灯片中提出的问题的(有趣的)答案。您还可以访问 VisuAlgo 在线测验的 Hard 设置。您可以自由地使用这些材料来增强您的数据结构和算法课程。请注意,未来可能会有其他 CS 讲师特定的功能。

对于任何拥有 VisuAlgo 账户的人,如果您希望不再与 VisuAlgo 工具有关联,您可以自行删除您的账户。