Lokalisieren Sie ein ASCII-Kunstbild in einem Textkörper mit einer gewissen Toleranz für Fehler

Brute-Force mit einem Match-Score:

• Definieren Sie ein "Quadrat" um Ihren "Schleim Torpedo"; das ist ein 2D-Array mit Breite und Höhe ein wenig breiter und höher als Ihr Torpedo.
• Markieren Sie in diesem 2D-Array Zellen entweder als aktiviert oder deaktiviert, um das gewünschte Bild zu erstellen.
• Durchlaufen Sie nun jedes Zeichen (nennen wir es eine "Index" -Position) in Ihrem ganzen Bild und vergleichen Sie für jedes die Positionen in der Nähe mit denen des entsprechenden Zeichens im 2D-Array.
• Suchen Sie nach "checked" (oder ungeprüfter) Position im Bild, was einer aktivierten (oder nicht markierten) Position im Slime Torpedo Array entspricht (zum Beispiel ein Char X über und Y links von der aktuellen Indexposition in der Bild, das mit dem Status X oben und Y links vom Mittelpunkt des Schleim Torpedo-Array übereinstimmt). Fügen Sie für jede solche "Übereinstimmung" einen "Punkt" zu dieser Indexposition im Bild hinzu.

Jetzt ist der Trick : Um dies effektiver zu machen, überprüfe nur einige der Positionen im Schleim-Torpedo - zum Beispiel jede 10. Stelle oder noch weniger. Das sollte die Laufzeit grob um den Faktor 10 reduzieren.

Das würde bedeuten, dass Sie (1/10) * the number of characters in the 2D array für jedes Zeichen im gesamten Bild überprüfen müssen.

Jetzt verfolgen Sie die Positionen mit den höchsten Punktzahlen im Gesamtbild. Die Position mit der höchsten Punktzahl sollte die beste Übereinstimmung sein.

Wenn Sie möchten, können Sie dies mehrmals mit unterschiedlichem Detaillierungsgrad ausführen, indem Sie zum Beispiel nur 1/20 der Positionen beim ersten Mal und dann 1/2 als nächstes prüfen, aber dieses Mal nur auf z. B. fokussieren die höchsten 20 (oder 50? 100?) Punkte aus der ersten Runde.

(Alternativ könnten Sie einen detaillierteren Scan aller Positionen durchführen, die höher als ein Schwellenwert S sind).

Hoffen Sie, lassen Sie uns wissen, wie es geht, was auch immer Sie entscheiden, interessante Frage! :)

Als Antwort auf die folgenden Kommentare aktualisieren:

Vielleicht war meine Erklärung etwas unklar. Kurz / Pseudo-Code, müssten Sie so etwas tun, um die Punktzahl für jede Zelle zu finden:

Das ist offensichtlich ein wenig unordentlich, und ich bin mir nicht sicher über alle Details, aber ich hoffe, es zeigt eine allgemeine Idee, die funktionieren sollte. Wenn du damit fertig bist, iteriere erneut über alle Zellen und nimm die Zellen mit der höchsten Punktzahl auf (oder baue eine separate High-Score-Liste auf dem Weg - das wäre wahrscheinlich schneller).

Sie müssen einige Änderungen vornehmen, z. B. die ForEach Schleifen durch eine reguläre For(int i=0; i < someArrayLength; i = i + levelOfDetail){ ... } oder etwas ähnliches ersetzen, wobei levelOfDetail eine ganze Zahl ist, mit der Sie die Detailstufe anpassen (dh wie viele Zellen) im SlimeTorpedoArray zu überprüfen). Ich bin mir sicher, dass du es schaffen kannst ...;)

Nehmen wir an, die Parameter für Breite und Höhe (in Bezug auf die Anzahl der Zeichen) sind für Ihre erste Form bekannt. Lassen Sie sie width und height sein.

• Kodieren Sie Ihre Eingabe in ein 2D-Array von Bits (oder + Zeichen). Also hast du int[][] inputBits = new int[height][width]; und du solltest auffüllen es richtig. (Es ist deine Aufgabe, Alter.)
• Dann wenden Sie eine einfache Suche auf die größere Form an (vorausgesetzt, es ist auch in ein anderes 2D-Array kodiert). Verschieben Sie den Pivot-Bereich nach rechts um jeweils eins (der Schwenkbereich entspricht dem Bereich des ersten Form) und prüfen, ob der Schwenkbereich (2D-Array) alle Elemente enthält gleich der ersten Form. Das ist ein Brute-Force-Algorithmus =)

Für Interessierte habe ich dieses Problem mit XOR-Mapping in Java gelöst:

Ссылка

Es berücksichtigt auch, dass es falsche Positive oder Duplikate geben kann, es gibt eine Option, um den Mindestschwellenwert für eine gute Übereinstimmung festzulegen, eine benutzerdefinierte Daten-Image-Datei hinzuzufügen usw. ...