Vertegenwoordigen en oplossen van een doolhof gegeven een afbeelding

| | | | | | | | | | | | | | | | | | | | | | | | |

Wat is de beste manier om een doolhof voor te stellen en op te lossen op basis van een afbeelding?

De omslagafbeelding van The Scope Issue 134

Gegeven een JPEG-afbeelding (zoals hierboven te zien), wat is de beste manier om deze in te lezen, in een gegevensstructuur te parseren en het doolhof op te lossen? Mijn eerste instinct is om de afbeelding pixel voor pixel te lezen en op te slaan in een lijst (array) van booleaanse waarden: True voor een witte pixel, en False voor een niet-witte pixel (de kleuren kunnen worden weggegooid). Het probleem met deze methode is dat de afbeelding mogelijk niet "pixelperfect" is. Daarmee bedoel ik eenvoudigweg dat als er ergens een witte pixel op een muur is, deze een onbedoeld pad kan creëren.

Een andere methode (die bij mij opkwam na een beetje nadenken) is om de afbeelding te converteren naar een SVG-bestand - dat is een lijst met paden die op een canvas zijn getekend. Op deze manier kunnen de paden worden ingelezen in hetzelfde soort lijst (booleaanse waarden) waarbij True een pad of muur aangeeft, False die een berijdbare ruimte aangeeft. Een probleem met deze methode doet zich voor als de conversie niet 100% nauwkeurig is en niet alle muren volledig verbindt, waardoor er gaten ontstaan.

Een probleem bij het converteren naar SVG is dat de lijnen niet "perfect " Rechtdoor. Dit heeft tot gevolg dat de paden kubieke bezier-curven zijn. Met een lijst (array) van booleaanse waarden geïndexeerd door gehele getallen, zouden de curven niet gemakkelijk worden overgedragen, en alle punten die op de curve lijn zouden moeten worden berekend, maar zullen niet exact overeenkomen met de lijstindices.

Ik neem aan dat hoewel een van deze methoden kan werken (hoewel waarschijnlijk niet), ze jammerlijk inefficiënt zijn gezien zo'n groot beeld, en dat er een betere manier bestaat.Hoe kan dit het beste (het meest efficiënt en/of met de minste complexiteit ) gedaan? Is er zelfs een beste manier?

Dan komt het oplossen van het doolhof. Als ik een van de eerste twee methoden gebruik, krijg ik in wezen een matrix. Volgens dit antwoord, een goede manier om een doolhof weer te geven is het gebruik van een boom, en een goede manier om het op te lossen is het gebruik van de A*-algoritme. Hoe zou je een boomstructuur van de afbeelding kunnen maken? Enig idee?

TL;DR
De beste manier om te ontleden? In welke da een structuur? Hoe zou de genoemde structuur helpen/hinderen bij het oplossen?

UPDATE
Ik heb geprobeerd te implementeren wat @Mikhail in Python heeft geschreven, met behulp van numpy, zoals @Thomas heeft aanbevolen. Ik heb het gevoel dat het algoritme correct is, maar het werkt niet zoals gehoopt. (Code hieronder.) De PNG-bibliotheek is PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Geeft als resultaat of (x, y) ongeveer een witte pixel is.""" a = Waar voor i in xrange(3): if not a: break a = image[coord[1]][coord[0] * 3 + i] > 240 retourneer een def bfs(s, e, i, bezocht): """ Voer een breedte-eerste zoekopdracht uit. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) als is_white(np, i) en np niet in bezocht: frontier.put(np) bezocht.append(s) s = frontier.get() return bezocht def main(): r = png.Reader(filename = "thescope-134.png") rijen, cols, pixels, meta = r.asDirect() assert meta["planes"] == 3 # zorg ervoor dat het bestand RGB is image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) start, end = (402, 985), (398 , 27) print bfs(start, end, image2d, [])