The answer given by @mxmlnkn is a great start, but unfortunately the methodology for calculating the covered area is not correct for when 3 or more windows are on top of the target window.
To see why, imagine that there are 3 windows (which we'll call X, Y, and Z) on top of a target window T); further suppose that all these windows have the same coordinates. Then the given solution would first add |X ∩ T|+|Y ∩ T|+|Z ∩ T|=3*windowArea, and then subtract |(X U Y) ∩ T| + |(X U Z) ∩ T| + |(Y U Z) ∩ T| =3*windowArea, resulting in a net area calculation of 0. The error here is we are actually "double counting" the attempt to compensate for "double counting". To correct this, we add |X ∩ Y ∩ Z ∩ T|. This notion is formalized with the Principle of Inclusion-Exclusion (see here).
The "covered area" can be defined as (forgive the haphazard mathematical notation, unix.stackexchange.com does not allow LaTeX)
(A_1 U A_2 U ... U A_n) ∩ B
where A_1, A_2, ..., A_n are the windows that lie on top of the target window, and B is the target window.
We can use the Principle of Inclusion-Exclusion to expand (A_1 U A_2 U ... U A_n). We can then distribute the intersection with B across this result.
Concretely, this results in the following algorithm (C++):
bool windowIsVisible(Display *display, Window window, float threshold) {
// Indicates whether a window is fully covered
if (!windowIsViewable(display, window)) {
return false;
}
auto rootWindow = DefaultRootWindow(display);
auto coords = getWindowCoords(display, rootWindow, window);
if (coords.size() <= 1) {
return true;
}
float area = (coords[0][2]-coords[0][0]) * (coords[0][3]-coords[0][1]);
float coveredArea = 0;
auto selector = std::vector<bool>(coords.size()-1);
for (int i = 0; i < selector.size(); i++) {
std::fill(selector.begin(), selector.begin()+i+1, true);
std::fill(selector.begin()+i+1, selector.end(), false);
auto selectedWindows = std::vector<std::vector<int>>(i);
do {
selectedWindows.clear();
for (int j = 0; j < selector.size(); j++) {
if (selector[j]) selectedWindows.push_back(coords[j+1]);
}
selectedWindows.push_back(coords[0]);
coveredArea += pow(-1, i)*calculateWindowOverlap(selectedWindows);
} while (std::prev_permutation(selector.begin(), selector.end()));
}
float tol = 1e-4;
return (1 - ((float)coveredArea)/((float)area) + tol) >= threshold;
}
int calculateWindowOverlap(std::vector<std::vector<int>> windowCoords) {
if (windowCoords.size() == 0) {
return 0;
}
std::vector<int> intersect = windowCoords[0];
for (int i = 1; i < windowCoords.size(); i++) {
intersect[0] = std::max(intersect[0], windowCoords[i][0]);
intersect[1] = std::max(intersect[1], windowCoords[i][1]);
intersect[2] = std::min(intersect[2], windowCoords[i][2]);
intersect[3] = std::min(intersect[3], windowCoords[i][3]);
}
return std::max(0, intersect[2]-intersect[0]) *
std::max(0, intersect[3]-intersect[1]);
}
std::vector<std::vector<int>> getWindowCoords(Display *display,
Window queryWindow, Window targetWindow,
bool *reachedTargetPtr = nullptr, int absX = 0, int absY = 0) {
// Gather geometry of all windows in higher zorder
std::vector<std::vector<int>> coords = {};
bool reachedTarget = false;
if (!reachedTargetPtr) {
reachedTargetPtr = &reachedTarget;
}
Window rWindow;
Window parentWindow;
Window *childrenWindows;
unsigned int numChildren;
XQueryTree(display, queryWindow, &rWindow, &parentWindow,
&childrenWindows, &numChildren);
for (int i = 0; i < numChildren; i++) {
if (childrenWindows[i] == targetWindow) {
*reachedTargetPtr = true;
}
XWindowAttributes windowAttributes;
XGetWindowAttributes(display, childrenWindows[i], &windowAttributes);
if (*reachedTargetPtr && windowAttributes.map_state == IsViewable &&
windowAttributes.c_class != InputOnly) {
coords.push_back(std::vector<int> {
windowAttributes.x + absX,
windowAttributes.y + absY,
windowAttributes.x + absX + windowAttributes.width,
windowAttributes.y + absY + windowAttributes.height });
}
if (childrenWindows[i] != targetWindow) {
auto childCoords = getWindowCoords(display, childrenWindows[i],
targetWindow, reachedTargetPtr, absX + windowAttributes.x,
absY + windowAttributes.y);
coords.reserve(coords.size() + childCoords.size());
coords.insert(coords.end(), childCoords.begin(), childCoords.end());
}
}
return coords;
}
Basically, for k=1,2,...,n, we find all combinations of n choose k. We then calculate the area of the intersections of these windows, along with the target window, and add/subtract that result from the running area (in accordance with the (-1)^(k-1) term from the Principle of Inclusion-Exclusion.
I have implemented this in a simple tool I made here. Also, this is essentially an extension of the Rectangle Area II problem from leetcode. There are some more efficient ways to do this (check the solutions section), but I personally found that the mathematically intuitive way achieved adequate performance.
