Ответы пользователя по тегу Алгебра
  • Найти максимальное и минимальное значение от деления нацело?

    @Mercury13
    Программист на «си с крестами» и не только
    UPD. Переписал с нуля.
    r <= z/x < r + 1
    l <= z/y < l + 1

    Тогда y/x = z/x : z/y > r / (l+1)
    С другой стороны: y/x < z/x : z/y < (r+1)/l

    Пока вижу диапазон [r / (l+1)]; [(r+1)/l]
    Второе — минус один, если точное целое: приблизиться-то можно, а достичь нельзя. Сымитируем это таким образом…
    [r / (l+1)]; [r/l]

    Покажем, что границы достижимы (например, первая). Она затрагивает два неравенства.
    z/x < r + 1
    z/y >= l
    Подбором x, y и z можно довести второе до равенства и сколь угодно сильно приблизить первое.

    UPD2. Пусть r = [z/x] = 10, l = [z/y] = 3
    Тогда [y/x] будет в пределах от [10/4] = 2 до [10/3] = 3. А Если без целой части — то от 2,5 до 3 2/3.
    z = 100.000, x=10.000, y=25.001, y/x = 2,5001
    z = 100.000, x = 9091, y=33.333, y/x ≈ 3,66659
    Ответ написан
    Комментировать
  • Есть ли алгоритм для наиболее быстрого нахождения включает ли одна фигура другую?

    @Mercury13
    Программист на «си с крестами» и не только
    1. Надо указывать не только то, что все точки первой фигуры внутри второй, но и то, что все точки второй фигуры снаружи первой.
    2. Даже примитивный алгоритм даёт скорость O(mn). Сколько у вас примерно точек?
    3. Можно воспользоваться эвристиками. Если охватывающий прямоугольник 1-й фигуры целиком во 2-й — ДА. Если вылезает из охватывающего прямоугольника 2-й — НЕТ.
    4. Можно поступить так. Отсортируем все точки той фигуры, которую проверяем на точки, по X-координате. Также отсортируем все отрезки той фигуры, которую проверяем на отрезки, по X-координате левой точки. Указатель отрезков ставим в начало перечня отрезков. Заводим список активных отрезков. Проходимся по всем точкам, поступая так…
    • Для всех отрезков в списке активных: если точка вышла из [X1, X2) — исключить из списка!
    • Смотрим на тот отрезок, что под указателем. Если X точки >= X1 — идём по фигуре дальше; если заодно X < X2 и Y выше отрезка (X1,X2 — (Y1,Y2) — включаем отрезок в список.
    При определённом устройстве списка (куча по X2) имеем O(n log n). И если меньшая фигура имеет сложность примерно как у большей (т.е. не логарифм) — имеем выигрыш.
    Ответ написан
  • Как разобрать матрицу трансформации на состовляющие?

    @Mercury13
    Программист на «си с крестами» и не только
    Как я понял, твоя матрица 3×3 — это однородные координаты в 2D? Я бы поступил так.
    1. Убедиться, что элементы 3-1 и 3-2 нули (иначе — это не аффинное преобразование).
    2. Элемент 3-3 превратить в единицу, соответственно увеличив остальные (на что — читай, что такое однородные координаты).
    3. Элементы 1-3 и 2-3 — перенос. Отрежем их, получается матрица 2×2.
    4. То, что осталось, должно быть вида (c, s), (-s, c). Если с какой-то погрешностью это не так и 2-норма строк не единица (тоже с какой-то погрешностью) — это не поворот (т.е. может быть масштабирование или наклон). Остаётся взять atan2(c, s) — получается угол.
    Ответ написан
    Комментировать