analytics

Monday, December 29, 2014

Shortnet definition and source code

I'm defining the Shortnet of a group of points to be the subset S of the collection of every possible line connecting pairs of points C, such that every line crossing a line shorter than itself has been removed.
Example: You have your points...
 Then you create all the lines connecting every point pairwise...
Then you remove any line that crosses a line shorter than itself...
Here is one with 50 points:

There will never be any lines that cross left as one or the other of each pair of lines that cross is removed.
Source Code using PIL drawing library and Python:
import random
import Image, ImageDraw
def cross(a1, b1, c1, d1, a2, b2, c2, d2):
    if (-a2*b1+a2*d1+c2*b1-c2*d1+b2*a1-b2*c1-d2*a1+d2*c1)== 0:
        return False
    if (-a2*b1+a2*d1+c2*b1-c2*d1+b2*a1-b2*c1-d2*a1+d2*c1) == 0:
        return False

    s = 1.0*(a1*d1-d2*a1+d2*c1-c1*b1+c2*b1-c2*d1)/(-a2*b1+a2*d1+c2*b1-c2*d1+b2*a1-b2*c1-d2*a1+d2*c1)
    t = 1.0*(-b2*c1+a2*d1+b2*c2-a2*d2+d2*c1-c2*d1)/(-a2*b1+a2*d1+c2*b1-c2*d1+b2*a1-b2*c1-d2*a1+d2*c1)
    if s > 0 and s < 1.0:
        if t > 0 and t < 1.0:
            return True
    return False
def gen(num):
    points = []
    for i in range(0, num):
        point = [random.randint(100, 700), random.randint(100, 700)]
        points.append(point)
    return points
def shorter(a1, b1, c1, d1, a2, b2, c2, d2):
    d1 = ((c1 - a1)**2.0 + (d1 - b1)**2.0)**.5
    d2 = ((c2 - a2)**2.0 + (d2 - b2)**2.0)**.5
    if d1 <= d2:
        return True
    else:
        return False
def makelines(points):
    lines = []
    for i in range(0, len(points)-1):
        for j in range(i+1, len(points)):
            lines.append([points[i][0], points[i][1], points[j][0], points[j][1]])
    return lines
def picklines(lines):
    marked = []
    for i in range(0, len(lines)):
        marked.append(True)
    for i in range(0, len(lines)-1):
        for j in range(i+1, len(lines)):
            if cross(lines[i][0], lines[i][1], lines[i][2], lines[i][3], lines[j][0], lines[j][1], lines[j][2], lines[j][3]):
                if shorter(lines[i][0], lines[i][1], lines[i][2], lines[i][3], lines[j][0], lines[j][1], lines[j][2], lines[j][3]):
                    marked[j] = False
                else:
                    marked[i] = False
    for i in range(0, len(lines)):
        if marked[i] == False:
            lines[i] = False
    return lines
def drawlines(d, lines):
    for line in lines:
        if line != False:
            d.line(line)
def drawpoints(d, points):
    for point in points:
        d.ellipse([point[0]-10, point[1]-10, point[0]+10, point[1]+10], fill=(255,0,0))
def main():
    points = gen(10)
    plot = Image.new("RGB", [800, 800])
    d = ImageDraw.Draw(plot)
    drawpoints(d, points)
    plot.save("dots.png")
    lines = makelines(points)
    drawlines(d, lines)
    plot.save("all.png")
    plot = Image.new("RGB", [800, 800])
    d = ImageDraw.Draw(plot)
    drawpoints(d, points)
    lines = picklines(lines)
    drawlines(d, lines)
    plot.save("shortnet.png")
main()

1 comment: