Как уменьшить блоки без наложения пикселей

Question

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

Типовые данные примера:

Original length: 200000

Уменьшено до 25x25 pixel grid (это мало для разработки и отладки) Уменьшенная максимальная длина: 625 (25 * 25))

Scale-ratio: (625 / 200000) = 0,003125

Пример данных 1 - перекрывающиеся, масштабированные блоки перезаписывают друг друга Начало блока => конец блока: [начало, конец)

1: 2100 => 2800
2: 2800 => 3600
3: 3600 => 4500
4: 4500 => 5500

Перепрыгивая через показ результатов этого примера, потому что я думаю, что примеры 2 и 3 поймут смысл.Оставьте это для полноты.

Пример данных 2 - неверный пробел между 2 и 3 Начало блока => конец блока: [начало, конец)

1: 960 => 1440
2: 1440 => 1920
3: 1920 => 2400

1: 960 => 1440, length: 480, scaled length: 1.5:
2: 1440 => 1920, length: 480, scaled length: 1.5:
3: 1920 => 2400, length: 480, scaled length: 1.5:

начало, конец, длина пикселя

1: 3, 0, 1
2: 4, 0, 1
3: 6, 0, 1

Отображаемая сетка:

[ 0, 0, 0, 1, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Пример данных 3 - 1 неверно сдвинут на шаг назад Начало блока => конецблока: [начало, конец)

1: 896 => 1344
2: 1344 => 1792
3: 1792 => 2240

1: 896 => 1344, length: 448, scaled length: 1.4:
2: 1344 => 1792, length: 448, scaled length: 1.4:
3: 1792 => 2240, length: 448, scaled length: 1.4:

пиксель начало, конец, длина

1: 2, 0, 1
2: 4, 0, 1
3: 5, 0, 1

Отображаемая сетка:

[ 0, 0, 1, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Какие примеры данных 2 и 3должен был выглядеть следующим образом:

[ 0, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Помните, что значения блока [начало, конец)

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

Обновление

#include <iostream>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <vector>
#include <array>
#include <utility> // pair
#include <algorithm> // for_each

using namespace std;

const size_t width_size = 25; // 25 pixels
const size_t height_size = 25; // 25 pixels
const size_t grid_length = width_size * height_size; // width * height
array<size_t, grid_length> grid;

const size_t original_length = 200000;

typedef pair<unsigned long, unsigned long> block;
vector<block> test_values;

void show_grid()
{
    for (size_t y = 0; y < height_size; ++y) {
        const size_t start_pos_for_current_heigth = y * width_size;
        const size_t end_pos_for_current_heigth = start_pos_for_current_heigth + width_size;

        cout << "[ ";
        for (size_t i = start_pos_for_current_heigth; i < end_pos_for_current_heigth; ++i) {
            if (i + 1 < end_pos_for_current_heigth)
                cout << grid[i] << ", ";
            else
                cout << grid[i];
        };
        cout << " ]" << endl;
    }
}

void scale_and_add(const float scale)
{
    size_t test_value_id = 1;

    for_each(test_values.cbegin(), test_values.cend(), [&](const block &p) {
        const float s_f = p.first * scale;
        const unsigned long s = round(s_f);
        const float e_f = p.second * scale;
        const unsigned long e = round(e_f);
        const unsigned long block_length = p.second - p.first;
        const float block_length_scaled = block_length * scale;
        assert(s <= grid_length);
        assert(e <= grid_length);

        cout << test_value_id << ":" << endl;
        cout << " " << p.first << " => " << p.second << " length: " << block_length << endl;
        cout << " " << s << " (" << s_f << ") => " << e << " (" << e_f << ") length: " << (e - s) << " (" << block_length_scaled << ")" << " (scaled)" << endl;

        for (size_t i = s; i < e; ++i) {
            if (grid[i] != 0) {
                cout << "overlapp detected !" << endl;
            }
            grid[i] = test_value_id;
        }

        ++test_value_id;
    });
}

void reset_common()
{
    grid.fill(0);
    test_values.clear();
}

int main()
{
    const float scale = ((float)grid_length / (float)original_length);
    cout << "scale: " << scale << " length per pixel: " << ((float)original_length / (float)grid_length) << endl;

    // Example data 1
/*    cout << "Example data 1" << endl;

    test_values.push_back(make_pair(2100, 2800));
    test_values.push_back(make_pair(2800, 3600));
    test_values.push_back(make_pair(3600, 4500));
    test_values.push_back(make_pair(4500, 5500));

    scale_and_add(scale);
    show_grid();

    reset_common();

    // Example data 2
    cout << "Example data 2" << endl;

    test_values.push_back(make_pair(960, 1440));
    test_values.push_back(make_pair(1440, 1920));
    test_values.push_back(make_pair(1920, 2400));

    scale_and_add(scale);
    show_grid();

    reset_common();

    // Example data 3
    cout << endl << "Example data 3" << endl;

    test_values.push_back(make_pair(896, 1344));
    test_values.push_back(make_pair(1344, 1792));
    test_values.push_back(make_pair(1792, 2240));

    scale_and_add(scale);
    show_grid();

    reset_common();*/

    // Generated data - to quickly find the problem
    cout << "Generated data" << endl;

    auto to_op = [&](const size_t v) {
        return v * (original_length / grid_length) * 1.3; // 1.4 and 1.5 are also good values to show the problem
    };
    size_t pos = 0;
    size_t psize = 1; // Note this value (length) and check it with the displayed one, you'll be surprised !
    for (size_t g = 0; g < 10; ++g) {
        test_values.push_back(make_pair(to_op(pos), to_op(pos + psize)));
        pos += psize;
    }

    scale_and_add(scale);
    show_grid();

    return 0;
}

Вывод:

scale: 0.003125 length per pixel: 320
    Generated data
1:
 0 => 416 length: 416
 0 (0) => 1 (1.3) length: 1 (1.3) (scaled)
2:
 416 => 832 length: 416
 1 (1.3) => 3 (2.6) length: 2 (1.3) (scaled)
3:
 832 => 1248 length: 416
 3 (2.6) => 4 (3.9) length: 1 (1.3) (scaled)
4:
 1248 => 1664 length: 416
 4 (3.9) => 5 (5.2) length: 1 (1.3) (scaled)
5:
 1664 => 2080 length: 416
 5 (5.2) => 7 (6.5) length: 2 (1.3) (scaled)
6:
 2080 => 2496 length: 416
 7 (6.5) => 8 (7.8) length: 1 (1.3) (scaled)
7:
 2496 => 2912 length: 416
 8 (7.8) => 9 (9.1) length: 1 (1.3) (scaled)
8:
 2912 => 3328 length: 416
 9 (9.1) => 10 (10.4) length: 1 (1.3) (scaled)
9:
 3328 => 3744 length: 416
 10 (10.4) => 12 (11.7) length: 2 (1.3) (scaled)
10:
 3744 => 4160 length: 416
 12 (11.7) => 13 (13) length: 1 (1.3) (scaled)
[ 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

Этот пример кода более ясно демонстрирует мою проблему.

Интересный факт: mingw-g ++, который я использовал для написания этого примера, показывает немного другие значения,Я обычно пользуюсь Visual Studio 2010, но на этот раз не смог, потому что меня нет дома.

Answer 1

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

Не имея дело с несколькими рядами пикселей, если у вас есть два диапазона R1 = [a, b) и R2 = [b, c) немасштабированный, вы просто рисуете от a до b-1 и от b до c-1, и ваши диапазоны вычерчиваются так, что является проблемой в масштабированном случае от (int) (a * scale) до ((int) (b * scale) -1), а затем от (int) (b * scale) до((int) (c * scale) -1), вы можете использовать любое преобразование с плавающей точкой в ​​int, округление, пол или потолок, и все должно быть в порядке.

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

Псевдокод

DrawRanges(List<Range> ranges, float scale)
  int carry = 0;
  foreach(Range range in ranges)
  {
      int newStart = ceiling(range.start*scale);
      int newEnd = ceiling(range.end*scale)-1;

      if (newStart <= newEnd)
      {
        newEnd = newStart;
        ++carry;
      }
      DrawRange(newStart+carry,newEnd+carry);
  }

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

Решает ли это вашу проблему?

Answer 2

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

Ну, на вопрос: -)

Обычно при рисовании возникают проблемы с перекрытием, и в компьютерной 3D-графике со сканерами с отрисовкой линий (например, DirectX и OpenGL) они обычно пропускают ровно один пиксель (скажем, все справа и снизу). Может быть, это поможет вам.

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

НТН