Алгоритм Raster to Shape

[lell3]

Добрый день.
Прошу помочь советом.

Есть бинарный геопривязанный файл (координаты точек А1,А2,А3,А4 на рисунке 1 известны). На фоне нулевых значений единицами отображен полигон (см. рисунки 1 и 2).
Задача вычислить кординаты углов полигона(координаты углов а1,а2,а3...аn на рисунке 1).

Подскажите в какую сторону копать? Какие алгоритмы можете посоветовать?


Рисунок 1

Рисунок 2

[Игорь Белов]

Convex hull

[Ariki]

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

Вот что нагуглилось.

[gamm]

Convex hull

неправда ваша - а вдруг он не выпуклый, да еще с дырками?

самый простой вариант - сделать из него растр, и построить изолинии на уровне 0.99 (взять построение изолиний в GDAL). Еще более простой - построить конечный автомат, который обходит объекты по границам клеточек, оставляя объект всегда слева. Да, а капать не нужно, в крайнем случае - копать