geometry - 如何匹配 2D 框的几何模板以适应另一组 2D 框

Question

我正在尝试在具有坐标 (A) 的一组 2D 框（从具有已知大小和框之间距离的模板）与另一组具有坐标 (B) 的 2D 框（可能包含比 A 更多的框）之间找到匹配项）。它们应该根据 A 中的每个框对应于 B 中的单个框来匹配。A 中的框一起形成一个“印章”，该“印章”至少在一个维度上是不对称的。

问题说明

解释：插图中的“斯坦兹”是 A 组中的一个盒子。

甚至可以将 Set A 视为仅 2D 点（框的中心点）以使其更简单。

最终的结果将是知道哪个 A 框对应哪个 B 框。

我只能想到非常具体的方法，针对特定的盒子布局量身定制，是否有任何已知的通用方法来处理这种形式的匹配/搜索问题，它们叫什么？

编辑：可能的解决方案

我提出了一种可能的解决方案，为集合 A 中的单个框在每个可能的 B 中心位置寻找所有可能的旋转。在这里，A 中的所有点都将被旋转并与到 B 中心的距离进行比较。不确定这是否是一个好方法。

在每个 B 中心点解决方案中寻找可能的旋转

标签： geometry2dcomputational-geometry

Answer 1

在您的示例中，模板及其在 B 中的存在之间的转换可以由两个匹配点完全定义（实际上是过度定义）。

所以这是一个简单的方法，它是一种高性能。首先，将 B 中的所有点放入 kD-tree 中。现在，在 A 中选择一个规范的“第一”点，并假设将其与 B 中的每个点匹配。要检查它是否与 B 中的特定点匹配，请在 A 中选择一个规范的“第二”点并测量它到“第一”点。然后，使用标准的 kD 邻近边界查询来查找 B 中的所有点，这些点与 B 中假设的匹配“第一个”点的距离大致相同。对于每个点，确定 A 和 B 之间的转换，以及对于每个点A 中的其他点，确定 A 中的点是否在大致正确的位置（同样，使用 kD-tree），与第一个不匹配的点提前出局。

对于病理情况（我认为），那里的最坏情况性能可能会变得非常糟糕，O(n^3 log n)但总的来说，我预计O(n log n)对于具有低阈值的表现良好的数据来说大致是这样。请注意，阈值处理有点粗略，结果可能取决于您对“第一”和“第二”点的选择。