Efficient algorithms for finding a region in $\mathbf R^2$
Here's an idea that might be quick in practice. Judging from the OP's comments, this is idea is implementable.

The idea is that we start scanning from a corner and approach the center of the rectangle. Once the scan finds a vertex $v$ with label $1$, it halts. Start a DFS from $v$. Keep a stack $F$ that represents the frontier into which you can expand the search. A vertex is put into the stack if and only if it has at least one neighbor whose label is $0$. The idea is to complete a cycle, while staying on the boundary.


The figure above is a rough representation of the initial region of the green vertices labeled $1$. Say we start scanning from the upper right corner. The vertex $29$ is the one we hit, and the one from which we start a DFS.


The DFS was started from the purple vertex $29$. In the figure, $F$ would contain $9$ and $28$, because they are the only neighbors we can visit next that have at least one neighbor with the label $0$. The cycle is completed when we come back to $29$ or when the frontier meets.