栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

按顺时针/逆时针顺序对一组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

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



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/569153.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号