My Super Awesome Unobstructed Rectangle Sweep Line Algorithm

Long ago, I was writing a web-automation framework for botting(), and noticed that there was no way to find an unobstructed point on an element. I knew where the element was, but I couldn't click it via JavaScript for risk of detection.

Action chains had been my go-to solution, however, if the element is partially obstructed you run the risk of clicking the wrong thing. My only savior was the elementsFromPoint JavaScript API.

This led to the invention of the SmartClick TM system:

1. Pick a random point on your target element (weighted towards the center for realism).
2. Try elementsFromPoint, if there are any obstructions, add them to a list.
3. Find the largest gap and repeat.
   (until the first clickable element is your target, or you run out of gaps)

However, I could not find a fast algorithm to locate these gaps, so I did it myself... Enjoy!

Section 1: Locating Important Lines

Traversing every point on a parent rectangle (target element) would be slow and wasteful. If all rectangles are running in parallel, we need only check the start and end of each obstruction.

Opening Lines

These appear one unit after the end of each obstruction. This is the only place where a new rectangle may begin.

I also use an opening line on the first unit of the parent rectangle, because it is easier than manually implementing that case.

Closing Lines

These appear on the first unit of each obstruction. This is the only place where a rectangle may end or be subdivided.

Take this example:

The algorithm will draw four lines:

• A opening line at the start of the parent rectangle.
• A closing line at the start of the first obstruction (same location as the parent's opening line).
• A opening line at the end of the first obstruction.
• A closing line at the start of the second obstruction.

NOTE: If a line starts before or ends after the parent rectangle, such as the closing line of the last obstruction, it is discarded.

/// A line we need to check for gaps.
struct Line<T> {
    x: T,
    opens: bool,
}

Section 2: Finding Gaps Between Obstructions

The algorithm can identify all gaps on each line, by filtering out obstructions that don't intersect and then sorting them by the top edge. As it iterates downward we save a pointer to the bottom of the last obstruction, this starts initialized to the top of the parent rectangle.

On each obstruction:

1. It checks if the pointer to the bottom of the last obstruction is above the current obstruction's top edge; if it is, there is a gap between them.
2. Then it updates the pointer to the minimum of its current value and this obstruction's bottom. This is required to handle obstructions that overlap.

Example of overlapping obstructions:

The outer obstruction is processed first; if the pointer was just updated to the inner obstruction, a false gap would be found.

/// A gap between two obstructions.
struct Gap<T> {
    top: T,
    bottom: T,
}

Section 3: Rectangle Identification

As the algorithm process the gaps from left to right, it maintains a list of active rectangles and a list of completed rectangles.

Opening Lines

When it encounters a gap on an opening line without an already active rectangle. It adds a new one starting at the current line with the gap's top and bottom.

Closing Lines

When it encounters a closing line the algorithm checks if each active rectangle fits within one of the gaps. If it does, the rectangle continues uninterrupted, otherwise:

• It is added to the completed rectangles list, ending one unit before the current line started.
  • If the closed rectangle was only partially obstructed, it is subdivided into the gaps contained within; the new active rectangles have the same start position as the original.

/// A rectangle that has not been obstructed yet.
#[derive(Clone)]
struct UnfinishedRect<T> {
    left: T, // Start
    top: T,
    bottom: T,
}

Section 4: Finalization

After processing all lines, any remaining active rectangles are added to the completed rectangles list. Their right edges extend to the parent rectangle's boundary.

In our example, this leaves us with four rectangles:

Section 5: Implementation

Here is the algorithm as I implemented it in the rect-lib crate:

If there is anything that can be improved, please contact me or create an issue.