algorithme pour calculer un ensemble de bacs délimitées par un contour

Question

discrets sur un plan en fonction de grille discrète (pense: pixels d'une image), I ont un contour fermé qui peut être exprimé soit par:

• un ensemble de points 2D (x1,y1);(x2,y2);(x3,y3);...
• ou un 4-connecté Freeman code, avec un point de départ: (x1,y1) + 00001112...

je sais comment passer de l'un à l'autre de ces représentations. Ce seront les données d'entrée.

Je souhaite obtenir l'ensemble des coordonnées de la grille délimitées par le contour. Considérons cet exemple, où les coordonnées rouges sont le contour et le gris le point de départ:

Si le gris coordonnée est, par exemple, à (0,0), alors je veux un vecteur maintien: (1,1),(2,1),(3,1),(3,2)

L'ordre n'est pas important, et le vecteur de sortie peut également contenir le contour lui-même.

Langue de choix est C++, mais je suis ouvert à tout code existant, algorithme, bibliothèque, pointeur, peu importe ...

Je pensais que CGAL aurait peut-être quelque chose comme ça, mais je ne connais pas bien et je ne pouvais pas trouver mon chemin à travers le manuel, donc je ne suis même pas sûr. J'ai également regardé vers Opencv mais je pense qu'il ne fournit pas cet algorithme (mais je peux me tromper?).

Je pensais trouver le rectangle de délimitation, puis vérifier chacun des points dans le rectangle pour voir s'ils sont inside/outside, mais cela semble sous-optimal. Une idée ?

Answer 1

Une façon de résoudre cela est drawContours, et vous avez des contours de points avec vous.

1. Créer un cache et dessiner un contour avec une épaisseur = 1 (limite).
2. Créer un autre cache et dessiner un contour d'épaisseur = CV_FILLED (toute la zone incluant la limite).
3. Maintenant bitwise_and entre deux (vous avez une zone remplie à l'exclusion de la limite).
4. Enfin, vérifiez les pixels non nuls.