Regular Polyhedra formula

I found this formula that you put in S for how many sided polygons and P for how many meet at a vertex and gives the number of Edges, Faces, and Vertices it must have...

**Proof
There are 3 formulas describing such polyhedra...
Euler's formula for polyhedra:
F = E-V+2
Another one saying that the number of Faces times the number of sides on each face equals twice the number of edges, because every edge connects two faces.
F*S = 2*E
And one more saying that the number of vertices times the number of edges connecting to it equals twice the number of edges, because every edge connects two vertices.
V*P = 2*E

These solve in terms of S and P as the formula for E, F, and V given.

For example if we want triangles so S=3 meeting 5 at each vertex:

It says there must be 30 edges, 20 faces and 12 vertices, which is the regular icosahedron. 

I find it interesting that the assumptions are quite general, Euler's formula for polyhedra can be proven even over topologies with holes in them like a donut, and the other two would certainly still be true. But it says you could never have say a 1000 vertex donut polyhedra where the whole surface is divided into triangles and 5 meet at every vertex, because the only solution is for there to be 12 vertices for that configuration of S and P.

**Note**
I was thinking about how a toroid can be broken into almost any number of 4 sided figures with 4 edges meeting at each vertex.. there is a caveat that these formulas end up dividing by 0 for S=4 and P=4...

easy way to find the volume of a polyhedron

An easy formula for finding the volume of a polyhedron when you know the coordinates of the vertices...

where the bars are absolute value.

The sums in this formula are over all of the faces, Maxheight is the maximum height for any of the vertices, MinHeight the minimum value of the height of all vertices. F(i)Aveheight is the average of the height coordinates of the ith face and F(i)Area is the area of a face polygon after all the height coordinates are replaced with 0.

To see why it works first think of the 2 dimensional version of this formula:

We start finding the area B underneath each face down to the minimum value the height coordinate takes on. The red area would only be counted once as it is below the faces along the top and above any of the faces along the bottom, but we count the area underneath the faces along the bottom as well so the purple area ends up being counted twice. The area of each face is calculated as the average value of the height of the face, times the length when the height coordinates are replaced by 0 for the two vertices in the 2d case this is just the width.  

Now we do almost the same thing but find the area T above the faces of the polygons up to the maximum value of the height coordinate (Note that this area will be negative). 

Now we can solve that the total area of the polygon will be abs(T-B)/2 because it is the symmetric difference of the two overlapping regions.  It's hard to do a direct proof because of the absolute values but one way to reason about it is if you have a cube so that T and B are each the whole volume of the cube, but B negative, then it would be abs(T-B)/2, but that always has to be the solution because it is always the same system of linear equations relating T,B, the red area and the total area. 

So this same sort of thing is presented above for 3 dimensions, but it is average values of faces times the area of face polygons when the heights are replaced by 0 to make shafts of volume, but otherwise the same concept.  

  

Finding a path through every point of a graph

For a simple connected graph with coordinates I believe this algorithm finds a path visiting every point once if it is possible.

The first step is to go to a point on the graph X, and find two points out of those that X is connected to, P and N, that maximizes this formula:

This will ensure that the vectors from P to X and from X to N are going around clockwise, and that the angle between them taken counterclockwise is maximized.
For the example above, this will make W=P and N=Y.

So we do this for every point on the graph:

And then eliminate any edges such that every point after removal is still connected to two other points. If this isn't possible than, you either already have the solution or it isn't possible to visit every point once and return to the original point.

**Idea for proof**
The formula being maximized is individual terms from the shoelace formula for polygons, so when each term is maximized the formula as a whole is maximized, and that must mean you have a closed polygon ordered clockwise which will visit every point once and return to the start.
 http://en.wikipedia.org/wiki/Shoelace_formula

Generating pythagorean triples from the positive rationals [0..1]

consider this formula:

For rationals [0..1] these (x,y) pairs are on the unit circle in the first quadrant, as proven here: http://mathnow.wordpress.com/2009/11/06/a-rational-parameterization-of-the-unit-circle/

Another way to write the above formula since m is a rational between [0..1] is to substitute in p/q as that rational to get...

For any rational number [0..1] a pythagorean triple can be generated as follows...

Put the rational number in for m (or as p/q in the two other formulas), here I'm using as an example 7/12...

A, B of the triple appear in the numerators of the simplified fractions and C is the denominator common to both...

*Simple direct proof

The above shows that x,y lie on the unit circle as the sum of the squares equals 1. In the first link it shows that p/q [0..1] covers the top right quarter of the circle.

And the above shows that the numerator of x squared plus the numerator of y squared equals the common denominator squared.
This proof really admits a great deal more generality than just for pythagorean triples, considering it doesn't even require p,q be rational numbers. One could have p=pi and q = -sqr(2)/2.

*Alternate more explanatory Proof

