iOS-Polygone prüfen: Rand, Löcher und Füllregeln

Eine Auswahl auf der Karte sieht aus, als hätte sie ein Loch – ein Klick in dieses Loch wird aber trotzdem als Treffer gewertet. Ein Punkt auf der Zeichenfläche liegt genau auf einem Liniensegment, doch je nach Zoomstufe fällt das Ergebnis anders aus. Solche Fehler liegen meist nicht an ungenauen Klicks über den Remote-Desktop, sondern daran, dass Rendering, Koordinatentransformation und geometrische Prüfung unterschiedlichen Festlegungen folgen. Mit einem reinen Swift-Regressionsskript auf einem Cloud-Mac lassen sich Geometrie- und Oberflächenprobleme zunächst voneinander trennen.

Zuerst drei Ergebniszustände und die Koordinateneinheit festlegen

Nicht gleich einen booleschen Wert zurückgeben. Zunächst drei Zustände definieren: innen, außen und auf dem Rand. Erst danach festlegen, ob ein Randpunkt als ausgewählt gilt. Ein Karteneditor kann die Auswahl am Rand erlauben, während bei einer Ausschlusszone auch der Rand gesperrt sein muss. Für beide Fälle darf nicht ohne ausdrückliche Festlegung dieselbe boolesche Regel gelten.

Dieser Artikel behandelt einfache geschlossene Ringe aus geraden Liniensegmenten in einem gemeinsamen ebenen Koordinatensystem. Löcher innerhalb eines Außenrings sind erlaubt. Nicht behandelt werden die direkte Projektion geografischer Koordinaten, die Reparatur von Selbstüberschneidungen und Abstände zu Kurven. Prüfpunkt und Eckpunkte müssen dieselbe Koordinatentransformation durchlaufen haben.

Eine geometrische Toleranz ist keine vergrößerte Touch-Trefferfläche. Die eine stabilisiert die numerische Klassifikation, die andere gehört zum Interaktionsdesign. Die Auswahlfläche darf nicht stillschweigend durch eine größere Toleranz erweitert werden.

Werden Koordinaten in logischen Einheiten der Zeichenfläche angegeben, muss auch die Toleranz in diesen Einheiten vorliegen. Ein fester Klickradius in Bildschirmkoordinaten muss über die inverse Transformation in Koordinaten der Zeichenfläche umgerechnet werden. Bei nicht gleichmäßiger Skalierung reicht es nicht, durch einen einzelnen Skalierungsfaktor zu teilen.

Den Rand über den Abstand zum Liniensegment erkennen

Zuerst auf Randnähe prüfen, danach die Enthaltenseinsprüfung des Pfads aufrufen. Die berechnete Projektionsposition muss auf den Bereich zwischen den beiden Segmentenden begrenzt werden. Andernfalls kann ein Punkt fälschlich als nahe am Segment gelten, obwohl er nur nahe an dessen unendlich verlängerter Geraden liegt. Erzeugen doppelte Eckpunkte eine Kante der Länge null, wird stattdessen der Abstand zu diesem Punkt berechnet.

Den folgenden Code als polygon-check.swift speichern. Die Beispieltoleranz beträgt 0.000001 Koordinateneinheiten. Sie ist nur für diese festen Testdaten gedacht und keine allgemeingültige Genauigkeitsvorgabe für Karten oder Zeichenflächen.

import Foundation
import CoreGraphics

enum Location: Equatable {
    case inside, outside, boundary
}

func distance(_ p: CGPoint, _ a: CGPoint, _ b: CGPoint) -> CGFloat {
    let dx = b.x - a.x
    let dy = b.y - a.y
    let lengthSquared = dx * dx + dy * dy
    if lengthSquared == 0 {
        return hypot(p.x - a.x, p.y - a.y)
    }
    let projection = ((p.x - a.x) * dx + (p.y - a.y) * dy)
        / lengthSquared
    let t = min(1, max(0, projection))
    return hypot(p.x - a.x - t * dx, p.y - a.y - t * dy)
}

func locate(
    _ point: CGPoint,
    rings: [[CGPoint]],
    rule: CGPathFillRule,
    epsilon: CGFloat
) -> Location {
    precondition(epsilon.isFinite && epsilon >= 0)
    precondition(point.x.isFinite && point.y.isFinite)
    precondition(!rings.isEmpty)

    let path = CGMutablePath()
    for ring in rings {
        precondition(ring.count >= 3)
        precondition(ring.allSatisfy { $0.x.isFinite && $0.y.isFinite })
        for i in ring.indices {
            let next = (i + 1) % ring.count
            if distance(point, ring[i], ring[next]) <= epsilon {
                return .boundary
            }
        }
        path.move(to: ring[0])
        for vertex in ring.dropFirst() {
            path.addLine(to: vertex)
        }
        path.closeSubpath()
    }
    return path.contains(point, using: rule) ? .inside : .outside
}

Diese Vorbedingungen eignen sich für Testdaten, die bereits eine Eingabevalidierung durchlaufen haben. Produktionscode sollte bei importierten Dateien behandelbare Validierungsfehler zurückgeben, statt den Prozess wegen ungültiger Koordinaten zu beenden. Auch die Größenordnung der Koordinaten muss begrenzt werden, damit beim Quadrieren kein Überlauf entsteht. Endliche Eingabewerte garantieren nicht, dass alle Zwischenergebnisse endlich bleiben.

Feste Testdaten mit Loch anlegen und Füllregeln vergleichen

