Как найти замыкание всех точек

Приветствую Вас, уважаемые Читатели! Сегодня у нас последний из выпусков подборки «Абстрактная математика» перед переходом к удивительно красивому и строгому миру топологических пространств. В прошлых материалах мы познакомились с понятиями внутренности, внешности и границы. Сейчас же мы рассмотрим не менее важное понятие замыкания. Итак, поехали!

Замыкание как множество

Рассмотрим произвольное множеств Х (считаем, что оно всеобъемлющее). Рассмотрим две его особенные точки: одна из них лежит внутри, а вторая – на границе множества.

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

У каждой из этих точек любая окрестность пересекается с множеством Х. Множество всех предельных точек множества составляет его замыкание:

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

Другое определение cl(Х) – это пересечение всех замкнутых множеств, содержащих Х.

Поскольку пересечение произвольного семейства замкнутых множеств замкнуто (не зря же мы рассматривали это фундаментальное свойство), замыкание всегда есть замкнутое множество.

Следующее важное свойство замыкания мы восстановим в связке с понятием внешности множества. Пусть А лежит в множестве Х. Тогда замыкание – это наименьшее замкнутое множество, включающее в себя данное множество.

Чтобы его получить, нужно из бОльшего множества Х вычесть внутренность дополнения А (заштрихованную область). Внутренность дополнения – это внешность, как мы определили в прошлом материале.

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

Замыкание как операция

Теперь используем прошлое равенство для решения вполне конкретной задачи, в которой мы будем применять замыкание как унарную операцию над множеством. Итак, нам требуется найти замыкание множества рациональных чисел Q на вещественной прямой R:

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

Для этого (по формуле выше) рассмотрим, что из себя представляет внешность множества рациональных чисел. Взгляните на произвольный интервал:

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

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

Когда пустая внешность – это всюду плотность. Что такое замыкание множества (ч.10)

Интуитивно, множество рациональных чисел «настолько плотное», что всё, что кроме него составляет множество меры 0, в промежутках между (вне) рациональными числами не найти такого, что их не содержит. В топологии принято использовать термин «всюду плотное множество».

Замыкание же его, судя по формуле, равно R. Если приводить еще примеры на вещественной оси, то замыкание отрезка, интервала и полуинтервала – это отрезок с соответствующими концами.

  • Спасибо за внимание! Следующий материал – про топологические пространства!
  • TELEGRAM и Вконтакте– там я публикую не только интересные статьи, но и математический юмор и многое другое.

В математике, замыкание подмножества S точек в топологическое пространство состоит из всех точек в S вместе со всеми предельными точками S. Замыкание S может быть эквивалентно определено как union S и его границы, а также как пересечение всех замкнутых множеств, содержащих S.Интуитивно замыкание можно рассматривать как все точки, которые находятся либо в S, либо “около” S. Точка, которая находится в замыкании S, является точкой замыкания S. Понятие замыкания во многих отношениях двойственно к понятие внутреннее.

Содержание

  • 1 Определения
    • 1.1 Точка закрытия
    • 1.2 Предельная точка
    • 1.3 Закрытие набора
  • 2 Примеры
  • 3 Оператор закрытия
  • 4 Факты о закрытии
  • 5 Категориальная интерпретация
  • 6 См. Также
  • 7 Примечания
  • 8 Ссылки
  • 9 Внешние ссылки

Определения

Точка закрытия

Для S подмножество евклидова пространства, x является точкой закрытия S, если каждый открытый шар с центром в x содержит точку из S (эта точка может быть самой x).

Это определение обобщается на любое подмножество S метрического пространства X. Полностью выраженный, для X метрическое пространство с метрикой d, x является точкой замыкания S, если для любого r>0 существует y в S такое, что расстояние d (x, y) < r. (Again, we may have x = y.) Another way to express this is to say that x is a point of closure of S if the distance d(x, S) := inf { d (x, s): s в S} = 0.

