在给定网格节点的情况下，在网格上查找飞机的位置

Question

我在做一个项目，一些飞行物体扫描地面，以知道它的确切位置。例如，让下面的网格为地面，字母按字面意思放在地面上。网格中的每个三角形都是唯一的。你知道吗

A---B---C---D
 \ / \ / \ / \
  E---A---H---G
 / \ / \ / \ / \
H---F---B---E---A

飞行物体可以访问包含这些字母的文件，这些字母之间用空格隔开。零表示空节点。你知道吗

A B C D 0
E A H G 0
H F B E A

这个飞行物体拍下了地面的照片，但因为它离地面很近，所以只能看到地面的一部分。你知道吗

A---H---G
 \ / \ /
  B---E

飞机使用OpenCV扫描这个模式，它识别数字。它还可以在每个扫描的数字上放置一个坐标。例如，A放在拍摄照片的坐标（100200）上，H放在坐标（301201）上，B放在坐标（195403）上等等。你知道吗

给定字母及其（近似）坐标（在图片上），以及图片中心的坐标，飞机如何准确地找到它在网格上的位置。如果能产生以下输出，这将是最佳的：

• 如果飞机在三角形上方盘旋，返回三角形的3个字母。你知道吗
• 如果飞机大约在三角形的一侧盘旋，则返回该一侧的2个字母。你知道吗
• 如果飞机大约在某个节点上悬停，则返回该节点的字母。你知道吗

很抱歉，如果这是一个非常广泛的问题，我只是不知道如何解决它。我试着用subgraph isomorphism problem来表示这个问题，但是这个问题的解决方案是NP完全的。网格最多可以有200个字母。你知道吗

我目前正在用python工作，但对这个问题的任何解决方案（或想法）都表示感谢。你知道吗

编辑：问题的一部分可能有点模糊。在找到飞机飞行的顶点/边/三角形之后，我需要在给定的网格文件中找到这个顶点/边/三角形。这就是为什么我尝试子图同构问题。所以如果飞机发现它在上面盘旋：

• 顶点H是三角形HBE的一部分，算法应返回[（2,1）]
• 边HB是三角形HBE的一部分，算法应返回[（2,1），（2,2）]
• 三角形HBE，算法应返回[（2,1），（2,2），（3,2）]

非常感谢！你知道吗

Answer 1

一个问题是你把它复杂化了。子图同构比你要做的要困难得多。你知道吗

假设您能够分析图像并确定每个字母的近似坐标（在图像上）。您应该能够获取字母的点集，每个点都唯一地映射到一个字母，并进行线性搜索，以找到离图像中心最近的三个点。你知道吗

下一步是三角形查找。首先，由于网格中的每个三角形都是唯一的，您可以简单地循环遍历网格中的所有三角形，对它们进行标准化（通过规范化），然后将它们添加到字典中以提供快速查找，这一点很重要。因此，构建查找字典的代码如下所示：

def canonize_triangle_letters(letter_triple):
    # Used in larger algorithm below
    return tuple(sorted(list(letter_triple)))

def triangle_lookup_from_grid(triangle_grid)
    # This is a preprocessing step
    # Only needs to be done once if the grid doesn't change.
    # If grid does change, a more complex approach will be needed.
    triangle_lookup = {} # Used in larger algorithm below
    for points_triple in get_points_triples(triangle_grid):
        letter_to_point = dict((point_to_letter[p],p) for p in points_triple)
        triangle = canonize_triangle_letters(letter_to_point.keys())
        triangle_lookup[triangle] = letter_to_point
    return triangle_lookup

下一步是确定返回的是顶点、边还是三角形。一个简单的，但相当主观的方法，相当有用，例如，如果你想偏向算法返回一个边，而不是一个顶点或三角形。你知道吗

• 如果中心明显靠近一个点，则返回该点的字母。你知道吗
• 如果中心接近两点，则返回这两点的字母。你知道吗
• 否则，返回所有三个点。你知道吗

一个更平衡，更精确的方法需要一些额外的数学。下图大致显示了如何进行。为了避免在返回顶点（a）、返回边（AB）或返回三角形（ABC）以及数学的区域之间产生混淆。顶点A标记为5，顶点B标记为6，顶点C标记为7。注意，这里的半径是L/3，其中L是边的长度。图像假设最接近中心的点是A，然后是B，然后是C。因此，点永远不会位于顶点5和8的直线右侧，因为它打破了点更接近A和B而不是C的假设

评估方法如下：

1. 如果最近点（A）在中心的1/3范围内。然后返回A
2. 创建一个点p1（图中的顶点8），沿着a到B和a到C之间的夹角的一半。然后放置第二个点p2（图中的顶点9），与a到B的夹角相同，距离为L。从那里可以使用叉积来确定中心在直线的哪一侧。你知道吗
3. 如果交叉（p1，屏幕中心，p2）小于0，则返回AB，否则返回ABC。你知道吗

代码如下所示。代码中有一些神奇的数学函数，但用于它们的算法应该不难在网上查找。你知道吗

def find_nearest_triangle(points, screen_center):
    # Returns the nearest triangle, sorted by distance to center
    dist_to_center = lambda p: distance(p, screen_center)

    # Use the first three points in the list to create the inital triangle
    nearest_triangle = set(points[:3])
    farthest_point = max(nearest_triangle, key=dist_to_center)
    farthest_dist = dist_to_center(farthest_point)
    for point in points[3:]:
        dist = dist_to_center(point)
        if dist < farthest_dist: # Check for a closer point
            farthest_dist = dist
            nearest_triangle.remove(farthest_point)
            nearest_triangle.add(point)
            # Find the new farthest point
            farthest_point = max(nearest_triangle, key=dist_to_center)

    return sorted(list(nearest_triangle), key=dist_to_center)

def get_location(nearest_triangle, screen_center):
    # nearest_triangle should be the same as returned by find_nearest_triangle.
    # This algorithm only returns the 1-3 points that make up the triangle.

    A, B = nearest_triangle[:2]
    side_length = distance(A, B)

    vertex_radius = side_length / 3.0

    if distance(A, screen_center) < vertex_radius:
        return [A], nearest_triangle

    def cross(o, a, b): # Cross product
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    angle_AB = angle(A, B)
    angle_AC = angle(A, C)
    middle_angle = ((angle_AB + angle_AC) % 360) / 2.0 # For angle in degrees

    p1 = offset_point_by_angle_dist(A, middle_angle, distance)
    p2 = offset_point_by_angle_dist(p1, angle_AB, side_length)

    if cross(p1,screen_center,p2) < 0:
        return [A,B]
    return [A,B,C]

def lookup_location(triangle_lookup, image_point_to_letter, points, screen_center):
    nearest_triangle = find_nearest_triangle(points, screen_center)
    triangle = canonize_triangle_letters([image_point_to_letter[p] for p in nearest_triangle])
    letter_to_position = triangle_lookup[triangle]
    location = get_location(nearest_triangle, screen_center)
    letters = [image_point_to_letter[p] for p in location]
    return [letter_to_position[L] for L in letters]

注：上述算法的运行时间为O（N），其中N是点集中的点数。但是，必须为每个图像运行它。因此，如果需要检查大量图像，最好尽量限制字母的数量。不过，从图像中提取字母可能需要更多的时间。虽然，由于算法只需要最接近的三个字母，它应该是最好的