Схемы отбора в выборку

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

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

image

Основные принципы отбора в выборку

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

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

Если выборка недостаточно репрезентативна — исследование будет считаться предвзятым. Если она будет недостаточно большой — неточным.

image

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

Схемы отбора для вероятностных выборок

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

На основе жеребьевки

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

Из генеральной совокупности N случайным образом отбирается один элемент, вероятность попадания элемента в выборку равна 1/N. Затем из выборки N-1 выбирается второй элемент с вероятностью 1/(N-1) и так далее до n-го элемента с вероятностью 1/(N-n).

Отбор Бернулли

Отбор происходит из упорядоченного списка из N элементов. Пусть наперед задано некоторое число ε (1<ε<0) и набор N независимых реализаций равномерно распределенной на [0,1] случайной величины ε1…εN. Каждому элементу k ставится в соответствие значение. Если εк<π, то этот элемент отбирается, в другом случае — нет. Возможность того, что элемент будет выбран равна π для каждого из N элементов. Таким образом каждый элемент, который попал в выборку является биномиально распределенной величиной.

Систематический отбор

Пусть N — размер генеральной совокупности. а — некоторое фиксированное число. а ∈ N. Первый элемент выборки выбирается случайным образом среди первых a элементов совокупности. Выбранное число r 1≤ r ≤a называется случайным стартом (началом), а число а — выборочным интервалом. Каждый элемент [1,2… а] имеет одинаковую вероятность быть выбранным, равную 1/а. Далее в выборку попадают элементы с шагом а.

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

Простой случайный отбор с возвращением

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

Например, выполняется m независимых отборов элементов из генеральной совокупности размера N с одинаковыми вероятностями 1/N. Отобранный элемент возвращается в совокупность. Таким образом все N элементов участвуют в отборе постоянно.

Пропорциональный отбор: с возвращением и без

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

image

Стратифицированный отбор

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

image

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

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

Схемы отбора для невероятностных выборок

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

Кластерный отбор

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

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

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

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

Типовой отбор

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

Снежный ком

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

Конспект

  1. Выборки бывают вероятностные и невероятностные.
  2. Если неправильно выбран метод отбора в выборку. исследование может стать предвзятым или неточным.
  3. Лучше быть возможно правым, чем точно не правым.

ссылка на оригинал статьи http://habrahabr.ru/post/263931/

Xonix на Javascript с картинками

Xonix — популярная игра времен DOS, клон видеоигры Qix.

На Javascript Xonix уже был портирован несколько раз. Лучшая и наиболее приближенная к оригиналу из существующих реализаций на сегодняшний день, пожалуй, вот эта. Ее я поначалу пытался приспособить для своей реализации/модификации… Но, к сожалению, код даже после деобфускации так и не стал понятным (во всяком случае для меня). К тому же, насколько я смог понять, код там местами не совсем эффективен, либо вовсе устаревший. Так что пришлось все писать с нуля.

В результате у меня получился такой вот «свой» Xonix, с картинками и ответами.

Демо | Исходники

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

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

Основное отличие моей реализации от классического Ксоникса это то, что за черной областью скрывается картинка, уникальная для каждого уровня. Этим она походит на другую модификацию Ксоникса — Sexonix. Но в моей картинка появляется не просто так. Это часть вопроса, на который следует дать ответ. А вся игра таким образом превращается в викторину.

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

Движение всех объектов (курсора и точек) происходит строго по ячейкам, так что в каждый момент времени каждый объект занимает ровно одну ячейку. Такая структура игрового поля значительно упрощает реализацию игры. Сложность представляет только определение «завоеванных» областей, образующихся при пересечении курсором «моря», но об этом позже.

Движение объектов

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

В Xonix у любого объекта есть всего 4 варианта направления движения: для курсора — вверх/вниз/вправо/влево, для точки (обоих типов) — то же самое, только по диагонали. Объединяем эти варианты в множество возможных направлений, которые будем задавать в градусах. Получаем 8 углов движения: от 0 до 315 градусов с шагом 45. Каждому значению угла ставим в соответствие пару координат вектора направления движения. В результате получаем такую структуру, которую будем использовать при расчете движения:

Фрагмент кода

dirset = {     vecs: {         0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1],         180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1]     },     get: function(v) {         return v in this.vecs? this.vecs[v] : [0, 0];     },     find: function(x, y) {         x = x == 0? 0 : (x > 0? 1 : -1);         y = y == 0? 0 : (y > 0? 1 : -1);         for (var v in this.vecs) {             var vec = this.vecs[v];             if (vec[0] == x && vec[1] == y) return parseInt(v);         }         return false;     } }; 

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

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

Для расчета столкновений точек с курсором, отскока точек от границы «своей» области и некоторых других вещей нам понадобится матрица состояний всех ячеек — двумерный массив (n+4) * (m+4),
где (n+4), (m+4) — соответственно ширина и высота игрового поля в ячейках, а первый элемент матрицы соответствует ячейке в левом верхнем углу игрового поля.

Каждый элемент будет хранить состояние соответствующей ячейки, включающее в себя 2 признака: тип области, к которой она относится (море/суша), а также то, проходит ли по ней в данный момент «след» от движения курсора по «морю». Храниться это состояние будет в битовом поле из двух битов. Для этого нам нужно объявить две константы-маски для каждого признака соответственно:

var CA_CLEAR = 1 << 0; // ячейка очищена, т.е. относится к суше var CA_TRAIL = 1 << 1; // ячейка - часть следа движения курсора по "морю" 

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

i = n * (y + 2) + x + 2; x = i % n - 2; y = Math.floor(i / n) - 2 

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

 OOO OX1 O23 

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

Отскок от границы имеет место, если хотя бы в одной из указанных трех ячеек тип области противоположен типу точки. Т.е. если, например, точка «морская», то одна из этих ячеек должна быть «сухопутной». При этом, если данное условие выполняется только в одной из ячеек 1 или 2 (но не в обоих), то к углу движения прибавляется соответственно +90 или -90 градусов. В противном случае угол движения изменяется на противоположный (+180 градусов).

При любом другом угле движения логика отскока очевидно будет точно такой же.

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

Определение столкновения «сухопутной» точки с курсором тривиально. Просто проверяем контакт точки с курсором, сравнивая координаты ячеек точки и курсора. Определение столкновения «морской» точки с курсором чуть сложнее: нам нужно проверить не только контакт самой точки с курсором, но и касание следа движения курсора. Для этого используем второй бит состояния ячеек: проверяем его у всех соседних с точкой ячеек.

Определение «завоеванных» областей

Как уже упоминалось, самое сложное в реализации — определение «завоеванных» у «моря» областей. Это замкнутые области, образующиеся в результате пересечения курсором «моря», внутри которых нет «морских» точек. В большинстве случаев при этом образуются две замкнутые области, получаемые разделением (следом движения курсора) доступной «морской» области на две части, из которых «завоеванной» становится только одна либо ни одной (см. скриншот 1). Но в некоторых, особенно сложных, случаях может образоваться сразу множество замкнутых (см. скриншот 2) и в том числе «завоеванных» областей. Кроме того, возможна ситуация, когда след курсора сам по себе образует замкнутую область (см. скриншот 3).

Скриншот 1

Скриншот 2

Скриншот 3

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

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

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

Контуры замкнутых областей

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

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

На основе перечисленного можно вывести алгоритм нахождения контуров. В общих словах он выглядит так.

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

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

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

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

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

Содержимое и тип замкнутой области

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

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

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

На первой итерации находим сторону (отрезок) многоугольника с наибольшей длиной, являющуюся частью выступающего прямоугольника. Если таких отрезков несколько, выбираем любой из них. Найденный отрезок будет одной из сторон искомого прямоугольника. Теперь нам нужно найти остальные его стороны. Для этого берем отрезки, исходящие из обоих концов найденной стороны перпендикулярно к ней, и выбираем самый короткий из них. Это будет вторая сторона прямоугольника. Чтобы найти третью сторону, нужно найти (ортогональную) проекцию второго конца данного отрезка на второй из перпендикулярных к первой стороне отрезков. Соединяем найденную точку с соответствующим концом первой стороны и получаем третью сторону. Отсюда получаем весь искомый выступающий прямоугольник. Теперь нам нужно отсечь его от исходного многоугольника. Для этого нужно удалить из многоугольника первый и второй найденные отрезки и соответствующие им вершины, после чего добавить найденную точку-проекцию, соединив ее с вершиной, которая раньше соединялась со вторым найденным отрезком. В результате получаем многоугольник, имеющий на две вершины меньше, чем исходный.

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

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

Рассмотрим процесс разбиения на прямоугольники на конкретном примере.
Пусть мы имеем многоугольник ABCDEFGHIJKL (см. рис. 1), представляющий собой контур области. Применим пошагово описанный алгоритм разбиения.

