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.
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