Грязные прямоугольники

Ответ 1

Vexi является эталонной реализацией этого. Класс org.vexi.util.DirtyList (лицензия Apache) и используется как часть производственных систем, то есть тщательно протестированных и хорошо прокомментированных.

Предостережение. В настоящее время описание класса несколько неточно: "Структура данных общего назначения для хранения списка прямоугольных областей, которые необходимо перекрасить, с интеллектуальным объединением". На самом деле в настоящий момент это не происходит. Поэтому вы можете рассматривать эту базовую реализацию DirtyList в том, что она пересекает только грязные() запросы, чтобы убедиться, что не перекрываются грязные области.

Один нюанс этой реализации заключается в том, что вместо использования Rect или другого аналогичного объекта области регионы сохраняются в массиве из целых чисел, то есть в блоках из 4 целых чисел в 1-мерном массиве. Это делается для эффективности времени выполнения, хотя в ретроспективе я не уверен, есть ли на это много преимуществ. (Да, я его реализовал.) Это должно быть достаточно простым, чтобы заменить Rect для используемых блоков массивов.

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

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

фрагмент кода. Полный код онлайн здесь.

public class DirtyList {

    /** The dirty regions (each one is an int[4]). */
    private int[] dirties = new int[10 * 4]; // gets grown dynamically

    /** The number of dirty regions */
    private int numdirties = 0;

    ...

    /** 
     *  Pseudonym for running a new dirty() request against the entire dirties list
     *  (x,y) represents the topleft coordinate and (w,h) the bottomright coordinate 
     */
    public final void dirty(int x, int y, int w, int h) { dirty(x, y, w, h, 0); }