1. Находим сторону многоугольника ABCDEFGHIJKL с наибольшей длиной. Это отрезок CD с длиной 4. Но он нам не подходит, т.к. не является частью выступающего прямоугольника. Поэтому игнорируем его и ищем дальше. Находим 3 отрезка с длиной 3: AL, FG, GH. GH нам не подходит по той же причине, что и CD. Так что остаются отрезки AL, FG. Выбираем любой из них. Пусть это будет AL. Перпендикулярные к нему отрезки — AB и KL, из них самый короткий — AB. Находим проекцию точки B на отрезок KL — это точка M (см. рис. 2). Таким образом получаем отсекаемый прямоугольник — ABML. После его отсечения остается многоугольник CDEFGHIJKM.

2. Находим сторону многоугольника CDEFGHIJKM с наибольшей длиной. Это отрезок FG с длиной 3… Отсекаемый прямоугольник — FGNE (см. рис. 2). После его отсечения остается многоугольник CDNHIJKM.

3. Находим сторону многоугольника CDNHIJKM с наибольшей длиной. Это уже знакомый нам отрезок CD с длиной 4… Отсекаемый прямоугольник — CDNO. После его отсечения остается многоугольник OHIJKM.

4. Находим сторону многоугольника OHIJKM с наибольшей длиной. Таких сторон две. Это отрезки OH и HI с длиной 2. Выбираем первый из них — OH… Отсекаемый прямоугольник — OHPM. После его отсечения остается прямоугольник KPIJ. Теперь отсекать уже нечего. Так что на этом алгоритм завершается.

В результате мы получаем 5 прямоугольников, составляющих содержимое замкнутой области: ABML, FGNE, CDNO, OHPM и KPIJ (см. рис. 2).

Рис. 1

Рис. 2

После того как замкнутые области найдены, необходимо определить тип каждой из них (является ли она «завоеванной» или нет). Тип области определяется путем подсчета «морских» точек внутри нее. Не обязательно считать все точки внутри области, достаточно лишь узнать есть ли там хотя бы одна точка. Если есть, то эта область не «завоевана» (и соответственно мы ее не стираем), потому как в «завоеванной» области не должно быть ни одной точки.

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

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

Все найденные «завоеванные» области подлежат стиранию, которое реализуется еще тривиальнее: просто стираем (методом clearRect) все прямоугольники, составляющие данную область.

Анимация, управление игрой и прочее

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

Для тех, кому это интересно, ниже приведен весь код игры. Впрочем, ценность его сомнительна, т.к. комментариев там — кот наплакал. Но основную логику я, надеюсь, объяснил.

Код игры