Consider some right triangle with whole number hypotenuse and legs such that it is contained in the first quadrant. This has an a,b,c in the usual way for right triangles. We can divide a and b by the distance to that point (a,b) to normalize the vector to that point to somewhere on the circle. Because it is a pythagorean triple triangle, we will have to divide by c to normalize it (because (a^2+b^2)^1/2=c. The formula I gave after substituting in p/q  once simplified can be thought of as such a  normalization because it is two rational numbers with the same denominator and is on the unit circle, hence we clear the common denominator from x,y to get a,b and that denominator becomes c. 

* Note

I just find that interesting that it puts an ordering on primitive pythagorean triples.

I guess it's also interesting that because rational points are dense on the unit circle, if you draw a line through somewhere on the circle from the origin you will pass arbitrarily close to an infnite number of pythagorean triple points, I don't know enough topology to know what to conclude from that.  

map cardinal traversal rectification

This program takes a map of a certain number of different colors like:

And produces this:

This map preserves the order that you will reach different colored areas (including white) of the map by traveling purely in North, East, South or West increments. It's also the simplest such map.
The way it works is it takes a row of pixels making a list of the colors that it reaches along that row. It does this for each row and takes all the lists and removes any duplicate lists that are adjacent in this list of lists. It also does this for every column. This gives you a grid of colors.

**Python Source Code**
import Image
def order(rorc, which, map):
    o = []
    if rorc == 0:
        nlastcolor = (255,255,255)
        lastcolor = map.getpixel((0,which))
        o.append(lastcolor)
        for i in range(1, map.size[0]):
            thiscolor = map.getpixel((i, which))
            if thiscolor != lastcolor:
                o.append(thiscolor)
                lastcolor = thiscolor
    if rorc == 1:
        nlastcolor = (255,255,255)
        lastcolor = map.getpixel((which,0))
        o.append(lastcolor)
        for i in range(1, map.size[1]):
            thiscolor = map.getpixel((which, i))
            if thiscolor != lastcolor:
                o.append(thiscolor)
                lastcolor = thiscolor
    return o

def markchange(rorc, map):
    mark = [0]
    if rorc==0:
        for i in range(1, map.size[1]):
            o = order(0, i, map)
            p = order(0, i-1, map)
            if p!=o:
                mark.append(i)
    if rorc==1:
        for i in range(1, map.size[0]):
            o = order(1, i, map)
            p = order(1, i-1, map)
            if p!=o:
                mark.append(i)
    return mark
def makemap(map, mapout, r, c):
    for i in range(1, len(c)):
        for j in range(1, len(r)):
            coord = ((c[i-1]*1.0+c[i])/2, (r[j-1]*1.0+r[j])/2.0)
            color = map.getpixel(coord)
            for x in range((i-1)*20, (i+1)*20):
                for y in range((j-1)*20, (j+1)*20):
                    mapout.putpixel((x,y), color)
def main():
    map = Image.open("map.png")
    r= markchange(0, map)
    c= markchange(1, map)
    mapout = Image.new("RGB", (21*len(c), 21*len(r)), (255,255,255))
    makemap(map, mapout, r, c)
    mapout.save("m.png")
main()

"wiggling" a polygon keeping constant area

Ok suppose you have a polygon:

I noticed you can "wiggle" any of the points to 4 possible new points so that the distance to the new point from the original point is a certain number delta and the overall area of the polygon remains unchanged. Below the point (5.11) and the 4 points it can wiggle to with delta = .1

A way to figure the polygon's area is the shoelace formula:

I define the wiggle of a polygon as solving an equation like this:

where xp,yp then x,y then xn,yn are 3 consecutive points on the polygon listed clockwise with wrap around and delta is how far the wiggled point will end up being from the original point. The structure of the formula for the overall area, interestingly, is such that we can just consider the part of the sum where the variables x or y occur, which is only 4 terms depending only on the point before or after x,y as you go around clockwise no matter the polygon, and keep that the same, and the rest stays the same so the total is the same.
For example, the polygon above "wiggling" the point (5,11) with delta of .1

The interpretation is that the point (5,11) can have it's x coordinate moved + or - .288 and the y coordinate moved + or - .128 and the polygon as a whole will still have the same area.
So I thought it would be interesting to make an animation of random points on this starting polygon being wiggled 2700 wiggles altogether...

I think with many more points than 5 making a sort of blob it might look a lot like a drop of water sizzling on a frying pan, as it moves all around but maintaining area.
** Python source code (Warning! Creates 2700 .png images for making a movie with)
import random
import Image, ImageDraw

def wigglepoly(points, delta):
    i = random.randint(0, len(points)-1)
    x,y = points[i]
    if i > 0:
        xp, yp = points[i-1]
    else:
        xp, yp = points[len(points)-1]
    if i < len(points)-1:
        xn, yn = points[i+1]
    else:
        xn, yn = points[0]
    
    rad = (xp**2.0-2*xp*xn+xn**2+yn**2-2*yn*yp+yp**2)*delta
    b = ((rad)**.5*(yn-yp))/(xp**2.0-2*xp*xn+xn**2+yn**2-2*yn*yp+yp**2)
    a = (delta-b**2.0)**.5
    sign = random.randint(0, 1)
    if sign == 0:
        signa = -1
    else:
        signa = 1
    sign = random.randint(0, 1)
    if sign == 0:
        signb = -1
    else:
        signb = 1
    points2 = []
    for j in range(0, len(points)):
        if j == i:
            points2.append((x+signa*a, y+signb*b))
        else:
            points2.append(points[j])
    return points2
def main():
    
    points = [(500,1100),(1200,800),(900,500),(500,600),(300,400)]
    delta = 100
    for i in range(0, 2700):
        points = wigglepoly(points, delta)
        plot = Image.new("RGB", (1400,1400))
        draw = ImageDraw.Draw(plot)
        draw.polygon(points, fill=(255,255,255))
        plot.save("wigglepoly"+str(i)+".png")
main()