Вероятно, наиболее эффективным способом было бы вычисление вычитания прямоугольника-прямоугольника, которое может показаться сложным и во многих случаях, но на самом деле это не так сложно:
struct Rect{
int x0, y0, x1, y1;
Rect(int x0, int y0, int x1, int y1)
: x0(x0), y0(y0), x1(x1), y1(y1)
{}
};
std::vector<Rect> subtract(const Rect& a, const Rect& b) {
std::vector<Rect> result;
if (a.y1 <= b.y0 || a.y0 >= b.y1 || a.x1 <= b.x0 || a.x0 >= b.x1) {
// Trivial case: rectangles are not overlapping
result.push_back(a);
} else {
int ystart = a.y0, yend = a.y1;
if (ystart < b.y0) { // Something visible above
result.push_back(Rect(a.x0, ystart, a.x1, b.y0));
ystart = b.y0;
}
if (yend > b.y1) { // Something visible below
result.push_back(Rect(a.x0, b.y1, a.x1, yend));
yend = b.y1;
}
if (a.x0 < b.x0) { // Something visible on the left
result.push_back(Rect(a.x0, ystart, b.x0, yend));
}
if (a.x1 > b.x1) { // Something visible on the right
result.push_back(Rect(b.x1, ystart, a.x1, yend));
}
}
return result;
}
Вышеупомянутая функция с двумя прямоугольниками A и B возвращает вектор прямоугольников с результатом A-B.Этот вектор может быть пустым (B охватывает A) или может иметь от одного до четырех прямоугольников (четыре - это когда B строго содержится в A, таким образом, результатом будет прямоугольник с прямоугольным отверстием в нем).
Используя эту функцию, вы можете легко вычислить new-old и old-new области.
Обратите внимание, что схема координат, используемая в приведенном выше коде, предполагает систему координат точка-база (неоснованная на пикселях система координат):
На рисунке выше обратите внимание, что горизонтальные координаты X прямоугольников идут от 0 до W (не W-1), а вертикальные координаты Y идут отОт 0 до H (а не до H-1).
Пиксели - это просто прямоугольники области 1 с координатами (x, y)-(x+1, y+1);центр этого пикселя (x+0.5, y+0.5).Прямоугольник с x0==x1 или y0==y1 является пустым.
Обратите также внимание, что код предполагает (и возвращает) непустые ориентированные прямоугольники, т.е. x0<x1 && y0<y1.
Этот подход разделенияКонцепция координаты пикселя из концепции координат точки упрощает большую часть математики пикселей: например, площадь прямоугольника равна width*height, а не (width-1)*(height-1).
Небольшая программа для проверки с вашим входным регистром - этоследующий
void print_result(const char *name,
const std::vector<Rect>& rects)
{
printf("Result '%s' (%i rects):\n", name, int(rects.size()));
for (int i=0,n=rects.size(); i<n; i++)
{
printf(" %i) (%i, %i) - (%i, %i)\n",
i+1,
rects[i].x0, rects[i].y0,
rects[i].x1, rects[i].y1);
}
}
int main()
{
Rect A(1, 1, 6, 6);
Rect B(3, 2, 8, 7);
print_result("A-B", subtract(A, B));
print_result("B-A", subtract(B, A));
return 0;
}
и вывод этой программы
Result 'A-B' (2 rects):
1) (1, 1) - (6, 2)
2) (1, 2) - (3, 6)
Result 'B-A' (2 rects):
1) (3, 6) - (8, 7)
2) (6, 2) - (8, 6)