按顺时针逆时针顺序对一组3-D点进行排序

按顺时针逆时针顺序对一组3-D点进行排序,第1张

按顺时针/逆时针顺序对一组3-D点进行排序

没有轴和方向,“顺时针”或“逆时针”的概念定义不明确!(证明:例如,如果您从显示器屏幕的另一侧查看这些点或将它们翻转,该怎么办!)

您必须定义轴和方向,并将其指定为附加输入。指定它的方法包括:

  • 一条线(
    1x=2y=3z
    ),使用右手定则
  • (A_x, A_y, A_z)
    使用右手法则的(单位向量;这是首选的方式

为了确定方向,您必须更深入地研究问题:必须定义网格的“向上”和“向下”大小。然后,对于每组点,必须取形心(或另一个“内部”点)并构造指向垂直于表面的“上”的单位向量。(执行此 *** 作的一种方法是找到最小二乘拟合平面,然后找到通过该点的两个垂直向量,并沿“向上”方向拾取一个。)


您将需要使用以上任何建议来确定轴。这将使您可以按如下方式重新编写问题:

输入:

  • 点集{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

一旦有了角度,就可以对其进行排序。



欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5560430.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-14
下一篇 2022-12-14

发表评论

登录后才能评论

评论列表(0条)

保存