Это определение обобщается на топологические пространства путем замены «открытого шара» или «шара» на «окрестности “. Пусть S – подмножество топологического пространства X. Тогда x является точкой замыкания (или точкой соединения ) S, если каждая окрестность x содержит точка S. Обратите внимание, что это определение не зависит от того, должны ли окрестности быть открытыми.

Предельная точка

Определение точки закрытия тесно связано с определением предельной точки. Разница между этими двумя определениями тонкая, но важная – а именно, в определении предельной точки каждая окрестность рассматриваемой точки x должна содержать точку из множества, отличную от самой x. Множество всех предельных точек набора S называется производным набором набора S.

Таким образом, каждая предельная точка является точкой закрытия, но не каждая точка закрытия – это предельная точка. Точка закрытия, которая не является предельной точкой, является изолированной точкой. Другими словами, точка x является изолированной точкой S, если она является элементом S и если существует окрестность x, которая не содержит других точек S, кроме самого x.

Для данного множества S и точка x, x является точкой замыкания S тогда и только тогда, когда x является элементом S или x является предельной точкой S (или обоих).

Замыкание множества

Замыкание подмножества подмножества S топологического пространства (X, τ), обозначаемое cl (S), Cl (S), S или S можно определить с помощью любого из следующих эквивалентных определений:

  1. cl (S) – это набор всех точек закрытия S.
  2. cl (S) – множество S вместе с всеми его предельными точками.
  3. cl (S) – это пересечение всех замкнутых множеств, содержащих S.
  4. cl (S) наименьшее замкнутое множество, содержащее S.
  5. cl (S), является объединением S и его границы ∂(S).
  6. cl (S) – это множество всех x ∈ X, для которого существует сеть (со значениями) в S, сходящаяся к x в (X, τ).

Замыкание множества обладает следующими свойствами.

  • cl (S) является закрытым надмножеством S
  • Множество S закрыто тогда и только тогда, когда S = cl (S).
  • Если S является подмножество T, то cl (S) является подмножеством cl (T).
  • Если A – замкнутое множество, то A содержит S тогда и только тогда, когда A содержит cl (S).

Иногда второе или третье свойство выше рассматривается как определение топологического замыкания, которое все еще имеет смысл при применении к другим типам замыканий (см. ниже).

В пространстве с первым счетом (например, метрическое пространство ), cl (S) – это набор всех пределов всех сходящихся последовательностей точек в S.Для общего топологического пространства это утверждение остается верным, если заменяет «последовательность» на «net » или «фильтр ».

Обратите внимание, что эти свойства также удовлетворяются, если “закрытие”, “надмножество”, “пересечение”, “содержит / содержащий”, “наименьший” и “закрытый” заменяются на “внутреннее”, “подмножество”, «объединение», «содержащийся в», «наибольший» и «открытый». Подробнее об этом см. Ниже в разделе оператор замыкания.

Примеры

Рассмотрим сферу в 3 измерениях. Неявно есть две области интересов, создаваемые этой сферой; сама сфера и ее внутренность (которая называется открытым 3-шаром). Полезно уметь различать внутреннюю часть 3-шара и поверхность, поэтому мы различаем открытый 3-шар и закрытый 3-шар – закрытие 3-шара. Закрытие открытого 3-шара – это открытый 3-шар плюс поверхность.

В топологическом пространстве :

  • В любом пространстве, ∅ = cl (∅) { displaystyle varnothing = mathrm {cl} ( varnothing)} varnothing =  mathrm {cl} ( varnothing) .
  • В любом пространстве X, X = cl (X).

Придание R и C стандартной (метрической) топологии :

  • Если X – евклидово пространство R из действительных чисел, тогда cl ((0, 1)) = [0, 1].
  • Если X – евклидово пространство R, то Замыкание набора Q из рациональных чисел представляет собой все пространство R . Мы говорим, что Q является плотным в R.
  • . Если X является комплексной плоскостью C= R, то cl ({z in C : | z |>1}) = {z in C : | z | ≥ 1}.
  • Если S является конечным подмножеством евклидова пространства, то cl (S) = S. (Для общего топологического пространства это свойство эквивалентно T1аксиома.)

