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

 
 

spiral chart

A program I wrote takes some values like:
[3,5,2,8,1,3,7]
first sorts greatest to smallest:
[8,7,5,3,3,2,1] (The program works whether they are sorted or not)
Then makes a spiral with the area of each rectangle corresponding to the values in this list... it doesn't write the numbers on them but I've labeled them:

I had intended it as a good way to show the relative sizes of elements of a dataset, but it doesn't really work for that as well as I thought it would because I think people aren't as good at recognizing rectangular areas and there's some optical illusions.
For example:
[1,1,1,1,1,1,1]

I had to actually measure these to verify they all have the same area so that precludes it from being a good tool for data representation. It's kind of an interesting optical illusion though.
The way I wrote the program you can put any size in for the main rectangle here is the all 1's again but in 800x350

There can be any number of data points here is 14 following the Fibonacci series:

This one is a 1920x1080 for a desktop background of the numbers 1,2,3,...13,14

I'm kind of proud of this source code, it took some thinking to make the program this short...

*Python Source Code**
import Image, ImageDraw
def rsum(data, i):
    sum = 0
    if i+1 < len(data):
        for d in range(i, len(data)):
            sum+=data[d][0]
        return sum
    else:
        return data[len(data)-1][0]
def parserec(coords):
    leastx = coords[0][0]
    leasty = coords[0][1]
    mostx = coords[0][0]
    mosty = coords[0][1]
    for i in range(1, len(coords)):
        if coords[i][0] < leastx:
            leastx = coords[i][0]
        if coords[i][0] > mostx:
            mostx = coords[i][0]
        if coords[i][1] < leasty:
            leasty = coords[i][1]
        if coords[i][1] > mosty:
            mosty = coords[i][1]
    return [(leastx, leasty), (mostx, mosty)]
def main():
    size = [800,800]
    pic = Image.new("RGB", size)
    draw = ImageDraw.Draw(pic)
    data = [[1, (255,255,0), "widgets"],[1,(255,0,0), "thingies"],[1,(0,255,0),"stuff"],[1,(0,0,255),"foo"], [1,(0,255,255),"bar"], [1,(125,125,255),"bar2"],[1,(125,125,0),"bar3"]]
    r = rsum(data,0)
    data = list(reversed(sorted(data)))
    rects = [[(0,1),(0,0),(size[0],0),(size[0],1)], [(size[0]-1,1),(size[0],1),(size[0],size[1]),(size[0]-1,size[1])],[(size[0]-1, size[1]-1), (size[0]-1, size[1]), (0,size[1]), (0, size[1]-1)],[(1,size[1]-1), (0, size[1]-1), (0, 1), (1, 1)]]
    for i in range(0, len(data)):
        thisrect = i+4
        width = data[i][0]*1.0/rsum(data, i)
        x0 = rects[thisrect-1][3][0]+width*(rects[thisrect-1][0][0]-rects[thisrect-1][3][0])
        y0 = rects[thisrect-1][3][1]+width*(rects[thisrect-1][0][1]-rects[thisrect-1][3][1])
        x1 = rects[thisrect-1][3][0]
        y1 = rects[thisrect-1][3][1]
        x2 = rects[thisrect-3][0][0]
        y2 = rects[thisrect-3][0][1]
        x3 = (x0-x1)+x2
        y3 = (y0-y1)+y2
        coords = [(x0,y0),(x1,y1),(x2,y2), (x3,y3)]
        rects.append(coords)
        coordstlbr = parserec(coords)
        draw.rectangle(coordstlbr, fill=data[i][1])
    pic.save("spiralgraph.png")
main()

square angles (squangles)

First every vector in the plane can be mapped to the 2 by 2 square centered at the origin by dividing both components of the vector by the magnitude of the larger of the two components. So (3,6), the larger of the two components is 6 so divide both components by 6 and get (1/2,1), which is a point on the  square. For (-5,-2) the magnitude of the larger component is 5 so divide both by 5 and get (-1,-2/5) which is the corresponding point on the square. 

To find the angle between 2 square normalized vectors find the distance around the square to get from one coordinate to another. In this case from (1/2,1) you have to go left 1+1/2 and then down 1 and 2/5 to get -2.9 because you're going counterclockwise.  From the other vector it would be 2.9 clockwise.

