Output.txt

Intersecting Lines:
A B
A C
A E
A G
F G

Pairwise intersecting lines in 2D.swift

// [5/23/2014] Challenge #163 [Hard] Intersecting Lines in 2-D space : dailyprogrammer http://www.reddit.com/r/dailyprogrammer/comments/26b42x/5232014_challenge_163_hard_intersecting_lines_in/

import Cocoa

struct Line {
    let name: String
    let x1, x2, y1, y2: Double
    let m: Double
}

class Intersection {
    var lines = [Line]()
    let inputData: String
    
    init (data: String) {
        inputData = data
        determinePairwiseIntersections()
    }
    
    func processInputData() {
        let rows = inputData.componentsSeparatedByCharactersInSet(NSCharacterSet.newlineCharacterSet())
        for row in rows {
            let column = row.componentsSeparatedByCharactersInSet(NSCharacterSet.whitespaceCharacterSet())
            if column.count == 5 {
                let line = Line(
                    name: column[0],
                    x1: NSString(string: column[1]).doubleValue,
                    x2: NSString(string: column[3]).doubleValue,
                    y1: NSString(string: column[2]).doubleValue,
                    y2: NSString(string: column[4]).doubleValue,
                    m: 0.0)
                lines += [line]
            }
        }
    }
    
    func determineSlopeOfLines() {
        var processedLines = [Line]()
        for line in lines {
            let m = (line.y2 - line.y1) / (line.x2 - line.x1)
            let line = Line(name: line.name, x1: line.x1, x2: line.x2, y1: line.y1, y2: line.y2, m: m)
            processedLines += [line]
        }
        
        lines = processedLines
    }
    
    func domainOfLines(l1: Line, l2: Line) -> (Double, Double) {
        let xMin = max(l1.x1, l2.x1)
        let xMax = min(l1.x2, l2.x2)
        
        return(xMin, xMax)
    }
    
    func isWithinDomainOfLines(x: Double, l1: Line, l2: Line) -> Bool {
        let domain = domainOfLines(l1, l2: l2)
        if x >= domain.0 && x <= domain.1 {
            return true
        } else {
            return false
        }
    }
    
    func determinePairwiseIntersections() {
        processInputData()
        determineSlopeOfLines()
        
        typealias Lines = (String, String)
        var intersectingLines = [Lines]()
        var x = 0.0
        var y = 0.0
        
        for i in 0 ..< lines.count {
            let line1 = lines[i]
            for j in i+1 ..< lines.count {
                let line2 = lines[j]
                if abs(line1.m) != abs(line2.m) { // eliminate parallels
                    
                    // compute intersection coordinates
                    if line1.m.isInfinite { // line 1 is vertical
                        x = line1.x1
                        y = line2.m * (x - line2.x1) + line2.y1
                    } else if line2.m.isInfinite { // line 2 is vertical
                        x = line2.x1
                        y = line1.m * (x - line1.x1) + line1.y1
                    } else {
                        x = ((line1.m * line1.x1) - (line2.m * line2.x1) + line2.y1 - line1.y1) / (line1.m - line2.m)
                        y = line1.m * (x - line1.x1) + line1.y1
                    }
                    
                    // decide if point of intersection is within domain
                    if isWithinDomainOfLines(x, l1: line1, l2: line2) {
                        intersectingLines += [Lines(line1.name, line2.name)]
                    }
                }
            }
        }
        
        if intersectingLines.count == 0{
            println("All the lines are parallel.")
        } else {
            println("Intersecting Lines:")
            for pair in intersectingLines {
                println("\(pair.0) \(pair.1)")
            }
        }
    }
}

let lines = "A -2.5 .5 3.5 .5\nB -2.23 99.99 -2.10 -56.23\nC -1.23 99.99 -1.10 -56.23\nD 100.1 1000.34 2000.23 2100.23\nE 1.5 -1 1.5 1.0\nF 2.0 2.0 3.0 2.0\nG 2.5 .5 2.5 2.0"
Intersection(data: lines)