Déterminer si un ensemble de tuiles sur une grille forme une forme fermée

Étant donné un ensemble de tuiles sur une grille, je veux déterminer:

• Si les tuiles font une figure fermée
• Si les tuiles font une figure fermée lorsque vous comptez les côtés de la planche comme bord de la figure
• Si l'une des deux déclarations précédentes est vraie, quelles tuiles supplémentaires se trouvent à l'intérieur de la figure ci-jointe, la forme initiale des tuiles.

Le joueur commencera par appuyer sur une tuile, puis en faisant glisser son doigt vers d'autres tuiles pour créer une chaîne de tuiles de même couleur. Je vérifierai au fur et à mesure pour voir si la prochaine tuile est valide. Ex. Si le joueur commence sur un carreau rouge leur seul mouvement suivant est valide pour une tuile rouge adjacente (diagonale do count). Lorsque l'utilisateur lève le doigt, je dois pouvoir vérifier les 3 éléments ci-dessus.

Donc, ma pensée initiale était que, puisque je vérifiais la validité de la chaîne à chaque fois que je partais, lorsque le joueur levait le doigt, je pouvais vérifier si la première et la dernière tuile étaient adjacentes. (Je sais déjà qu'ils sont de la même couleur.) S'ils étaient adjacents, j'avais le pressentiment que j'avais fait une figure fermée, et j'allais venir ici pour essayer de voir si je manquais quelque chose de gros et pour obtenir une sorte de preuve logique / mathématique que mon intuition était correcte (ou un exemple le prouvant incorrect.)

Mais c'est à ce moment-là que j'ai pensé à l'article numéro 2: je dois également tenir compte des chaînes qui utilisent un bord de la planche comme côté de la figure ci-jointe. Dans ce cas, le premier et le dernier élément de la chaîne ne seraient pas adjacents, mais j'aurais toujours une figure jointe. Alors maintenant, je suis de retour à la case départ, un peu.

Que puis-je faire avec cette chaîne de coordonnées de grille pour déterminer si elles font une figure fermée ou non? Et une fois que je ne sais que j'ai une figure ci - jointe, quelle est la meilleure façon d'obtenir une liste supplémentaire de toutes les tuiles qui tombent à l' intérieur de ses limites?

Ci-dessus, j'ai dessiné des images de ce que j'attends des 4 résultats possibles de ce test.

1. La chaîne ne fait pas de figure fermée.

2. La chaîne fait une figure fermée.

3. Si vous comptez les côtés de la planche comme un bord (ou plus d'un bord) de la figure, la chaîne fait une figure fermée.

4. La chaîne fait une figure fermée, mais il existe des points de données supplémentaires (valablement sélectionnés par l'utilisateur comme faisant partie de la chaîne) qui ne font pas partie de la figure créée.

Le cas 4 est le plus délicat, car il faudrait extraire les maillons de chaîne "supplémentaires" pour trouver la figure ci-jointe et les pièces qui s'y trouvent (mais pas autour de la zone "non fermée").

Alors ... Quelqu'un a une idée d'un bon moyen de résoudre ce problème, ou juste un point de départ pour moi? Je tourne en rond à ce stade et je pourrais utiliser une autre paire d'yeux.

1. Détection d'une boucle de tuiles

Le problème semble similaire à la détection d'un cycle (boucle) dans un graphe, voir ici ou ici .

• L'ensemble des nœuds Vde ce graphique G=(V, E)sont les tuiles,
• une arête e = (v1, v2)existe entre deux nœuds différents, si les tuiles sont des voisins directs ou diagonaux

2. Manipulation du boîtier de bordure d'écran

La bordure de l'écran se compose de ces tuiles imaginaires qui formeraient un bord large d'une tuile autour de l'écran des tuiles visibles.

Selon vos spécifications, une partie de la bordure de l'écran formerait une partie implicite d'une boucle fermée. Juste pour détecter une boucle fermée, il suffirait d'étendre le graphe Gà un graphe G'en honorant la connexion via cette règle:

• une autre arête existe entre deux nœuds différents, si les deux tuiles sont chacune positionnées directement près de la bordure de l'écran

Ainsi, les tuiles à (0,0) et (1,0) feraient partie d'une boucle fermée, avec les "tuiles de bordure" (-1,0), (-1, -1), (0, -1) , (1, -1).

3. La partie intérieure d'une zone en boucle

J'irais dans une direction similaire à ce que l'utilisateur Arthur Wulf White a suggéré:

Limiter l'ensemble de tuiles que nous devons examiner par la boîte englobante des tuiles de boucle.

Ensuite, utilisez un remplissage d'inondation pour sélectionner toutes les tuiles dans la zone de délimitation qui sont extérieures ou intérieures à la boucle fermée. Il ne peut s'agir que d'un de ces deux cas. Lequel nous devons découvrir par la suite.

L'extension du cadre de délimitation d'une tuile dans chaque direction serait également une bonne idée, ce qui donnerait le extbb, nous nous retrouvons donc avec un ensemble connecté de points extérieurs, au cas où nous aurions commencé le remplissage avec une tuile extérieure.

Une fois que nous avons la zone de remplissage, nous calculerions également son cadre de délimitation, le ffbb. Dans le cas où nous avons commencé avec une tuile extérieure, elle doit être identique à la boîte englobante de la boucle étendue.

ffbb == extbb

Dans le cas où nous avons commencé avec une tuile intérieure, elle devrait donner un cadre de délimitation nettement plus petit, car les tuiles en boucle doivent être prises en sandwich entre les deux boîtes de délimitation.

ffbb < extbb

La tuile de départ initiale pour le remblayage peut être n'importe quelle tuile à l'intérieur de extbblaquelle est une tuile libre. Peut-être en choisir un au hasard est la meilleure approche.

Si je savais auparavant que l'intérieur est plus petit que l'extérieur, je commencerais autour du centre de masse des points de boucle qui est à l'intérieur pour de nombreuses zones (contre exemple: zone en forme de C), sinon à la frontière de la extbb. Mais je ne sais pas comment estimer cela.

Remarques finales

Normalement, je dirais qu'une simple marche à partir de certaines tuiles et garder une liste des tuiles visitées serait suffisante pour détecter un cycle, mais cette condition aux limites de l'écran pourrait produire un graphique plus compliqué, vous devriez donc être du bon côté avec un algorithme de graphique .

Ci-dessous, un exemple où l'intérieur n'est pas connecté, par contre la détection de cycle devrait trouver deux boucles dans ce cas, une devrait être jetée.

Vous pouvez résoudre ce problème en:

1. Trouver la boîte englobante de cette forme.
2. Augmenter sa taille de 1 dans chaque direction.
3. Itération sur le cadre du nouveau cadre de délimitation légèrement agrandi et application d'un remblayage.
4. S'il y a des tuiles que vous n'avez pas marquées avec un remplissage d'inondation qui ne sont pas sur cette chaîne, elles sont fermées. Je suppose que selon votre définition, s'il y a des carreaux fermés, la forme est une figure fermée.

Pour faire un, sur toutes les tuiles itérer sur la chaîne et trouver leur minX, minY, maxXet maxYet qui est votre cadre de sélection ou AABB.

Deux est trivial.

Itérer sur le cadre est simple, assurez-vous simplement de ne pas remplir à l'extérieur de la grille. Vous pouvez apprendre à remplir le contenu de Wikipédia .

Pour le numéro quatre, vous pouvez commencer par ne vérifier que les tuiles adjacentes à la chaîne. Vous pouvez remplir de n'importe quelle tuile non marquée pour localiser plus de tuiles.

Votre intuition est bonne, en supposant que la chaîne se termine dès que l'utilisateur essaie de sélectionner une tuile qu'il a déjà sélectionnée. Dans ce cas, la forme ressemble en général à un lasso, dans votre photo (4). S'ils peuvent continuer à glisser, alors ils peuvent dessiner de nombreuses boucles, et les choses deviennent plus compliquées. Ce que vous voulez faire, c'est répondre à la question des points dans le polygone .

Tout d'abord, nous devons définir le problème. Je vais supposer que la situation ressemble à (2), c'est-à-dire que toute queue a été supprimée et que l'extrémité se connecte de nouveau au début, de sorte que chaque tuile a exactement un "prédécesseur" et exactement un "successeur" dans la chaîne (où le prédécesseur du successeur de la tuile X est toujours la tuile X). De plus, si vous suivez les «successeurs» assez longtemps, vous revenez finalement à votre point de départ. Vous pouvez utiliser la suggestion de Gurgadurgen pour détecter si la boucle se recroise sur elle-même à tout moment. En supposant que vous mettez fin à l'entrée de l'utilisateur lorsqu'il le fait, cela ressemblera à une série de nœuds dans une ligne, suivie d'une boucle. Vous pouvez supprimer la ligne de la boucle.

Maintenant, pour chaque ligne, nous procédons comme suit:

1. Commencez par le bord gauche et gardez une trace d'un booléen pour chaque tuile qui indique si nous sommes IN ou OUT. Commencer.
2. Si la tuile actuelle fait partie de la chaîne, regardez à la fois le successeur et le prédécesseur (qui doit être adjacent). Si l'un est strictement au-dessus (c'est-à-dire au nord, au nord-est ou au nord-ouest de la tuile actuelle), définissez l'état de la tuile actuelle à l'opposé de la tuile à sa gauche. Sinon, définissez-le sur le même que la tuile à gauche. Aller à 4.
3. Si la vignette actuelle ne fait pas partie de la chaîne, définissez la vignette sur l'état du titre à sa gauche. Aller à 4.
4. La tuile à droite est maintenant la tuile actuelle. Aller à 2.

Maintenant, prenez toutes les tuiles qui sont IN, ajoutez les tuiles sur la bordure (y compris une queue si vous l'avez enlevée plus tôt ou non, votre choix), et appelez cela la région.

Si vous souhaitez autoriser l'utilisateur à utiliser des bordures, n'oubliez pas que cela ne définit pas et IN / OUT sur la carte, mais la divise simplement en deux parties. Vous pouvez, par exemple, sélectionner la plus petite région ou demander à l'utilisateur d'utiliser deux côtés adjacents (c'est-à-dire à gauche et en bas, mais pas en haut / en bas ni à gauche / à droite).

Une optimisation est que vous avez seulement besoin de faire des lignes qui ont une bordure (si vous ne pouvez pas utiliser les côtés). Je suppose que votre carte est suffisamment petite pour que l'itération sur chaque tuile et l'exécution d'un calcul très simple ne soient pas un problème, même sur le système mobile le plus faible. (Vous devez les rendre, après tout, ce qui est beaucoup plus complexe d'une tâche).