判断多边形顺时针还是逆时针 |
您所在的位置:网站首页 › 力偶的顺逆时针方向怎么判断 › 判断多边形顺时针还是逆时针 |
最近在看recast&detour源码的时候有遇到许多数学上的算法问题,特此记录,以便以后查看。 问题:给出一个点序列,判断按这个点序列连接组成的多边形是逆时针还是顺时针。 计算面积--鞋带公式:其中: 公式1【源码中所用的公式】 公式2 边的和【见参考中 overflow 链接】 去掉上述计算S中的绝对值,让其有正负,判断逆顺:点序为顺, 面积为负值。 点序为逆,面积为正值。 所以可以根据上述公式计算出来的面积的正负值,来判断多边形是顺时针还是逆时针。 源码: static int calcAreaOfPolygon2D(const int* verts, const int nverts) { int area = 0; for (int i = 0, j = nverts-1; i < nverts; j=i++) { const int* vi = &verts[i*4]; // 后一个点 相当于Pi+1 const int* vj = &verts[j*4]; // 前一个点 相当于Pi // 相当于 (xi+1 * yi - xi * yi+1) 正好是 没有绝对值的公式1 的 相反数 。(xz平面)。 area += vi[0] * vj[2] - vj[0] * vi[2];// area正为顺时针, 负为逆时针。 } return (area+1) / 2; }上述函数返回负值,即代表是逆时针,即代表是hole。 winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1; if (winding[i] < 0) nholes++;疑问: 分析代码中为什么返回值 (area+1) / 2 要多加一个1?(觉得应该是 -1) 注意上述中点的坐标都是整数,函数的返回值也为整形。 即如果不+1,当area = -1 时候,函数返回值为 0,即winding[i] = 1 。那么,此时这个多边形就不会被判断为洞了。 而+1了以后,当area = -2 和 -1时候,函数返回值均为 0,即winding[i] = 1 。那么,此时依然不能正确判断多边形。 而如果是-1 ,当area = -1 的时候,函数返回-1,即winding[i] = -1,能正确判断多边形顺逆。 既然是这么麻烦,为什么不直接返回 area ? 直接通过area的正负来判断顺逆不是更简单? 参考:鞋带公式推导: https://en.wikipedia.org/wiki/Shoelace_formula 中的 Proofs。 overflow讨论: https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |