Bestimmen Sie, ob eine Reihe von Kacheln in einem Raster eine geschlossene Form bildet

Bei einer Reihe von Kacheln in einem Raster möchte ich Folgendes bestimmen:

• Wenn die Fliesen eine beiliegende Figur machen
• Wenn die Kacheln eine geschlossene Figur bilden, wenn Sie die Seiten des Bretts als Kante der Figur zählen
• Wenn eine der beiden vorherigen Aussagen zutrifft, welche zusätzlichen Kacheln in die beigefügte Abbildung fallen, bilden sich die ursprünglichen Kacheln.

Der Spieler drückt zunächst auf ein Plättchen und zieht dann seinen Finger auf andere Plättchen, um eine Kette gleichfarbiger Plättchen zu erstellen. Ich werde prüfen, ob die nächste Kachel gültig ist. Ex. Wenn der Spieler auf einem roten Ziegel beginnt, ihre einzige nächste gültige Bewegung ist zu einem benachbarten roten Ziegel (Diagonalen tun count). Wenn der Benutzer seinen Finger hebt, muss ich in der Lage sein, nach den 3 oben genannten Elementen zu suchen.

Mein erster Gedanke war also, dass ich, da ich jedes Mal die Gültigkeit der Kette überprüfte , wenn der Spieler seinen Finger hob, überprüfen konnte, ob das erste und das letzte Plättchen nebeneinander lagen. (Ich weiß bereits, dass sie die gleiche Farbe haben.) Wenn sie nebeneinander lagen, hatte ich die Vermutung, dass ich eine beiliegende Figur gemacht hatte, und ich würde hierher kommen, um zu versuchen, herauszufinden, ob mir etwas Großes fehlt, und um es zu bekommen eine Art logischer / mathematischer Beweis dafür, dass meine Vermutung richtig war (oder ein Beispiel, das beweist, dass sie falsch ist).

Aber dann dachte ich an Artikel 2: Ich muss auch Ketten berücksichtigen, die eine Kante der Tafel als Seite der beiliegenden Figur verwenden. In diesem Fall wären das erste und das letzte Element in der Kette nicht benachbart, aber ich hätte immer noch eine beiliegende Figur. Jetzt bin ich wieder auf dem ersten Platz.

Was kann ich mit dieser Kette von Gitterkoordinaten tun, um herauszufinden, ob sie eine geschlossene Figur bilden oder nicht? Und wenn ich weiß, dass ich eine beiliegende Figur habe, wie kann ich am besten eine zusätzliche Liste aller Kacheln erhalten, die innerhalb ihrer Grenzen liegen?

Oben habe ich Bilder gezeichnet, von denen ich erwarte, dass die 4 möglichen Ergebnisse dieses Tests sein können.

1. Die Kette macht keine beiliegende Figur.

2. Die Kette macht eine beiliegende Figur.

3. Wenn Sie die Seiten des Bretts als Kante (oder mehr als eine Kante) der Figur zählen, bildet die Kette eine geschlossene Figur.

4. Die Kette bildet zwar eine beigefügte Figur, es gibt jedoch zusätzliche Datenpunkte (vom Benutzer als Teil der Kette gültig ausgewählt), die nicht Teil der erstellten Figur sind.

Fall 4 ist am schwierigsten, da Sie die "zusätzlichen" Kettenglieder extrahieren müssten, um die beiliegende Figur und die Teile zu finden, die in sie fallen (aber nicht um den "nicht geschlossenen" Bereich herum).

Also ... hat jemand eine Idee, wie man das gut lösen kann, oder nur einen Ausgangspunkt für mich? Ich gehe an dieser Stelle im Kreis und könnte einen anderen Satz Augen gebrauchen.

1. Erkennen einer Kachelschleife

Das Problem scheint dem Erkennen eines Zyklus (einer Schleife) in einem Diagramm ähnlich zu sein, siehe hier oder hier .

• Die Knotenmenge Vdieses Diagramms G=(V, E)sind die Kacheln.
• Eine Kante e = (v1, v2)existiert zwischen zwei verschiedenen Knoten, wenn die Kacheln direkte oder diagonale Nachbarn sind

2. Behandlung des Bildschirmrandfalls

Der Bildschirmrand besteht aus den imaginären Kacheln, die einen um eine Kachel breiten Rand um den Bildschirm der sichtbaren Kacheln bilden würden.

Gemäß Ihrer Spezifikation würde ein Teil des Bildschirmrahmens einen impliziten Teil einer geschlossenen Schleife bilden. Um eine geschlossene Schleife zu erkennen, würde es ausreichen, den Graphen Gzu einem Graphen zu erweitern, G'indem die Verbindung über diese Regel eingehalten wird:

• Eine weitere Kante befindet sich zwischen zwei verschiedenen Knoten, wenn die beiden Kacheln jeweils direkt am Bildschirmrand positioniert sind

Somit wären Kacheln bei (0,0) und (1,0) zusammen mit den "Randkacheln" (-1,0), (-1, -1), (0, -1) Teil einer geschlossenen Schleife. , (1, -1).

3. Der innere Teil eines Schleifenbereichs

Ich würde in eine ähnliche Richtung gehen, wie es der Benutzer Arthur Wulf White vorgeschlagen hat:

Die Begrenzung des Kachelsatzes müssen wir durch den Begrenzungsrahmen der Schleifenkacheln untersuchen.

Verwenden Sie dann eine Flutfüllung, um alle Kacheln innerhalb des Begrenzungsrahmens auszuwählen, die sich entweder außerhalb oder innerhalb der geschlossenen Schleife befinden. Es kann nur einer dieser beiden Fälle sein. Welches müssen wir später herausfinden.

Es wäre auch eine gute Idee, den Begrenzungsrahmen um eine Kachel in jede Richtung zu erweitern, um die zu erhalten. Daher erhalten extbbwir nur einen verbundenen Satz von Außenpunkten, falls wir die Flutfüllung mit einer Außenkachel beginnen.

Sobald wir die Flutfüllfläche haben, würden wir auch den Begrenzungsrahmen berechnen, den ffbb. Wenn wir mit einer Außenkachel begonnen haben, sollte diese mit dem Begrenzungsrahmen für erweiterte Schleifen identisch sein.

ffbb == extbb

Wenn wir mit einer Innenkachel begonnen haben, sollte diese einen deutlich kleineren Begrenzungsrahmen ergeben, da die Schlaufenkacheln zwischen beiden Begrenzungsrahmen eingeklemmt werden müssen.

ffbb < extbb

Die anfängliche Startkachel für die Flutfüllung kann eine beliebige Kachel innerhalb der Kachel sein, bei der es sich um extbbeine freie Kachel handelt. Vielleicht ist die zufällige Auswahl der beste Ansatz.

Wenn ich vorher wissen würde, dass das Innere kleiner als das Äußere ist, würde ich um den Massenmittelpunkt der Schleifenpunkte beginnen, der sich für viele Bereiche im Inneren befindet (Gegenbeispiel: C-förmiger Bereich), ansonsten am Rand des extbb. Aber ich habe keine Ahnung, wie ich das einschätzen soll.

Schlussbemerkungen

Normalerweise würde ich sagen, dass ein einfacher Spaziergang ausgehend von einer Kachel und das Führen einer Liste der besuchten Kacheln ausreichen würde, um einen Zyklus zu erkennen, aber diese Bildschirmgrenzbedingung könnte zu einem komplizierteren Diagramm führen. Sie sollten also mit einem Diagrammalgorithmus auf der sicheren Seite sein .

Unten sehen Sie ein Beispiel, bei dem der Innenraum nicht angeschlossen ist. Andererseits sollte die Zykluserkennung zwei Schleifen finden. In diesem Fall sollte eine verworfen werden.

Sie können dies beheben, indem Sie:

1. Finden des Begrenzungsrahmens dieser Form.
2. Erhöht die Größe in jeder Richtung um 1.
3. Über den Rahmen des neuen, leicht vergrößerten Begrenzungsrahmens iterieren und Flood-Fill auftragen.
4. Wenn es Kacheln gibt, die Sie nicht mit Flood-Fill markiert haben und die sich nicht in dieser Kette befinden, sind sie eingeschlossen. Ich nehme an, dass nach Ihrer Definition, wenn es eingeschlossene Kacheln gibt, die Form eine geschlossene Figur ist.

