Comment vérifiez-vous qu'un bitmap 2d est contigu?
https://stackoverflow.com/questions/3687896
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Le mot Let vous avez la structure suivante en C #:
struct Piece : IEquatable<Piece> {
public readonly int size;
public readonly bool[,] data;
public Piece(Piece p) {
size = p.size;
data = (bool[,])p.data.Clone();
}
public Piece(int s, bool[,] d) {
size = s;
if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();
data = (bool[,])d.Clone();
}
public bool Equals(Piece other) {
if (size != other.size) return false;
return (data.Equals(other.data));
}
}
L'idée est qu'il représente un ensemble de sizexsize de bits qui représente une forme (une carte peu, si vous voulez).
Maintenant, toutes les combinaisons possibles de bits sont valides. J'ai quelques exigences:
- Il doit être seulement des bits
sizeau total. (C'est facile, je l'ai déjà mis en oeuvre) - Tous les bits doivent être contiguës.
Alors, encore une fois en supposant size==4, ce qui suit est bon:
..#.
..#.
.##.
....
Alors que le suivant n'est pas:
...#
...#
#...
#...
Comment puis-je déterminer si tous les bits sont contigus ou non?
Edit: Voici le code complet, intégrant la réponse de Eric Lippert. Cela peut certainement être resserré, des performances, mais il est très facile à lire.
struct Point : IEquatable<Point> {
public int X, Y;
public Point(int x, int y) {
X = x; Y = y;
}
public bool Equals(Point obj) {
return X == obj.X && Y == obj.Y;
}
public override bool Equals(object obj) {
if (obj == null) return false;
if(obj is Point)
return Equals((Point)obj);
return false;
}
public override int GetHashCode() {
return X ^ ~Y;
}
public static bool operator == (Point p1, Point p2) {
return p1.X == p2.X && p1.Y == p2.Y;
}
public static bool operator !=(Point p1, Point p2) {
return p1.X != p2.X || p1.Y != p2.Y;
}
public static readonly Point Empty = new Point(int.MinValue, int.MinValue);
}
struct Piece : IEquatable<Piece> {
public readonly int size;
public readonly bool[,] data;
private bool valid;
public Piece(Piece p) {
size = p.size;
valid = p.valid;
data = (bool[,])p.data.Clone();
}
public Piece(int s, bool[,] d) {
size = s;
if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();
data = (bool[,])d.Clone();
valid = false;
CalcValidity();
}
public bool IsValid {
get {
return valid;
}
}
private enum Square {
White,
Black,
Red,
Blue,
}
private int NumSquares(Square[,] map, Square q) {
int ret = 0;
for (int y = 0; y < size; y++) {
for(int x = 0; x < size; x++) {
if (map[x, y] == q) ret++;
}
}
return ret;
}
private Point PickSquare(Square[,] map, Square q) {
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (map[x, y] == q) return new Point(x, y);
}
}
return Point.Empty;
}
private void MakeNeighboursRed(Square[,] map, Point p) {
if (p.X > 0 && map[p.X - 1, p.Y] == Square.Black) map[p.X - 1, p.Y] = Square.Red;
if (p.X < size - 1 && map[p.X + 1, p.Y] == Square.Black) map[p.X + 1, p.Y] = Square.Red;
if (p.Y > 0 && map[p.X, p.Y - 1] == Square.Black) map[p.X, p.Y - 1] = Square.Red;
if (p.Y < size - 1 && map[p.X, p.Y + 1] == Square.Black) map[p.X, p.Y + 1] = Square.Red;
}
private void CalcValidity() {
Square[,] map = new Square[size, size];
int count = 0;
Point square = Point.Empty;
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (data[x, y]) {
map[x, y] = Square.Black;
square = new Point(x, y);
} else {
map[x, y] = Square.White;
}
}
}
if (square != Point.Empty) {
map[square.X, square.Y] = Square.Red;
}
while (true) {
if (NumSquares(map, Square.Red) == 0) {
if (NumSquares(map, Square.Black) == 0) {
valid = count == size;
return;
} else {
valid = false;
return;
}
} else {
square = PickSquare(map, Square.Red);
MakeNeighboursRed(map, square);
map[square.X, square.Y] = Square.Blue;
count++;
}
}
}
#region IEquatable<Piece> Members
public bool Equals(Piece other) {
if (size != other.size) return false;
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (data[x, y] != other.data[x, y]) return false;
}
}
return true;
}
#endregion
}
La solution
Voici une façon de penser à l'algorithme de remplissage d'inondation qui n'utilise pas récursivité.
Commencez par chaque ensemble carré soit blanc (blanc) ou noir (rempli). La question est « sont les régions noires contiguës ou non? »
Vous pouvez utiliser cet algorithme:
- S'il n'y a pas de carrés noirs, alors il est vrai qu'il n'y a pas de régions noires contiguës, de sorte que vous avez terminé.
- Dans le cas contraire, il y a au moins un carré noir. Choisissez une carré noir et tournez-le rouge.
- S'il n'y a pas de carrés rouges et sans carré noir, alors vous avez terminé, et les régions noires sont contiguës .
- S'il n'y a pas de carrés rouges, mais un ou plusieurs carrés noirs alors vous avez terminé. Les régions noires ne sont pas contiguës . La région est encore noir est discontiguous de la région qui est bleu.
- Dans le cas contraire, il doit y avoir au moins un carré rouge. Choisissez une carré rouge. Mettez tous ses voisins noirs au rouge, puis le transformer en bleu.
- Retour à l'étape 3.
voir comment cela fonctionne? Les carrés rouges sont les « bords » de la région qui ne sont pas remplies par les inondations. Les carrés bleus sont la région inondée. Si les inondations bleues tout le noir, alors il doit avoir été contigu.
MISE À JOUR: Re, votre commentaire:
Merci beaucoup! C'est parfait. J'aime votre blog, en particulier les articles sur LINQ et « écrire ce que vous voulez dire », et j'ai essayé d'appliquer ces principes ici
Merci pour les mots aimables. Si ce que vous aimez est très « LINQ-y » des solutions à ce genre de problèmes, alors je le ferais pas utiliser la solution que je dessinai ici. Notez que l'algorithme est essentiellement « muter une structure de données pour apprendre les faits à ce sujet ». Ce n'est pas une chose très LINQ-ish à faire. LINQ est tout au sujet de l'interrogation des structures de données sans les modifier.
Si je voulais faire une solution plus comme LINQ à votre problème, je prendrais une approche très différente. Voici ce que je ferais.
Tout d'abord, savez-vous ce qu'est une « classe d'équivalence » ou une « relation d'équivalence » est? Je vais brièvement les définir si vous ne connaissez pas. relation est une fonction qui prend deux choses et retourne un bool. Par exemple, « moins », « égal à », « avoir le même dernier chiffre sur dix de base » et « somme à un nombre pair » sont toutes les relations sur les entiers. Une équivalence relation (A ~ B) est une relation qui est réflexif (X ~ X est toujours vrai), symétrique (X ~ Y et y ~ X sont les mêmes) et transitive (si X ~ y et y ~ Z sont vraies alors il en est X ~ Z).
Dans nos exemples, « moins » est transitive, mais pas réfléchi ou symétrique. Les trois autres sont des relations d'équivalence.
partitions Une relation d'équivalence de l'ensemble en classes d'équivalence. Par exemple, la relation d'équivalence « somme à un nombre pair » partitions Les entiers en deux classes d'équivalence: les nombres pairs et les nombres impairs. Choisissez deux nombres impairs et X ~ Y est vrai. Choisissez deux nombres pairs et X ~ Y est vrai. Mais un nombre impair et un nombre pair, X ~ Y est faux. Tous les chiffres sont même « équivalent » aux fins de cette relation.
Considérons maintenant la relation « est un voisin sur cet ensemble de tuiles » pour un de vos ensembles de tuiles. Il est clair que cela ne une relation d'équivalence; il est symétrique, mais pas réfléchi ou transitive. Mais toute relation peut être étendue pour une relation d'équivalence en définissant une nouvelle relation qui est le fermeture réflexive et transitive de la relation. Ceci est le « est accessible à partir de » relation.
Votre question est donc essentiellement « combien de classes d'équivalence sont là pour la relation d'équivalence de joignabilité »? Si la réponse est zéro, alors il n'y a pas de régions noires. Si la réponse est un alors il y a une seule région contiguë. Si elle est plus d'un alors il doit y avoir des régions contiguës.
Par conséquent, une autre façon de caractériser votre question est « étant donné qu'il ya au moins un blcarrelage ack, est l'ensemble de carreaux noir identique à la fermeture réflexive et transitive de la relation de voisinage sur une tuile arbitraire? » Si la réponse est « oui », il y a une seule région contiguë. Si « non », il faut alors une région qui est non joignable.
Puisque vous avez un moyen de compter les carreaux, et puisque les nombres entiers sont finis, nous pouvons faire encore mieux que cela. Nous pouvons simplement demander « est la taille de la fermeture réflexive et transitive de la relation de voisinage sur une tuile noire arbitraire identique au nombre de toutes les tuiles noires? » pour résoudre votre problème.
Alors, comment répondre à cette question? Supposons que vous avez une méthode qui prend une tuile et retourne une séquence de ses voisins:
public static IEnumerable<Tile> GetNeighbours(Tile tile)
{
... yield return the north, south, east and west neighbours
... if they exist and they are on
}
En fait cette méthode est « donné une tuile, donnez-moi toutes les tuiles qui ont la relation de voisinage avec lui ». Cela fonctionne très bien si vous pouvez calculer que les membres ont une relation avec un membre donné, qui clairement dans ce cas, vous pouvez le faire si bon marché.
Maintenant, vous pouvez calculer la transitive et la fermeture réflexive de cette relation en utilisant le code que j'ai posté ici:
http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx
Et maintenant votre algorithme entier devient en effet très court:
bool HasExactlyOneRegion()
{
return (tilesTurnedOn.Count == 0) ?
false :
TransitiveAndReflexiveClosure(GetNeighbours, tilesTurnedOn.First()).Count == tilesTurnedOn.Count;
}
Si vous avez les bons outils à votre disposition alors la solution est une seule instruction!
Notez que les deux solutions que j'ai donné (et croquis de Albin aussi) sont identiques dans leur fonctionnement . Dans ma deuxième solution, les « tuiles rouges » de la première solution sont les tuiles dans la structure de données « pile », et les « tuiles bleues » sont les tuiles dans la structure de données « fermeture » du code dans le lien que j'ai donné.
La différence entre les solutions est que dans la façon dont vous que à propos de la solution. Je me plais à penser mathématiquement, donc je préférerais la deuxième solution. Il est tout au sujet des ensembles et des relations et des fermetures, des idées très abstraites. Si vous êtes plus d'un penseur visuel puis ma première solution, vous pouvez visualiser une vague rouge tranchant se répandre dans une zone noire jusqu'à ce qu'elle soit pleine, peut-être plus facile à comprendre et à raisonner sur.
Autres conseils
Vous commencez à un peu « vrai » au hasard. Ensuite, vous « marchez » au nord, au sud, un à l'est et à l'ouest à la fois. Si vous trouvez un « vrai » bit qui est pas « visité », marque ce nœud « visité » dans une structure séparée et « marcher » récursive dans toutes les directions à partir de là. Si le bit est « faux » ou « visité », ne rien faire et retour au « niveau » précédent. Lorsque vous ne pouvez pas trouver tous les nœuds non plus « visités », compter le nombre de noeuds visités et comparer avec le nombre total de noeuds « vrais ».
Edit:. Notez que la récursivité se déroulera hors de l'espace de pile si les bitmaps sont grandes
