To avoid being an XY problem, I will talk about some background first.
I am writing the game Planarity as an iOS app. The game starts off with a graph and the player has to move the vertices of the graph so that none of the edges intersect another edge.
I want to color code the edges so that edges that intersect another edge will be in red and those that does not intersect other edges will be in green.
I used a custom UIView called GraphView to display the graph. The GraphView contains subviews of type NodeView, which are used to represent the vertices. In the draw(_:) method of GraphView, I draw the edges between the vertices:
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()
}
}
I set up a CADisplayLink to call setNeedsDisplay every frame so that the color of the connections will respond instantly to a user's dragging of the vertices.
When I increase the number of vertices and edges of the graph, the app becomes very laggy. I suppose this is because draw can't return in 1/60 of second (one frame).
I used Instruments to find out that indeed draw is doing a lot of work:
I think I need to make checkIntersection run more quickly.
This is 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
}
As you can see, I knew that this would take a lot of time when I was writing this algorithm, so I already tried to check as few connections as possible. But since this is so slow, I wonder if I can check even fewer connections. It's ok if this is already the fewest number of checks.
How can I check the fewest connections possible?
EDIT:
Martin R suggested that I should use a nested for loop:
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
}
From Instruments, I can see that the "Weight" of the checkIntersections call is about 50%, which is roughly the same as before, when I used sets.
As for the intersects(with:) method, I adapted a solution from another SO answer (that I now can't find), it looks like this:
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
}
The original answer finds the intersection point of two line segments, not just checking whether they intersect. Maybe just checking for intersection can be more easily done than this?
