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:

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

## No comments:

## Post a Comment