// requestAnimationFrame/cancelAnimationFrame polyfill: (function() {     var tLast = 0;     var vendors = ['webkit', 'moz'];     for(var i = 0; i < vendors.length && !window.requestAnimationFrame; ++i) {         var v = vendors[i];         window.requestAnimationFrame = window[v+'RequestAnimationFrame'];         window.cancelAnimationFrame = window[v+'CancelAnimationFrame'] ||             window[v+'CancelRequestAnimationFrame'];     }     if (!window.requestAnimationFrame)         window.requestAnimationFrame = function(callback, element) {             var tNow = Date.now();             var dt = Math.max(0, 17 - tNow + tLast);             var id = setTimeout(function() { callback(tNow + dt); }, dt);             tLast = tNow + dt;             return id;         };     if (!window.cancelAnimationFrame)         window.cancelAnimationFrame = function(id) {             clearTimeout(id);         }; }());  (function() {      window.picxonix = function(v1, v2) {         if (typeof v1 != 'string') {             return init(v1, v2);         }         switch (v1) {             case 'level': // начать новый уровень                 loadLevel(v2);                 break;             case 'end': // закончить уровень                 endLevel(v2);                 break;             case 'play': // пауза/возобновление игры                 setPlayMode(v2);                 break;             case 'cursorDir': // угол движения курсора                 typeof v2 == 'string'? setDir(v2) : setDirToward(v2);                 break;             case 'cursorSpeed': // скорость движения курсора                 setCursorSpeed(v2);                 break;             case 'enemySpeed': // скорость движения точек                 setEnemySpeed(v2);                 break;             case 'enemySpawn': // увеличить число сухопутных точек                 spawn();                 break;             case 'state': // текущее состояние уровня                 return buildLevelState();             default:         }         return 0;     }      var cfgMain = {         width: 600,         height: 400,         sizeCell: 10,         colorFill: '#000000',         colorBorder: '#00aaaa',         colorBall: '#ffffff',         colorBallIn: '#000000',         colorWarder: '#000000',         colorWarderIn: '#f80000',         colorCursor: '#aa00aa',         colorCursorIn: '#00aaaa',         colorTrail: '#a800a8',         timeoutCollision: 1000,         callback: null,         callbackOnFrame: false     };     var cfgLevel = {         nBalls: 1,         nWarders: 1,         speedCursor: 5,         speedEnemy: 5     };     // cell attributes:     var CA_CLEAR = 1 << 0;     var CA_TRAIL = 1 << 1;     // размеры:     var sizeCell;     var width, height;     // ресурсы:     var elContainer;     var ctxPic;     var ctxMain;     var imgPic;     var imgBall;     var imgWarder;     var imgCursor;     // объекты игры:     var dirset;     var cellset;     var cursor;     var aBalls = [], aWarders = [];     var nBalls = 0, nWarders = 0;     // текущее состояние уровня:     var idFrame = 0;     var tLevel = 0;     var tLastFrame = 0;     var tLocked = 0;     var bCollision = false;     var bConquer = false;     var dirhash = {         'left': 180, 'right': 0, 'up': 270, 'down': 90, 'stop': false     };      function init(el, opts) {         if (elContainer || !el || !el.appendChild) return false;         elContainer = el;         // установка общих настроек игры:         merge(cfgMain, opts);         if (!cfgMain.sizeCell) return false;         sizeCell = cfgMain.sizeCell;         if (typeof cfgMain.callback != 'function') cfgMain.callback = null;         // установка настроек уровня:         if (opts.speedCursor ^ opts.speedEnemy) {             opts.speedCursor = opts.speedEnemy = Math.max(opts.speedCursor || 0, opts.speedEnemy || 0);         }         merge(cfgLevel, opts);         setLevelData(cfgMain.width, cfgMain.height);         var oWrap = document.createElement('div');         oWrap.style.position = 'relative';         // создаем канвас фона (картинки):         (function() {             var canvas = document.createElement('canvas');             ctxPic = canvas.getContext('2d');             canvas.width = width;             canvas.height = height;             canvas.style.position = 'absolute';             canvas.style.left = canvas.style.top = (2*sizeCell) + 'px';             ctxPic.fillStyle = cfgMain.colorTrail;             ctxPic.fillRect(0, 0, width, height);             oWrap.appendChild(canvas);         }());         // создаем канвас игрового поля:         (function() {             var canvas = document.createElement('canvas');             ctxMain = canvas.getContext('2d');             canvas.width = width+ 4*sizeCell;             canvas.height = height+ 4*sizeCell;             canvas.style.position = 'absolute';             canvas.style.left = canvas.style.top = 0;             fillCanvas();             ctxMain.fillStyle = cfgMain.colorFill;             ctxMain.fillRect(2*sizeCell, 2*sizeCell, width, height);             oWrap.appendChild(canvas);         }());         elContainer.appendChild(oWrap);         // создаем временный канвас:         var canvas = document.createElement('canvas');         var ctxTmp = canvas.getContext('2d');         canvas.width = sizeCell;         canvas.height = sizeCell;         // создаем изображение морской точки:         var r = sizeCell / 2, q = sizeCell / 4;         ctxTmp.clearRect(0, 0, sizeCell, sizeCell);         ctxTmp.beginPath();         ctxTmp.arc(r, r, r, 0, Math.PI * 2, false);         ctxTmp.fillStyle = cfgMain.colorBall;         ctxTmp.fill();         if (cfgMain.colorBallIn) {             ctxTmp.beginPath();             ctxTmp.arc(r, r, q, 0, Math.PI * 2, false);             ctxTmp.fillStyle = cfgMain.colorBallIn;             ctxTmp.fill();         }         imgBall = new Image();         imgBall.src = ctxTmp.canvas.toDataURL();         function prepareSquare(colorOut, colorIn) {             ctxTmp.clearRect(0, 0, sizeCell, sizeCell);             ctxTmp.fillStyle = colorOut;             ctxTmp.fillRect(0, 0, sizeCell, sizeCell);             if (colorIn) {                 ctxTmp.fillStyle = colorIn;                 ctxTmp.fillRect(q, q, sizeCell - r, sizeCell - r);             }         }         // создаем изображение сухопутной точки:         prepareSquare(cfgMain.colorWarder, cfgMain.colorWarderIn);         imgWarder = new Image();         imgWarder.src = ctxTmp.canvas.toDataURL();         // создаем изображение курсора:         prepareSquare(cfgMain.colorCursor, cfgMain.colorCursorIn);         imgCursor = new Image();         imgCursor.src = ctxTmp.canvas.toDataURL();         return {width: width+ 4*sizeCell, height: height+ 4*sizeCell};     }      function loadLevel(data) {         if (tLevel || tLastFrame || !data || !data.image) return;         if (!data.image) return;         var img = new Image();         img.onload = function() {             applyLevel(img, data);         };         img.src = data.image;     }      function applyLevel(img, data) {         imgPic = img;         merge(cfgLevel, data, true);         setLevelData(img.width, img.height);         ctxMain.canvas.width = width+ 4*sizeCell;         ctxMain.canvas.height = height+ 4*sizeCell;         fillCanvas();         cellset.reset();         ctxPic.canvas.width = width;         ctxPic.canvas.height = height;         ctxPic.drawImage(imgPic, 0, 0, width, height, 0, 0, width, height);         var pos = cellset.placeCursor();         cursor.reset(pos[0], pos[1]);         aBalls = []; aWarders = [];         var i, aPos;         aPos = cellset.placeBalls(nBalls);         for (i = 0; i < nBalls; i++)             aBalls.push(new Enemy(aPos[i][0], aPos[i][1], false));         aPos = cellset.placeWarders(nWarders);         for (i = 0; i < nWarders; i++)             aWarders.push(new Enemy(aPos[i][0], aPos[i][1], true, 45));         tLevel = Date.now();         tLastFrame = 0;         startLoop();     }      function endLevel(bClear) {         if (tLastFrame) return;         tLevel = 0;         if (!bClear) return;         fillCanvas();         ctxMain.clearRect(2*sizeCell, 2*sizeCell, width, height);     }      function setLevelData(w, h) {         if (w) width = w - w % (2*sizeCell);         if (h) height = h - h % (2*sizeCell);         if (cfgLevel.nBalls) nBalls = cfgLevel.nBalls;         if (cfgLevel.nWarders) nWarders = cfgLevel.nWarders;     }      function setPlayMode(bOn) {         if (bOn ^ !tLastFrame) return;         tLastFrame? endLoop() : startLoop();     }      function setDir(key) {         if (!tLastFrame) return;         if (key in dirhash) cursor.setDir(dirhash[key]);     }      function setDirToward(pos) {         if (!tLastFrame || !pos || pos.length < 2) return;         var xc = Math.floor(pos[0] / sizeCell) - 2,             yc = Math.floor(pos[1] / sizeCell) - 2;         var b = cellset.isPosValid(xc, yc);         if (!b) return;         var posCr = cursor.pos(), dirCr = cursor.getDir(), dir = false;         if (dirCr === false) {             var dx = xc - posCr[0], dy = yc - posCr[1],                 dc = Math.abs(dx) - Math.abs(dy);             if (dc == 0) return;             dir = dirset.find(dx, dy);             if (dir % 90 != 0) {                 var dir1 = dir-45, dir2 = dir+45;                 dir = dir1 % 180 == 0 ^ dc < 0? dir1 : dir2;             }         }         else {             var delta = dirCr % 180? xc - posCr[0] : yc - posCr[1];             if (!delta) return;             dir = (delta > 0? 0 : 180) + (dirCr % 180? 0 : 90);         }         cursor.setDir(dir);     }      function setCursorSpeed(v) {         if (v > 0) cfgLevel.speedCursor = v;     }      function setEnemySpeed(v) {         if (v > 0) cfgLevel.speedEnemy = v;     }      function startLoop() {         if (!tLevel) return;         idFrame = requestAnimationFrame(loop);     }      function endLoop() {         if (idFrame) cancelAnimationFrame(idFrame);         tLastFrame = idFrame = 0;     }      // Главный цикл анимации     function loop(now) {         var dt = tLastFrame? (now - tLastFrame) / 1000 : 0;         bCollision = bConquer = false;         if (!tLastFrame || update(dt)) {             render();             tLastFrame = now;         }         if (bCollision) {             lock();             cfgMain.callback && cfgMain.callback(1);             return;         }         if (bConquer) {             bConquer = false;             tLastFrame = 0;             cellset.conquer();             if (cfgMain.callback && cfgMain.callback(2))                 return;         }         else             cfgMain.callback && cfgMain.callbackOnFrame && cfgMain.callback(0);         startLoop();     }      function update(dt) {         var distCursor = Math.round(dt * cfgLevel.speedCursor),             distEnemy = Math.round(dt * cfgLevel.speedEnemy);         if (!(distCursor >= 1 || distEnemy >= 1)) return false;         cursor.update(distCursor);         var i;         for (i = 0; i < nBalls; i++) aBalls[i].update(distEnemy);         for (i = 0; i < nWarders; i++) aWarders[i].update(distEnemy);         return true;     }      function render() {         cellset.render();         cursor.render();         var i;         for (i = 0; i < nBalls; i++) aBalls[i].render();         for (i = 0; i < nWarders; i++) aWarders[i].render();     }      function lock() {         tLastFrame = 0;         bCollision = false;         var posCr = cursor.pos();         cellset.add2Trail(posCr[0], posCr[1], false);         setTimeout(unlock, cfgMain.timeoutCollision);     }      function unlock() {         if (!tLevel) return;         cellset.clearTrail();         var pos = cellset.placeCursor();         cursor.reset(pos[0], pos[1], true);         var aPos = cellset.placeWarders(nWarders);         for (var i = 0; i < nWarders; i++)             aWarders[i].reset(aPos[i][0], aPos[i][1]);         startLoop();     }      function spawn() {         if (!tLevel) return;         var pos = cellset.placeSpawned();         if (!pos) return;         aWarders.push(new Enemy(pos[0], pos[1], true));         nWarders++;     }      function buildLevelState() {         return {             play: Boolean(tLastFrame),             posCursor: cursor.pos(),             warders: nWarders,             speedCursor: cfgLevel.speedCursor,             speedEnemy: cfgLevel.speedEnemy,             cleared: cellset.getPercentage()         };     }      function fillCanvas() {         ctxMain.fillStyle = cfgMain.colorBorder;         ctxMain.fillRect(0, 0, width+ 4*sizeCell, height+ 4*sizeCell);     }      function drawCellImg(img, x, y) {         ctxMain.drawImage(img,             0, 0, sizeCell, sizeCell,             (x+2)*sizeCell, (y+2)*sizeCell, sizeCell, sizeCell         );     }      function clearCellArea(x, y, w, h) {         ctxMain.clearRect(             (x+2)*sizeCell, (y+2)*sizeCell, (w || 1)* sizeCell, (h || 1)* sizeCell         );     }      function fillCellArea(color, x, y, w, h) {         ctxMain.fillStyle = color;         ctxMain.fillRect(             (x+2)*sizeCell, (y+2)*sizeCell, (w || 1)* sizeCell, (h || 1)* sizeCell         );     }      // Множество доступных направлений:     dirset = {         vecs: {             0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1], 180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1]         },         get: function(v) {             return v in this.vecs? this.vecs[v] : [0, 0];         },         find: function(x, y) {             x = x == 0? 0 : (x > 0? 1 : -1);             y = y == 0? 0 : (y > 0? 1 : -1);             for (var v in this.vecs) {                 var vec = this.vecs[v];                 if (vec[0] == x && vec[1] == y) return parseInt(v);             }             return false;         }     };      // Матрица ячеек игрового поля:     cellset = {         nW: 0,         nH: 0,         nWx: 0,         nCleared: 0,         dirTrail: 0,         iPreTrail: 0,         aCells: [],         aTrail: [],         aTrailNodes: [],         aTrailRects: [],         reset: function() {             var nW = this.nW = Math.floor(width / sizeCell);             var nH = this.nH = Math.floor(height / sizeCell);             var n = (this.nWx = nW+4)* (nH+4);             this.nCleared = 0;             this.aCells = [];             var aAll = [];             for (var i = 0; i < n; i++) {                 var pos = this.pos(i), x = pos[0], y = pos[1];                 this.aCells.push(x >= 0 && x < nW && y >= 0 && y < nH? 0 : CA_CLEAR);                 aAll.push(i);             }             fillCellArea(cfgMain.colorFill, 0, 0, nW, nH);         },         render: function() {             if (this.aTrailRects.length) {                 for (var i = this.aTrailRects.length-1; i >= 0; i--) {                     fillCellArea.apply(null, [cfgMain.colorFill].concat(this.aTrailRects[i]));                 }                 this.aTrailRects = [];             }         },         isPosIn: function(x, y) {             return x >= 0 && x < this.nW && y >= 0 && y < this.nH;         },         isPosValid: function(x, y) {             return x >= -2 && x < this.nW+2 && y >= -2 && y < this.nH+2;         },         find: function(x, y) {             return this.isPosValid(x, y) ? (this.nWx)*(y+2) + x+2 : -1;         },         pos: function(i) {             return [i % this.nWx - 2, Math.floor(i / this.nWx)-2];         },         posMap: function(arr) {             var _this = this;             return arr.map(function(v) { return _this.pos(v) });         },         value: function(x, y) {             var i = this.find(x,y);             return i >= 0? this.aCells[i] : 0;         },         set: function(x, y, v) {             var i = this.find(x,y);             if (i >= 0) this.aCells[i] = v;             return i;         },         setOn: function(x, y, v) {             var i = this.find(x,y);             if (i >= 0) this.aCells[i] |= v;             return i;         },         setOff: function(x, y, v) {             var i = this.find(x,y);             if (i >= 0) this.aCells[i] &= ~v;             return i;         },         placeCursor: function() {             return [Math.floor(this.nW/2), -2];         },         placeBalls: function(n) {             var a = [], ret = [];             for (var i = 0; i < n; i++) {                 var k;                 do k = Math.floor(Math.random() * this.nW * this.nH);                 while (a.indexOf(k) >= 0);                 a.push(k);                 var x = k % this.nW, y = Math.floor(k / this.nW);                 ret.push([x, y]);             }             return ret;         },         placeWarders: function(n) {             var z;             var aPos = [                 [Math.floor(this.nW/2), this.nH+1],                 [-1, this.nH+1], [this.nW, this.nH+1], [-1, -2], [this.nW, -2],                 [-1, z = Math.floor(this.nH/2)], [this.nW, z],                 [z = Math.floor(this.nW/4), this.nH+1], [3*z, this.nH+1]             ];             var i0 = (n+ 1)% 2;             return aPos.slice(i0, Math.min(n+ i0, 9));         },         placeSpawned: function() {             if (nWarders >= 9) return false;             function dist(pos1, pos2) {                 return Math.pow(pos1[0]- pos2[0], 2) + Math.pow(pos1[1]- pos2[1], 2);             }             function find(pos0) {                 var n = nWarders;                 for (var l = 0; l < x0; l++) {                     for (var dx = -1; dx <= 1; dx+= 2) {                         var p = [pos0[0]+ l* dx, pos0[1]];                         for (var i = 0; i < n && dist(aWarders[i].pos(), p) >= 4; i++) ;                         if (i >= n) return p;                     }                 }                 return pos0;             }             var x0 = Math.floor(this.nW/2);             var aPos = [[x0, this.nH+1], [x0, -2]];             var posCr = cursor.pos();             var posSt = dist(aPos[0], posCr) > dist(aPos[1], posCr)? aPos[0] : aPos[1];             var ret = find(posSt);             return ret;         },         applyRelDirs: function(x, y, dir, aDeltas) {             var ret = [];             for (var n = aDeltas.length, i = 0; i < n; i++) {                 var d = (dir + aDeltas[i] + 360) % 360;                 var vec = dirset.get(d), xt, yt;                 ret.push([xt = x + vec[0], yt = y + vec[1], d, this.value(xt, yt)]);             }             return ret;         },         add2Trail: function(x, y, dir) {             var i = this.setOn(x, y, CA_TRAIL);             if (i < 0) return;             var n = this.aTrail.length;             if (!n || dir !== this.dirTrail) {                 var iNode = n? this.aTrail[n-1] : i;                 if (!n || iNode != this.aTrailNodes[this.aTrailNodes.length-1])                     this.aTrailNodes.push(iNode);                 if (!n) {                     var aPos = this.applyRelDirs(x, y, dir, [180]);                     this.iPreTrail = this.find(aPos[0][0], aPos[0][1]);                 }             }             this.aTrail.push(i);             this.dirTrail = dir;         },         lastTrailLine: function() {             var pos0 = this.pos(this.aTrailNodes[this.aTrailNodes.length-1]),                 pos = this.pos(this.aTrail[this.aTrail.length-1]);             return [                 Math.min(pos[0], pos0[0]), Math.min(pos[1], pos0[1]),                 Math.abs(pos[0] - pos0[0])+1, Math.abs(pos[1] - pos0[1])+1             ];         },         clearTrail: function() {             this.aTrailRects = this._buildTrailRects();             for (var n = this.aTrail.length, i = 0; i < n; i++) {                 this.aCells[this.aTrail[i]] &= ~CA_TRAIL;             }             this.aTrail = []; this.aTrailNodes = [];         },         getPreTrail: function() {             return this.iPreTrail;         },         conquer: function() {             var nTrail = this.aTrail.length;             if (!nTrail) return;             if (nTrail > 1)                 this.aTrailNodes.push(this.aTrail[nTrail-1]);             var aConqRects = this._conquer() || this._buildTrailRects();             this.aTrail = []; this.aTrailNodes = [];             if (!aConqRects || !aConqRects.length) return;             for (var n = aConqRects.length, i = 0; i < n; i++) {                 var rect = aConqRects[i];                 var x0 = rect[0], y0 = rect[1], w = rect[2], h = rect[3];                 for (var x = 0; x < w; x++) {                     for (var y = 0; y < h; y++) {                         if (this.value(x + x0, y + y0, CA_CLEAR) & CA_CLEAR) continue;                         this.set(x + x0, y + y0, CA_CLEAR);                         this.nCleared++;                     }                 }             }             for (i = 0; i < n; i++) {                 clearCellArea.apply(null, aConqRects[i]);             }             aConqRects = [];         },         getPercentage: function() {             return this.nCleared / (this.nW * this.nH) * 100;         },         _conquer: function() {             var nTrail = this.aTrail.length, nNodes = this.aTrailNodes.length;             var dz = Math.abs(this.aTrailNodes[0] - this.aTrailNodes[nNodes-1]);             var aOutlineset = [], bClosedTrail = false;             if (bClosedTrail = nNodes >= 4 && dz == 1 || dz == this.nWx) {                 aOutlineset.push([this.aTrailNodes, 1]);             }             var bAddTrail = false;             var posPre = this.pos(this.iPreTrail), posCr = cursor.pos();             var aDeltas = [-90, 90];             for (var d = 0; d < 2; d++) {                 var dd = aDeltas[d];                 var k = 0;                 var sum = 0, bSum = false, bEndAtNode = false;                 for (var l = 0; l < nTrail && sum < nTrail; l++) {                     var iStart = this.aTrail[l];                     var pos = this.pos(iStart);                     var pos0 = l? this.pos(this.aTrail[l - 1]) : posPre;                     var x = pos[0], y = pos[1];                     var dir = (dirset.find(x - pos0[0], y - pos0[1]) + dd + 360) % 360;                     var aDirs = bEndAtNode? [] : [dir];                     if (this.aTrailNodes.indexOf(iStart) >= 0) {                         var pos2 = l < nTrail - 1? this.pos(this.aTrail[l + 1]) : posCr;                         dir = (dirset.find(pos2[0] - x, pos2[1] - y) + dd + 360) % 360;                         if (dir != aDirs[0]) aDirs.push(dir);                     }                     if (this.aTrail[l] == this.aTrailNodes[k+1]) ++k;                     var ret = 0;                     for (var nDs = aDirs.length, j = 0; j < nDs && !ret; j++) {                         dir = aDirs[j];                         var vec = dirset.get(dir);                         var xt = x + vec[0], yt = y + vec[1];                         var v = this.value(xt, yt);                         if (v & CA_CLEAR || v & CA_TRAIL) continue;                         ret = this._outline(xt, yt, dir);                         if (!ret || ret.length < 3) return false;                     }                     bEndAtNode = false;                     if (!ret) continue;                     var len = ret[0], aNodes = ret[1], bClosed = ret[2], iEnd = aNodes[aNodes.length-1];                     if (bClosed) {                         aOutlineset.push([aNodes, len]);                         bSum = true;                         continue;                     }                     var aXtra = [iStart];                     for (var i = l+1; i < nTrail && this.aTrail[i] != iEnd; i++) {                         if (this.aTrail[i] == this.aTrailNodes[k+1])                             aXtra.push(this.aTrailNodes[++k]);                     }                     if (i >= nTrail) continue;                     aOutlineset.push([aNodes.concat(aXtra.reverse()), len + i - l]);                     sum += i - l + 1;                     l = (bEndAtNode = this.aTrail[i] == this.aTrailNodes[k+1])? i-1 : i;                 }                 if (!sum && !bSum && !bClosedTrail) return false;                 if (sum < nTrail && !bClosedTrail) bAddTrail = true;             }             if (!aOutlineset.length)                 return false;             aOutlineset.sort(function (el1, el2) { return el1[1] - el2[1]; });             var aRects = [], n = aOutlineset.length, b = false;             for (i = 0; i < n; i++) {                 if (i == n- 1 && !b) break;                 ret = this._buildConquerRects(aOutlineset[i][0]);                 if (ret)                     aRects = aRects.concat(ret);                 else                     b = true;             }             if (!aRects.length)                 return false;             return bAddTrail? aRects.concat(this._buildTrailRects()) : aRects;         },         _outline: function(x0, y0, dir) {             var aNodes = [], aUniqNodes = [], aUsedDirs = [], aBackDirs = [];             var x = x0, y = y0,                 lim = 6 * (this.nW + this.nH), n = 0, bClosed = false;             function isClear(arr) {                 return arr[3] & CA_CLEAR;             }             do {                 bClosed = n && x == x0 && y == y0;                 var iCurr = this.find(x,y), iUniq = aUniqNodes.indexOf(iCurr);                 var aCurrUsed = iUniq >= 0? aUsedDirs[iUniq] : [];                 var aCurrBack = iUniq >= 0? aBackDirs[iUniq] : [];                 var aPosOpts = this.applyRelDirs(x,y, dir, [-90, 90, 0]);                 var aTestDirs = [180+45, -45, 45, 180-45, -45, 45];                 var aPassIdx = [], aPassWeight = [];                 for (var i = 0; i < 3; i++) {                     var d = aPosOpts[i][2];                     if (aCurrUsed.indexOf(d) >= 0) continue;                     if (isClear(aPosOpts[i])) continue;                     var aTestOpts = this.applyRelDirs(x,y, dir, aTestDirs.slice(i*2,i*2+2));                     var b1 = isClear(aTestOpts[0]), b2 = isClear(aTestOpts[1]);                     var b = b1 || b2 || (i == 2? isClear(aPosOpts[0]) || isClear(aPosOpts[1]) : isClear(aPosOpts[2]));                     if (!b) continue;                     aPassIdx.push(i);                     aPassWeight.push(                         (b1 && b2? 0 : b1 || b2? 1 : 2) + (aCurrBack.indexOf(d) >= 0? 3 : 0)                     );                 }                 var nPass = aPassIdx.length;                 var min = false, idx = false;                 for (i = 0; i < nPass; i++) {                     if (!i || aPassWeight[i] < min) {                         min = aPassWeight[i]; idx = aPassIdx[i];                     }                 }                 var pos = nPass? aPosOpts[idx] : this.applyRelDirs(x,y, dir, [180])[0];                 var dir0 = dir;                 x = pos[0]; y = pos[1]; dir = pos[2];                 if (pos[2] == dir0) continue;                 nPass? aNodes.push(iCurr) : aNodes.push(iCurr, iCurr);                 dir0 = (dir0 + 180) % 360;                 if (iUniq < 0) {                     aUniqNodes.push(iCurr);                     aUsedDirs.push([dir]);                     aBackDirs.push([dir0]);                 }                 else {                     aUsedDirs[iUniq].push(dir);                     aBackDirs[iUniq].push(dir0);                 }             }             while (n++ < lim && !(this.value(x, y) & CA_TRAIL));             if (!(n < lim)) return false;             if (bClosed) {                 aNodes.push(iCurr);                 if (aNodes[0] != (iCurr = this.find(x0,y0))) aNodes.unshift(iCurr);                 var nNodes = aNodes.length;                 if (nNodes % 2 && aNodes[0] == aNodes[nNodes-1]) aNodes.pop();             }             else                 aNodes.push(this.find(x,y));             return [n+1, aNodes, bClosed];         },         _buildTrailRects: function() {             if (this.aTrailNodes.length == 1)                 this.aTrailNodes.push(this.aTrailNodes[0]);             var aRects = [];             for (var n = this.aTrailNodes.length, i = 0; i < n-1; i++) {                 var pos1 = this.pos(this.aTrailNodes[i]), pos2 = this.pos(this.aTrailNodes[i+1]);                 var x0 = Math.min(pos1[0], pos2[0]), y0 = Math.min(pos1[1], pos2[1]);                 var w = Math.max(pos1[0], pos2[0]) - x0 + 1, h = Math.max(pos1[1], pos2[1]) - y0 + 1;                 var rect = [x0, y0, w, h];                 aRects.push(rect);             }             return aRects;         },         _buildConquerRects: function(aOutline) {             if (aOutline.length < 4) return false;             var aNodes = this.posMap(aOutline);             var n = aNodes.length;             if (n > 4 && n % 2 != 0) {                 var b1 = aNodes[0][0] == aNodes[n-1][0], b2;                 if (b1 ^ aNodes[0][1] == aNodes[n-1][1]) {                     b2 = aNodes[n-2][0] == aNodes[n-1][0];                     if (!(b2 ^ b1) && b2 ^ aNodes[n-2][1] == aNodes[n-1][1])                         aNodes.pop();                     b2 = aNodes[0][0] == aNodes[1][0];                     if (!(b2 ^ b1) && b2 ^ aNodes[0][1] == aNodes[1][1])                         aNodes.shift();                 }                 b1 = aNodes[0][0] == aNodes[1][0]; b2 = aNodes[1][0] == aNodes[2][0];                 if (!(b1 ^ b2) && b1 ^ aNodes[0][1] == aNodes[1][1] && b2 ^ aNodes[1][1] == aNodes[2][1])                     aNodes.shift();             }             if (aNodes.length % 2 != 0) return false;             var aRects = [];             for (var l = 0; l < 10 && aNodes.length > 4; l++) {                 n = aNodes.length;                 var dim1 = 0, dim2 = 0, iBase = 0, iCo = 0;                 var posB1, posB2, posT1, posT2;                 for (var i = 0; i < n; i++) {                     posB1 = aNodes[i]; posB2 = aNodes[(i+1)%n];                     posT1 = aNodes[(i-1+n)%n]; posT2 = aNodes[(i+2)%n];                     var dir = dirset.find(posT1[0]-posB1[0], posT1[1]-posB1[1]);                     if (dir != dirset.find(posT2[0]-posB2[0], posT2[1]-posB2[1])) continue;                     var dirTest = Math.floor((dirset.find(posB2[0]-posB1[0], posB2[1]-posB1[1])+ dir) / 2);                     var vec = dirset.get(dirTest - dirTest% 45);                     if (this.value([posB1[0]+ vec[0], posB1[1]+ vec[1]]) & CA_CLEAR) continue;                     var b = false, t, w, k;                     if ((t = Math.abs(posB1[0]-posB2[0])) > dim1) {                         b = true; k = 0; w = t;                     }                     if ((t = Math.abs(posB1[1]-posB2[1])) > dim1) {                         b = true; k = 1; w = t;                     }                     if (!b) continue;                     var k2 = (k+1)%2;                     vec = dirset.get(dir);                     var sgn = vec[k2];                     var co2 = posB1[k2];                     var left = Math.min(posB1[k], posB2[k]), right = Math.max(posB1[k], posB2[k]);                     var min = Math.min(sgn* (posT1[k2]- co2), sgn* (posT2[k2]- co2));                     for (var j = i% 2; j < n; j+= 2) {                         if (j == i) continue;                         var pos = aNodes[j], pos2 = aNodes[(j+1)%n], h;                         if (pos[k2] == pos2[k2] && (h = sgn*(pos[k2]- co2)) >= 0 && h < min &&                             pos[k] > left && pos[k] < right && pos2[k] > left && pos2[k] < right)                             break;                     }                     if (j < n) continue;                     dim1 = w; dim2 = sgn*min;                     iBase = i; iCo = k;                 }                 var iB2 = (iBase+1)%n, iT1 = (iBase-1+n)%n, iT2 = (iBase+2)%n;                 posB1 = aNodes[iBase];                 posB2 = aNodes[iB2];                 posT1 = aNodes[iT1];                 posT2 = aNodes[iT2];                 var aDim = [0, 0], pos0 = [];                 var iCo2 = (iCo+1)%2;                 aDim[iCo] = dim1;                 aDim[iCo2] = dim2;                 pos0[iCo] = Math.min(posB1[iCo], posB2[iCo]);                 pos0[iCo2] = Math.min(posB1[iCo2], posB2[iCo2]) + (aDim[iCo2] < 0? aDim[iCo2]: 0);                 var rect = [pos0[0], pos0[1], Math.abs(aDim[0])+1, Math.abs(aDim[1])+1];                 var bC = Math.abs(posT1[iCo2] - posB1[iCo2]) == Math.abs(dim2);                 if (this._containBall(rect)) return false;                 aRects.push(rect);                 if (bC) {                     posB2[iCo2] += dim2;                     aNodes.splice(iBase,1);                     aNodes.splice(iT1 < iBase? iT1 : iT1-1, 1);                 }                 else {                     posB1[iCo2] += dim2;                     aNodes.splice(iT2,1);                     aNodes.splice(iB2 < iT2? iB2 : iB2-1, 1);                 }             }             var aX = aNodes.map(function(v) {return v[0]});             var aY = aNodes.map(function(v) {return v[1]});             var x0 = Math.min.apply(null, aX);             var y0 = Math.min.apply(null, aY);             rect = [x0, y0, Math.max.apply(null, aX)-x0+1, Math.max.apply(null, aY)-y0+1];             if (this._containBall(rect)) return false;             aRects.push(rect);             return aRects;         },         // проверяем, содержит ли прямоуг. область морскую точку:         _containBall: function(rect) {             var x1 = rect[0], x2 = x1+ rect[2] - 1;             var y1 = rect[1], y2 = y1+ rect[3] - 1;             for (var i = 0; i < nBalls; i++) {                 var o = aBalls[i], x = o.x, y = o.y;                 if (x >= x1 && x <= x2 && y >= y1 && y <= y2) return true;             }             return false;         }     };      // Курсор:     cursor = {         x: 0, // текущая x координата         y: 0, // текущая y координата         x0: 0, // предыдущая x координата         y0: 0, // предыдущая y координата         dir: false, // текущий угол движения (в градусах)         state: false, // текущий режим курсора (true - режим следа)         state0: false, // предыдущий режим курсора         // сброс позиции курсора:         reset: function(x, y, bUnlock) {             var bPre = bUnlock && cellset.value(this.x, this.y) & CA_CLEAR;             this.x0 = bPre? this.x : x;             this.y0 = bPre? this.y : y;             this.x = x;             this.y = y;             this.dir = this.state = this.state0 = false;         },         // обновление позиции - перемещение на заданное расстояние:         update: function(dist) {             if (this.dir === false) return;             var x = this.x, y = this.y;             var vec = dirset.get(this.dir), vecX = vec[0], vecY = vec[1];             var bEnd =  false;             for (var n = 0; n < dist; n++) {                 if (cellset.find(x + vecX, y + vecY) < 0) {                     this.dir = false; break;                 }                 x += vecX; y += vecY;                 if (cellset.value(x, y) & CA_TRAIL) {                     bCollision = true; break;                 }                 var b = cellset.value(x, y) & CA_CLEAR;                 if (this.state && b) {                     bEnd = true; break;                 }                 this.state = !b;                 if (this.state) cellset.add2Trail(x, y, this.dir);             }             this.x = x;             this.y = y;             if (!bEnd) return;             if (cellset.getPreTrail() == cellset.find(x,y))                 bCollision = true;             else {                 this.dir = this.state = false;                 bConquer = true;             }         },         // рендеринг текущей позиции:         render: function() {             if (this.x0 == this.x && this.y0 == this.y) {                 if (tLastFrame) return;             }             else {                 if (this.state0) {                     var rect = cellset.lastTrailLine();                     fillCellArea.apply(null, [cfgMain.colorTrail].concat(rect));                 }                 else {                     if (cellset.isPosIn(this.x0, this.y0))                         clearCellArea(this.x0, this.y0);                     else                         fillCellArea(cfgMain.colorBorder, this.x0, this.y0);                 }                 this.x0 = this.x; this.y0 = this.y;             }             this.state0 = this.state;             drawCellImg(imgCursor, this.x, this.y);         },         // получить текущую позицию:         pos: function() {             return [this.x, this.y];         },         // получить текущий угол движения:         getDir: function() {             return this.dir;         },         // изменить угол движения:         setDir: function(dir) {             if (dir === this.dir) return;             if (this.state && this.dir !== false && Math.abs(dir - this.dir) == 180)                 return;             this.dir = dir;         }     };      // Конструктор класса точки (морской и сухопутной):     function Enemy(x, y, type, dir) {         this.x = x;         this.y = y;         this.x0 = x;         this.y0 = y;         var aDirs = [45, 135, 225, 315];         this.dir = dir === undefined? aDirs[Math.floor(Math.random()*4)] : dir; // текущий угол движения         this.type = Boolean(type); // (boolean) тип точки (false - морская, true - сухопутная)     }     // Методы класса точки:     Enemy.prototype = {         // сброс позиции:         reset: function(x, y) {             this.x = x;             this.y = y;         },         // обновление позиции - перемещение на заданное расстояние:         update: function(dist) {             var ret = this._calcPath(this.x, this.y, dist, this.dir);             this.x = ret.x;             this.y = ret.y;             this.dir = ret.dir;         },         // рендеринг текущей позиции:         render: function() {             if (this.x0 == this.x && this.y0 == this.y) {                 if (tLastFrame) return;             }             else {                 if (this.type && cellset.isPosIn(this.x0, this.y0))                     clearCellArea(this.x0, this.y0);                 else                     fillCellArea(this.type? cfgMain.colorBorder : cfgMain.colorFill, this.x0, this.y0);                 this.x0 = this.x; this.y0 = this.y;             }             drawCellImg(this.type? imgWarder : imgBall, this.x, this.y);         },         // получить текущую позицию:         pos: function() {             return [this.x, this.y];         },         // вычислить путь движения (перемещения):         _calcPath: function(x, y, dist, dir) {             var vec = dirset.get(dir), vecX = vec[0], vecY = vec[1];             var posCr = cursor.pos();             var xC = posCr[0], yC = posCr[1],                 vC = cellset.value(xC, yC), bC = !this.type ^ vC & CA_CLEAR;             if (bC && Math.abs(x - xC) <= 1 && Math.abs(y - yC) <= 1 ||                 !this.type && this._isCollision(x, y, dir)) {                 bCollision = true;             }             for (var n = 0; n < dist && !bCollision; n++) {                 var xt = x + vecX, yt = y + vecY;                 var dirB = this._calcBounce(x, y, dir, xt, yt);                 if (dirB !== false)                     return this._calcPath(x, y, dist - n, dirB);                 if (bC && Math.abs(xt - xC) <= 1 && Math.abs(yt - yC) <= 1 ||                     !this.type && this._isCollision(xt, yt, dir))                     bCollision = true;                 if (!this.type && !cellset.isPosIn(xt, yt))                     break;                 x = xt; y = yt;             }             return {x: x, y: y, dir: dir};         },         // вычислить отскок точки от границы поля (если есть):         _calcBounce: function(x, y, dir, xt, yt) {             var ret = cellset.applyRelDirs(x,y, dir, [-45, 45]);             var b1 = this.type ^ ret[0][3] & CA_CLEAR,                 b2 = this.type ^ ret[1][3] & CA_CLEAR;             return b1 ^ b2?                 (b1? dir + 90 : dir + 270) % 360 :                 this.type ^ cellset.value(xt, yt) & CA_CLEAR || b1 && b2?                     (dir+180) % 360 : false;         },         // проверить столкновение точки с курсором:         _isCollision: function(x, y, dir) {             if (cellset.value(x, y) & CA_TRAIL) return true;             var aDirs = [-45, 45, -90, 90];             for (var i = 0; i < 4; i++) {                 var d = (dir + aDirs[i] + 360) % 360, vec = dirset.get(d);                 if (cellset.value(x + vec[0], y + vec[1]) & CA_TRAIL) return true;             }             return false;         }     };           function merge(dest, src, bFilter) {         if (!src) return dest;         for(var key in dest) {             if (!dest.hasOwnProperty(key) || !src.hasOwnProperty(key)) continue;             var v = src[key];             if ((!bFilter || v) && (typeof v != 'number' || v >= 0))                 dest[key] = v;         }         return dest;     }  })(); 

