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

Parallelizable convex hull algorithm

Suppose you have a number of points in any number of dimensions, here I will just show 2.

First find the centroid, and the point farthest from that centroid Pc and construct the circle or n-dimensional sphere to it from the centroid... (Centroid shown in blue)

Now consider all the straight lines C to P(i) to B(i) from the Centroid to each Point and continuing on to a point on the Bounding region. Make a list of Pc and all points P(i) such that P(i) to B(i) is shorter than any other line from a different point P(j) to B(i).

This last step is the part that can be done in parallel, passing the entire set to as many processors as there are points and each one finding the solution for its given point. The points that are closest to their respective bounding point than any other point is to that bounding point are the hull. 

recursive formula for points on the unit circle of regular 2^n gon's

I found that formulas of this type:

describe the points on a circle corresponding to regular 2^(n+1)-gons where n is the number of square root symbols in the formulas and a,b,c... are each 1 or 2. For example a 16-gon

I haven't quite figured out where each point will be on the unit circle by the signs of the terms though. 

Fast parallelizable way to generate approximate points for a circle without using trig functions

This method starts with the four points of the bounding square...

Then replaces each point with two points (1- root 2/2) away from the sides... This is basically like truncating every corner to the right proportion...

Then iterates this process but using .25 instead of (1-root 2/2) that I found by experiment works very well. I suppose for perfect accuracy there is a recursive series involving root 2 but it approaches .25 so quickly that I didn't bother with it.

I found 4 iterations is enough for fairly large circles...

And in the end you have an list with all the points in counter clockwise order around the circle. 

Python source code (Using PIL for drawing)

import Image, ImageDraw

def plot(points, draw):

    for i in range(0, len(points)-1):

        draw.line([points[i], points[i+1]])

    draw.line([points[len(points)-1], points[0]])

def truncate(points):

    newpoints = []

    param = .29

    if len(points)>4:

        param = .25

    for i in range(0, len(points)-1):

        x1 = points[i+1][0]*(param)+points[i][0]*(1.0-param)

        y1 = points[i+1][1]*(param)+points[i][1]*(1.0-param)

        x2 = points[i+1][0]*(1.0-param)+points[i][0]*(param)

        y2 = points[i+1][1]*(1.0-param)+points[i][1]*(param)

        newpoints.append((x1, y1))

        newpoints.append((x2, y2))

    x1 = points[0][0]*(param)+points[len(points)-1][0]*(1.0-param)

    y1 = points[0][1]*(param)+points[len(points)-1][1]*(1.0-param)

    x2 = points[0][0]*(1.0-param)+points[len(points)-1][0]*(param)

    y2 = points[0][1]*(1.0-param)+points[len(points)-1][1]*(param)

    newpoints.append((x1, y1))

    newpoints.append((x2, y2))

    return newpoints

def main():

    points = [(100,100),(100,700),(700,700),(700,100)]

    

    for i in range(1, 5):

        p = Image.new("RGB", [800,800])

        draw = ImageDraw.Draw(p)

        points = truncate(points)  

        plot(points, draw)

        p.save("plots"+str(i)+".png")

main()

Using physics to try and find a Hamilton Circuit of a graph with odd number of vertices

Supposing you have a simply connected planar graph of even number of vertices with no loops edges labeled like so:

I found one can set one edge leading to one vertex, say A arbitrarily to 1, then write equations from Kirtchoff's laws for the graph...
http://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws

Kirchoff's laws say that the sum of the edges connected to each vertex is 0 and the sum around each face is 0.

It's kind of interesting that after you set one edge to 1, this will always be the right number of equations because of the graph equation V+F=E+2, and we have V+F equations to solve for E unknowns, The plus two in this formula is canceled by the fact that usually the formula counts the region outside of the graph as a face, but we don't use write an equation for that, and we've set one edge value to 1 so there is one less unknown edge.

Note there will be no solution if c,g,l, or m in this example is the edge chosen to be 1. But for any the other edges it will either be this solution or -1*all the values.

Then we can plot these solutions...

Now we can follow the flow of the graph around through every vertex exactly once by starting with A which is 1, then following the path from that vertex that is -1, and from there to the vertex following the path of 1, and so on alternating values. Since there are an odd number of vertices this works out evenly.

If you had an odd number of vertices to start out with, you could break the edge that you set as 1 into two edges one -1 and 1...

**Reasoning**
I don't know how to prove it, it just seems to work in every case. It makes sense to me electrically that if there is a nonzero flow around each face's edges, that some faces will combine and form one flow around the outside. I don't know how to prove that that will always go through every vertex though.