作者shininglion (lionking - 辛巴)
站内Prob_Solve
标题[问题] 如何判断多边形的座标点顺序
时间Fri Jul 20 21:12:18 2012
标题非常简略所以可能很难懂...抱歉
---------------------------------------------
以下是前情提要：
1. 我有一个演算法是针对多边形做一些处理，而多边形的输入格式为
以逆时针方向依序给定多边形的每个座标点
2. 被处理的多边形不会有中空的情形
并且这多边形的每个转角都是直角
3. 我要处理的多边形的量非常多(数量级至少以百万做单位)
----------------------------------------------
以下是我遇到的问题：
因为该演算法只能吃以逆时针方向给做标点
所以遇到有顺时针给点的座标点我会预先把它处理成逆时针方向
但现在遇到的问题是我有一个 case 他里面的多边形
有些是顺时针有些是逆时针
偏偏数量太多我不可能一个一个抓出来检查到底是顺时针还逆时针
想请问有没有什麽方法可以判断他给座标点的顺序是顺时针还是逆时针呢?
谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.135.238.148
※ 编辑: shininglion 来自: 220.135.238.148 (07/20 21:13)
1F：→ Angrybird11:算叉积? 07/20 21:18
2F：→ suhorng:判断算出来的面积是正的还是负的 07/20 22:01
3F：→ suhorng:如果是凸多边形,随便抓三个连续点判断就好 07/20 22:01
4F：→ shininglion:不是凸多边形，有可能凹进去 07/20 22:04
5F：→ shininglion:不过算面积应该可行! 也不会太麻烦~感谢! 07/20 22:05
6F：→ tkcn:找 Y 座标最小的那条，判断是往上还是往下即可。 07/20 22:28
7F：→ rifiz:先sort, 用最左下的点先找第一组逆时钟的 07/21 07:41
8F：推 DJWS:找到最下再最左的顶点，判断下一个顶点是往上还是往右即可 07/21 07:55
9F：→ DJWS:写个 for + if 就可以判断了 不需要排序 07/21 07:57
10F：→ shininglion:感谢楼上提供的好方法! 以解决 07/21 22:36