Line Number | Syntax Highlight | Download Raw

from math import *
from sets import *

def getintersect(p1,p2,p3,p4):

    #given two line segments, determine if they intersect.
    #returns point if they do, None if they don't

    x1,y1 = p1
    x2,y2 = p2
    x3,y3 = p3
    x4,y4 = p4

    x12 = x1 - x2
    y12 = y1 - y2
    x34 = x3 - x4
    y34 = y3 - y4
                
    c = x12 * y34 - y12 * x34

    if (abs(c) >= 0.0001): #lines not parallel?
        a = x1 * y2 - y1 * x2
        b = x3 * y4 - y3 * x4

        x = (a * x34 - b * x12) / c
        y = (a * y34 - b * y12) / c

        #check if intersecting point in bounds
        
        if (x <= (max([x1,x2]) + 0.0001) and x >= (min([x1,x2]) - 0.0001) and
            x <= (max([x3,x4]) + 0.0001) and x >= (min([x3,x4]) - 0.0001) and
            y <= (max([y1,y2]) + 0.0001) and y >= (min([y1,y2]) - 0.0001) and
            y <= (max([y3,y4]) + 0.0001) and y >= (min([y3,y4]) - 0.0001)):
            return [x,y]
        else:
            return None
    else:
        return None
                    
for number_of_points in range(3,7):

    points = list()

    #first we create the outside points

    for i in range(number_of_points):
        angle = ((2 * pi) / number_of_points) * i
        points.append([sin(angle),cos(angle)])

    #now we create the initial lines

    lines = list()

    for i in range(number_of_points):
        for j in range(i + 1,number_of_points):
            lines.append([i,j])

    #Now we repeatedly scan the lines to see if any intersect

    scan_again = True

    while scan_again:

        newlines = list()
        scan_again = False

        for line1 in lines:
            for line2 in lines:
                if line1[0] not in line2 and line1[1] not in line2:

                    intersect = getintersect(points[line1[0]],points[line1[1]],points[line2[0]],points[line2[1]])

                    if intersect:
                        point_number = None
                        for i in range(len(points)):
                            point = points[i]
                            if abs(point[0]-intersect[0]) < .000001 and abs(point[1]-intersect[1]) < .000001:
                                point_number = i
                        if point_number == None:
                            point_number = len(points)
                            points.append(intersect)

                        for newline in [[line1[0],point_number],
                                        [line1[1],point_number],
                                        [line2[0],point_number],
                                        [line2[1],point_number]]:
                            if newline[0] != newline[1]:
                                newline.sort()
                                newlines.append(newline)

        for line in newlines:
            if line not in lines:
                lines.append(line)
                scan_again = True

    #Now we look st the points and try to find triangles

    triangles = list()

    for line1 in lines:
        for line2 in lines:
            triangle = set(set(line1).union(line2))
            if len(triangle) == 3: #one point in common?
                if getintersect(points[line1[0]],points[line1[1]],points[line2[0]],points[line2[1]]): #not parelell?
                    for line3 in lines:
                        if line3 not in [line1,line2] and len(triangle.union(line3)) == 3: #found a third line?
                            tri = list(triangle)
                            tri.sort()
                            if tri not in triangles: #new triangle?
                                triangles.append(tri)
                
    print number_of_points,len(triangles)

Encryption / Decryption Key