На множество действительных чисел можно поставить другую топологию вместо стандартной.

  • Если X = R, где R имеет нижнюю предельная топология, тогда cl ((0, 1)) = [0, 1).
  • Если рассматривать на R дискретную топологию, в которой каждое множество замкнуто (открыто), тогда cl ((0, 1)) = (0, 1).
  • Если рассматривать на R тривиальную топологию в котором единственными закрытыми (открытыми) множествами являются пустое множество и сам R, тогда cl ((0, 1)) = R.

Эти примеры показывают, что закрытие множества зависит от топологии нижележащее пространство. Последние два примера являются частными случаями следующего.

  • В любом дискретном пространстве, поскольку каждое множество закрыто (а также открыто), каждое множество равно своему закрытию.
  • В любом недискретном пространстве X, поскольку единственными замкнутыми множествами являются пустое множество и сам X, мы имеем, что закрытие пустого множества является пустым множеством, и для каждого непустого подмножества A из X cl (A) = X. Другими словами, каждое непустое подмножество недискретного пространства плотно.

Замыкание множества также зависит от того, в каком пространстве мы выполняем замыкание. Например, если X – это набор рациональных чисел, с обычной относительной топологией, индуцированной евклидовым пространством R, и если S = ​​{q in Q : q>2, q>0}, тогда S закрывается в Q, и закрытие S в Q равно S; однако замыкание S в евклидовом пространстве R – это набор всех действительных чисел, больших или равных 2. { displaystyle { sqrt {2}}.}{ sqrt {2}}.

Оператор замыкания

A оператор замыкания для набора X – это отображение набора мощности для X, P (X) { displaystyle { mathcal {P}} (X)}{ mathcal {P}} (X) , в себя, которое удовлетворяет аксиомам замыкания Куратовского.

Учитывая топологическое пространство (X, T) { displaystyle (X, { mathcal {T}})}(X, { mathcal {T}}) , отображение: S → S для всех S ⊆ X является оператором замыкания на X. И наоборот, если c является оператором замыкания на множестве X, топологическое пространство получается путем определения множеств S с c (S) = S как замкнутых множеств (так что их дополнениями являются открытые множества топологии).

Оператор замыкания двойственен оператору внутреннего в смысл, что

S = X (X S)

, а также

S = X (X S)

, где X обозначает базовое множество топологического пространства, содержащего S, а обратная косая черта относится к теоретико-множественной разнице.

Следовательно, абстрактная теория операторов замыкания и d аксиомы замыкания Куратовского можно легко перевести на язык внутренних операторов, заменив множества их дополнениями .

В общем случае оператор замыкания не коммутирует с пересечениями. Однако в полном метрическом пространстве верен следующий результат:

Теорема (К. Урсеску) – Пусть X будет полным метрическим пространством и пусть S 1, S 2,… быть последовательностью подмножеств X.

  • Если каждый S i замкнут в X, то cl ⁡ ( ∪ я ∈ N int ⁡ S я) знак равно cl ⁡ int ⁡ (∪ я ∈ NS я) { displaystyle operatorname {cl} left ( cup _ {i in mathbb {N}} operatorname {int} S_ {i} right) = operatorname {cl} operatorname {int} left ( cup _ {i in mathbb {N}} S_ {i} right)}{ displaystyle  operatorname {cl}  left ( cup _ { i  in  mathbb {N}}  operatorname {int} S_ {i}  right) =  operatorname {cl}  operatorname {int}  left ( cup _ {i  in  mathbb {N}} S_ { i}  right)} .
  • Если каждое S i открыто в X, тогда int ⁡ (∩ i ∈ N cl ⁡ S i) = int ⁡ cl ⁡ (∩ i ∈ NS i) { displaystyle operatorname {int} left ( cap _ {i in mathbb {N}} operatorname {cl} S_ {i} right) = operatorname {int} operatorname {cl} left ( cap _ {i in mathbb {N}} S_ {i} right)}{ displaystyle  operatorname {int}  left ( cap _ {i  in  mathbb {N}}  operatorname {cl} S_ {i}  right) =  operatorname {int}  operatorname {cl}  left ( cap _ {i  in  mathbb {N}} S_ {i}  right)} .

