# Collinear convex hull

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.

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)]

• no, they will never overlap and input will always be a list of 1x1 squares Commented Jul 23, 2023 at 12:24

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)$$.

• It's more complicated than it seems. I will try to implement your algorithm. Thank you very much for taking the time to do this! Commented Jul 23, 2023 at 22:29