Как проверить, является ли регион кругом?

Question

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

Поиск регионов относительно прост, я сделал это. Однако найти круги сложнее. Моя идея - найти все граничные точки региона, найти среднюю точку - возможный центр этого круга - и вычислить расстояния между каждой граничной точкой и «центром». Тогда, если они не сильно отличаются друг от друга, это действительно круг.

Прежде всего, это даже жизнеспособно? Во-вторых, этот метод также распознает очень тонкие кольца в виде кругов, и я не хочу этого. Как это исправить?

UPD: Как эффективно найти граничные точки? Последний слой BFS? Точки с менее чем 6 соседями (мне кажется, что-то вроде bruteforce)?

Answer 1

После того, как вы оценили радиус путем усреднения расстояния пограничных пунктов к центру, вычислите:

• области A1 пересечения области и окружности
• области А2 окружности
• область А3 области

Затем соотношение этих областей должно быть близко к 1, если это диск. Вы можете определить некоторые допуски. Например:

• А1/А2> 0,98
• А1/А3> 0,97

В качестве альтернативы, радиус можно оценить без границ очков. Просто вычислите среднее расстояние каждой точки региона до центра и умножьте на 3/2.