Efficient algorithms for finding a region in $\mathbf R^2$

Question

This question is an extension of a previous question I've asked.

Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (We have to check each point to know its kind).

Assume that somehow we know that the points of kind 1 (and so the points of kind 2) form a connected region (i.e. , 1s and 2s are not scattered in the plane arbitrarily). Given the condition of being of kind 1 or 2, The goal is to find the region occupied by 1s (a search problem). Consider somehow we know the following attributes of the region occupied by 1s: (one at a time)

1. The region occupied by 1s forms a convex set (so it is 1-connected too).

2.The region occupied by 1s forms a simply connected region , but not necessarily convex.

The simplest algorithm for finding the region of 1s is to simply start from bottom of the rectangle and sweep it and check all of the points in the rectangle to determine their kind and this way find the region.This is not an efficient algorithm, because we can use the known fact of convexity (or simply-connectivity) of the region of 1s to find it more easily without inspecting all of the points.

What more efficient algorithms are there to find the region , as fast as possible? (with an acceptable accuracy, which is about 0.001 in my work). The regions may have sharp edges. But their detection is limited to the mentioned accuracy too. (It is clear that finding the boundary of the region suffices)

Please don't forget that the problem is to find an unknown set of points, not bound a known set of points. i.e., it's a search problem , not a convex hull finding problem.

(also, speed is very important for me)

EDIT1:

After some suggestions (in the comments) I should say that I think we can take advantage of simply-connectivity of the region to write an algorithm that tries to find the boundary of the region instead of checking more points to find the region directly.

Answer 1

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.