    /** 
     *  Add a new rectangle to the dirty list; returns false if the
     *  region fell completely within an existing rectangle or set of
     *  rectangles (i.e. did not expand the dirty area)
     */
    private void dirty(int x, int y, int w, int h, int ind) {
        int _n;
        if (w<x || h<y) {
            return;
        }
        for (int i=ind; i<numdirties; i++) {
            _n = 4*i;
            // invalid dirties are marked with x=-1
            if (dirties[_n]<0) {
                continue;
            }

            int _x = dirties[_n];
            int _y = dirties[_n+1];
            int _w = dirties[_n+2];
            int _h = dirties[_n+3];

            if (x >= _w || y >= _h || w <= _x || h <= _y) {
                // new region is outside of existing region
                continue;
            }

            if (x < _x) {
                // new region starts to the left of existing region

                if (y < _y) {
                    // new region overlaps at least the top-left corner of existing region

                    if (w > _w) {
                        // new region overlaps entire width of existing region

                        if (h > _h) {
                            // new region contains existing region
                            dirties[_n] = -1;
                            continue;
                        }// else {
                        // new region contains top of existing region
                        dirties[_n+1] = h;
                        continue;

                    } else {
                        // new region overlaps to the left of existing region

                        if (h > _h) {
                            // new region contains left of existing region
                            dirties[_n] = w;
                            continue;
                        }// else {
                        // new region overlaps top-left corner of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(x, _y, _x, h, i+1);
                        return;

                    }
                } else {
                    // new region starts within the vertical range of existing region

                    if (w > _w) {
                        // new region horizontally overlaps existing region

                        if (h > _h) {
                            // new region contains bottom of existing region
                            dirties[_n+3] = y;
                            continue;
                        }// else {
                        // new region overlaps to the left and right of existing region
                        dirty(x, y, _x, h, i+1);
                        dirty(_w, y, w, h, i+1);
                        return;

                    } else {
                        // new region ends within horizontal range of existing region

                        if (h > _h) {
                            // new region overlaps bottom-left corner of existing region
                            dirty(x, y, _x, h, i+1);
                            dirty(_x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains right part of new region
                        w = _x;
                        continue;
                    }
                }
            } else {
                // new region starts within the horizontal range of existing region

                if (y < _y) {
                    // new region starts above existing region

                    if (w > _w) {
                        // new region overlaps at least top-right of existing region

                        if (h > _h) {
                            // new region contains the right of existing region
                            dirties[_n+2] = x;
                            continue;
                        }// else {
                        // new region overlaps top-right of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(_w, _y, w, h, i+1);
                        return;

                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // new region overlaps to the above and below of existing region
                            dirty(x, y, w, _y, i+1);
                            dirty(x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains bottom part of new region
                        h = _y;
                        continue;
                    }
                } else {
                    // new region starts within existing region

                    if (w > _w) {
                        // new region overlaps at least to the right of existing region

                        if (h > _h) {
                            // new region overlaps bottom-right corner of existing region
                            dirty(x, _h, w, h, i+1);
                            dirty(_w, y, w, _h, i+1);
                            return;
                        }// else {
                        // existing region contains left part of new region
                        x = _w;
                        continue;
                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // existing region contains top part of new region
                            y = _h;
                            continue;
                        }// else {
                        // new region is contained within existing region
                        return;
                    }
                }
            }
        }

        // region is valid; store it for rendering
        _n = numdirties*4;
        size(_n);
        dirties[_n] = x;
        dirties[_n+1] = y;
        dirties[_n+2] = w;
        dirties[_n+3] = h;
        numdirties++;
    }

    ...
}

Ответ 2

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

• Начните с пустой области (возможно, прямоугольник, установленный в 0,0,0,0 - что-то, что вы можете обнаружить как "не требуется обновление" )

Для каждой добавленной грязной области:

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

Windows, по крайней мере, поддерживает область обновления уведомлений об изменениях и любую перерисовку, которая должна быть выполнена из-за того, что окно не было закрыто и обнаружено. Область - это объект, который состоит из множества, возможно, прерывистых прямоугольников, многоугольников и эллипсов. Вы сообщаете Windows о части экрана, которую необходимо перекрасить, вызывая InvalidateRect - для более сложных областей есть функция InvalidateRgn. Если вы решите сделать некоторую живопись до появления следующего сообщения WM_PAINT, и вы хотите исключить это из грязной области, существуют функции ValidateRect и ValidateRgn.

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

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

Ответ 3

Похоже, что вам нужна ограничивающая рамка для каждой фигуры, которую вы визуализируете на экране. Помните, что ограничивающий прямоугольник многоугольника может быть определен как "нижний левый" (минимальная точка) и "верхний правый" (максимальная точка). То есть, х-компонент точки минимума определяется как минимум всех х-компонент каждой точки в многоугольнике. Используйте ту же методологию для y-компонента (в случае 2D) и максимальной точки ограничивающего прямоугольника.

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

Теперь, если вы все это делаете на Java, вы можете получить свой ограничивающий прямоугольник для Area (который вы можете построить из любого Shape) напрямую, используя getBound2D() метод.

Ответ 4

Какой язык вы используете? В Python Pygame может сделать это за вас. Используйте группу RenderUpdates и некоторые объекты Sprite с атрибутами изображения и прямой.

Например:

#!/usr/bin/env python
import pygame

class DirtyRectSprite(pygame.sprite.Sprite):
    """Sprite with image and rect attributes."""
    def __init__(self, some_image, *groups):
        pygame.sprite.Sprite.__init__(self, *groups)
        self.image = pygame.image.load(some_image).convert()
        self.rect = self.image.get_rect()
    def update(self):
        pass #do something here

def main():
    screen = pygame.display.set_mode((640, 480))
    background = pygame.image.load(open("some_bg_image.png")).convert()
    render_group = pygame.sprite.RenderUpdates()
    dirty_rect_sprite = DirtyRectSprite(open("some_image.png"))
    render_group.add(dirty_rect_sprite)

    while True:
        dirty_rect_sprite.update()
        render_group.clear(screen, background)
        pygame.display.update(render_group.draw(screen))

Если вы не используете Python + Pygame, вот что я буду делать:

• Создайте класс Sprite, который обновит(), move() и т.д. метод устанавливает "грязный" флаг.
• Сохраняйте право для каждого спрайта
• Если ваш API поддерживает обновление списка исправлений, используйте его в списке исправлений, чьи спрайты загрязнены. В SDL это SDL_UpdateRects.
• Если ваш API не поддерживает обновление списка исправлений (у меня никогда не было возможности использовать что-либо помимо SDL, поэтому я бы не знал), проверьте, можно ли быстрее вызвать функцию blit несколько раз или один раз с большим прямоугольником. Я сомневаюсь, что любой API будет быстрее использовать один большой прямоугольник, но опять же, я не использовал ничего, кроме SDL.

Ответ 5

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

Пошаговый принцип работы:

• Подделение изображения в логический 12x12 по прямоугольникам.

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

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

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

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

Ответ 6

Посмотрите R-tree и quadtree структуры данных.