没有轴和方向,“顺时针”或“逆时针”的概念定义不明确!(证明:例如,如果您从显示器屏幕的另一侧查看这些点或将它们翻转,该怎么办!)
您必须定义轴和方向,并将其指定为附加输入。指定它的方法包括:
为了确定方向,您必须更深入地研究问题:必须定义网格的“向上”和“向下”大小。然后,对于每组点,必须取形心(或另一个“内部”点)并构造指向垂直于表面的“上”的单位向量。(执行此 *** 作的一种方法是找到最小二乘拟合平面,然后找到通过该点的两个垂直向量,并沿“向上”方向拾取一个。)
您将需要使用以上任何建议来确定轴。这将使您可以按如下方式重新编写问题:
输入:
- 点集{P_i}
- 轴,我们将其称为“ z轴”,并将其视为以点的质心(或“内部”某处为中心)的单位矢量
- 通过上述方法之一选择的方向(例如,逆时针方向)
建立:
- 对于所有点,选择两个相互正交的单位矢量作为轴,我们将其称为“ y轴”和“ x轴”。(只需在两个方向上将 z轴单位矢量旋转90度,http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations)
算法:
- 对于每个点P,将P投影到x轴和y轴上(使用点积),然后使用http://en.wikipedia.org/wiki/Atan2
一旦有了角度,就可以对其进行排序。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)