Collinear convex hull

Question

Is there an algorithm where I provide a list of non-overlapping squares, for example:

sq1 = [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0)]
sq2 = [(1, 0), (1, 1), (2, 1), (2, 0), (1, 0)]
sq3 = [(1, 1), (1, 2), (2, 2), (2, 1), (1, 1)]

and it will return some sort of "collinear convex hull" where the results will be?:

res = [(0,0), (0,1), (1,1), (1,2), (2,2), (2,0), (0,0)]

If I try the regular convex hull algorighm, it returns

Update: Every square will share at least one side with another, but if for examples there is an empty square in the middle of a 9x9 grid:

sq1 = [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0)]
sq2 = [(0, 1), (0, 2), (1, 2), (1, 1), (0, 1)]
sq3 = [(0, 2), (0, 3), (1, 3), (1, 2), (0, 2)]
sq4 = [(1, 2), (1, 3), (2, 3), (2, 2), (1, 2)]
sq5 = [(2, 2), (2, 3), (3, 3), (3, 2), (2, 2)]
sq6 = [(2, 1), (2, 2), (3, 2), (3, 1), (2, 1)]
sq7 = [(2, 0), (2, 1), (3, 1), (3, 0), (2, 0)]
sq8 = [(1, 0), (1, 1), (2, 1), (2, 0), (1, 0)]

Then the result would be:

ret = [(0, 0), (0, 3), (3, 3), (3, 0), (0, 0)]

So ignoring the "hole" in the middle. This would be the same results generated by the "regular" Convex Hull algorithm.

However, if instead I have:

sq1 = [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0)]
sq2 = [(0, 1), (0, 2), (1, 2), (1, 1), (0, 1)]
sq3 = [(0, 2), (0, 3), (1, 3), (1, 2), (0, 2)]
sq4 = [(1, 2), (1, 3), (2, 3), (2, 2), (1, 2)]
sq5 = [(2, 2), (2, 3), (3, 3), (3, 2), (2, 2)]
sq6 = [(2, 1), (2, 2), (3, 2), (3, 1), (2, 1)]
sq7 = [(2, 0), (2, 1), (3, 1), (3, 0), (2, 0)]

Then the result should be:

ret = [(0, 0), (0, 3), (3, 3), (3, 0), (2, 0), (2, 2), (1, 2), (1, 0), (0, 0)]

Answer 1

The problem is to find the outer boundary of the union of the squares. We state two claims that help design an $O(n)$ algorithm, where $n$ are the number of given squares.

Let $S_1,\dotsc,S_n$ be the set of given squares. Each square boundary is composed of four line segments. Let $L = \{\ell_1,\dotsc,\ell_m\}$ be the multiset of all the line segments of all squares. By the definition of the boundary, the following claim holds:

Claim 1: A line segment $\ell_i \in L$ forms the boundary of the union if and only if it appears exactly once in the multiset $L$.

The above claim is easy to see. That is, if a line segment $\ell_i$ appears more than once in $L$, then it is shared by some two squares thus it is not a part of the boundary of the union. Now, we state the second claim.

Let $L'$ be the set of line segments that appears exactly once in $L$. Since each square shares at least one side with another square, the following claim holds:

Claim 2: Each line segment $\ell_i \in L'$ shares each of its end point with one other line segment in $L'$.

Using claim $1$ and $2$, the following algorithm finds the outer boundary $B$ of the union of the squares:

1. Given $L$, find $L'$ using a hash map in $O(n)$ time.
2. Let $E$ be the set of all end points of the line segments in $L'$. Create a hash map $H$ such that each endpoint in $E$ maps to the two line segment in $L'$ which incident on it. It can be done in $O(n)$ time.
3. Let $e_l$ be an endpoint in $E$ that has the least $x$ coordinate value. This endpoint is definitely a part of the outer boundary. Add $e_{l}$ to set $B$.
4. Let $\ell_e$ be one of the line segment in $L'$ that is incident on $e_l$. The line segment $\ell_e$ can be found in $O(1)$ time using hash map $H$.
5. Let $e'$ be the other end point of $\ell_e$. Add $e'$ to $B$.
6. Repeat step $4$ with $e_l$ replaced with $e'$ till the complete boundary is traversed. The complete boundary is traversed when $e_l$ is encountered again.

The step $4$ and $5$ can be implemented in $O(1)$ time using hash map. Therefore, the overall running time is linear in $n$, i.e., $O(n)$.