intersecting_lines.py

import sys
import matplotlib.pyplot as plt
import random

def in_range(a,b,c):
    '''
    Returns true if b <= a <= c
    '''
    return a >= b and a <= c

def is_equal(a,b):
    '''
    Returns True if floats are almost equal, or if both are None
    '''
    if a == None and b == None:
        return True
    elif a == None or b == None:
        return False
    epsilon = 1e-10
    return abs(a-b) < epsilon

def random_segments(x,y,n):
    '''
    Makes n random segments in x,y grid
    Prints them to file 'input.txt'
    '''
    with open('input.txt','w') as FH:
        for i in xrange(n):
            x1 = random.random()*x*2 - x
            x2 = random.random()*x*2 - x
            y1 = random.random()*y*2 - y
            y2 = random.random()*y*2 - y
            if x1 > x2:
                x2,x1 = x1,x2
            l = [i,x1,y1,x2,y2]
            l = map(str,l)
            l.append('\n')
            s = ' '.join(l)
            FH.write(s)
    return True

#filename = sys.argv[1]
filename = 'input.txt'
x_range = 10
y_range = 10
n_segments = 20
random_segments(x_range,y_range,n_segments)
pltdata = []
x_intersect = []
y_intersect = []

with open(filename) as FH:
    data = []
    for line in FH:
        l = line.rstrip().split()
        label = l.pop(0)
        l = map(float,l)
        pltdata.append((l[0],l[2]))
        pltdata.append((l[1],l[3]))
        pltdata.append('g')
        if l[0] > l[2]:
            print 'input error - x1 should always be less than x2'
        try:
            m = (l[1] - l[3]) / (l[0] - l[2])
            b = l[1] - m * l[0]
        except ZeroDivisionError:
            m = None
            b = None
        data.append((label,m,b,l[0],l[2],min(l[1],l[3]),max(l[1],l[3])))

    for counter,i in enumerate(data):
        label,m,b,x_min,x_max,y_min,y_max = i

        for j in range(counter+1,len(data)):
            label2,m2,b2,x_min2,x_max2,y_min2,y_max2 = data[j]
            intersect = ()

            if is_equal(m,m2) and not is_equal(b,b2):
                pass
            elif m == None and m2 == 0:
                # line1 vertical, line2 horizontal
                if in_range(x_min,x_min2,x_max2) and in_range(y_min2,y_min,y_max):
                    intersect = (x_min,y_min2)
            elif m == 0 and m2 == None:
                # line1 horizontal, line2 vertical
                if in_range(x_min2,x_min,x_max) and in_range(y_min,y_min2,y_max2):
                    intersect = (x_min2,y_min)
            elif m == None and m2 == None and is_equal(x_min,x_min2):
                # two vertical segments on same line
                if is_equal(y_max,y_min2):
                    intersect = (x_min,y_max)
                elif is_equal(y_min,y_max2):
                    intersect = (x_min,y_min)
                elif in_range(y_min,y_min2,y_max2) and in_range(y_max,y_min2,y_max2):
                    # first line subset of second line
                    intersect = ((x_min,y_min),(x_max,y_max))
                elif in_range(y_min2,y_min,y_max) and in_range(y_max2,y_min,y_max):
                    # second line subset of first line
                    intersect = ((x_min2,y_min2),(x_max2,y_max2))
                elif in_range(y_max,y_min2,y_max2):
                    # second line overlaps top of first line
                    intersect = ((x_min,y_min2),(x_min,y_max))
                elif in_range(y_min,y_min2,y_max2):
                    # second line overlaps bottom of first line
                    intersect = ((x_min,y_min),(x_min,y_max2))
            elif is_equal(m,m2) and is_equal(b,b2):
                # same line, see if they intersect at a single point
                if is_equal(x_min,x_max2):
                    intersect = (x_min,m*x_min+b)
                elif is_equal(x_max,x_min2):
                    intersect = (x_max,m*x_max+b)
                elif in_range(x_min,x_min2,x_max2) and in_range(x_max,x_min2,x_max2):
                    # first line subset of second line
                    intersect = ((x_min,m*x_min+b),(x_max,m*x_max+b))
                elif in_range(x_min2,x_min,x_max) and in_range(x_max2,x_min,x_max):
                    # second line subset of first line
                    intersect = ((x_min2,m2*x_min2+b2),(x_max2,m2*x_max2+b2))
                elif in_range(x_min2,x_min,x_max):
                    # second line overlaps right side of first line
                    intersect = ((x_min2,m2*x_min2+b2),(x_max,m*x_max+b))
                elif in_range(x_max2,x_min,x_max):
                    # second line overlaps left side of first line
                    intersect = ((x_min,m*x_min+b),(x_max2,m2*x_max2+b))
            elif m == None:
                # first line is vertical, second is not vert or hor
                if in_range(x_min,x_min2,x_max2) and in_range(m2*x_min+b2,y_min2,y_max2):
                    intersect = (x_min,m2*x_min+b2)
            elif m2 == None:
                # second line is vertical, first is not vert or hor
                if in_range(x_min2,x_min,x_max) and in_range(m*x_min2+b,y_min,y_max):
                    intersect = (x_min2,m*x_min2+b)
            else:
                try:
                    x = (b2 - b) / (m - m2)
                except ZeroDivisionError:
                    print m,m2,i,data[j]
                if in_range(x,x_min,x_max) and in_range(x,x_min2,x_max2):
                    intersect = (x,m*x+b)
            if intersect:
                if len(intersect) == 2:
                    x_intersect.append(intersect[0])
                    y_intersect.append(intersect[1])

plt.axis([-x_range,x_range,-y_range,y_range])
plt.plot(*pltdata)
plt.plot([x_intersect],[y_intersect],'ro')