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

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

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

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

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

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

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

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

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

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

Единственный нюанс этой реализации заключается в том, что вместо использования Rect или другого подобного объекта региона регионы хранятся в массиве целых чисел, то есть в блоках по 4 целых в одномерном массиве. Это сделано для повышения эффективности во время выполнения, хотя, оглядываясь назад, я не уверен, есть ли в этом заслуга. (Да, я реализовал это.) Это должно быть достаточно просто, чтобы заменить используемые блоки массива 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++;
    }

    ...
}

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

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

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

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

Например:

#!/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, у которого метод update (), move () и т. Д. Устанавливает «грязный» флаг.
• Держите прямоугольник для каждого спрайта
• Если ваш API поддерживает обновление списка прямоугольников, используйте его в списке прямоугольников, спрайты которых загрязнены. В SDL это SDL_UpdateRects.
• Если ваш API не поддерживает обновление списка прямоугольников (у меня никогда не было возможности использовать что-либо, кроме SDL, поэтому я не знаю), проверьте, быстрее ли вызывать функцию blit несколько раз или один раз с помощью большой прямоугольник. Я сомневаюсь, что какой-либо API был бы быстрее, используя один большой прямоугольник, но опять же, я не использовал ничего, кроме SDL.

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

Пошаговая суть того, как это работает:

1. Разбиение изображения на логические 12х12 прямоугольниками.

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

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

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

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

Загляните в R-tree и quadtree структур данных.