Algorithm to compute set of bins bounded by a disc

问题:

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

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

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

I want to get the set of grid coordinates that are bounded by the contour. Consider this example, where the red coordinates are the contour, and the gray one the starting point:

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

Order is not important, and the output vector can also hold the contour itself.

Language of choice is C++, but I'm open to any existing code, algorithm, library, pointer, whatever...

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

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

回答1:

One way to solve this is drawContours, and you have contours points with you.

1. Create blank Mat and draw contour with thickness = 1(boundary).
2. Create another blank Mat and draw contour with thickness = CV_FILLED(whole area including boundary).
3. Now bitwise_and between above two(you got filled area excluding boundary).
4. Finally check for non-zero pixel.