Liegt der Mauszeiger in dieser Fläche? Bei einem Rechteck sind das vier Vergleiche. Sobald die Fläche Einbuchtungen hat, etwa eine Trigger-Zone, ein Gebiet auf einer Karte oder ein frei gezeichneter Bereich, reichen vier Vergleiche nicht mehr. Der Klassiker schießt einen Strahl vom Punkt aus los und zählt, wie oft er die Kanten kreuzt.
Der Mauszeiger ist der Testpunkt. Von ihm läuft ein gestrichelter Strahl nach rechts, jede Kante, die er kreuzt, wird orange, und jeder Schnittpunkt bekommt eine Markierung. Die Ecken lassen sich ziehen, ein Klick auf eine Kante setzt eine neue Ecke, Rechtsklick oder Entf nimmt eine weg (drei bleiben immer stehen). Oben links steht das Ergebnis. Beim Ziehen bleibt der Testpunkt, wo er war, so sieht man, wie sich das Ergebnis ändert, während die Ecke wandert.
Zählen
Ungerade Anzahl Schnitte heißt innen, gerade heißt außen. Der Strahl betritt oder verlässt die Fläche bei jedem Schnitt, und ganz rechts ist er garantiert draußen. Offen ist nur, wann eine Kante den Strahl schneidet. Zuerst muss ein Ende der Kante über und das andere unter der Strahlhöhe liegen:
inline bool spansRow(Vec2 a, Vec2 b, double y) { return (a.y > y) != (b.y > y); }
Danach muss der Schnittpunkt rechts vom Punkt liegen. Dafür könnte man ihn ausrechnen und vergleichen. Ich entscheide das über das Vorzeichen eines Kreuzprodukts, da fällt die Division weg und bei ganzzahligen Koordinaten ist das Ergebnis exakt:
const double cross = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
const bool right = b.y > a.y ? cross > 0.0 : cross < 0.0;
if (right) out.push_back({detail::xAt(a, b, p.y), detail::direction(a, b), i});
Die x-Position des Schnitts rechne ich trotzdem aus, aber nur, damit die Demo die Markierung dort hinsetzen kann.
Die Ecke
Hier steckt die Falle, und spansRow oben ist die Antwort darauf. Was passiert, wenn der Strahl genau durch eine Ecke läuft? Die naheliegende Prüfung mit geschlossenem Intervall (p.y liegt zwischen den beiden y-Werten, die Enden zählen mit) erwischt die Ecke für beide Kanten, die sich dort treffen. Läuft das Polygon an der Stelle durch den Strahl hindurch, wird der Schnitt doppelt gezählt und die Parität kippt. Bei einer waagerechten Kante auf Strahlhöhe kommt dazu, dass man durch null teilen würde.
(a.y > p.y) != (b.y > p.y) macht das Intervall auf einer Seite offen. Eine Kante deckt damit die Höhen von ihrem kleineren y bis knapp unter ihr größeres y ab. Man kann sich das auch so vorstellen: Eine Ecke, die exakt auf dem Strahl liegt, wird behandelt, als läge sie einen Hauch darunter, also bei kleinerem y. Der Strahl trifft dann keine Ecke mehr, es gibt nur noch saubere Kreuzungen. Daraus folgt für die drei Fälle:
Läuft das Polygon durch die Ecke hindurch, zählt genau eine der beiden Kanten. Berührt nur eine Spitze den Strahl, zählen entweder beide oder keine, die Parität bleibt gerade. Eine waagerechte Kante besteht den Test nie und wird nie gezählt, ihre Nachbarkanten regeln das allein.
Ausprobieren geht mit dem Chip "Snap ray to corner" (Taste S). Der Strahl rastet dann auf der Höhe der nächsten Ecke ein, und die Ecke bekommt einen Ring. Auf dem konkaven Polygon sieht man, dass von den zwei Kanten an einer Durchgangsecke nur eine orange wird. Im Test steht dasselbe als Raute, deren linke und rechte Ecke exakt auf Höhe 0 liegen:
const Polygon d{{0, -2}, {2, 0}, {0, 2}, {-2, 0}};
assert(evenOdd(d, {0, 0})); // ray leaves through the right corner: that must count once
assert(!evenOdd(d, {-5, 0})); // ray passes the left corner and the right corner: once each, even
Gerade-ungerade oder Winding Number
Statt nur zu zählen, kann man den Treffern eine Richtung geben: +1, wenn die Kante zu größerem y läuft, sonst -1. Die Summe ist die Winding Number, und ungleich 0 heißt innen:
inline int windingNumber(const Polygon& poly, Vec2 p) {
int w = 0;
for (const Crossing& c : rayCrossings(poly, p)) w += c.dir;
return w;
}
Bei normalen Polygonen kommt dasselbe heraus. Der Unterschied zeigt sich, wenn sich das Polygon selbst überschneidet. Die Demo startet deshalb mit einem Fünfeck-Stern, bei dem fünf Ecken jeweils mit der übernächsten verbunden sind. Das Fünfeck in der Mitte wird von dem Linienzug zweimal umrundet. Der Strahl vom Mittelpunkt schneidet zwei Kanten, zwei ist gerade, also meldet Ray Casting "outside" und lässt die Mitte beim Füllen hohl. Mit Chip 2 (Taste 2) zählt er zweimal +1, die Winding Number ist 2 und die Mitte "inside". Die Füllung der Demo wird mit der gewählten Regel gezeichnet, du siehst den Wechsel also direkt. SVG und Canvas kennen beide Regeln als fill-rule, Standard ist dort nonzero.
Stolperfallen
Liegt der Testpunkt selbst genau auf dem Rand, ist das Ergebnis eine Konvention. Mit dieser Regel sind die Seiten mit kleinerem x oder y innen und die mit größerem x oder y außen. Beim Quadrat von (0,0) bis (4,4) ist (0,2) also innen und (4,2) außen. Zwei Polygone, die sich eine Kante teilen, beanspruchen so nie denselben Punkt beide. Mit Mauskoordinaten kommt das selten vor, deshalb gibt es den Snap-Chip, der die Strahlhöhe auf eine Ecke setzt.
Zum Absichern gibt es neben handgerechneten Fällen einen Test, der dieselben Polygone an der y-Achse spiegelt und prüft, dass das Ergebnis gleich bleibt. Ein Strahl nach rechts im gespiegelten Polygon ist ein Strahl nach links im Original, das ist eine zweite, unabhängige Antwort auf dieselbe Frage. Ein Polygon mit weniger als drei Ecken hat keine Fläche, rayCrossings liefert dafür gar keine Treffer, und beim Löschen hört die Demo bei drei Ecken auf.
Den Code findest du im Repo unter point-in-polygon. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.