Классифицировать точки на сетке

[Loic]

Добрый день!
Возникла такая задача: задана сетка с известным шагом. На сетке есть "особые" узлы, это координаты точек некоторой фигуры, формирующие множество S (на рисунке они выделены красным). В каждой точке сетки задана величина d - это расстояние от этой точки до ближайшей точки из множества S.
Вокруг точек множества S формируется ещё одно множество, в которое, кроме точек S входят и точки, находящиеся от них на расстоянии, не большем, чем R, то есть если $d<=R$, то точки включаются в это новое мноежство (оно закрашено зелёным цветом на рисунке).
Таким образом, исходное множество, состоящее из всех узлов сетки, рабивается на три: 1) узлы, лежащие внутри области, закрашенной зелёным; 2) узлы, которые попали в область, ограниченную этой зелёной полосой - на рисунке она обозначена M2; 3) узлы, которые попали во внешнюю по отношению к "зелёной полосе" область, она обозначена M1.

Рисунок:



И множество M1, и множество M2 одинаковы в том плане, что там в каждом узле $d>R$. Но необходимо их каким-то образом разграничить, то есть пройти все узлы и определить, лежит ли точка во множестве M1, или же она лежит во множестве M2.
Как я понимаю, нужно начинать движение с начала координат - это точка обязательно принадлежит множеству M1. Потом проверять связанные с ней точки на условие $d>R$, при этом каким-то образом прекращая движение, как только мы попадём в зелёную полосу... Но как сделать такой обход, не попадая в точки из множества M2, я не представляю...
Может быть есть какой-то простой способ классификации точек в таком случае?
Заранее спасибо за любые советы!

[ewert]

Выходите из этой области и идите к краю доски (например, по горизонтали). Точка лежит во внутренней области, если количество пересечений с красной линией будет нечётным. Под пересечением понимается ситуация, когда точки, примыкающие к краям очередного сплошь красного участка, на который мы наткнулись, лежат по разные стороны от этой горизонтали.

[Loic]

ewert
Извиняюсь, не совсем корректный рисунок нарисовал - красная линия не обязательно сплошная, там могут быть "дырки", то есть вместо некоторых красных точек (где d=0), могут быть синие (где d<R).

[Pavia]

Делаем бинаризацию. $d>R$ выделяем связанные области известным алгоритмом. Искать по слову Labeling. Дальше просто есть только одно множество M1 которое считается внешним. Как вы сказали это множество содержащие начало координат. А следовательно оно будет первое. Хотя возможно лучше отнести к М1 все множества которые имеют точки расположенные по периметру матрицы.

[Loic]

Pavia, спасибо!
Я правильно понял, что в общем алгоритм должен выглядеть так:
Начинаю движение из начала координат (0,0). Присваиваю этой точке метку OUT, проверяю, если в соседних точках (1,0) и (0,1) d>R, то им также присваиваю метку OUT.
Перехожу к следующей точке (2,0). Проверяю её соседей - в общем случае это точки (i+1,j), (i-1,j), (i,j+1), (i,j-1). Если у них d>R и хотя бы один сосед имеет метку OUT, то и этой точке присваиваю метку OUT. В моём случае одним из соседей для точки (2,0) будет точка (1,0) которой назначена метка OUT. Иду так по всем точкам.
Когда попадаю в множество M2, то оказывается, что хоть там и d>R, но ни одного соседа с меткой OUT нет, в этом случае я пропускаю такую точку.

Или что-то неверно?

[Circiter]

2Loic
Если зеленая область в отличии от красной "линии" не имеет дырок, то вы имеете дело с задачей обычной заливки (если считать точки зеленой области граничными), как в любом простейшем растровом редакторе, вроде ms paint'а. :)

Если же и зеленая область имеет дырки, то, в принципе, эти дырки можно попробовать предварительно закрыть морфологическим dilation-фильтром, а потом произвести заливку или применить идею ewert'а (нечувствительность его алгоритма к небольшим дыркам можно обеспечить направляя "сканирующий луч" в разных направлениях и подсчитывая голоса).

Ещё можно попробовать через МНК натянуть окружность на красные точки... :)