3D网格方向检测
3D mesh direction detection
我有一个由三角形多边形组成的 3D 网格。我的网格可以向左或向右：
我正在寻找检测网格方向的方法：右与左。
到目前为止，我尝试使用网格 centroid:
- 将质心与边界框 (b-box) 中心进行比较
- 查看质心是否位于b-box中心
的左侧
- 看看质心是否位于b-box中心
的右边
但问题是在大多数情况下质心和 b-box 中心没有可靠的区别。
我想知道检测网格方向的快速算法是什么。
更新
@collapsar 提出的一个想法是按顺时针顺序对 Convex Hull 点进行排序并调查最长的边：
更新
@YvesDaoust 建议的另一种方法是研究网格的两个特定区域：
算法解决问题的效率将取决于表示网格的数据结构。您可能需要更具体地了解它们，以获得足够高效的程序。
算法以非正式的方式呈现。对于更严格的分析，math.stackexchange 可能是一个更合适的提问地点（或者其他贡献者更善于回答......）。
算法本质上是启发式的。建议 1 和 3 适用于局部边界的曲率主要是局部凸的网格（此处跳过严格的数学定义）。建议 2 应该较少依赖于网格形状（并且可以很容易地调整以适应 ill-behaved 形状）。
提案 1（凸包，2D）
设 M 为一组网格点，按照您提供的图形的建议投影到 'suitable' 平面上。
- 计算
M 的凸包 CH(M)。
- 将
CH(M)的n个点相对于CH(M)内的任意一点按顺时针顺序排列得到一个点序列seq(P) = (p_0, ..., p_(n-1))，其中p_0为CH(M) 的任意元素。请注意，这通常是 by-product 的凸包计算。
- 找出
CH(M)所隐含的凸多边形的最长边。
具体来说，找到 k，使得距离 d(p_k, p_((k+1) mod n)) 在所有 d(p_i, p_((i+1) mod n)); 0 <= i < n; 中最大
- 考虑向量
(p_k, p_((k+1) mod n))。
如果它的头的 y 坐标大于它的尾巴的坐标（即它在 ((0,0), (0,1)) 线上的投影是向上的）那么你的网格向左打开，否则向右打开。
步骤 3 利用网格边界大部分是局部凸的条件。因此凸包多边形边基本上很短，除了跨越网格开口的边。
提案 2（二等分线抽样，2D）
- 按
x 坐标在序列 seq(M) 中对网格点进行排序 seq(M)。
- 将
seq(M)分成两半，让seq_left(M)、seq_right(M)表示分割元素。
对两个点集重复以下步骤。
3.1. Select从点集中随机抽取2个点p_0、p_1。
3.2.找到线段 (p_0, p_1).
的平分线 p_01
3.3.测试 p_01 是否在网格内。
3.4.统计 失败的 测试。
统计上，'contains' 开口的网格点子集将在每个分区上对于相同给定数量的测试 运行 产生更多的失败。替代测试标准也将起作用，例如。记录网格外的平均距离 d(p_0, p_1) 或 (p_0, p_1) 部分的平均长度（均在具有开口的网格点子集上更高）。如果两半测试结果相差'sufficiently pronounced'，则停止第3步的重复。对于 ill-behaved 个形状，增加重复次数。
提案 3（凸包，3D）
仅出于完整性考虑，因为您的问题描述表明分析实际上是在 2D 中进行的。
与提案1类似，可以在3D中执行计算。网格点的凸包意味着一个凸多面体，其面应按面积排序。 Select 具有最大面积的面并计算其 outward-pointing 法线，它表示从 b-box 中心的角度看开口的方向。
如果网格点的最小边界框的边长变化很大，计算会变得更加复杂，即。如果存在网格点坐标的大部分变化发生的平面。在您提供的图形中，假设网格点的坐标沿垂直于平面的轴变化不大。
解决方案是识别这样一个平面并将网格点投影到它上面，然后求助于建议 1。
计算边界框两个预定义区域中的顶点数。这是一个相当简单的 O(N) 过程。
除非您的数据集以某种方式排序，否则您的速度不会比 O(N) 快。但是，如果点密度允许，您可以在应用程序时通过每十分之一点进行二次采样。
您也可以保留质心的想法，但也可以在子部分中应用它。
我有一个由三角形多边形组成的 3D 网格。我的网格可以向左或向右：
我正在寻找检测网格方向的方法：右与左。
到目前为止，我尝试使用网格 centroid:
- 将质心与边界框 (b-box) 中心进行比较
- 查看质心是否位于b-box中心 的左侧
- 看看质心是否位于b-box中心 的右边
但问题是在大多数情况下质心和 b-box 中心没有可靠的区别。
我想知道检测网格方向的快速算法是什么。
更新
@collapsar 提出的一个想法是按顺时针顺序对 Convex Hull 点进行排序并调查最长的边：
更新
@YvesDaoust 建议的另一种方法是研究网格的两个特定区域：
算法解决问题的效率将取决于表示网格的数据结构。您可能需要更具体地了解它们，以获得足够高效的程序。
算法以非正式的方式呈现。对于更严格的分析，math.stackexchange 可能是一个更合适的提问地点（或者其他贡献者更善于回答......）。
算法本质上是启发式的。建议 1 和 3 适用于局部边界的曲率主要是局部凸的网格（此处跳过严格的数学定义）。建议 2 应该较少依赖于网格形状（并且可以很容易地调整以适应 ill-behaved 形状）。
提案 1（凸包，2D）
设 M 为一组网格点，按照您提供的图形的建议投影到 'suitable' 平面上。
- 计算
M的凸包CH(M)。 - 将
CH(M)的n个点相对于CH(M)内的任意一点按顺时针顺序排列得到一个点序列seq(P) = (p_0, ..., p_(n-1))，其中p_0为CH(M)的任意元素。请注意，这通常是 by-product 的凸包计算。 - 找出
CH(M)所隐含的凸多边形的最长边。
具体来说，找到k，使得距离d(p_k, p_((k+1) mod n))在所有d(p_i, p_((i+1) mod n)); 0 <= i < n; 中最大
- 考虑向量
(p_k, p_((k+1) mod n))。 如果它的头的y坐标大于它的尾巴的坐标（即它在((0,0), (0,1))线上的投影是向上的）那么你的网格向左打开，否则向右打开。
步骤 3 利用网格边界大部分是局部凸的条件。因此凸包多边形边基本上很短，除了跨越网格开口的边。
提案 2（二等分线抽样，2D）
- 按
x坐标在序列seq(M)中对网格点进行排序seq(M)。 - 将
seq(M)分成两半，让seq_left(M)、seq_right(M)表示分割元素。 对两个点集重复以下步骤。
3.1. Select从点集中随机抽取2个点p_0、p_1。
3.2.找到线段(p_0, p_1).
的平分线p_013.3.测试p_01是否在网格内。
3.4.统计 失败的 测试。统计上，'contains' 开口的网格点子集将在每个分区上对于相同给定数量的测试 运行 产生更多的失败。替代测试标准也将起作用，例如。记录网格外的平均距离
d(p_0, p_1)或(p_0, p_1)部分的平均长度（均在具有开口的网格点子集上更高）。如果两半测试结果相差'sufficiently pronounced'，则停止第3步的重复。对于 ill-behaved 个形状，增加重复次数。
提案 3（凸包，3D）
仅出于完整性考虑，因为您的问题描述表明分析实际上是在 2D 中进行的。
与提案1类似，可以在3D中执行计算。网格点的凸包意味着一个凸多面体，其面应按面积排序。 Select 具有最大面积的面并计算其 outward-pointing 法线，它表示从 b-box 中心的角度看开口的方向。
如果网格点的最小边界框的边长变化很大，计算会变得更加复杂，即。如果存在网格点坐标的大部分变化发生的平面。在您提供的图形中，假设网格点的坐标沿垂直于平面的轴变化不大。
解决方案是识别这样一个平面并将网格点投影到它上面，然后求助于建议 1。
计算边界框两个预定义区域中的顶点数。这是一个相当简单的 O(N) 过程。
除非您的数据集以某种方式排序，否则您的速度不会比 O(N) 快。但是，如果点密度允许，您可以在应用程序时通过每十分之一点进行二次采样。
您也可以保留质心的想法，但也可以在子部分中应用它。