За сим закругляюсь. Спасибо за внимание.

ссылка на оригинал статьи http://habrahabr.ru/post/261853/

Технологии, меняющие порядок вещей

image

Роботы в виде больших собак, воздушные шары с LTE-связью, плывущие по стратосфере, 3D-принтеры, производящие живые клетки, и машина, которая превращает ваши нечистоты в питьевую воду, — это все инновации, но не те, которые должны прийти через 20 лет.

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

Только что собака-робот или интернет-шар может сделать для мира?

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

 
image
 

Какой наиболее полезный объект может создать 3D-принтер? Гитару? Может быть, пару обуви?

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

В то время как ранние 3D-принтеры использовали в основном пластиковые и металлические сплавы, сегодня ученые смешивают и сопоставляют различные материалы, некоторые из которых — живые.

В прошлом году, например, Дженнифер А. Льюис, ученый-материалист Гарвардского университета, напечатала биологическую ткань с сосудистой сеткой, которая помогает сохранить клетки живыми после их выхода из принтера.

Чтобы сделать это, Льюис и ее исследовательская группа разработали принтер, который может точно воспроизводить структуры с компонентами размером в один микрометр, сообщает MIT Technology Review.

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

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

"Имея возможность непосредственно печатать функциональную ткань, можно получить гораздо более основательный подход к фармацевтическому скринингу лекарств, а также тканевой инженерии", — сказала Льюис C&EN.

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

 


 
 
