Wie bekomme ich die Bereiche, die von einer beliebigen 2D-Form umschlossen sind?

7

In meinem Spiel möchte ich, dass Benutzer beliebige 2D-Formen beliebiger Länge um Spielobjekte zeichnen können. Die Formen müssen mit einem einzigen Strich geschlossen und gezeichnet werden, der sich nicht überlappt.

Zum Beispiel:

Geben Sie hier die Bildbeschreibung ein

Ich möchte das Vorhandensein eines Spielobjekts in den grünen Bereichen oben erkennen.

Ich kann erkennen, ob sich ein Punkt innerhalb eines bestimmten Polygons befindet, aber wie kann ich feststellen, wo sich die Polygone (grüne Bereiche) nur von den Punkten in der Linie befinden?

2d mathematics user1953221
quelle
1
Eine spezielle Flutfüllung würde ich vermuten. Interessante Frage.
MichaelHouse
Nur um diesen Fall oben rechts zu disambiguieren: Es gibt tatsächlich zwei Möglichkeiten, diese Form zu zeichnen, von denen eine eine Überlappung von Linien beinhaltet (und daher ungültig ist; der Strich wird abgebrochen, wenn sich die Linien überlappen), von denen eine nicht (und) ist also vollkommen gültig).
user1953221
2
Können Sie den vom Benutzer gezeichneten Strich aufzeichnen oder haben Sie nur das Bild des Strichs? Wenn erstere, warum können Sie den Punkt nicht einfach im Polygontest machen?
GuyRT
Es ist das erstere. Das Problem beim Point-in-Polygon-Test (zumindest in meinen Augen) ist, dass er die Punkte, die er erhält, als Darstellung eines geschlossenen Polygons betrachtet. Während das Polygon möglicherweise nicht geschlossen ist, wie in den Bildern oben rechts und unten links.
user1953221

Antworten:

3

Definieren Sie zunächst, was "Nachbar" ist. In Ihrem Fall sind die Pixel 'A' und 'B' verbunden, wenn abs(A.x - B.x) <= 1 && abs(A.y - B.y) <= 1. Dies ist die Regel, die Microsoft Paint beim Füllen von Fluten verwendet.

Ihr Validund Invalid-shape isn't closedkann leicht mit einer Flutfüllung erkannt werden. Eine Flutfüllung markiert ein nicht leeres Pixelgrün. Es setzt dann die Flutfüllung mit seinen Nachbarn fort und füllt schließlich die volle Form. Wählen Sie dazu ein zufälliges Pixel aus und suchen Sie einen leeren Nachbarn. Führen Sie von diesem Nachbarn aus eine Flutfüllung mit einer einzigartigen Farbe durch. Wiederholen Sie alle Pixel, um sicherzustellen, dass Sie alle Bereiche ausgefüllt haben. (Bild 2)

Finden Sie nun heraus, welche Farben die Bildränder berühren. Diese Farben sollten gelöscht werden, da sie keinen geschlossenen Raum darstellen. (Bild 3)

Jetzt möchten Sie Linien erkennen, die nicht zu einem gefüllten Bereich beitragen. Markieren Sie dazu alle schwarzen Pixelnachbarn eines gefüllten Pixels in BLAU. (Bild 4)

Alle Linien, die noch schwarz sind, tragen nicht zu den Rändern eines Bereichs bei. Sie sind ungültig. (Bild 5).

Erklärung des Algorithmus

Das Erkennen Ihres "Gültig innerhalb eines einzigen Strichs" erfordert einen kleinen zusätzlichen Schritt. Starten Sie für jedes ungültige Pixel eine Flutfüllung. Wenn Sie während Ihrer Flutfüllung die Kanten von zwei verschiedenen Bereichen berühren, verbindet diese Linie tatsächlich zwei Bereiche und ist daher Teil Ihres gültigen Bildes.

Sie müssen entscheiden, ob dieser Algorithmus gut genug ist. Wenn Sie beispielsweise eine dicke Kante zeichnen, indem Sie einige Pixel zurückgehen, wird dies als "ungültig" markiert, da dieser zusätzliche "Tintenklecks" nicht zwei Bereiche verbindet. Sie können diesen Algorithmus verbessern, indem Sie eine Zeitdimension hinzufügen: Sie geben eine Liste der Pixel in der Reihenfolge an, in der sie gezeichnet wurden.

Denken Sie abschließend an die Benutzererfahrung. Das Zeichnen einer 'V'-Form führt höchstwahrscheinlich zu> 2 Pixel Nachbarn für ein neues Pixel, das in der Spitze des V gezeichnet wird. Können Sie einen Algorithmus, der überlappende Kanten erkennt, damit umgehen?

parasietje
quelle
Interessanter Ansatz, und es ist offensichtlich, dass es funktioniert. Vielen Dank, dass Sie sich die Zeit genommen haben, eine ausführliche Erklärung abzugeben. Ein Problem dabei ist jedoch, dass die Laufzeit der Flutfüllung quadratisch mit der Größe der Leinwand (oder zumindest der Größe des Rechtecks, das die Zeichnung darauf einnimmt) zunimmt, und ich plante, eine riesige Leinwand zu haben Welt, in der der Benutzer scrollen konnte, mit sehr häufigen Aktualisierungen der gültigen Bereiche - also hoffte ich (vielleicht naiv), dieses Problem geometrisch zu lösen, heh. Aber ich werde auf jeden Fall Ihren Algorithmus verwenden, wenn ich keinen schnelleren Ansatz finde!
user1953221
1
Möglichkeiten zur Optimierung: Finden Sie die minimalen / maximalen X / Y-Koordinaten einer gezeichneten Linie und schneiden Sie das Bild zu. Sie können auch eine Heuristik (z. B. Manhattan-Abstand) verwenden, um eine Flutfüllung in Richtung der anderen Kanten zu priorisieren. Dies würde eine
Flutfüllung bewirken,