Поиск максимально возможной формы внутри сетки

С помощью python , и если я правильно понял, вы можете построить DistanceBand на основе метрики Чебышева , а затем сделать convex_hull из набора MultiPoint , сделанного из подключенные_компоненты:

from libpysal import weights
from shapely import MultiPoint

db = weights.DistanceBand.from_array(
    points,
    p=float("inf"), # "chebyshev"
    threshold=1,
    silence_warnings=True,
)

shapes = [
    MultiPoint([points[n] for n in cc]).convex_hull
    for cc in nx.connected_components(db.to_networkx())
    if len(cc) > 1
]

Примечание: точки 17 и 18 связаны (поскольку диагональ = 1), в отличие от того, что показано на вашем рисунке.

Выход (shapes):

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

С анимацией, подчеркивающей разницу между тремя видами расстояний:

Использовано points :

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),
]

Каждая из «форм», которые вы ищете, представляет собой контур двусвязного компонента на графике.

Начните с поиска двусвязных компонентов, используя любой из алгоритмов на связанной странице в Википедии. Затем для каждого из них начните с верхней левой вершины и обведите ее контур.

Следите за областью по ходу движения: для каждого края контура, опускающегося вниз, area += x1+x2. Для каждого края контура, идущего вверх, area -= x1+x2. В конце area = abs(area)/2.

Запомните площадь самой большой фигуры.

Ваша интуиция по формированию выпуклой оболочки для каждого кластера точек — хорошая идея. Однако, поскольку максимальное расстояние сегментов линии равно единице, нам придется изменить алгоритм выпуклой оболочки, поскольку не гарантируется, что все внутренние углы будут меньше 180 градусов с этим дополнительным ограничением при формировании оболочки.

Вот одно из возможных решений.

Мы можем модифицировать сканирование Грэма, заменив сортировку упорядоченным обходом пути. Путь должен состоять из ребер длины один между любыми двумя точками и быть круговым.

Предполагая, что нет перекрывающихся фигур, мы можем найти самый длинный соединенный круговой путь для каждой точки. Мы начинаем с построения списка смежности для представления графа со смещением против часовой стрелки, где каждая точка соединена с соседними точками на расстоянии одной единицы. Затем мы выполняем поиск в глубину из каждой точки, чтобы изучить все возможные пути. Вот одна из таких реализаций:

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)

Это можно запомнить для работы в линейном времени, и также существует много разных способов получить этот путь.

Для этих points взято из ответа Timeless.

 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),
 ]

Мы находим следующие пути.

Затем мы можем изменить алгоритм сканирования Грэма, чтобы включить ограничение смежности, гарантируя, что сегменты между точками действительны. Это справедливо, поскольку путь, по которому следует следовать, смещен против часовой стрелки, следовательно, 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

Мы можем передать найденные пути в модифицированное сканирование Грэма, чтобы сформировать оболочки.

Вот полный код. Это всего лишь черновик, и есть возможности для оптимизации.

Немного неясно, хотите ли вы найти наибольшую возможную фигуру среди всех точек. Однако, если у вас теперь есть точки и точки периметра каждой фигуры, вы можете вычислить площадь каждой фигуры за линейное время, используя Теорему о шнурках:

, чтобы найти наибольшую форму.