Den folgenden Code anhängen. Außen- und Innenring haben dieselbe Umlaufrichtung. Deshalb füllt die Nicht-Null-Windungsregel auch den Innenring, während die Gerade-Ungerade-Regel dessen Fläche als Loch behandelt. Beide Ergebnisse entsprechen der jeweiligen Regel. Ein Screenshot allein belegt also keinen Fehler in der Geometriebibliothek.

let outer: [CGPoint] = [
    CGPoint(x: 0, y: 0), CGPoint(x: 10, y: 0),
    CGPoint(x: 10, y: 10), CGPoint(x: 0, y: 10)
]
let hole: [CGPoint] = [
    CGPoint(x: 3, y: 3), CGPoint(x: 7, y: 3),
    CGPoint(x: 7, y: 7), CGPoint(x: 3, y: 7)
]
let rings = [outer, hole]
let epsilon: CGFloat = 0.000001

func check(_ x: CGFloat, _ y: CGFloat, _ expected: Location) {
    precondition(
        locate(
            CGPoint(x: x, y: y),
            rings: rings,
            rule: .evenOdd,
            epsilon: epsilon
        ) == expected
    )
}

check(1, 1, .inside)
check(5, 5, .outside)
check(12, 5, .outside)
check(0, 5, .boundary)
check(3, 5, .boundary)
check(0, 0, .boundary)
check(-epsilon / 2, 5, .boundary)
check(-epsilon * 2, 5, .outside)

precondition(
    locate(
        CGPoint(x: 5, y: 5),
        rings: rings,
        rule: .winding,
        epsilon: epsilon
    ) == .inside
)

Im Terminal des Knotens ausführen:

xcrun --find swift
xcrun swift polygon-check.swift

Wird das Skript regulär mit Exitcode null beendet, sind diese Prüfungen erfolgreich durchgelaufen. Schlägt eine Prüfung fehl, ist der Exitcode ungleich null. Dieses Abnahmeskript darf nicht mit Optimierungseinstellungen ausgeführt werden, die die Assertions-Prüfungen deaktivieren.

Testfälle für Umlaufrichtung, Transformationen und degenerierte Geometrie ergänzen

Ein Rechteck deckt nur den einfachsten Pfadfall ab. Die Regressionstests sollten mindestens um konkave Polygone, horizontale Kanten, aufeinanderfolgende kollineare Eckpunkte sowie zwei nahe Punkte vor und hinter einem Eckpunkt ergänzt werden. Ein Punkt in einer Einbuchtung muss weiterhin als außen gelten. Er darf nicht allein deshalb ausgewählt werden, weil er innerhalb des umschließenden Rechtecks liegt.

Bei der Gerade-Ungerade-Regel muss die Klassifikation aller Testpunkte, die nicht auf dem Rand liegen, unverändert bleiben, wenn die Reihenfolge der Eckpunkte eines beliebigen Rings umgekehrt wird. Werden alle Eckpunkte und Prüfpunkte um denselben Vektor verschoben, muss ebenfalls das ursprüngliche Ergebnis herauskommen. Bei einer gleichmäßigen Vergrößerung der gesamten Geometrie muss die Toleranz mitskaliert werden. Sonst wird nicht mehr derselbe Randbereich verglichen.

Weniger als drei unterschiedliche Eckpunkte, ein vollständig kollinearer Ring, Selbstüberschneidungen und Löcher, die über den Außenring hinausragen, müssen bei der Eingabe gesondert abgelehnt oder in ihrem Verhalten ausdrücklich definiert werden. Die Prüfung der Eckpunktanzahl im Beispiel ist keine Prüfung auf ein gültiges Polygon. Auffällige Punkte dürfen nicht automatisch entfernt werden, um anschließend weiterzutesten. Dadurch könnte aus der Benutzereingabe eine andere Fläche entstehen.

Fehlerfälle reproduzierbar dokumentieren

Für jeden Fehlerfall die Reihenfolge der Eckpunkte aller Ringe, die Punktkoordinaten, die Füllregel, die Toleranz und die Transformationsmatrix speichern. Gleitkommawerte mit ausreichender Präzision sichern, nicht nur die gerundeten Koordinaten aus der Oberfläche. Durch Rundung können Punkte auf gegenüberliegenden Seiten des Randes denselben Wert erhalten.

Bei der Einbindung in iOS nur noch die Koordinatenkette prüfen

Sobald die reinen Geometrietests erfolgreich sind, dieselbe Prüffunktion wieder in die App einbinden. Schritt für Schritt kontrollieren, ob der Berührungspunkt aus Ansichtskoordinaten in Pfadkoordinaten umgerechnet wird, ob ein Scrollversatz versehentlich doppelt abgezogen wird und ob Zeichnen und Treffertest dieselbe Füllregel verwenden.

Wird vor und nach dem Zoomen derselbe logische Punkt ausgewählt, sollte das Ergebnis identisch sein. Falls nicht, zuerst die inverse Transformation prüfen, statt die Toleranz zu erhöhen. Auch die Strichbreite ist nicht mit der gefüllten Fläche gleichzusetzen. Soll die Kontur anklickbar sein, braucht sie eine eigene Trefferprüfung.

Am Ende bleiben zwei Testarten bestehen: Das reine Swift-Skript prüft den geometrischen Vertrag, wenige Oberflächentests prüfen die Koordinatenabbildung. Ersteres lässt sich bei jedem Commit auf einem Remote-Mac ausführen, Letztere überprüfen die tatsächliche Interaktionskette. So lässt sich bei einem Fehler zunächst klären, ob Daten, Regeln oder Ansichtstransformationen die Ursache sind, statt immer wieder über die Klickposition zu spekulieren.

Häufig gestellte Fragen