image
 

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

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

 
Таков и Spot от Boston Dynamics — 160-фунтовый четвероногий робот, который похож на собаку. Однако он не будет дремать рядышком и не попросит почесать ему живот.

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

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

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


 
 
image
 
Во всем мире у 4,3 миллиарда человек нет надежного подключения к Интернету.

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

Это проект, над которым инженеры Google работают с 2012 года, когда компания запустила над Калифорнией тестовые шары, оснащенные технологией.

С тех пор были разработаны более продвинутые шары, которые пересекли весь мир. Воздушные шары Loon дешевле в производстве и эксплуатации, чем спутниковые системы.

Чтобы потенциально дать миллиардам людей доступ к Интернету, Google разработала флот надувных шаров с электроникой внутри, которая питается от солнечных батарей.
 
image
Каждый шар покрывает 40 км и способен поймать интернет-сигнал с земли и передавать его удаленным пользователям
 
Летая на 20 километров выше стратосферы, что намного выше, чем высота полета коммерческих самолетов, воздушные шары Loon подключаются через радиосети к существующим телекоммуникационным сетям для предоставления высокоскоростного Интернета (обеспечивает стабильную связь на расстоянии до 40 км) устройствам, которые могут быть вне досягаемости сигнала.

Google создала алгоритмы, вычисляющие, где разместить свои воздушные шары в стратосфере, чтобы они могли двигаться с помощью ветра. Инженеры могут отслеживать самолеты с помощью GPS.

