点与多边形的关系
需积分: 16 55 浏览量
2016-07-15
09:56:28
上传
评论
收藏 131KB DOC 举报
点与多边形的关系
（注：
1、样例中的第 1 点和第 n-1 点是一致的。这个第 n-1 点没必要输入，多输入这个重复点也许会导致判断错误 ！
2、上图中的输出 10 应该是分成两行的 1 和 0 ）
计算原理：
（1）是否为凸多边形：前三个点计算三角形的面积（封闭线的面积，用积分方式计算），以后每加一个点面积
均应增加或至少相等。
（2）最后一个点是否在凸多边形内：同上方式计算加上这个点的多边形的面积，相等或减少表示在内 ！
问题：
1、如何保证前 n-1 个点是顺序输入的？只有沿着凸多边形顺时针或者逆时针顺序输入多边形的角点，所构成的多
边形才可能是凸多边形。
2、第 N 个点应该放在前 n-1 个点中的哪两个点（比如 A、B）之间？这个问题只要求线段 NA、NB 的连线不能和
多边形的其他边线相交。但可以和问题 1 一并解决 ！
解决办法：
假设多边形的点是毫无规则、杂乱无章输入的。如何将这 n 个点重组成顺时针（或逆时针）的规则排列？
我们的办法是：
1、先通过算术平均的方式求出这 n 个点的相对中心，以这个中心点作为相对坐标原点。通过原点的 x 轴、y 轴将
平面分成 1、2、3、4 四个象限。
2、将 n 个点依据其位置分到四个象限中，在正 x 轴上的点规定放在第 1 象限，正 y 轴上的点规定放在第 2 象限，
负 x 轴上的点规定放在第 3 象限，负 y 轴上的点规定放在第 4 象限。
3、求出各象限内点相对坐标原点的正切值（记为 r，对于 y 轴上的点直接赋 r= -1e15）。
4、依据 r 的大小对各象限内点排序，使点的顺序变为逆时针顺序。
资源评论
