Задать вопрос
DmitryITWorksMakarov

Дмитрий Макаров

Ответы пользователя по тегу Алгоритмы

  • Какой алгоритм подойдет для наиболее оптимального решения задачи?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    Положить все номера в хэш-таблицу.
    start: Берем первый непомеченный номер и, начиная с него, делаем поиск в ширину по всем соседям (их меньше либо равно 20).
    Если сосед найден, то выписываем эту пару.
    Когда у очередного номера найдены все соседи, то помечаем его.
    Следующую итерацию поиска проводим только для непомеченных соседей.
    Повторяем, начиная со start`а, пока есть непомеченные номера.
    Ответ написан
    Комментировать
    Комментировать

  • Как найти все соседние клетки одинакового типа в двумерном массиве?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    Представим, что двумерный массив - это граф, где каждая клетка - это узел. Данные узла: его координаты, цвет, массив ссылок на соседей, булево значение посещен/не посещен.

    Отметить все узлы непосещенными.
    На вход алгоритма подается узел графа.
    Процедура P:
    1. Выдать координаты входного узла.
    2. Пометить входной узел посещенным.
    3. Применить процедуру Р ко всем непосещенным соседям такого же цвета.

    Необязательно строить граф явно. Можно соседей получать непосредственно в процедуре Р. Для "посещен/не посещен" нужна какая то быстрая и компактная структура данных, в которую можно быстро записать координаты клетки и быстро проверить: записывались ли раньше какие-либо координаты.
    В простейшем случае - это булев двумерный массив того же размера, что и исходный. Но в зависимости от исходных данных и ограничений, другие способы могут быть более подходящими.
    Ответ написан
    2 комментария
    2 комментария

  • Что написать на C#?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    Когда коту нечего делать, он "занимается гигиеной", когда программисту нечего делать - он занимается рефакторингом.
    Ответ написан
    6 комментариев
    6 комментариев

  • Какие есть алгоритмы определения относительного расстояния по изображению?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    Вместо двух камер можно использовать одну и пару зеркал. И все алгоритмы для двухкамерной системы.
    Ответ написан
    Комментировать
    Комментировать

  • Как увеличить высоту повернутого прямоугольника математически (быстрый алгоритм)?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    При рисовании повернутых фигур можно применять афинные преобразования. Компьютер умеет это делать быстро.

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

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

    Либо можно соответствующим образом модифицировать матрицу преобразования. Матрица преобразования определяет в том числе и растяжение/сжати по осям.

    В .NET в GDI+ есть готовые возможности для работы с афинными преобразованиями:
    Матричное представление преобразований
    Использование преобразований в управляемом GDI+

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

  • Как реализовать скелетную модель?

    DmitryITWorksMakarov
    @DmitryITWorksMakarov
    Мне кажется, такого интерфейса для базового элемента достаточно:

    interface IBone 
{
    float angle; // in radians
    float length;

    IEnumerable<IBone> children;
}


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

    При необходимости рисования скелета делаем так:

    void DrawBone(Graphics inGraphics, PointF inPosition, IBone inBone)
{
    var boneEnd = inPosition + new SizeF((float)(inBone.length * Math.Cos(inBone.angle)), 
                                         (float)(inBone.length * Math.Sin(inBone.angle)));

    inGraphics.DrawLine(Pens.Black, inPosition, boneEnd);

    foreach (var next in inBone.children)
    {
        DrawBone(inGraphics, boneEnd, next);
    }
}
    Ответ написан
    1 комментарий
    1 комментарий