Определить, если контур закрыт или нет

Question

Мне нужен способ определить, представляет ли контур линию или замкнутую форму. В Java у меня есть объект Shape , который содержит все точки, которые снова определяют его как отдельные объекты. Объект Точка представляет координаты точки. Я попытался проанализировать фигуры с помощью рекурсии, но для более крупных фигур, более 150 баллов, производительность очень низкая. Я прилагаю изображение форм, которые я хочу проанализировать, чтобы лучше понять вопрос.

Я помещаю изображение для лучшей визуализации проблемы.

Это просто показывает все формы, которые я получил. Я хочу отобразить только два закрытых.

Спасибо заранее. Василь Коссев

Answer 1

Первая идея: используйте подходящий алгоритм трассировки контура , чтобы получить упорядоченный контур. Если ваш контур замкнут, вы в конечном итоге вернетесь к первой точке.

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

Третья идея: использовать морфологию. Удалить одиночные пиксели. Найти все конечные точки и точки ветвления. Удалить все точки ветвления. Связанные компоненты без конечных точек - это замкнутые контуры («круги»), связанные компоненты с двумя конечными точками - это открытые контуры («линии»). Перепроектируйте подключенные компоненты без конечных точек на исходное изображение и оставьте только подключенные компоненты, которые имеют общую часть с ними. Я думаю, что это может быть реализовано в режиме реального времени и проще всего.

Answer 2

Если у вас есть контурные линии шириной 1 пиксель, то вы можете посчитать количество соседей для каждой точки *. Если каждая точка данного контура имеет 2 соседей, то контур является замкнутым . Если есть 2 точки с только 1 соседом в каждой, то контур равен открытый .

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

* Подсчет соседей очень просто: используйте исходное изображение! Выберите одну точку контура случайным образом, проверьте соседние 8 пикселей и сосчитайте те, которые являются частью контура. Затем повторяйте проверку соседей для них и так далее, пока все пиксели контура не будут проверены.

Answer 3

Если точки сохраняются по порядку, вы можете сравнить первые и последние точки. Если они пространственно равны, контур замкнут.