Шары Loon уже применялись крупными поставщиками связи в Бразилии, Новой Зеландии и Австралии.

В то время как первые воздушные шары оставались в небе всего несколько суток, сегодня они в состоянии летать в течение более чем 100 дней и могут обогнуть земной шар.
 
image
На полигоне за пределами города Крайстчерч, Новая Зеландия.
 


 
 

image

 
Покинув должность генерального директора Microsoft в 2000 году, Билл Гейтс постепенно перешел на постоянную деятельность в сфере благотворительности со своей женой Мелиндой, основав фонд The Bill & Melinda Gates Foundation, который в прошлом году выплатил почти $4 млрд в форме субсидий.

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

 
Новый проект Гейтса — машина, которая превращает сточные воды в чистую воду.

Omniprocessor — машина, которая была разработана и построена компанией Janicki Bioenergy. Ее работа заключается в поглощении ила и его кипячении, отделения водяного пара от твердых частиц, которые подаются на огонь и превращаются в пар, а тот в свою очередь питает процессор и выдает избыток электроэнергии.

Как чистая питьевая вода выходит из этого технологического гиганта?

Omniprocessor фильтрует водяной пар, созданный в процессе кипения, через систему очистки, которая выкачивает чистую питьевую воду.

Почему бы не построить канализацию? В развивающемся мире они являются дорогостоящими и энергетически неэффективными.

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

