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.
In this visualization, you can edit the currently displayed simple polygon (at least 3 points) into any other valid simple polygon, without any collinear points (actually, it is possible to modify our implementation to allow collinear points, just that it will complicate a few operations). The smallest such polygon is a triangle.
The polygon that you draw can be either convex (line connecting any two points inside the polygon will remain inside the polygon) or concave.
If you do not close the loop (draw an edge from last vertex back to vertex 0), we will do that automatically for you.
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.
We provide a few example polygons as a starting point.
Upon loading this visualization page, we will randomize the chosen example polygon.
Note that some of these example polygons indeed already have a few collinear points to showcase some edge cases, making some of these example polygons a bit hard to edit.
多边形的周长就是连续线段（多边形边）的长度（欧几里得距离）之和。
这个程序适用于凸多边形和凹多边形，运行时间为 O(n)。
那么我们现在就来计算当前绘制的多边形的 。
当多边形的顶点以环形方式（顺时针或逆时针）给出时，我们可以使用鞋带公式来计算其面积。
这个鞋带公式返回的面积，是由边缘端点定义的向量的交叉积的一半。
这个公式非常通用，因为它适用于凸多边形和凹多边形。它可以在O(n)中计算。
那么我们现在就来计算当前绘制的多边形的 。
如果我们在多边形内部的任意两个不同点之间画一条线，并且线始终保持在多边形内部，那么这个多边形就被称为凸多边形。否则，多边形被称为凹。
有一种更简单的方法可以检查给定的多边形（假设没有三个共线的点）是否为凸的，而不需要使用上述的直接定义。我们可以检查多边形的所有三个连续顶点是否形成同一种类型的转弯（全部为CCWs或全部为CWs）。这个检查显然是O(n)。
言归正传，让我们检查当前绘制的多边形 。
There are a few algorithms for checking if a point (pt1) is inside a polygon or not. We reckon the most robust algorithm is the Winding Number algorithm that computes the sum of angles subtended by each edge/side of the polygon with pt1 as the origin. As there are only n such angles, this check also runs in O(n).
The input simple polygon can be as complicated as the currently displayed "MAZE" test case. Try , , or test cases.
In Exploration Mode, you will be asked to provide the tested point (pt1) as additional input of this operation.
We can cut a convex polygon with a straight line defined by two points (pt1, pt2). The result of the cut are two smaller but also convex polygons. This algorithm currently returns the smaller polygon on 'the left side' of the cutting vector (pt1 → pt2).
Note that although possible, cutting a Concave polygon is more complicated as it may result in more than two (and possibly degenerate) polygons. We allow such operation in this visualization but extra care must be exercised in the actual implementations.
Try to see the default version of this routine and where we swap pt1 and pt2 to get the other side of the cut.
In Exploration Mode, you will be asked to provide two points to define the cut line (pt1 and pt2) as additional input of this operation (to avoid degenerate case, these two points should be placed at different locations).
This routine also runs in 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.
Edit Polygon
示例多边形
周长(P)
面积(P)
isConvex(P)
inPolygon(pt, P)
cutPolygon（ln，P）