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.
多边形的顶点可以按顺时针（CW）或逆时针（CCW）顺序排列。在这个可视化中，我们更喜欢使用CCW顺序（尽管以CW顺序绘制多边形也是可以接受的）。在底层，我们还将第一个顶点设置为最后一个顶点以简化实现。
请注意，我们限制绘制的多边形为简单多边形，即，没有边交叉。
多边形的顶点/角数存储在变量n中。由于多边形是一个封闭的电路，多边形的边数/边数也是n。
所有可用的操作都如常在左侧菜单中列出。
前两个是用于给出简单输入多边形的，接下来的五个是你可以在当前绘制的多边形上运行的计算几何算法。
在这个可视化中，你可以绘制任何简单多边形（至少3个点），没有任何共线的点（实际上，我们可以修改我们的实现以允许共线的点，只是这会复杂化一些操作）。最小的这样的多边形是一个三角形。
你绘制的多边形可以是凸的（连接多边形内任意两点的线将保持在多边形内）或凹的。
如果你没有关闭循环（从最后一个顶点回到顶点0绘制一条边），我们将自动为你完成这个操作。
我们提供了一些示例多边形作为起点。
加载此可视化页面后，我们将随机选择示例多边形。
多边形的周长就是连续线段（多边形边）的长度（欧几里得距离）之和。
这个程序适用于凸多边形和凹多边形，运行时间为 O(n)。
那么我们现在就来计算当前绘制的多边形的 。
当多边形的顶点以环形方式（顺时针或逆时针）给出时，我们可以使用鞋带公式来计算其面积。
这个鞋带公式返回的面积，是由边缘端点定义的向量的交叉积的一半。
这个公式非常通用，因为它适用于凸多边形和凹多边形。它可以在O(n)中计算。
那么我们现在就来计算当前绘制的多边形的 。
如果我们在多边形内部的任意两个不同点之间画一条线，并且线始终保持在多边形内部，那么这个多边形就被称为凸多边形。否则，多边形被称为凹。
有一种更简单的方法可以检查给定的多边形（假设没有三个共线的点）是否为凸的，而不需要使用上述的直接定义。我们可以检查多边形的所有三个连续顶点是否形成同一种类型的转弯（全部为CCWs或全部为CWs）。这个检查显然是O(n)。
言归正传，让我们检查当前绘制的多边形 。
有几种算法可以检查一个点（pt1）是否在多边形内。我们认为最稳健的算法是绕数算法，它计算多边形的每条边/侧与pt1为原点所成的角度之和。由于只有n个这样的角度，所以这个检查也以O(n)运行。
输入的简单多边形可以像当前显示的 "MAZE" 测试用例那样复杂。尝试 和 测试用例。
在探索模式中，您将被要求提供被测试点（pt1）作为此操作的额外输入。
我们可以用由两点 (pt1, pt2) 定义的直线切割一个凸多边形。切割的结果是两个较小但也是凸的多边形。此算法当前返回切割线 (pt1, pt2) '左侧'的较小多边形。
请注意，尽管可能，但切割凹多边形更复杂，因为它可能会产生超过两个（可能是退化的）多边形。我们在这个可视化中允许这样的操作，但在实际实现中必须格外小心。
尝试 查看此例程的默认版本，以及 我们交换 pt1 和 pt2 以获取切割的另一侧。
在探索模式中，您将被要求提供两个点来定义切割线 (pt1 和 pt2) 作为此操作的额外输入（为避免退化情况，这两个点应放置在不同的位置）。
此例程也以 O(n) 运行。
VisuAlgo中还有一个计算几何可视化：凸包。
您现在可以使用这些算法在多边形程序中解决一些编程练习：UVa 11265 - Sultan的问题 和 Kattis - robotprotection。
您可以使用/修改我们的多边形算法实现代码：
polygon.cpp | py | java | ml