## 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.
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()