Факты о замыканиях

Набор S { displaystyle S}S закрыт тогда и только тогда, когда С l (S) = S { Displaystyle Cl (S) = S}Cl (S) = S . В частности:

Если A { displaystyle A}A является подпространством из X { displaystyle X}X , содержащий S { displaystyle S}S , затем закрытие S { displaystyle S}S , вычисленное в A { displaystyle A}A , равно пересечению A { displaystyle A}A и замыканию S { displaystyle S}S вычисляется в X { displaystyle X}X : C l A (S) = A ∩ C l X (S) { displaystyle Cl_ {A} (S) = A cap Cl_ {X} (S)}Cl_ {A} (S) = A  cap Cl_ {X} (S) . В частности, S { displaystyle S}S плотно в A { displaystyle A}A тогда и только тогда, когда A { displaystyle A}A является подмножеством C l X (S) { displaystyle Cl_ {X} (S)}Cl_ {X} (S) .

Категориальная интерпретация

Можно элегантно определить оператор замыкания в терминах универсальные стрелки, как показано ниже.

powerset набора X может быть реализован как частичный порядок категория P, в котором объекты являются подмножествами, а морфизмы – включениями A → B { displaystyle A to B}A  to B , если A является подмножеством B. Кроме того, топология T на X является подкатегорией P с функтором включения I: T → P { displaystyle I: T to P}I: T  to P . Набор замкнутых подмножеств, содержащий фиксированное подмножество A ⊆ X { displaystyle A substeq X}A  substeq X , можно идентифицировать с помощью категории запятой (A ↓ I) { displaystyle (A стрелка вниз I)}(A  downarrow I) . Эта категория – также частичный порядок – тогда имеет начальный объект Cl (A). Таким образом, существует универсальная стрелка от A к I, заданная включением A → C l (A) { displaystyle A to Cl (A)}A  to Cl (A) .

Аналогично, поскольку каждое замкнутое множество, содержащее X A, соответствует с открытым набором, содержащимся в A, мы можем интерпретировать категорию (I ↓ X ∖ A) { displaystyle (I downarrow X setminus A)}( Я стрелка вниз X  setminus A) как набор открытых подмножеств, содержащихся в A, с конечным объектом int (A) { displaystyle { text {int}} (A)}{ text {int}} (A) , внутренним из A.

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

См. Также

  • Точка привязки
  • Алгебра замыкания
  • Производное множество (математика)
  • Внутреннее (топология)
  • Предельная точка – точка, к которой сходятся функции в топологии

Примечания

Ссылки

  • Бейкер, Крамп В. (1991), Введение в топологию, Wm. C. Brown Publisher, ISBN 0-697-05972-3
  • Крум, Фред Х. (1989), Принципы топологии, Saunders College Publishing, ISBN 0-03-012813-7
  • Джеминьяни, Майкл К. (1990) [1967], Элементарная топология (2-е изд.), Довер, ISBN 0-486-66522-4
  • Hocking, John G.; Янг, Гейл С. (1988) [1961], Топология, Довер, ISBN 0-486-65676-4
  • Куратовски К. (1966), Топология, I, Academic Press
  • Pervin, William J. (1965), Foundations of General Topology, Academic Press
  • Schubert, Horst (1968), Topology, Allyn and Bacon

External ссылки

  • , Энциклопедия математики, EMS Press, 2001 [1994]

В геометрии и топологии замыка́ние подмножества топологического пространства — это пересечение всех замкнутых подмножеств содержащих данное подмножество. Эквивалентно, замыкание подмножества — это совокупность всех его точек прикосновения.

Точка прикосновения

Определение

