Record surface interpolation

Just thinking that the spiral groove on a record is a sort of space filling curve in the limit in polar coordinates... here dividing coefficients by 10 and going to 10*pi, the 10 could be forever increased to make the spiral denser...

If Maple had support for 3 dimensional parametric polar graphs, I could plot this where the z coordinate is following some kind of wave along the 2d spiral, here just sin(t)...

Then it would be like the surface of a record, with the height being the wave of the music to be played...

But we could also use it to construct a surface like...

Where the height of the red curve is the smoothest wave through the z values along the spiral,  represented by the darkness and lightness in this graph...

Certain height maps, like one above,  might be easier to represent this way than with other 3d surface interpolations like polynomial interpolation across a grid... I think the z coordinate of the one above would be a sine wave with decreasing frequency and increasing amplitude over time.. Things like spiral armed galaxies might be easy to describe... For other types of information different space filling curves might be more useful...

**Aside**
I was thinking about records and how much better of a musical record we could make nowadays with modern materials and engineering... like very hard ceramic coated high strength metal for the record and a high strength but slightly less hard material for a micro needle, so the grooves could be very close together for a very long playing record, and maybe with now adays electronic components it could be made so it also only needs to spin at very low rpm, making it play even longer... probably not practical but I always hear about vinyl coming back so maybe there would be some interest...

Plane cross theorem

Some definitions:
The centroid of all the points is C
The centroid of all the points except point A is C(A)
V is the normalized vector from A to C
V2 is the normalized vector C to C(A)
Point A is colored red if:
VxV2 < 0
And blue if:
VxV2 > 0
where x is the cross product, V(x)*V2(y)-V2(x)*V(y)

What you end up with is a division of the points into a red group and a blue group such that the line dividing the two groups through the centroid crosses the line between the centroid of the red group and the centroid of the blue group through the centroid of all the points (not necessarily perpendicularly)

In the above the blue dot's center is to the left of the line going through it...

So it might be really good for divide and conquer algorithms as evaluating it is in linear time to the number of points...
**Python Source Code**
from PIL import Image, ImageDraw
import random
def distance(a, b):
    return ((a[0]-b[0])**2.0 + (a[1]+b[1])**2.0)**.5
def main():
    points = []
    plot = Image.new("RGB", (800,800))
    plotdraw = ImageDraw.Draw(plot)
    centroid = [0,0]
    numpoints = 20
    for i in range(0, numpoints):
        x = random.randint(100,700)
        y = random.randint(100,700)
        centroid[0] += x
        centroid[1] += y
        points.append((x,y))
    centroid[0] = centroid[0] / numpoints
    centroid[1] = centroid[1] / numpoints
    x = centroid[0]
    y = centroid[1]
    plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (255,255,255))
    centerred = [0,0]
    nred = 0
    centerblue = [0,0]
    nblue = 0
    for i in range(0, numpoints):
        x = points[i][0]
        y = points[i][1]
        cv = ((centroid[0]-x)/distance(centroid, (x,y)), (centroid[1]-y)/distance(centroid, (x,y)))
        c2x = (centroid[0]*numpoints - x)/(numpoints-1)-cv[0]
        c2y = (centroid[1]*numpoints - y)/(numpoints-1)-cv[1]
        c2 = [c2x, c2y]
        c2[0] /= distance(c2, cv)
        c2[1] /= distance(c2, cv)
        d = cv[0]*c2[1]-cv[1]*c2[0]
        
        if d < 0:
            centerred[0]+=x
            centerred[1]+=y
            nred +=1
            plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (255,0,0))
        elif d > 0:
            centerblue[0]+=x
            centerblue[1]+=y
            nblue +=1
            plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (0,0,255))
        else:
            plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (0,255,0))
    centerred[0]/=nred
    centerred[1]/=nred
    centerblue[0]/=nblue
    centerblue[1]/=nblue
    
    plotdraw.ellipse([(centerred[0]-10,centerred[1]-10), (centerred[0]+10, centerred[1]+10)], (255,255,255))
    plotdraw.ellipse([(centerblue[0]-10,centerblue[1]-10), (centerblue[0]+10, centerblue[1]+10)], (255,255,255))
    plot.save("plot.png")
main()    

Lattice for nearest neighbor

Supposing you have some metric space with well defined midpoints, here just a plane with points...

Start making a latice by picking a point to be the root...

Now pick another point and make it a child...

The general rule for adding another point is:

For a parent G with children {A,B,...} and a point k to be sorted, there are 4 things that can happen, in order of precedence:
1. k is closer to the midpoint of G and and one or more X,Y... of {A,B,...};  than the midpoint is to either G or X
or
2. k is closer to G than it is to any X of {A,B,...}
or
3. k is closer to the midpoint of two of G's children, X and Y,  than it is to either of the children in question
or
4. k is closest to one of the children X

