Algorithm for calculating the set of bins limited by a discrete contour

Question

On a discrete grid-based plane (think: image pixels), I have a closed loop that can be expressed either:

• a set of two-dimensional points (x1,y1);(x2,y2);(x3,y3);...
• or 4-connected Freeman code with a starting point: (x1,y1) + 00001112...

I know how to switch from one to the other of these views. This will be the input.

I want to get a set of grid coordinates limited by a contour. Consider this example, where the red coordinates are the path and the gray is the starting point:

If the gray coordinate is, say, in (0,0), then I need a vector holding: (1,1),(2,1),(3,1),(3,2)

The order is not important, and the output vector can also hold the loop itself.

The language of choice is C ++, but I am open to any existing code, algorithm, library, pointer, any ...

I, although maybe CGAL would have something like this, but I am not familiar with it and could not find my way through the manual, so I'm not even sure. I also looked at Opencv , but I think it does not provide this algorithm (but can I be wrong?).

I thought about finding a bounding rectangle, and then checking each of the points in the rectangle to see if they are inside / outside , but that seems suboptimal. Any idea?

Answer 1

One way to solve this problem is drawContours , and you have outline points.

• Create an empty Mat and draw path with thickness = 1 (border).
• Create another empty Mat and draw path with thickness = CV_FILLED (the entire area, including the border).
• Now bitwise_and between the two above (you filled the area excluding the border).
• Finally, check for a nonzero pixel.