Ответ 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++;
}
...
}