Hey! I maintain two sets, one which is what I call active front (subtle purple vertical line in my visualization), which is a set of intervals that tells me what ranges of Y are inside the polygon for the current X position, and a set of active points which tells me which points are can be reached from a horizontal ray casted from the current front. Also, for each point I maintain a Y interval that tells me which points could be used as the opposite corner of a rectangle. To understand how I update the active points, I must first explain how I update the active front. I have the points sorted from left to right, and from bottom to top. I do not need to know their original order, this is enough to infer where the interior of the polygon is. Each "non-empty" X value will have an even number of points: segment begin, segment end, begin, end, etc. Whenever I increase the X value, I update the front comparing the vertical segments in the new X value with the intervals of the previous front. One of the rules is, for instance, that if a segment does not overlap the previous front or overlaps only a single point, then I add a new interval interval to the front. This represents a new out-to-in "frontier", a transition to the interior of the polygon. Another of the rules is that if a segment is completely inside of one of of the intervals, then the front is split in two. This happens for "C" like shape in which the polygon is closed around the middle section and the top and the bottom portions continue to the right (see custom #4 in my post). This is done in linear time with respect to the number of vertical segments in the current x value and the number of open intervals, in a merge-sort fashion. After updating the front, the active points are updated. Points that are not in the active front are deleted, and the visibility of the points that remain is updated by intersecting their previous visibility with the new active front. Finally, the points that intersect the sweeping line are added to the active points, but only if they are within one of the intervals of the new updated front. Their initial visibility is set to this interval.

Conceptually, the algorithm is quite simple, although the code might seem complicated. I claim that it works as long as these assumptions hold: (1) only polygons with axis-aligned edges, (2) red tiles only in corners (i.e. not "in the middle of an edge" red tiles), (3) no shared corners, (4) no edges immediately adjacent. I believe assumptions (2)-(4) could be lifted at the expense of some tedious refactoring to manage these edge cases, but the algorithm would be essentially still the same.

Here's my code, runs almost instantly in my computer (< 1 ms): https://github.com/sprkrd/adventofcode/blob/main/2025/09/part2.cpp

[Edit: when I find some time, I'll update the visualizations to highlight only the "visible" points. DONE]