将任意多边形重置为顺时针顺序 |
您所在的位置：网站首页 › 顺逆时针分辨是在平面还是空间上 › 将任意多边形重置为顺时针顺序 |
将任意多边形重置为顺时针顺序
|
第二篇博客，记录下如何判断一个多边形的边界散点是按顺时针还是逆时针绘制。 查阅了一些资料， 1、有使用某一个点计算叉积矢量叉积然后查看正负， ((xi - xi-1),(yi - yi-1)) x ((xi+1 - xi),(yi+1 - yi)) = (xi - xi-1) * (yi+1 - yi) - (yi - yi-1) * (xi+1 - xi) 上式正值为逆时针，负值为顺时针。 也有使用 2、还有一种说明是取多边形的极点值，多边形的方向和这个顶点与其相邻两边构成的方向相同。 需要注意的是在屏幕坐标中，Y是向下的，所以在屏幕坐标系中看到的顺时针既是在Y轴向上的直角坐标系中看到的逆时针方向。1.凸包的时候，只要判断前三个点即可，计算叉积，判断方向 2.凹包情况就复杂了，可以从三个方面考虑 首先，可以去凸包上的特殊点，x最大最小的点，y最大最小的点，这些极值点肯定是在凸包上的，可以计算这些的叉积，其次，直接统计叉积正负的数量，正多负少，是逆时针，反之，顺时针。 一个简单的做法是，计算面积，用面积的正负判断方向。 3、本文使用另外一种思路：找到多边形的最高点，则这一点必然为凸点，然后再比较两侧的点X方向的大小，可以区分顺时针还是逆时针。 def reorder_clockwise(polygon_point): # 输入的多边形为二维数组(x, y)，多行两列，可以是二维列表，也可以是npumpy二维数组 # 方法为先确定最高点，则该点一定是凸边的，再按x增大的方向来开始排序 # 1、转换成numpy的array pp = np.array(polygon_point) # 2、如果多边形的头尾相连，去掉重复的一个点 if (pp[0] == pp[-1]).all(): pp = np.delete(pp, -1, axis=0) x = pp[:, 0] y = pp[:, 1] # 3、获取最高点位置, np.argmax是默认取到第一个数，所以两边不可能相等 max_y_index = np.argmax(y) # 4、判断前后相邻点在左右的位置，如果最高点在首个，后一个为最后一个，如果最高点在最后一个，则前一个为首个 pre_index = max_y_index -1 next_index = 0 if max_y_index == len(pp) - 1 else max_y_index + 1 # 5、比较前后两个的X大小来确定顺逆时针 if x[pre_index] < x[next_index]: # X是朝大的方向移动，为顺时针 return polygon_point else: # X是朝小的方向移动，为逆时针，重新排序 return polygon_point[::-1]以下为测试 import matplotlib.pyplot as plt px = [2, 1, 0.5, 0, 1, 3, 4, 3.5, 3, 2] py = [1, 1, 2, 1, 0, 0, 1, 2, 1, 1] plt.plot(px, py) plt.axis("equal") plt.scatter(px[:3], py[:3], marker=".", s=100, c="r") plt.text(px[0], py[0]+0.1, "A") plt.text(px[1], py[1]+0.1, "B") plt.text(px[2], py[2]+0.1, "C") plt.text(px[3], py[3]+0.1, "D") plt.show()显示前3个点，图为逆时针方向
经过函数变换后，出图如下 pp = np.array([px, py]).T # 多边形边界，需要转置成(N,2)形式输入 new_pp = reorder_clockwise(pp) px = new_pp[:, 0] py = new_pp[:, 1] print(px, py) plt.plot(px, py) plt.axis("equal") plt.scatter(px[:3], py[:3], marker=".", s=100, c="r") plt.text(px[0], py[0]+0.1, "A") plt.text(px[1], py[1]+0.1, "B") plt.text(px[2], py[2]+0.1, "C") plt.text(px[3], py[3]+0.1, "D") plt.show()
|
【本文地址】