Пусть задано топологическое пространство {displaystyle (X,{mathcal {T}})}, и подмножество {displaystyle Msubset X}. Точка {displaystyle xin X} называется то́чкой прикоснове́ния множества {displaystyle M}, если любая её окрестность пересекается с {displaystyle M}. То есть,

{displaystyle forall Uin {mathcal {T}}quad (xin U)Rightarrow (Ucap Mnot =emptyset ).}

Замечание

Очевидно, если {displaystyle xin M}, то {displaystyle x} является точкой прикосновения. Обратное, вообще говоря, неверно.

Примеры

Пусть {displaystyle X=mathbb {R} } – множество действительных чисел со стандартной топологией, и {displaystyle M=(a,b)} – произвольный интервал. Тогда любая точка {displaystyle xin [a,b]} является точкой прикосновения {displaystyle M}.

Замыкание

Определение

Совокупность всех точек прикосновения множества {displaystyle Msubset X} называется замыканием {displaystyle M} и обозначается {displaystyle {bar {M}}} или {displaystyle mathrm {cl} (M)}.

Свойства

  1. Операция замыкания является унарной операцией на множестве всех подмножеств {displaystyle X}.
  2. Замыкание множества содержит само множество, то есть {displaystyle Msubset {bar {M}}}.
  3. Замыкание множества замкнуто.
  4. Множество замкнуто тогда и только тогда, когда оно совпадает со своим замыканием, то есть {displaystyle M={bar {M}}}.
  5. В частности, {displaystyle {bar {X}}=X,;{bar {emptyset }}=emptyset .}
  6. {displaystyle {bar {bar {M}}}={bar {M}}.}
  7. Замыкание множества {displaystyle M} является наименьшим замкнутым множеством, содержащим {displaystyle M}, то есть {displaystyle {bar {M}}=bigcap left{Csupset Mmid C={bar {C}}right}.}
  8. Замыкание сохраняет отношение вложения, то есть {displaystyle (Msubset N)Rightarrow left({bar {M}}subset {bar {N}}right).}
  9. Замыкание объединения есть объединение замыканий, то есть {displaystyle {overline {Acup B}}={bar {A}}cup {bar {B}}.}
  10. Замыкание пересечения есть подмножество пересечения замыканий (но, вообще говоря, не равно ему), то есть {displaystyle {overline {Acap B}}subset {bar {A}}cap {bar {B}}.}

Замечание

Свойство 7 часто принимается в качестве определения замыкания. Данное выше определение тогда выводится в качестве одного из свойств.

Примеры

Во всех нижеследующих примерах топологическим пространство является числовая прямая {displaystyle mathbb {R} } с заданной на ней стандартной топологией.

cs:Uzávěr množiny
he:סגור (טופולוגיה)
pl:Domknięcie

У этого термина существуют и другие значения, см. Замыкание.

Замыка́ние — конструкция, дающая наименьшее замкнутое множество, содержащее данное множество топологического пространства.

Замыкание множества S обычно обозначается bar S. Другие обозначения: {displaystyle operatorname {cl} (S),operatorname {Cl} (S).}

Определения[править | править код]

Следующие два определения равносильны.

Как наименьшее замкнутое множество[править | править код]

Пусть S есть подмножество топологического пространства X.
Замыканием S в X называется пересечение всех замкнутых множеств, содержащих S.

Замечание.
Поскольку пересечение произвольного семейства замкнутых множеств замкнуто, замыкание всегда замкнуто.

Через точки прикосновения[править | править код]

Точка x топологического пространства X называется точкой прикосновения множества S, если любая окрестность x содержит хотя бы одну точку множества S.

Множество всех точек прикосновения S называется замыканием S.

