Find the location of an airplane on a grid given some nodes of the grid

Question

One issue is that you are over-complicating it. Sub-graph isomorphism is much, much harder than what you are trying to do.

Assuming that you are able to analyze the imagine and determine the approximate coordinates (on the image) for each of the letters. You should be able to take the point set of the letters, with each point uniquely mapped to a letter, and do a linear search to find the three points nearest to to the center of the image.

The next step is the triangle lookup. First, is it important to know that since each triangle in the grid is unique, you can simply loop through all the triangles in the grid, standardize (via a canonization) them, then add them to dictionary to provide a fast lookups. Thus the code for building the look-up dictionary looks something like this:

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

The next step is to determine if the return a vertex, edge or triangle. A simple, but rather subjective method, rather useful for example if you want to bias the algorithm towards returning an edge rather than a vertex or triangle.

If the center is significantly closer to one point, return the letter of that point.
If the center is close to two points, return the letters of those two points.
Otherwise, return all three points.

A more balanced, precise way requires some extra math. The below image shows roughly how to go about it. To avoid confusion between areas where a vertex is returned (A), an edge is returned (AB) or a triangle is returned (ABC) as well as the math. The vertex A is labeled as 5, the vertex B is labeled as 6 and the vertex C is labeled as 7. Note that L/3 is showing the radius there, where L is the length of a side. The image assumes that closest point to the center is A followed by B then C. Thus a point would never be on the right side side of the line from vertices 5 and 8, as it breaks the assumption of the point being closer to A and B than C.

Triangle Partition

The way it is evaluated is as followed:

If the closest point (A) is within L/3 of the center. Then return A.
Create a point, p1 (vertex 8 in the diagram), that is way along the angle halfway between the angle from A to B and A to C. You then place a second point, p2 (vertex 9 in the diagram), at the same angle as A to B and at a distance of L. From there you can use the crossproduct to determine which side of the line the center is on.
If cross(p1,screen_center,p2) less than 0, then return AB, else return ABC.

The code then looks something like below. There are a few magic math functions in the code, but the algorithms for them shouldn't be difficult to look-up online.

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]

Note the above algorithm has a runtime of O(N), where N is the number of points in the point set. However, it must be ran for each image. Thus if a lot of images need to be checked, it is best to try to limit the number of letters. Although, it's likely that extracting the letters from the image will be more time intensive. Although, since the algorithm only needs the closest three letters, it should be best