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

Question

Чтобы избежать проблем с XY, сначала я расскажу о некотором фоне.

Я пишу игру Planarity как приложение для iOS. Игра начинается с графика, и игрок должен переместить вершины графика так, чтобы ни одно из ребер не пересекало другое ребро.

Я хочу закрасить края так, чтобы края, которые пересекают другое ребро, были красного цвета, а те, которые не пересекают другие ребра, были зеленого цвета.

Я использовал пользовательский UIView с именем GraphView для отображения графика. GraphView содержит подпредставления типа NodeView, которые используются для представления вершин. В draw(_:) методе GraphView я рисую ребра между вершинами:

override func draw(_ rect: CGRect) {
    // "graph" is the model. It stores where all the vertices are and which vertex is connected to which
    if graph == nil { return }

    // intersectionDict is of type [Connection: Bool]. It stores whether a Connection intersects with another connection
    // value is "true" for a connection that should be red
    // and "false" for a connection that should be green
    let intersectionDict = graph.checkIntersections()

    for connection in graph.connections {
        let path = UIBezierPath()
        path.lineWidth = 2
        path.move(to: CGPoint(x: connection.node1.x, y: connection.node1.y))
        path.addLine(to: CGPoint(x: connection.node2.x, y: connection.node2.y))
        // assume this is always true, because it is irrelevant
        if UserSettings.colorCodeConnections {
            if intersectionDict[connection] ?? false {
                UIColor.red.setStroke()
            } else {
                UIColor.green.darker().setStroke()
            }
        } else {
            UIColor.black.setStroke()
        }
        path.stroke()
    }
}

Я настроил CADisplayLink для вызова setNeedsDisplay каждого кадра, чтобы цвет соединений мгновенно реагировал на перетаскивание пользователем вершин.

Когда я увеличиваю количество вершин и ребер графа, приложение становится очень медленным. Я полагаю, это потому, что draw не может вернуться за 1/60 секунды (один кадр).

Я использовал Инструменты, чтобы выяснить, что действительно draw выполняет большую работу:

Я думаю, мне нужно заставить checkIntersection работать быстрее.

Это checkIntersections:

func checkIntersections() -> [Connection: Bool] {
    var dict = [Connection: Bool]()
    var tempConnections = connections // tempConnections is a Set<Connection>
    while true {
        // find the next connection to check
        // we subtract the dictionary's keys here because we don't need to check them (they are already checked)
        if let connectionToCheck = tempConnections.subtracting(dict.keys).first {
            // get all the connections that connectionToCheck intersects with
            let intersections = Set(tempConnections.filter { connectionToCheck.intersects(with: $0) })
            if intersections.isEmpty {
                dict[connectionToCheck] = false
                tempConnections.remove(connectionToCheck)
            } else {
                dict[connectionToCheck] = true
                for connection in intersections {
                    dict[connection] = true
                }
            }
        } else {
            break
        }
    }
    return dict
}

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

Как я могу проверить наименьшее количество возможных соединений?

EDIT:

Мартин Р предложил мне использовать вложенный цикл for:

func checkIntersections() -> [Connection: Bool] {
    var dict = [Connection: Bool]()

    let arrConnections = Array(connections)
    for i in 0..<arrConnections.count {
        for j in (i+1)..<arrConnections.count {
            if arrConnections[i].intersects(with: arrConnections[j]) {
                dict[arrConnections[i]] = true
                dict[arrConnections[j]] = true
            }
        }
    }
    return dict
}

Из Instruments я вижу, что «вес» вызова checkIntersections составляет около 50%, что примерно так же, как и раньше, когда я использовал наборы.

Что касается метода intersects(with:), я адаптировал решение из другого SO-ответа (которого я сейчас не могу найти), это выглядит так:

func intersects(with connection: Connection) -> Bool {
    let p1 = self.node1
    let p2 = self.node2
    let p3 = connection.node1
    let p4 = connection.node2
    let d = (p2.x - p1.x)*(p4.y - p3.y) - (p2.y - p1.y)*(p4.x - p3.x)
    if d == 0 {
        return false
    }

    // if a line starts at where another ends, they don't intersect
    // samePointAs just checks whether the two nodes have the same coordinates
    if p2.samePointAs(p3) || p4.samePointAs(p1) || p2.samePointAs(p4) || p1.samePointAs(p3){
        return false
    }

    let u = ((p3.x - p1.x)*(p4.y - p3.y) - (p3.y - p1.y)*(p4.x - p3.x))/d
    let v = ((p3.x - p1.x)*(p2.y - p1.y) - (p3.y - p1.y)*(p2.x - p1.x))/d
    if !(0.0...1.0).contains(u) || !(0.0...1.0).contains(v) {
        return false
    }
    return true
}

Исходный ответ находит точку пересечения двух отрезков, а не просто проверяет, пересекаются ли они. Может быть, просто проверить перекресток проще, чем этот?