Omniprocessor, который в настоящее время проходит пробный запуск в Сенегале, в конечном итоге сможет справиться с отходами от 100 000 человек и превратит их в 86 000 литров чистой питьевой воды и 25 киловатт чистой электроэнергии день, ожидают в Gates Foundation.
 
image
Omniprocessor может превратить сточные воды в чистую питьевую воду
 

ссылка на оригинал статьи http://geektimes.ru/post/259604/

Корреляция, ковариация и девиация (часть 3)

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

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

7. Центрирование и нормирование одномерных координат

Разминку проведем на простом и всем понятном — центрировании и нормировании данных. Пусть у нас есть ряд чисел . Тогда операция центрирования сводится к нахождению среднего (центроида набора)

и построению нового набора как разности между исходными числами и их центроидом (средним):

Центрирование — это первый шаг к собственной системе координат (ССК) исходного набора, поскольку сумма центрированных координат равна 0. Вторым шагом является нормирование суммы квадратов центрированных координат к 1. Для выполнения данной операции нам нужно вычислить эту сумму (точнее среднее):

Теперь мы можем построить ССК исходного набора как совокупность собственного числа S и нормированных чисел (координат):

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

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

Упражнение для тех, кто любит «щупать руками». Построить ССК для набора {1, 2, 3, 4}.

Ответ.

Собственное число (дисперсия): 1.25.
Собственный вектор: {-1.342, -0.447, 0.447, 1.342}.

8. Центрирование и ортонормирование многомерных координат

Что, если вместо набора чисел нам задан набор векторов — пар, троек и прочих размерностей чисел. То есть точка (узел) задается не одной координатой, а несколькими. Как в этом случае построить ССК?

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

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

Что мы делаем дальше? Правильно — центрируем компоненты. То есть для каждого столбца (компоненты) находим центроид (среднее) и вычитаем его из значения компоненты:

Мы получили матрицу центрированных данных (МЦД) .
Следующим шагом нам как будто бы надо вычислить дисперсию для каждой компоненты и их нормировать. Но мы этого делать не будем. Потому что хотя таким образом мы действительно получим нормированные векторы, но нам-то нужно, чтобы эти векторы были независимыми, то есть ортонормированными. Операция нормирования не поворачивает вектора (а лишь меняет их длину), а нам нужно развернуть векторы перпендикулярно друг другу. Как это сделать?

Правильный (но пока бесполезный) ответ — рассчитать собственные вектора и числа (спектр). Бесполезный потому, что мы не построили матрицу, для которой можно считать спектр. Наша матрица центрированных данных (МЦД) не является квадратной — для нее собственные числа не рассчитаешь. Соответственно, нам надо на основе МЦД построить некую квадратную матрицу. Это можно сделать умножением МЦД на саму себя (возвести в квадрат).

Но тут — внимание! Неквадратную матрицу можно возвести в квадрат двумя способами — умножением исходной на транспонированную. И наоборот — умножением транспонированной на исходную. Размерность и смысл двух полученных матриц — разный.

Умножая МЦД на транспонированную, мы получаем матрицу корреляции:

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

Теперь переставим перемножаемые в (8.1) матрицы местами и получим матрицу ковариации (опять же опускаем множитель 1/(1-n), которым обычно нормируют значения ковариации):

Здесь перемножаются компоненты (а не векторы). Соответственно, размерность матрицы ковариации равна количеству исходных компонент. Для пар чисел матрица ковариации имеет размерность 2×2, для троек — 3×3 и т.д.

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

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

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

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

Правда, могут быть и отрицательные дисперсии, и тогда аналогия с эллипсоидом (псевдоэллипсоидом?) уже не очевидна.

9. Матрица девиации расстояний — это матрица корреляции векторов

Все это прекрасно, но причем здесь преобразование девиации?

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

Ответ мы дали в первой части — да, вполне. Здесь же мы покажем, что построенная по формуле (1.3′) матрица девиации квадратов расстояний и определенная нами выше матрица корреляции центрированных векторов (8.1) — это одна и та же матрица.

Как такое получилось? Сами в шоке. Чтобы в этом убедиться, надо подставить выражение для элемента матрицы квадратов расстояний

в формулу преобразования девиации:

Отметим, что среднее значение матрицы квадратов расстояний отражает дисперсию исходного набора (при условии, что расстояния в наборе — это сумма квадратов компонент):

Подставляя (9.1) и (9.3) в (9.2), после несложных сокращений приходим к выражению для матрицы корреляции (8.1):

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

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

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

Но уже не в этой статье. Здесь пока все, спасибо за уделенное время.

ссылка на оригинал статьи http://habrahabr.ru/post/263907/

Партизанская война Instagram с порнографией и пользователями, которые входят в окна, когда перед ними закрывают двери (Часть 2)

Для «среднестатистического» вуайериста описанные в предыдущей части статьи различия имеют мало значения. Ведь влагалище – оно и в Африке влагалище, независимо от того, было последнее сфотографировано и попало на сайт с легкой руки непосредственно его обладательницы, или же это работа порносайта, который пытается подражать крупным платным ресурсам и ищет новых участников с кредитными картами. Но для всех непреклонных пользователей, с которыми мне довелось пообщаться, Instagram является не только средством для просмотра эротических фотографий незнакомых людей. Для них это способ найти «своих» людей.

19-летний Эндрю сказал мне в общении по Kik: «Я не пытаюсь найти «обнажёнку» в Instagram, я в основном ищу контакты в Kik. Когда я не возбужден, идея меня не привлекает, но в противном случае я лишь хочу вести эротическую переписку, если уж у меня нет возможности заняться сексом». Он сокрушается по поводу «размножения» постов, которые переводят пользователей на другие порносайты. Он предпочитает им реальных пользователей.

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

