多边形是平面上由一系列线段构成的闭合曲线。也就是说，它是由一_

多边形是平面上由一系列线段构成的闭合曲线。也就是说，它是由一系列直线段构成的首尾相连的曲线。这些直线段称为多边形的边。一个连接两条连续边的顶点称为多边形的顶点。如果多边形是简单的(一般情况下都会作此假设)，那么它的内部不存在边交叉的情况。在平面上被简单多边形包围的点集组成了该多边形的内部(interior),恰落在多边形上的点组成了多边形的边界(boundary),而包围该多边形的点构成了多边形的外部(exterior)。对于-个简单多边形，如果给定任意两个位于其边界或内部的点，连接这两个点的线段上的所有点都在这个多边形的边界或内部，那么该多边形为凸多边形。一个凸多边形的顶点不能被表示成边界或内部任意两个顶点的凸组合。
Amundsen教授提出，对于由n个点组成的序列<p0, p1，....，pn-1>，可以用下面的方法来确定它们能否形成一个凸多边形的连续顶点。若集合{∠pipi+1pi+2: i=0,1，.，n-1}(下标是模n排列的)不是既包含左转又包含右转，则输出“yes";否则, 输出“no”。试说明虽然这种方法的运行时间是线性的，但它不总是得出正确结果。对教授的方法做修改, 使其总是能在线性时间内得出正确结果。

多边形是平面上由一系列线段构成的闭合曲线。也就是说，它是由一

问题信息

热门推荐

相关试题