It's an algorithm rather than a direct math quantity to find the square angle because of the complications first in finding the normalized square vector, that you have to divide by the largest component which is hard to put as a formula, and then in finding a formula for the distance around the square without using modular arithmetic or absolute values etc..., but it is nice that the angles around always add to 8,  squangle(a,b)+squangle(b,c)=squangle(a,c) and counterclockwise comparison is always a negative angle, etc...

**Note

I thought at first there would be a sort of distortion from the corners but there really isn't, consider the square angle between (0,1) and (1,0) and between (1,1) and (1,-1)  are both 2 even though one consists of just a straight line and the other goes around a corner. Any two vectors that the angle between them would ordinarily be 90 degrees the square angle is 2, 30 degrees 2/3 etc... This relationship makes it possible to use the algorithm to find the square angle, then convert to the regular angle without having to ever use a trigonometric function like cosine.  I think a proof of that could be start anywhere as a normalized square vector, add the square angle to itself as many times as will fit in 8, that has to map exactly to an angle of a certain number of degrees added to itself as many times as it goes into 360 because either way you went all the way around. 

simple locating goal and finding short path to it algorithm

The red square can move to any white square but is blocked by black squares. It can only check whether the square it is on is yellow (the goal). So the object is for the red square to find the yellow square and return a reasonably short path to getting there around obstacles and so on.
My algorithm is very simple, the red square keeps a list of squares he's visited, and randomly moves to another acceptable square by moving up,down,left,right, or any diagonal one square. Then he checks his list to see if he's ever been 1 move away from any square on his list starting at the beginning of the list. If he has been then he shortens his list by removing every square visited in between where he currently is and the earliest time he was 1 square away from where he is now. This has the effect of removing loops and double backs from the final path. This is like finding a "short cut" between where he is and where he was. Eventually he will end up on the yellow square and the program ends and returns his list.
**Python Source code
import Image
import random
class board():
    board = [[0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,0],[0,2,1,1,1,1,1,1,1,0],[0,1,1,1,1,1,1,1,1,0], [0,1,1,1,0,0,1,1,1,0], [0,1,1,1,0,0,1,1,1,0], [0,1,1,1,1,1,1,1,1,0], [0,1,1,1,1,1,1,1,1,0], [0,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0]]
    mousepos = [8,8]
    def drawboard(self, img):
        for i in range(0, 10):
            for j in range(0, 10):
                if self.board[i][j] == 1:
                    for m in range(i*50, (i+1)*50):
                        for n in range(j*50, (j+1)*50):
                            img.putpixel((m,n),(255,255,255))
                if self.board[i][j] == 2:
                    for m in range(i*50, (i+1)*50):
                        for n in range(j*50, (j+1)*50):
                            img.putpixel((m,n),(255,255,0))
                if self.mousepos[0] == i and self.mousepos[1]==j:
                    for m in range(i*50+10, (i+1)*50-10):
                        for n in range(j*50+10, (j+1)*50-10):
                            img.putpixel((m,n),(255,0,0))
    def drawsolution(self, img, states):
        for i in range(0, 10):
            for j in range(0, 10):
                if self.board[i][j] == 1:
                    for m in range(i*50, (i+1)*50):
                        for n in range(j*50, (j+1)*50):
                            img.putpixel((m,n),(255,255,255))
                if self.board[i][j] == 2:
                    for m in range(i*50, (i+1)*50):
                        for n in range(j*50, (j+1)*50):
                            img.putpixel((m,n),(255,255,0))
        for mousepos in states:
            for m in range(mousepos[0]*50+10, (mousepos[0]+1)*50-10):
                for n in range(mousepos[1]*50+10, (mousepos[1]+1)*50-10):
                    img.putpixel((m,n),(255,0,0))
                    
                        
    