«Я использую Instagram, потому что здесь много людей, и им нравится то, что мы делаем», – объяснила мне 18-летняя Ри в переписке на Kik, рассказав об аккаунте, который они создала с двумя подругами. «Когда мы начинали, у нас было всего 3 подписчика, теперь их 415». Ри вместе со своими подругами Лили и Ив решили создать их первый аккаунт на Instagram, хотя ранее они постили «обнажёнку» на Tumblr.

Когда я впервые натолкнулась на их аккаунт, в разделе биографии красовалось фото с грудью Лили со следующим текстом: «Добро пожаловать на нашу страницу! Вас приветствуют Лили, Ив и Ри. Только не отправляйте нам личных сообщений, потому что люди жалуются на нашу страничку». Все представленные 29 фото девушек были опубликованы в течение последнего часа, и изображали в разной степени обнажённых трех юных барышень: на одних снимках девицы полураздеты, на других – нагишом, на некоторых запечатлен процесс мастурбации. Если не считать фото с Ри и Лили, смеющихся на трибуне в спортзале гимназии, то ни на одном снимке нет лиц.

Каждому изображению было присвоено около 10-15 универсальных хэштегов, в том числе #eggplantz, #eggplantparm, #eggplantraww, #adule, #seduced и #daddydick. Когда аккаунт собрал поклонников в мгновение ока, то девушки убедились, что их уловка, использованная для того, чтобы не попасться под радары Instagram и спокойно развивать свою базу фанов, прекрасно работает. Девушки позднее обновили свою страницу с личной информацией, где указали, что их аккаунт будет публичным только в течение трех минут ежедневно. Они также взмолились, чтобы пользователи, случайно натолкнувшиеся на их страницу, лучше блокировали ее, чем обращались в Instagram.

«Это раздражает», – жаловалась Ри по поводу постов, которые были удалены без предупреждения. «Если тебе не нравится «обнажёнка», то и не кликай этот хэштег, не иди на эту страницу».

Ее меры предосторожности и разочарования не редкость. Большинство аккаунтов с «обнажёнкой», которые я просматривала на Instagram, содержат аналогичные формулировки, умоляющие участников сообщество пощадить их. И хотя здесь вы не найдете такой шумихи, которая развернулась над #freethenipple, но нельзя отрицать то, что в этом заключается настоящий смысл защиты сообщества, общая борьба против всего того, что порнушники-любители считают ненужной цензурой, которая осуществляется деспотичным технологическим властелином.

Но вопрос остается открытым: почему же они не присоединяются к значительно более лояльным сообществам Reddit и Tumblr или более новым платформам, посвящённым исключительно порно, например, Uplust или Pinsex, которые примут их с распростертыми объятиями?

«Если тебе не нравится «обнажёнка», то и не кликай этот хэштег, не иди на эту страницу».

Ирония заключается в следующем: несмотря на современные технологии борьбы с «непотребным» контентом в Instagram, для тех, кто делится «обнажёнкой», эта платформа более привлекательна, чем другие более лояльные уголки Интернета, именно благодаря своей технической мощи.

Reddit и Tumblr обеспечивают доступ с мобильных телефонов, но постить фото со смартфонов куда более трудоемко, чем с ноутбука (как убедилась Ри и ее подруги). Процесс создания фото куда проще на Instagram – прицелился, сфотографировал, запостил. К тому же Instagram и Kik могут быть установлены на одном и том же устройстве, которое всегда под рукой у пользователя.

Рамон, 28-летний молодой человек из Род-Айленда с особенно впечатляющим пенисом, говорит, что Instagram множество раз удалял его фото и банил аккаунты. И тем не менее, он снова регистрируется под разными именами. «Все, что тебе нужно, чтобы открыть аккаунт, – это электронный адрес. Все просто. Я занимаюсь этим, когда мне скучно», – говорит он.

Эти простые причины становятся ясны тогда, когда думаешь о том, сколь много у Instagram пользователей не старше 30 лет. 53 процента людей, пользующихся платформой, по состоянию на 2014 год были в возрасте от 18 до 29 лет. 56 процентов всех тинэйджеров Америки пользуются Instagram, и 91 процент попадают в Интернет с мобильных устройств. И, как оказалось, множество этих тинэйджеров любит делиться «обнажёнкой». Этот факт я прочувствовала на собственной шкуре, когда 14-летний отпрыск нежданно-негаданно отправил мне прямое сообщение с фото своего члена с личного аккаунта в Instagram, ранее наполненного «одетыми» снимками юноши в окружении его семьи и друзей. Кликните на какое-нибудь фото из многочисленной армии членов и грудей, доступных на платформе под соответствующими хэштегами, и убедитесь, что не такая уж редкость увидеть в биографии гордое сообщение о том, что этому пользователю 16-17 лет, и он в поисках ровесников-единомышленников. Даже самые хардкорные хэштеги приведут вас к толпам подростков, поэтому избежать их обнажённой плоти стало поистине геркулесовской задачей, дабы предотвратить размытия линии между репортером и ребенком-фотографом.

«Instagram является самым популярным приложением среди подростков после Facebook», – говорит репортер Аманда Хэсс (Amanda Hess), которая регулярно пишет об интернет-культуре, подростках и сексуальности (и которая с сознанием долга изучила природу возникновения «Eggplant Friday» для журнала Slate). «Люди хотят делиться фото эротического содержания или просматривать их в тех местах, где они уже зарегистрированы. Они не хотят устанавливать для этого какое-то специальное порно-приложение».

Вместе с тем она считает удобство использования платформы Instagram главной причиной того, что тинэйджеры публикуют свои обнажённые фото именно там. Настройки приватности Instagram «куда более интуитивные, чем на Facebook», – говорит Хэсс. – У Facebook тысячи настроек приватности, они постоянно изменяются, и ты не уверен, какие фото могут просматривать незнакомые пользователи. Instagram же просто закрыт или открыт». И, в отличие от Facebook, Instagram защищает анонимность. «Ты можешь создать имя пользователя, о котором не знают твои родители, и тебе необязательно добавлять в друзья бабушку с дедушкой, толпу двоюродных братьев и маминого шефа».

Конечно, когда дело касается сексуального взаимодействия, вопрос добровольности является основополагающим, но ситуация становится куда более неоднозначной, если речь заходит о несовершеннолетних. Во время расследования дела о «шайке подростков-секстеров» в Вирджинии в интервью для журнала The Atlantic Ханна Росайн (Hannah Rosin) отметила, что распространение «обнажёнки» даже по собственному желанию особ, запечатленных на фото, может нести серьезные последствия. Как сообщил заместитель шерифа округа Луиза в Вирджинии, «хранение или распространение фото с обнажёнными людьми, не достигшими совершеннолетия – даже если это их собственные фото – может закончиться привлечением к уголовной ответственности в соответствии с законами штата о детской порнографии». Кэти Нотополос (Katie Notopolous) из новостного портала BuzzFeed столкнулась с теми же проблемами, пытаясь узнать причины возникновения неожиданного потопа из фотографий членов, наводнивших ее Snapchat, нередко отправляемых подростками. (Лучшее утешение, которое смог найти для нее BuzzFeed – это то, что в конце концов она, «скорее всего», избежит тюрьмы).

Тем не менее, обмен «обнажёнкой» является для них взаимно желаемой формой общения и помогает познать сексуальный аспект человеческой жизни. Делясь своими обнажёнными фото в приложениях вроде Instagram, подростки могут благотворно изучать и развивать свое половое самосознание. И, независимо от возраста, это может быть поразительно раскрепощающей практикой.

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

Опять же, учитывая упорство таких пользователей, как Ри и Рамон, я не очень переживаю по этому поводу. И пока Instagram с возрастающей свирепостью продолжает «зачистку» порнохэштегов, целенаправленные пользователи подходят к вопросу более творчески. (Вот «горячие» теги этой недели, которые неизбежно исчезнут к тому времени, когда вы будете читать эту статью (как и все упомянутые выше хэштеги, кроме одного): #aaaasssss, #seducee, #becauseboobs, #freakshit.

Хотя эти любители-порнушники не могут иметь никакой связи с политикой, правозащитники свободы слова и большие почитатели «ню» могли бы поучиться у сообщества Instagram его тихому отказу капитулировать. Независимо от политических пристрастий пользователей, такие люди как Ри и Рамон являются живыми примерами того, как можно умело послать (и подальше) цензуру и ограничения на сексуальную свободу. Instagram сейчас находится на перепутье, а, если посмотреть ближе, сервис уже ступил одной ногой на неправильный путь развития. И этот факт может заставить сервис официально сдаться в битве, которую он уже проиграл.

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

«Тысячи одних и тех же хэштегов говорят о том, что не ты один получаешь удовольствие от порно», – говорит он.

ссылка на оригинал статьи http://megamozg.ru/post/18100/