algorithm - 几何图案质量和填充

Question

在上图中，有一些几何图案。模型a距离是已知的。点严格来说不在模型距离内。

我想要：

• 计算每个点的质量（点之间的实际距离不是a）更好的点适合图案更好的质量系数它应该有（我试图采取距离和 45 度角）
• 消除错误点（我用红色标记） - 它与模式质量计算有关

到目前为止我已经尝试过：

1. 互相取每个点
2. 计算它们之间的距离和角度
3. 只取与当前点相邻的点（距离在a - delta和a + delta
4. 质量是 realDistance/modelDistance * realAngle/modelAngle

为什么失败：

• 好点质量大幅下降，附近有坏点
• 如果坏点只有一个邻居并且距离和角度还可以，那么它的质量还可以。

所以问题是：在这种情况下计算点质量和填充模式的最佳算法是什么。模式应通过考虑邻居位置的平均元素位置来填充。最好的答案将是伪代码或代码或对某些已知算法的引用，这在这种情况下可能会有所帮助。

问题与我之前的问题Filling rectangle with points pattern有点相关，但填充不能用错误的质量点完成。

Answer 1

如果从左到右或从上到下时点的误差/失真没有变大（即a相邻好点之间的平均距离足够精确），您可以尝试以下操作：

• 当除以 a 时，通过取 x 和 y 坐标的余数将每个点 P _i带入正方形（生成 Q _i）。因此，好点将或多或少地映射到一个点上。[0,a[ x [0,a[
• 在这些生成的点Q _i中选择一个R最近邻的点（例如，1/distance对到其他点Q _j的所有距离求和，j≠i，并选择总和最大的点）。
• _{现在，您可以通过查看 Q i}到 R的距离来区分好点和坏点 P _i 。（对应的 Q _i接近 R的点 P _{i将是好点。）}

如果点 R（与最近的邻居）的坐标接近 0 或 a（即 R 接近正方形的边界[0,a[ x [0,a[），您最好从头开始并添加a/2到对应的坐标（每个 P _i之前）计算余数，以使点 R 更靠近正方形的中心。（或者您设法计算离开正方形[0,a[ x [0,a[的一侧并从另一侧返回正方形的不同可能性的最小距离。）

Answer 2

优点似乎沿网格对齐。可以使用使用RANSAC的线拟合算法找到网格线。RANSAC 线拟合是一种概率算法。您将不得不重复它，直到找到几乎水平或垂直的线。取出这条线上/附近的点，然后寻找下一条网格线。根据您的问题特征，如果剩下的点太少或在一条线上/附近的点太少，您将停止寻找新的网格线。剩下的点是坏点。当你取找到的网格线的交叉点并且在交叉点附近没有点（从所有原始点中），那么你可以在这里填写一个点。