vector - 确定点列表是否适合 "formation"？

Question

作为输入，我有一个任意的“格式”，它是一个矩形列表 F:



作为另一个输入，一个 2D 点的无序列表 P:



在这个例子中，我认为 P 与 F 匹配，因为如果 P 逆时针旋转 45°，F 中的每个矩形都将通过包含一个点来满足。如果 P 中有一个不属于矩形的无关点，它也将被视为匹配。

地层和点输入都没有特定的原点，两者之间的比例尺不要求相同，例如，地层可以描述一公里的面积，输入点可以描述一厘米的面积.最后，我需要知道哪个点最终出现在编队中的哪个节点。

我正在尝试开发一种满足所有这些约束的通用算法。它将针对大型位置信息数据库每秒执行数百万次，因此我试图尽快“失败”。

我考虑过取两个输入中所有点之间的角度并比较它们，或者计算和比较船体，但每种方法似乎都因其中一个约束而崩溃。

地层中的点也可以很容易地表示为具有 x,y 原点和公差半径的圆，这似乎简化了我迄今为止尝试过的方法。我很感激任何可靠的攻击计划或 A-Ha!见解。

Answer 1

我有另一个想法 - 这次使用极坐标。

描述变得复杂/模糊，所以 here是一些希望说明这个想法的代码。

要点是用极坐标表示地层和点，原点在地层/点集的中心。然后找到点和地层之间变换的旋转和缩放因子变得容易得多。通过比较点集和地层集的平均值，可以轻松找到平移分量。

请注意，这种方法不会将您的地层区域视为正方形或圆形，而是将其视为圆段的部分。希望这是一种你可以忍受的软糖。

它也不会返回有效映射变换的精确缩放和旋转项。它将为您提供地层区域和点之间的映射，以及最终旋转和缩放因子的良好近似。通过一个简单的松弛方案，这个近似可以很快地被细化成一个有效的解决方案。它也会很快忽略无效的点集。