Gehen Sie ein, Iterierte über alle Kacheln an der Kette und finden ihre minX, minY, maxXund , maxYund das ist Ihr Zeichen - Box oder AABB.

Zwei ist trivial.

Das Iterieren über den Rahmen ist einfach. Achten Sie nur darauf, dass Sie sich nicht außerhalb des Gitters überschwemmen. Sie können lernen, wie man in Wikipedia überflutet .

Bei Nummer vier können Sie zunächst nur die Kacheln neben der Kette überprüfen. Sie können jede Kachel, die Sie nicht markiert haben, überfluten, um weitere Kacheln zu finden.

Ihre Intuition ist richtig, vorausgesetzt, die Kette endet, sobald der Benutzer versucht, eine Kachel auszuwählen, die er bereits ausgewählt hat. In diesem Fall sieht die Form in Ihrem Bild im Allgemeinen wie ein Lasso aus (4). Wenn sie weiter wischen können, können sie viele Schleifen zeichnen, und die Dinge werden komplizierter. Sie möchten die Frage nach den Punkten im Polygon beantworten.

Zuerst müssen wir das Problem definieren. Ich gehe davon aus, dass die Situation wie folgt aussieht (2), dh jeder Schwanz wurde abgestreift und das Ende verbindet sich wieder mit dem Anfang, so dass jede Kachel genau einen "Vorgänger" und genau einen "Nachfolger" in der Kette hat (wobei der Vorgänger des Nachfolgers von Kachel X immer Kachel X ist). Wenn Sie "Nachfolgern" lange genug folgen, kehren Sie schließlich zu Ihrem Ausgangspunkt zurück. Sie können den Vorschlag von Gurgadurgen verwenden, um festzustellen, ob sich die Schleife zu irgendeinem Zeitpunkt tatsächlich auf sich selbst zurückkreuzt. Angenommen, Sie beenden die Benutzereingabe, wenn dies der Fall ist, sieht es aus wie eine Reihe von Knoten in einer Zeile, gefolgt von einer Schleife. Sie können die Linie von der Get the Loop entfernen.

Nun machen wir für jede Zeile Folgendes:

1. Beginnen Sie am linken Rand und verfolgen Sie für jede Kachel einen Booleschen Wert, der angibt, ob wir IN oder OUT sind. Beginnen.
2. Wenn die aktuelle Kachel Teil der Kette ist, sehen Sie sich sowohl den Nachfolger als auch den Vorgänger an (der nebeneinander liegen muss). Befindet sich einer der beiden Werte genau oberhalb (dh nördlich, nordöstlich oder nordwestlich der aktuellen Kachel), stellen Sie den Status der aktuellen Kachel auf das Gegenteil der Kachel links davon ein. Andernfalls setzen Sie es auf das gleiche wie die Kachel links. Gehe zu 4.
3. Wenn die aktuelle Kachel nicht Teil der Kette ist, setzen Sie die Kachel auf den Status des Titels links davon. Gehe zu 4.
4. Die Kachel rechts ist jetzt die aktuelle Kachel. Gehe zu 2.

Nehmen Sie nun alle Kacheln, die IN sind, fügen Sie die Kacheln am Rand hinzu (einschließlich eines Schwanzes, wenn Sie ihn früher entfernt haben oder nicht, Ihre Wahl), und nennen Sie das die Region.

Wenn Sie dem Benutzer erlauben möchten, Rahmen zu verwenden, denken Sie daran, dass dies nicht und IN / OUT auf der Karte definiert, sondern nur in zwei Teile unterteilt. Sie können beispielsweise den kleineren Bereich auswählen oder vom Benutzer die Verwendung von zwei benachbarten Seiten verlangen (dh links und unten, jedoch nicht oben / unten oder links / rechts).

Eine Optimierung besteht darin, dass Sie nur Zeilen erstellen müssen, in denen sich ein Rand befindet (wenn Sie die Seiten nicht verwenden können). Ich gehe davon aus, dass Ihr Board klein genug ist, dass das Durchlaufen jeder Kachel und das Durchführen einer sehr einfachen Berechnung selbst auf dem schwächsten mobilen System kein Problem darstellt. (Sie müssen sie schließlich rendern, was für eine Aufgabe weitaus komplexer ist).