Свойства[править | править код]

  1. Замыкание множества замкнуто.
  2. Замыкание множества содержит само множество, то есть
    {displaystyle Ssubseteq {bar {S}}.}
  3. Замыкание множества содержит все его предельные точки.
  4. Множество замкнуто тогда и только тогда, когда оно совпадает со своим замыканием, то есть
    S=bar{S}.
  5. Свойство идемпотентности: повторное применение операции замыкания не изменяет результат (что сразу вытекает из свойств 1 и 4):
    bar{bar{S}}=bar{S}.
  6. Замыкание сохраняет отношение вложения, то есть
    (Ssubset T)Rightarrow(bar{S}subsetbar{T}).
  7. Замыкание объединения есть объединение замыканий, то есть
    overline{Scup T}=bar{S}cupbar{T}.
  8. Замыкание пересечения является подмножеством пересечения замыканий, то есть
    overline{Scap T}subsetbar{S}capbar{T}.

Примеры[править | править код]

Во всех нижеследующих примерах топологическим пространством является числовая прямая mathbb {R} с заданной на ней стандартной топологией.

Время на прочтение
9 мин

Количество просмотров 5.2K

Это история не столько про алгоритмы сколько про ассоциации. Именно ассоциация с каналами кодирования цветов и послужила причиной написания этой статьи.

image

______________________________________________________________________________________

Суть:

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

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

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

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

Все обработанные узлы кешируются в той самой дополнительной матрице узлов и удаляются из общего цикла.

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

Если замыкание установлено класс вернет список всех точек контура, нет, он вернет undefined.

Раскраска векторов позволяет избавиться от токсичных узлов для анализа в одном из направлений, и при этом оставить актуальными узлы для обработки в других каналах. Именно нахождение одного узла в двух каналах и устанавливает соединение. Узел в двух и более обнаруженных каналах, является связующим узлом.

_____________________________________________________________________________________

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

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

Первым зарегистрировалась левая от центральной клетка, далее правая, верхняя и нижняя.

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

Алгоритм нашел два узла, единственную голубую и примыкающую к ней фиолетовую. Он пометил обе клетки как узлы соединения.

______________________________________________________________________________________

История ассоциаций:

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

Задача, вероятно, покажется вам достаточно простой, но я бы хотел пояснить что работаю на стыке двух областей программирования и дизайна, в связи с чем я не считаю себя ни сильным программистом ни сильным дизайнером, но в сумме у меня не плохой бекграунд для работы в области generative art или data visualization. В мир программирования я вошел через гейм. дев. К тридцати годам я накопил множество интересных знаний, но с учетом того что в найм обычно требуются узко специализированные специалисты мне порой приходится нелегко. Словом, это все лирика, возвращаясь к алгоритму у меня не было на момент начала работ готового алгоритма и я ушел гуглить, с учетом того что задание на самом деле комплексное и не ограничивается исключительно этой задачей, я посчитал это вполне корректным.

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

Я продолжил поиски, на этот раз я решил искать алгоритмы которые используются для заливки области однородным цветом в графических редакторах, через некоторое время я вышел на цепной код Фримена. Далее были статьи про распознавание контура в двухмерных и трехмерных пространствах, распознавание контура лиц и дорожных знаков, OpenCV, внутренности AutoCad, и большая база теоретической математики контуров, словом, невероятно увлекательное приключение, которое, тем не менее, жгло время. После если четырех часов чтива, я понял что все глубже погружаюсь в теоретические дебри и загрустил. Время безжалостно убегало, домашний пес просился на прогулку и я решил что сразу как вернусь буду писать алгоритм сам.

