## Sunday, February 22, 2015

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