问题
对于六面体单元的非结构化网格，您将如何对点云进行排序？
每个单元格都有一个中心和一个唯一的标签来表示它。基本上有两个云点（原始点云和单元中心的点云），但单元几何信息（边界框）可能有用，我不确定。
结果
我做了一些询问，并搜索了文献：
如果网格是六面体且非结构化的，则问题会简化为正交范围搜索。为此，最常使用 kd 树。如果网格基于八叉树数据结构进行细化，则可以围绕它构建范围搜索算法。目标是避免处理直接网格几何并专注于点云 A - 点云关系 B。点云 A：查询点，点云 B：网格单元中心。
相对于六面体单元的非结构化网格对点云进行排序
计算科学
算法
计算几何
2021-12-12 04:21:04
1个回答
重要说明：此答案不回答实际问题，但根据请求未删除。尴尬的是，我混淆了六面体和六边形。问题是关于将点分类为 3D 中的任意六面体单元，而此解决方案将点分类为 2D 中的规则六边形单元，或对应于任何维度中的某些 Voronoi 镶嵌的不规则单元。此方法仅适用于首先将网格生成为 Voronoi 细分的情况（这似乎是一种偶尔使用的方法）。
我不确定您在这里所说的排序是什么意思，但我假设您想将该点分类到平面上的六边形箱中。
Mathematica 是我所知道的，所以我将向您展示如何在 Mathematica 中进行操作，但该方法可以移植到其他系统。这个想法是六边形格子是三角形格子的对偶：它可以生成为三角形排列的点的 Voronoi 图。如果云中的点比任何其他六边形的中心更靠近该六边形的中心，则它属于给定的六边形。
这种方法也适用于不同形状的网格，只要它们可以生成为一些点排列的 Voronoi 图。（例如，六边形不需要是规则的。）
让我们生成网格。这是一个三角形格子：
pts = Join @@ Table[{x, Sqrt[3] y}, {x, 0, 4}, {y, 0, 2}];
points = Join[pts, TranslationTransform[{1/2, Sqrt[3]/2}] /@ pts];
Needs["ComputationalGeometry`"]
PlanarGraphPlot[points, LabelPoints -> False]
它的对偶是我们感兴趣的六边形：
DiagramPlot[points, LabelPoints -> False]
这构建了一个函数，该函数nf找到某个浊点最接近的六边形中心的索引。它是方法的关键：
nf = Nearest[N[points] -> Range@Length[points]];
现在让我们生成一个包含 1000 个随机点的云，并使用 对它们进行排序nf：
cloud = RandomReal[{-1/2, 5}, {1000, 2}];
indices = First /@ nf /@ cloud;
indices包含每个浊点最接近的中心的索引。这是我们需要的信息。现在我们可以用它们制作直方图......
Histogram[indices]
...或为每个人着色...
Show[
DiagramPlot[points, LabelPoints -> False],
Graphics@MapThread[{ColorData[3][#1], Point[#2]} &, {indices, cloud}],
PlotRange -> All, AspectRatio -> Automatic
]
...或者做任何我们想要的花哨的可视化。
tally = Tally[indices];
ListDensityPlot[Join[points, List /@ Sort[tally][[All, 2]], 2],
InterpolationOrder -> 0,
Epilog -> (Text[#2, points[[#1]]] & @@@ tally),
PlotRange -> {{-.5, 5}, {-.5, 5}}, Mesh -> All,
ColorFunction -> (ColorData["BeachColors"][1 - #] &)]
这里的关键点是找到离某物最近的点的函数 ( Nearest)。Mathematica 已内置此功能，但您的系统可能没有。如果是这种情况，请参阅有关如何有效实现此类功能的问题（或者如果您没有大量要处理的点，则只需使用幼稚的线性时间实现）。
其它你可能感兴趣的问题