Не буду описывать весь свой ход мыслей, по возвращению у меня была одна идея от которой я хотел оттолкнуться. Я понимал что, в действительности все не так сложно, у нашего алгоритма очень ограниченные возможности в передвижении по матрице, и мне просто нужна циклическая функция которая обходит все связанные точки. Алгоритм мог двигаться максимально всего в четырех направлениях, мне нужно отправить его в путь и как-то поймать его при приближении к исходной точки. Я не без улыбки вспоминал того парня который орал на оператора интернет провайдера, ну вы помните, про «разрыв соединения». Собственно это и была наша с псом полу-готовая идея.Изначально я хотел намеренно разорвать одно из направлений движения и, в случае если бы он вернулся по разорванной линии установить что контур замкнулся. Порисовав немного на бумаге, я понял что у моего варианта есть множество сложных исключений, главное из которых заключается в том что я могу разорвать связь по ложному вектору и, в итоге, просто упереться в тупик. Другие важные исключения были связаны с некой «токсичностью» уже пройденных точек, от которых нужно было избавляться, но которые в случае их утилизации блокировали весь цикл. Не уверен что я слишком точно описываю возможные проблемы, но надеюсь вы меня понимаете. Словом, все было очень плохо до тех пор пока я вдруг не нашел для векторов более подходящего и емкого определения. Я искал решение в четырех возможных каналах движения. Постойте, четыре канала, я же где-то уже это слышал. CMYK. Решение было найдено. Я решил покрасить каналы и тем самым избавиться от токсичности уже обработанных клеток.
Дальнейшая работа была связана уже исключительно с реализацией этой идеи на typescript.

Вместо заключения я хотел бы просто посоветовать всем желающим ознакомится с замечательной книгой Дэна Рома «Визуальное мышление». Возможно это не совсем к месту, но я был в свое время в большом восторге от ее прочтения.

Я спокойно приму вашу критику, поэтому вы можете указать мне на мои возможные ошибки и не слишком стройную архитектуру. Коду всего один день, надеюсь он найдет свое применение.

// algorith/cmyk.ts

import Point from "./../geom/point";

class StreamNode {

    // channel statuses
    public static BLACK: number = 0;
    public static CYAN: number = 1;
    public static YELLOW: number = 2;
    public static MAGENTA: number = 3;

    // link to position in original field
    public point: Point;

    // actual statuses channels
    protected cyan: boolean = false;
    protected yellow: boolean = false;
    protected magenta: boolean = false;
    protected black: boolean = false;

    // current channel
    public channel: number;

    /*
     * @ point - position in field
     * @ channel - node stream channel
     * @ full - if it is a entry point 
    */
    constructor(point: Point, channel: number, full: boolean = false) {
        this.point = point;
        this.channel = channel;
        if (full) {
            this.cyan = true;
            this.yellow = true;
            this.black = true;
            this.magenta = true;
        } else {
            this.registerChannel(channel);
        }

    }

    // register channel status, if it is a connection node or entry node several channels can be marked
    public registerChannel (channel: number): void {
        switch (channel) {
            case StreamNode.BLACK:
                this.black = true;
                break;
            case StreamNode.CYAN:
                this.cyan = true;
                break;
            case StreamNode.YELLOW:
                this.yellow = true;
                break;
            case StreamNode.MAGENTA:
                this.magenta = true;
                break;
            default:
                break;
        }
    }

    // check if it is a native or foreign channel
    public varifyChannel (channel: number): boolean {
        switch (channel) {
            case StreamNode.BLACK:
                return this.black === true;
            case StreamNode.CYAN:
                return this.cyan === true;
            case StreamNode.YELLOW:
                return this.yellow === true;
            case StreamNode.MAGENTA:
                return this.magenta === true;
            default:
                throw "can not identify channel";
        }
    }
}

class CMYK  {

    // matrix of field points, points can be full/empty/transformed
    private matrix: number[][];

    // matrix of stream nodes
    private nodes: StreamNode[][];

    // start point fo analize
    private sourcePoint: Point;

    // status of contrur, if we find connection, we will register it
    private connection: boolean = false;

