Найти полигон из bool-grid

Question

Найти полигон из bool-grid

У меня есть двумерный массив bool, как это

2-мерный массив bool

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

охватывающий многоугольник

Есть ли готовый алгоритм для этого случая? Я не смог найти ни одного, но я не уверен, знаю ли я правильный поисковый термин для этой задачи.

-1

arrays bitmap polygon concave-hull

Источник

user2033412 16 сен '13 в 13:42

2 ответа

Решение

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

0

Источник

user340457 16 сен '13 в 14:15

Другие вопросы по тегам arrays bitmap polygon concave-hull

user2033412 18 сен '13 в 07:26 2013-09-18 07:26 · Accepted Answer · 2013-09-18 07:26

Подумав немного больше, я выяснил это, и для этого есть O(n)-поток: Поиск по строке для первой координаты, которая содержит хотя бы одно смежное поле, установленное в true. Оттуда вы можете сделать первый шаг вправо. Отныне просто ходите по полю, решая, в каком направлении идти дальше, основываясь на четырех смежных полях.