Matricový filtr downsamplingu 50M bodů

Matricový filtr pro dokonalé downsampování scatter grafů se 50 miliony bodů

Matricový filtr zajišťuje 100% pokrytí a vizuální shodu při vykreslování 50 milionů bodů tlaku v ropných vrtech. Klasické algoritmy jako LTTB ztrácejí až 59 % hustoty dat. Přístup funguje v jednom průchodu bez třídění a omezuje výstup počtem pixelů obrazovky.

Scatter grafy jsou nezbytné pro nepravidelná data s mezerami: čáry zkreslují prázdnoty a skrývají shluky. Standardní metody jsou optimalizovány pro čárové grafy a ignorují dvourozměrnou strukturu.

Omezení klasických algoritmů

MinMax, M4, LTTB a hybridy dělí osu X na koše a vybírají 1–4 body podle Y. V hustých sloupcích se ztrácí 96–99 % dat: oblak se zploští na extrémy.

• MinMax: minimum a maximum — zachovává špičky, ale ignoruje rozložení.
• M4: první, poslední, min/max — pixelově dokonalé pro čáry.
• LTTB: maximální plocha trojúhelníku — silueta křivky.
• MinMaxLTTB: fixuje extrémy, pak vyhlazuje.

Pro scatter je to zásadní vada: algoritmy nezohledňují Y souřadnici v koších.

Princip matricového filtru

Analogie s Voxel Grid Filter z grafiky: promítá body na pixelovou mřížku W×H. V každé buňce zůstane jeden bod podle pořadí procházení.

public static void downsample(
        double[] times, double[] values,
        int width, int height,
        List<double[]> result) {

    int n = times.length;
    if (n == 0) return;

    // Krok 1: hranice
    double tMin = times[0], tMax = times[0];
    double vMin = values[0], vMax = values[0];
    for (int i = 1; i < n; i++) {
        if (times[i]  < tMin) tMin = times[i];
        if (times[i]  > tMax) tMax = times[i];
        if (values[i] < vMin) vMin = values[i];
        if (values[i] > vMax) vMax = values[i];
    }
    double tRange = Math.max(tMax - tMin, 1e-10);
    double vRange = Math.max(vMax - vMin, 1e-10);

    // Krok 2: mřížka
    boolean[] grid = new boolean[width * height];

    // Krok 3: filtrování
    for (int i = 0; i < n; i++) {
        int px = (int) Math.min(width  - 1, (times[i]  - tMin) / tRange * (width  - 1));
        int py = (int) Math.min(height - 1, (values[i] - vMin) / vRange * (height - 1));
        int idx = py * width + px;
        if (!grid[idx]) {
            grid[idx] = true;
            result.add(new double[]{times[i], values[i]});
        }
    }
}

Metoda simuluje vykreslení: aktivuje pixely, které by se rozsvítily při plném souboru. Omezení — pouze pro vizualizaci, ne pro statistiku.

Testovací metodika

~3000 datových sad telemetrie vrtů: od 19k do 50M+ bodů. Pixlové porovnání s originálem v režimech scatter (2×2px) a lines (1px).

Metriky:

• Pokrytí: % pixelů originálu pokrytých algoritmem.
• Přesnost: % pixelů algoritmu v originále.
• F1-score: harmonický průměr.
• Vizuální skóre: F1 s tolerancí ±1px (zohlednění subpixelů).

Rozpočet pro klasiku — výstup MatrixFilter 1920×1080. Testovací plošina: i7-7700K, Java 17, jeden vlákno.

Výsledky na reálných datech

Pravidelné (~20k bodů, 2930 souborů)

Scatter: MatrixFilter 1920×1080 — 100% ve všech metrikách. MatrixFilter 800×600 — Vizuální 99.6%, dvojnásobně méně bodů. Klasika: Pokrytí 63–84%, Vizuální 76–95%.

| Algoritmus | Prům. výstup | Celkem ms | Pokrytí | Přesnost | F1 | Vizuální |

|------------------|--------------|-----------|---------|----------|------|----------|

| Matrix 1920×1080 | 4939 | 695 | 100% | 100% | 100% | 100% |

| Matrix 800×600 | 2867 | 497 | 84.6% | 100% | 91.5%| 99.6% |

| MinMaxLTTB x4 | 4932 | 494 | 84.1% | 100% | 90.9%| 95.2% |

Střední a velké

Na 500k–50M bodech Matrix udržuje 100% Vizuální při čase ~ms/10k bodů. LTTB klesá na 16–40% Pokrytí u hustých dat.

Co je důležité

• Matricový filtr zajišťuje pixelově dokonalý scatter bez třídění, složitost O(n).
• Klasické algoritmy ztrácejí strukturu hustých oblaků i při štědrém rozpočtu.
• Vizuální skóre s ±1px je blíže vnímání: Matrix 800×600 je nerozeznatelný od plného vykreslení.
• Použití striktně vizuální: pro čáry/statistiku jsou potřeba jiné metody.
• Testováno na průmyslových datech těžby ropy s nepravidelnými mezerami.

— Editorial Team