    /*
     * @source:Point - start point for analyze
     * @matrix:number [][] - matrix of points and there states
     */
    public getStream (source: Point, matrix: number[][]): Point[] {

        // register sourcePoint 
        this.sourcePoint = source;

        // list of all points of cursor
        let responseStream: Point[] = [source];

        // no connections, contur is not closed at the moment
        this.connection = false;

        // sync matrix of points with matrix of stream nodes 
        this.syncMatrixes(matrix);

        // create a node for source point
        let sourceNode: StreamNode = new StreamNode(source, 0, true);

        // register node in matrix of nodes
        this.nodes[source.x][source.y] = sourceNode;

        // init nearest neighbors
        let neighbors: StreamNode[] = this.censur(source, 0, true);

        // init loop stream
        let stream: StreamNode[] = [];

        // add nearest neighbors into stream
        stream = stream.concat(neighbors);

        // run loop
        while (stream.length) {

            // extract some node 
            sourceNode = stream.pop();

            // register point of contur
            responseStream.push(sourceNode.point);

            // add neighbors of this point to stream 
            stream = stream.concat(this.censur(sourceNode.point, sourceNode.channel));
        };


        if (this.connection) {
            // if contur is closed return list of cursor points
            return responseStream;
        } else {
            return undefined;
        }
    }

    /*
     *  Sync matrix of points and matrix of stream nodes
     *  @matrix number[][] - number of points in field    
     */
    private syncMatrixes (matrix: number[][]): void {
        this.matrix = matrix;
        let rows: number = matrix.length;
        let lines: number  = matrix[0].length;
        this.nodes = [];
        for (let i: number = 0; i < rows; i ++) {
            this.nodes[i] = [];
            for (let j: number = 0; j < lines; j ++) {
                this.nodes[i][j] = undefined;
            }
        }
    }

    /*
     * Register new nodes, the nearest neighbors of actual stream node
     * 
     * @source - actual stream position
     * @channel - actual direction of analyze 
     * @increment - channel flag, let register the start point, or point of channel direction
     */
    private censur (source: Point, channel: number, increment: boolean = false): StreamNode[] {
        let stream: StreamNode[] = [];
        let xPosition: number = source.x - 1;
        let yPosition: number = source.y;
        let _channel: number = channel;

        // push left neighbor to stream if it not out of matrix border 
        if (source.x > 0) {
           this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        // change chanel for start point registration 
        if (increment) {
            _channel ++;
        }

        // push right neighbor 
        if (source.x < this.nodes.length - 1) {
            xPosition += 2;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        if (increment) {
            _channel ++;
        }

        // push up neighbor
        if (source.y > 0) {
            xPosition = source.x;
            yPosition -= 1;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        if (increment) {
            _channel ++;
        }

        // push down neighbor
        if (source.y < this.nodes[0].length - 1) {
            xPosition = source.x;
            yPosition += 2;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        return stream;
    }

    /*
     * Register new node for analyze if it doesn't analized yet
     * If it does we varifyChannel, if the channel is the same of parameter channel,
     * it mean that this is parent node, who create this one, and we ignore it. 
     * If the chanels are not the same, we found the connection and contur is closed 
     * If the status of point is empty, we ignore this point, and don't register new node 
     * 
     * @ xPosition - point X
     * @ yPosition - point Y
     * @ stream - stream of nodes which used in node
     * @ channel - actual direction channel
     */
    private pushToStream (xPosition: number, yPosition: number, stream: StreamNode[], channel: number): void {
        // new node
        let node: StreamNode;

        // there is no point in field (empty status) 
        if (this.matrix[xPosition][yPosition] !== 1) {
            // ignore it
            return;
        }
        // this node is already created
        if (this.nodes[xPosition][yPosition] !== undefined) {
            node = this.nodes[xPosition][yPosition];

            // check if this a parent node
            if (node.varifyChannel(channel)) {
                // ignore if it is
                return;
            } else {
                // Congratulattions! We found the connection
                this.connection = true;
                // add one mode channel status to node
                node.registerChannel(channel);

                // here we also can add the point of this node to coonections list ...
                // I don't need it, so I didn't 
            }
        } else {
            // register new node and add it in loop stream
            let point = new Point(xPosition, yPosition);
            node = new StreamNode(point, channel);
            this.nodes[xPosition][yPosition] = node;
            stream.push(node);
        }
    }
}

export default CMYK;

     
//  geom/point.ts
 
class Point {
    public x: number;
    public y: number;

    constructor(x: number, y:number) {
        this.x = x;
        this.y = y;
    }
}

export default Point; 

 

Добавить комментарий