Finding the biggest shape possible inside a grid

Question

I'm trying to make an algorithm, that finds the biggest possible shape with the given set of points. Each point can be connected to another one vertically, horizontally (by 1 unit) or diagonally. A shape is formed, where such connections between the points create a shape (obviously) (don't pay attention to colors)

A point has x and y indices, which determine its position on the board.

What did i try already?

1. My first idea was to use a pathfinding algorithm, configured specifically to pathfind back to the start point in the grid of points, with the only twist being that it tries to find the longest way possible, instead of the shortest. This failed, because the pathfinding algorithm was going through every possible point and not actually finding the biggest shape.
2. My second idea was to find the points of the same shape (not finding the shape itself, but rather points that are confirmed inside of it), and then find the convex hull of the set of points. Convex hull gives me the set of points, from which i can try to pathfind to the next point in the convex hull giving me the shape. I abandoned this idea for its complexity, as i am already lost in the theory of this method.

So what can I try to achieve what i am trying to do?

Answer 1

Your intuition for forming a convex hull for each cluster of points is a good idea. However, with the constraint of line segments having a max distance of one, we will have to modify a convex-hull algorithm since it is not guaranteed that all inner angles will be less than 180 degrees with this added constraint when forming the hull.

Here is one potential solution.

We can modify Graham scan by replacing the sort with an ordered path traversal. The path must consist of edges of length one, between any two points, and have to be circular.

Assuming there is no overlapping shapes, we can find the longest connected circular path for each point. We start by building an adjacency list to represent the graph, with a counterclockwise bias, where each point is connected to its neighboring points within a distance of one unit. We then perform a depth-first search from each point to explore all possible paths. Here is one implementation of such:

def dfs(point, graph, path, visited, start_point, longest_path, global_visited):
    path.append(point)
    visited.add(point)

    for neighbor in graph[point]:
        if neighbor == start_point and len(path) > 2:
            if len(path) > len(longest_path[0]):
                longest_path[0] = path.copy()
        elif neighbor not in visited and neighbor not in global_visited:
            dfs(neighbor, graph, path, visited, start_point, longest_path, global_visited)

    path.pop()
    visited.remove(point)

This can be memoised to run in linear time and there also exists many different ways of obtaining this path.

For the these of points, taken from Timeless's answer

 points = [
    (4, 11), (5, 10), (5, 11), (5, 12), (6, 10),
    (6, 11), (8, 12), (11, 11), (12, 10), (12, 12),
    (13, 10), (13, 11), (16, 9), (17, 7), (17, 8),
    (17, 10), (18, 8), (18, 9), (19, 10), (21, 9),
    (21, 10), (21, 11), (22, 10), (22, 11),
 ]

We find of the following paths.

We can then modify the Graham scan algorithm to incorporate the adjacency constraint by ensuring that the segments between points are valid. This holds as the path followed is biased to follow counterclockwise, hence cross > 0.

def is_valid_segment(p1, p2):
     return (abs(p1[0] - p2[0]) == 1 and abs(p1[1] - p2[1]) == 0) or \
           (abs(p1[0] - p2[0]) == 0 and abs(p1[1] - p2[1]) == 1) or \
           (abs(p1[0] - p2[0]) == 1 and abs(p1[1] - p2[1]) == 1)

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

def build_hull(points):
    hull = []
    for p in points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) > 0:
            if is_valid_segment(hull[-2], p):
                hull.pop()
            else:
                 break
        hull.append(p)
    return hull

We can pass the found paths into the modified Graham scan to form the hulls.

Here's the full code. This is just a draft and there is some room for optimisation.

---

Its slightly unclear if you would like to find the largest possible shape amongst all the points. However, provided you now have the points that you have the perimeter points to each shape, you can compute the area of each shape in linear time using the Shoelace Theorem:

, to find the largest shape.