多边形

多边形定义为各点互相直线连接所围成的无开口图形。
多边形又包含以下几个种类：

简单多边形

简单多边形必须符合多边形条件且任何一边都没有交叉。
但如何以N点建造一个简单多边形并且确定任何一边都没有交叉？

Naïve Method 朴素法

简单方法利用点列表的顺序连接各点，在与最后一点与第一点连接完成多边形。
因为这种方法是随机依照列表顺序(任何一种列表)连接各点，因此画出来的图形并无绝对。
下图为两种成功画出简单多边形的例子。

结论

这种方法在大多数例子都无法成功画出简单多边形，因为这种方法没有一定的点对点连接顺序。
下图为非简单多边形的例子。

Circular Scan 圆型扫描

圆型扫描是在所有点中选择一个中心点进行扫描，每次扫描到得点加入列表中，如果同一条线上两个以上的点，则以离中心点最近的优先加入列表。
虽然随机选择中心点有可能成功建立简单多边形，但也可能错误选择中心点。
下图为随机选择一点(非从点列表中选择)为中心点的例子。

如果加以分析，会发现随机选择一点为中心点，还是会无法让第一点及最后一点正确连接。

为了避免第一点及最后一点错误连接，中心点必须选择点列表的一点。
但是随机选择，还是无法确保所建立的多边形为简单多边形。
因此，可以选择在最大或最小X值的点或是在最大或最小Y值的点。
下图为选择最大X值的点。

以中心点加以分析会发现，第一点及最后一点所延伸到圆的直线，会是扇形的两边。

结论

如果随机选择中心点或是点列表中随机一点，都无法确保所建立的多边形为简单多边形。
但是选择在最大或最小X值的点或是在最大或最小Y值的点，可以改善并建立简单多边形

传送门：[笔记本: 演算法] 多边形篇 Part 2 - Convex Hull 凸包
传送门：[笔记本: 演算法] 多边形篇 Part 3 - Furthest Pair of Points 最远两点配对