class mouse():
    b = board()
    states = []
    def move(self, img):
        mousepos = self.b.mousepos
        okmove = False 
        while(okmove == False):
            tx = random.randint(-1,1)
            ty = random.randint(-1,1)
            if self.b.board[mousepos[0]+tx][mousepos[1]+ty] != 0:
                if self.b.board[mousepos[0]+tx][mousepos[1]+ty] == 2:
                    print "Found cheese"
                    print self.states
                    self.b.drawsolution(img, self.states)
                    return True
                mousepos = [mousepos[0]+tx, mousepos[1]+ty]
                self.b.mousepos = mousepos
                okmove = True
        self.checkstate(mousepos)
        return False
    def checkstate(self, mousepos):
        print mousepos
        self.states.append(mousepos)
        
        for i in range(0, len(self.states)-1):
             if self.states[i][0] == mousepos[0]-1 or self.states[i][0] == mousepos[0]+1:
                 if self.states[i][1] == mousepos[1]-1 or self.states[i][1] == mousepos[1]+1:
                     print "shortcut"
                     states2=[]
                     for j in range(0, i+1):
                         states2.append(self.states[j])
                     self.states = states2
                     self.states.append(mousepos)
                     break
                    
                
def main():
    
    img = Image.new("RGB", [500,500])
    m = mouse()
    while(m.move(img) == False):
        pass
        
    img.save("mouseboard.png")
main()

somewhat generalized recurrence

I'm not sure what class of curves this works on, I've tried it on a few exponential looking curves.
Suppose you have 2*n numbers indexed to the counting numbers:

You'd like to know a logical way it could continue...

A graph of the series with where you might guess the next point would be if it follows a smooth curve is:

I found that you can project to a solution solving a set of n-1 equations of degree n-1 like so:

The points are in order 1,17,54,166,332,680. The first equation is set up so the last point is a^2 times the  point before it plus b times the point before that and 1 times the point before that. And this same type of recurrence is applied for the second equation to 332. 

So you solve for a and b and plug the values of those coefficients in for a next term 

x= a^2*680+b*332+166

 1442

So now the plot with that point added looks like:

It seems to fit well. 

**Edit

In the above I was using exponents on the coefficients, but since each variable only occurred to the same power I think it's sufficient to just eliminate the powers. And I was always just plainly adding the last term but it works out nicely that every point in the whole list counts in the calculation if that last term has a coefficient as well and it should be more flexible as far as which curves can be evaluated. 

For an even number n points in a list of L values at the counting numbers solve n/2 equations in n/2 unknowns with x being the n/2th letter of the alphabet like:

L[n] = a*L[n-1]+b*L[n-2] + ... x*L[n/2]

L[n-1] = a*L[n-2]+b*L[n-3]+...x*L[n/2 -1]

...

L[n/2+1] = a*L[n/2] + b*L[n/2-1] +...x*L[1]

Then use those coefficients to find the next point... 

List correlation metric

Suppose you have two lists of the same n items ranked according to two different different metrics. If they end up listing the teams in the same order, you could say that the metrics are correlated 100%. If they ended up listing the teams in the exact reverse order of each other then that could be -100% correlation...
So this formula gives 100% and -100% in those two extreme cases and also a value to every intermediate case.

Where P[i,1] and P[i,2] are the position of item i on list 1 and list 2 respectively. 

The part in red sums the squares of the difference between where each item appears on list 1 and where it appears on list 2. The blue part is what the sums of the squares of the differences would work out to if the two lists were in complete reverse order from each other, which also is the maximum the part in red can reach. So the red part divided by the blue part is a number from 0 to 1 where 0 is the two lists are in the same order and 1 is for when the two lists are in reverse order from each other.  
The rest reverses and scales the result between -100 and 100 with -100 being the lists are in reverse order to each other and 100 being the lists are in the same order, with perhaps many values in between.
**Example

Consider the same graphic which lists how many points a football team in the NFL scored over last year and the difference between the number of turnovers they gained and how many they lost.

First we go through every team, and sum the squares of the differences for where they appear on each list. For example, the Denver Broncos are number 1 on the left list and 12 on the second so that is (12-1)^2=121. We do this for every team and add them all. The sum over all is 2298, and the blue part (an n of 32) of the formula is 10912, so plug those in the formula to get a correlation score of 57.8%, which is well towards a positive correlation on the scale of -100..100 so over a season a higher turnover differential correlates well with a higher point total.

** I think the nice thing about this method is it should detect any type of correlation, not just linear, because it doesn't depend on the values of the variables themselves just the order...  I think this would be a good initial test for any type of correlation and then you would use the conventional methods for determining which type of correlation, log normal, linear, etc..