and what you do for each case is:
1. remove X,Y... and any of their children from the tree and replace with k
2. add k as a child to G
3. take X and Y as parent nodes and repeat the process placing k somewhere under both
4. restart the process starting with X as the parent node

So for the example given:
1. k is not closer to the midpoint of G and E than either G or E
2. k is closer to G than it is to E
so we do 2 and make k another child of G

Now considering point b, we get all the way to rule 4, and make the new parent node E and continue with rule 2 adding b as a child of E.

Now considering point d, we would need rule 3 and make d a child of both e and k... Sometimes you will have to write it in the tree as two nodes but here we can draw it as one with 2 parents easily...

In the end you end up with a lattice where every node is closest to one of it's parents or one of it's children... 

** To be added**

I'll write some source code and post some results with big maps...

Dissolution of a polynomial

Suppose you have a polynomial of, for example, degree 3:

Because the first term is 5, you can imagine that it had 3 roots like:

Then to find a,b, and c solve for what terms multiply to if you expanded the above:

It gives:

Plugging back in:

Multiplying the above out gives something very close to the original polynomial (excepting rounding error)

Now you can find where those 3 terms equal 0 to find the roots, so it changes finding the roots into a problem about solving a set of simultaneous equations. Though if all you are doing is setting the polynomial to 0, it would be easier to divide out the leading 5 coefficient and simplify the formula...

Binary nearest neighbor for hull

Suppose you have some points, have found the centroid, and the bounding circle to the farthest point C(1)...

Now find the point halfway around the circle C(1/2) from the farthest point and the nearest neighbor from the point collection to that point...

Now further subdivide the circle to C(1/4) and C(3/4) and find the nearest neighbors...

Continue but here when the nearest neighbor is a point that's already been selected by one of the two blue points sudivided, the point on the circle is colored red...

Subdivide only between two points on the circle colored blue...

And continue until there are no more adjacent blue points on the circle...

Now the points ordered clockwise are a hull, but might not be convex. .

Root finding algorithm without using derivatives

This algorithm finds a root of an equation, like Newton's method, but is designed for situations when the function in question can be solved for x from a function f(x) though the derivative might be complicated or expensive to calculate making many other algorithms like Newton's method unsuitable...
Starting with an example function:

One first solves the equation for one x on the left from the original equation:

Then set y = 0 in this equation...

Then use this above formula and plug into a recursive structure like this:

Now you can plug in an initial guess (here -2):

And proceed recursively...

It approaches the root of 1.6666 quadratically...

**Proof**

Still working on a good proof...

Hex quotients

Considering that 1 node of the hex grid is labeled 1, there being 6 possible directions to go, 3 from one types of vertices, 3 from the other...

Any time you go straight up, you multiply by 2, straight down you divide by 2, down and to the right you multiply by 3, up and to the left you divide by 3, down and to the left you multiply by 5 up and to the right you divide by 5.
And it all hangs together nicely.
I don't know the use of it I just thought it was neat enough to spend time making a graphic...

Finding a nice way of drawing a graph

Vertices move towards other vertices they're connected to unless they are less than 100 pixels in distance from them, then they move away. And they move away from vertices they're not connected to unless they are more than 100 pixels away in which case it doesn't matter. All movements are normalized to 1 pixel left and right and up and down.

Cell labeling for bucketing positions on the grid

This idea is for cutting down on the number of items one has to check for possible interactions.
The cells can be labeled in this fashion (example: 4*j+i with i,j from 0..3):

An item on the plane within a square, like position 1567.5, 500 might be in cell 6 considering where it falls within the square on the plane. So one could check in cell 6-4 = 2 and cell 6+4 = 10 and 6-1 = 5 and 6+1 = 7 for possible interactions with the items in those cells, or counting diagonals also 6-3 and 6+3, 6-5 and 6+5. The +- 1, 3, 4, 5 is the same for any choice of cell except those on the edges.

So you might want to make your cell grid say 7x7 but only use the central 5x5 and cells number 0-6, 7*n+0, 41-48, and 7*n+6 would all be out of bounds ...To check a cells neighbors one would check it's cell number +- 1, 7, 6, 8

A "sparse" implementation could perhaps use something like a dictionary in python, and make new cells whenever there is a need for one with the specified number, and deleted when it is empty...

Easy seed value for square root algorithms

For even number of digits of the number to find the square root of:
3672
average the number you get when you slide the decimal point halfway across and the power of 10 you moved the decimal point by:
(36.72 + 100)/2 = 68.36, this will always be a bit larger than the actual square root, in this case  60.59

For odd number of digits first multiply by 10...
36725 x 10 = 367250
Then proceed as before
(367.250 + 1000)/2 = 683.625 and then divide by sqr(10) = 216, the actual is 191
It works even better in binary...
36725=
1000111101110101
10001111
 2^7= 1000000
(128 + 241)/2 = 181 when the actual is 191...

So this is a good way to find the initial seed value to continue with a precise method that needs a good guess like the Babylonian method to work it's best...