Полигоны iOS: проверяем границы, отверстия и заливку

На карте область выглядит так, будто в ней вырезано отверстие, но щелчок внутри него всё равно приводит к выделению. Точка на холсте лежит точно на отрезке, однако при разных масштабах результат проверки меняется. Причина таких сбоев обычно не в неточности щелчков через удалённый рабочий стол, а в том, что отрисовка, преобразование координат и геометрическая проверка опираются на разные соглашения. Сначала можно запустить регрессионный скрипт на чистом Swift на облачном Mac, чтобы отделить геометрические ошибки от проблем интерфейса.

Сначала определите три результата и единицы координат

Не сводите результат сразу к булеву значению. Предусмотрите три состояния: внутри, снаружи и на границе, — а затем отдельно решите, должна ли граница считаться выбранной. Редактор карт может разрешать выбор края, а запретная зона — исключать и саму границу. Использовать для обоих случаев одно булево правило без явного описания нельзя.

В этой статье рассматриваются простые замкнутые контуры из отрезков в одной плоской системе координат; внутри внешнего контура допускаются отверстия. Прямое проецирование широты и долготы, исправление самопересечений и расстояния до кривых здесь не рассматриваются. Проверяемая точка и вершины должны пройти одно и то же преобразование координат.

Геометрический допуск — не зона касания. Первый нужен для устойчивой численной классификации, вторая относится к проектированию взаимодействия. Не увеличивайте область выбора незаметно для пользователя за счёт расширения допуска.

Если координаты заданы в логических единицах холста, допуск тоже должен выражаться в этих единицах. Фиксированный радиус щелчка на экране нужно переводить в координаты холста обратным преобразованием. При неравномерном масштабировании нельзя просто разделить его на один коэффициент масштаба.

Определяйте границу по расстоянию от точки до отрезка

Сначала проверяйте близость к границе, а уже затем — принадлежность области пути. При вычислении проекции необходимо ограничить её положение концами отрезка, иначе точка может ошибочно считаться близкой к бесконечному продолжению прямой. Если повторяющиеся вершины образуют ребро нулевой длины, задача сводится к расстоянию до точки.

Сохраните следующий код в polygon-check.swift. В примере используется допуск 0.000001 единицы координат. Он подобран только для этих фиксированных тестовых данных и не задаёт универсальную точность для любых карт или холстов.

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
}

Эти предусловия рассчитаны на тестовые данные, уже прошедшие входную проверку. В рабочем коде при импорте файлов следует возвращать обрабатываемую ошибку валидации, а не завершать процесс из-за некорректных координат. Нужно также ограничить величину координат, чтобы избежать переполнения при возведении в квадрат: конечные входные значения не гарантируют конечность всех промежуточных результатов.

Зафиксируйте тест с отверстием и сравните правила заливки

Добавьте следующий код в тот же файл. Внешний и внутренний контуры обходятся в одном направлении, поэтому правило ненулевого числа обходов заполняет и внутренний контур. Правило чётности, напротив, считает область внутри него отверстием. Оба результата соответствуют своим правилам: одного снимка экрана недостаточно, чтобы объявить геометрическую библиотеку неисправной.

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
)

В терминале узла выполните:

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

Нормальное завершение с нулевым кодом выхода означает, что все эти проверки пройдены. Нарушение любого проверяемого условия приводит к ненулевому коду выхода. Не запускайте этот приёмочный скрипт с оптимизацией, отключающей проверки утверждений.

Добавьте проверки направления, преобразований и вырожденных случаев

Прямоугольники проверяют лишь самые простые контуры. В регрессионный набор стоит добавить как минимум вогнутый полигон, горизонтальные рёбра, последовательные коллинеарные вершины, а также две близкие к вершине точки — до и после неё. Точка в выемке должна оставаться снаружи: одного попадания в ограничивающий прямоугольник недостаточно для выбора.

При правиле чётности изменение порядка вершин любого контура на обратный не должно менять классификацию всех точек вне границы. Перенос всех вершин и тестовых точек также должен сохранять исходный результат. При равномерном увеличении всей геометрии допуск нужно масштабировать вместе с ней, иначе сравнение будет выполняться уже для другой приграничной полосы.

Контуры с менее чем тремя различными вершинами, полностью коллинеарные контуры, самопересечения и отверстия, выходящие за внешний контур, необходимо либо отдельно отклонять на входе, либо явно определять, как с ними работать. Проверка количества вершин в примере не равнозначна проверке корректности полигона. Не удаляйте проблемные точки автоматически, чтобы затем продолжить тест: так можно превратить пользовательские данные в совершенно другую область.

Сохраняйте данные для воспроизведения сбоя

В записи о сбое сохраняйте порядок вершин контуров, координаты точки, правило заливки, допуск и матрицу преобразования. Записывайте числа с плавающей точкой с достаточной точностью, а не только округлённые координаты из интерфейса: после округления точки по разные стороны границы могут получить одно и то же значение.

При подключении к интерфейсу iOS проверяйте только цепочку координат

Когда чисто геометрические тесты пройдены, подключите ту же функцию проверки к приложению. Последовательно проверьте, преобразуется ли точка касания из координат представления в координаты пути, не вычитается ли смещение прокрутки дважды и используется ли одно правило заливки для отрисовки пути и проверки попадания.

Выбор одной и той же логической точки до и после масштабирования должен давать одинаковый результат. Если это не так, сначала проверьте обратное преобразование, а не увеличивайте допуск. Толщина обводки тоже не определяет область заливки: если обводка должна реагировать на нажатия, для неё нужна отдельная логика проверки попадания.

В итоге сохраните два вида тестов: скрипт на чистом Swift проверяет геометрические соглашения, а небольшой набор интерфейсных тестов — отображение координат. Первый удобно запускать на удалённом Mac при каждом коммите, второй проверяет реальную цепочку взаимодействия. Тогда при сбое можно сначала установить, где проблема — в данных, правилах или преобразованиях представления, — вместо того чтобы снова и снова гадать, куда пришёлся щелчок.

Часто задаваемые вопросы