У меня есть двумерный массив bool, подобный этому
В фигуре не будет никаких отверстий — даже если они есть — я их проигнорирую. Теперь я хочу найти многоугольник, охватывающий мою фигуру:
Есть ли готовый алгоритм для этого случая? Мне ничего не удалось найти, но я не уверен, знаю ли я правильный поисковый запрос для этой задачи.
Вы можете использовать триангуляцию Делоне, а затем удалить самые длинные ребра. Я использую среднее значение всех ребер, умноженное на константу.
Немного подумав, я обнаружил это, и есть O (n)-способ сделать это: поиск по строке для первой координаты, которая содержит хотя бы одно соседнее поле, установленное как true. Оттуда вы определенно можете сделать первый шаг вправо. Отныне просто ходите по полю, решая, в каком направлении идти дальше, исходя из четырех соседних полей.
