Let's instead answer the equivalent question: What are the edges on the polygon's boundary, in clockwise order?

An edge is on the polygon's boundary if and only if it borders exactly one coloured tile. Also, we can compute the edges of a given tile in clockwise order fairly easily. So if we do this for all the coloured tiles and remove the edges that appear twice (by sorting or using a set data structure, for example), we get a list of all the edges on the polygon's boundary.

Now, we just need to output these edges in order. Notice that each edge in the list neighbours exactly two others. So we can create a map from each edge to its two neighbours, then trace a path from one edge to the next until we are back at our starting edge.

To make sure that this order is clockwise, recall that we computed the tiles' edges in clockwise order. We can store this directionality along with each edge. Then, when we choose an edge to start our path from, we make sure to trace it along the same direction as before.

Time complexity: ~\mathcal O(N \log N)~ or ~\mathcal O(N)~, depending on the set/map implementation you use.